How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Compute Latencies and Search Grid Path

Quick Overview

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.

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.

Input: (["message_type,id,synchronized_timestamp"], ["message_type,id,synchronized_timestamp"])

Expected Output: []

Explanation: Both files contain only headers, so there are no matching messages.

Input: ([], ["message_type,id,synchronized_timestamp", "x,0,2"])

Expected Output: []

Explanation: An empty send log means no message can match.

Input: (["message_type,id,synchronized_timestamp", "m,0,10"], ["message_type,id,synchronized_timestamp", "m,0,10", "m,1,11"])

Expected Output: ["m,0,0"]

Explanation: The matched message has zero latency. The unmatched receive-only message is 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.

Input: ([["A"]], "")

Expected Output: True

Explanation: The empty string is always formable.

Input: ([], "A")

Expected Output: False

Explanation: A non-empty target cannot be formed from an empty grid.

Input: ([["A", "A"], ["A", "B"]], "AAAB")

Expected Output: True

Explanation: A valid path is (1,0) -> (0,0) -> (0,1) -> (1,1).

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.

Quick Overview