Compute Latencies and Search Grid Path

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:

message_type,id,synchronized_timestamp
altitude,0,222
altitude,2,224
altitude,1,223
altitude,3,230

Receive file:

message_type,id,synchronized_timestamp
altitude,0,223
altitude,1,225
altitude,2,226

Expected output:

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

grid = [
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
target = "ABCCED"

Expected output:

true

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

Example 1

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"])
Output: ["altitude,0,1", "altitude,1,2", "altitude,2,2"]

Explanation: Message altitude,3 appears only in the send log, so it is ignored.

Example 2

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"])
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

1. Use a hash map keyed by (message_type, id) to store send timestamps.
2. 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

Example 1

Input: ([["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], "ABCCED")
Output: True

Explanation: One valid path is A -> B -> C -> C -> E -> D.

Example 2

Input: ([["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], "ABCB")
Output: False

Explanation: The only way to match the final B would require reusing a cell, which is not allowed.

Hints

1. Try depth-first search from every cell that matches the first character.
2. During the search, mark a cell as visited, explore neighbors, then undo the mark when backtracking.