Compute Latencies and Search Grid Path
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given two coding tasks from an internship interview.
## Task 1: Compute Message Latency from CSV Logs
Two systems, `ComputeA` and `ComputeB`, exchange messages. You are given two comma-separated value files:
- `ComputeA-send.csv`: records when messages are sent by `ComputeA`.
- `ComputeB-receive.csv`: records when messages are received by `ComputeB`.
Each file contains rows with the following columns:
- `message_type`: a string identifying the message category.
- `id`: a unique incrementing integer identifying the message within its type.
- `synchronized_timestamp`: an integer timestamp. The clocks are synchronized across both systems.
For every message that appears in both files, print its latency, defined as:
`latency = receive_timestamp - send_timestamp`
Output rows should contain:
- `message_type`
- `id`
- `latency`
### Example
Send file:
```text
message_type,id,synchronized_timestamp
altitude,0,222
altitude,2,224
altitude,1,223
altitude,3,230
```
Receive file:
```text
message_type,id,synchronized_timestamp
altitude,0,223
altitude,1,225
altitude,2,226
```
Expected output:
```text
message_type,id,latency
altitude,0,1
altitude,1,2
altitude,2,2
```
You may assume the input files can be read line by line. Clarify how your solution handles messages that appear in only one file.
## Task 2: Determine Whether a String Can Be Formed in a Grid
Given an `m x n` grid of characters and a target string, determine whether the target string can be formed by starting at any cell and repeatedly moving one step up, down, left, or right.
Rules:
- Each move must go to an orthogonally adjacent cell.
- The same grid cell cannot be used more than once in a single path.
- Return `true` if the target string can be formed; otherwise return `false`.
### Example
```text
grid = [
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
target = "ABCCED"
```
Expected output:
```text
true
```
Quick Answer: This question evaluates parsing and processing of timestamped event logs to compute message latencies and implementation of constrained grid path search, testing competencies in file I/O, record alignment/matching, time-delta computation, graph traversal, and stateful backtracking.
Part 1: Compute Message Latency from CSV Logs
You are given two CSV logs as lists of strings: one for messages sent by ComputeA and one for messages received by ComputeB. Each non-header row has the format "message_type,id,synchronized_timestamp". For every message identified by the pair (message_type, id) that appears in both logs, compute its latency as receive_timestamp - send_timestamp. Ignore messages that appear in only one log. Return the matching results as CSV strings in the format "message_type,id,latency", sorted by message_type and then by id.
Constraints
- 0 <= number of rows in each log <= 100000
- Each data row has exactly 3 comma-separated fields
- id and synchronized_timestamp fit in signed 32-bit integers
- Within a single log, there are no duplicate (message_type, id) pairs
- message_type contains no commas
Examples
Input: (["message_type,id,synchronized_timestamp", "altitude,0,222", "altitude,2,224", "altitude,1,223", "altitude,3,230"], ["message_type,id,synchronized_timestamp", "altitude,0,223", "altitude,1,225", "altitude,2,226"])
Expected Output: ["altitude,0,1", "altitude,1,2", "altitude,2,2"]
Explanation: Message altitude,3 appears only in the send log, so it is ignored.
Input: (["message_type,id,synchronized_timestamp", "temp,0,100", "altitude,1,50", "temp,1,120", "status,0,70"], ["message_type,id,synchronized_timestamp", "temp,0,105", "status,0,72", "altitude,1,55", "altitude,2,60"])
Expected Output: ["altitude,1,5", "status,0,2", "temp,0,5"]
Explanation: Only three messages appear in both logs. temp,1 and altitude,2 are unmatched and ignored.
Hints
- Use a hash map keyed by (message_type, id) to store send timestamps.
- If you want deterministic output, collect all matches and sort them at the end.
Part 2: Determine Whether a String Can Be Formed in a Grid
Given a 2D grid of characters and a target string, determine whether the target can be formed by starting from any cell and moving one step at a time up, down, left, or right. You may not reuse the same cell more than once in a single path. Return True if such a path exists; otherwise return False. An empty target string is considered formable.
Constraints
- 0 <= number of rows, number of columns <= 6
- 0 <= len(target) <= 15
- grid contains English letters
- Moves are allowed only in the four orthogonal directions
- A cell may be used at most once in a single path
Examples
Input: ([["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], "ABCCED")
Expected Output: True
Explanation: One valid path is A -> B -> C -> C -> E -> D.
Input: ([["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], "ABCB")
Expected Output: False
Explanation: The only way to match the final B would require reusing a cell, which is not allowed.
Hints
- Try depth-first search from every cell that matches the first character.
- During the search, mark a cell as visited, explore neighbors, then undo the mark when backtracking.