Karat

Detect a scrambled word within a given string from a list of candidate words.

Function:

function containsWord(words: string[], str: string): string | null

Requirements:

• Find word from list that is scrambled in the string
• Letters don't need to be in order or adjacent
• Letters cannot be reused
• At most one matching word exists

Examples:

1. words = ["cat", "baby", "dog", "bird", "car", "ax"] str = "tcabnihjs" Output: "car"

2. words = ["cat", "baby", "dog", "bird", "car", "ax"] str = "tbcanihjs" Output: "cat"

Find a word within a 2D grid where consecutive letters can be below or right.

Function:

function findWordLocation(grid: string[][], word: string): number[][]

Requirements:

• Word can start anywhere
• Next letter must be immediately below or right
• Return coordinates of found word
• Return any valid path if multiple exist

Example: Grid: [["c","c","x","t","i","b"], ["c","c","a","t","n","i"], ["a","c","n","n","t","t"]]

Word: "catnip" Output: [[1,2],[1,3],[2,3],[3,3],[3,4],[4,4]]

Time: O(r * c * w) Space: O(w)

Design a system to analyze web resource access logs with three main components:

1. User Access Time Analysis

Input: Array of [timestamp, userId, resourceId]
Example logs:
[
  ["58523", "user_1", "resource_1"],
  ["62314", "user_2", "resource_2"],
  ["54001", "user_1", "resource_3"],
  ["200", "user_6", "resource_5"]
]

Output: Map of user to [min, max] timestamps
{
  user_3: [53760, 53760],
  user_2: [54060, 62314],
  user_1: [54001, 58523]
}

2. Resource Access Window Analysis

Task: Find resource with most accesses in any 5-minute window
Input: Same log format
Output: [resourceId, accessCount]

Example:
most_requested_resource(logs) => ['resource_3', 3]
// resource_3 accessed at 53760, 54001, and 54060

3. Transition Graph Generation

Task: Build probability graph of resource transitions
Input: Same log format
Output: Adjacency list with probabilities

Example Output:
{
  'START': {
    'resource_1': 0.25,
    'resource_2': 0.125,
    'resource_3': 0.5,
    'resource_6': 0.125
  },
  'resource_1': {
    'resource_6': 0.333,
    'END': 0.667
  }
}

Notes:
- Include START state
- END is terminal state
- Probabilities based on user transitions

Requirements:

• Handle unsorted logs
• Process timestamps within same day
• Support multiple users and resources
• Calculate accurate probabilities
• Handle edge cases (single access, loops)