Solve restaurant path and order event tasks
Company: Coinbase
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given two independent coding tasks.
## Task 1: Shortest paths in a restaurant grid
Context: A restaurant is represented as a 2D grid. The waiter starts from a fixed starting cell and must walk around tables (obstacles) to pick up food items.
**Input**:
- Integers `m` and `n` for the grid dimensions.
- An `m × n` grid of characters, where:
- `S` – starting position of the waiter (exactly one cell).
- `.` – empty cell where the waiter can walk.
- `#` – obstacle (e.g., a table) the waiter cannot pass through.
- `F` – a cell containing a food item.
- The waiter can move in 4 directions (up, down, left, right). Each move to an adjacent non-obstacle cell costs 1 step.
Answer the following subproblems:
1. **Single-item shortest path**
You are given the coordinates `(targetRow, targetCol)` of a single food item (an `F` cell).
Compute the length of the shortest path from `S` to that cell.
If it is unreachable, return `-1`.
2. **All-items shortest path**
Now consider all cells marked `F` as items to be picked up. Starting from `S`, the waiter must visit every `F` cell at least once, in any order, and may end anywhere.
- Compute the minimum total number of steps required to collect all items, or `-1` if it is impossible.
- You may assume there are at most `k ≤ 12` food items in the grid.
For this task:
- Clearly describe the algorithm you would use for each subproblem.
- State the time and space complexity in terms of `m`, `n`, and the number of items `k`.
- You may be asked to implement functions such as:
- `int shortestPathToOneItem(char[][] grid, int targetRow, int targetCol)`
- `int shortestPathToAllItems(char[][] grid)`
---
## Task 2: Order event processing with idempotency
Context: You are processing a stream of order events consumed from a message queue similar to Kafka. Due to at-least-once delivery, events may be delivered more than once; your processing must be idempotent (re-processing the same logical event should not change the final result more than once).
Each event has the following fields:
- `eventId` (string): unique identifier for a logical event. If the same logical event is delivered multiple times, all its copies share the same `eventId`.
- `orderId` (string): the order this event belongs to.
- `type` (enum): one of `NEW`, `FILL`, `CANCEL`.
- `quantity` (integer, positive).
- `timestamp` (long, monotonically increasing for simplicity across this stream).
Event semantics:
- `NEW` – creates a new order with total quantity = `quantity`.
Initial state: `OPEN`, with `filledQuantity = 0`.
- `FILL` – fills `quantity` units of an existing `OPEN` or `PARTIALLY_FILLED` order.
- `filledQuantity` increases.
- If `filledQuantity == totalQuantity`, the order state becomes `FILLED`.
- You may assume you do not receive valid `FILL` events for an order that is already fully filled or cancelled, except for duplicated events.
- `CANCEL` – cancels an existing order.
- If the order is `OPEN` or `PARTIALLY_FILLED`, its state becomes `CANCELLED`.
- After an order is cancelled, subsequent non-duplicate fills must not change its state or filled quantity.
Assumptions:
- All events for a given `orderId` arrive in non-decreasing `timestamp` order.
- The global stream may contain duplicate events due to retries, but duplicates always share the same `eventId` as the original.
You are asked to:
1. **Core processing logic**
Design and implement a function that, given a list of events in arrival order, outputs the final state of each order. For each `orderId`, output:
- `state` in {`OPEN`, `PARTIALLY_FILLED`, `FILLED`, `CANCELLED`}.
- `totalQuantity` (from the corresponding `NEW` event).
- `filledQuantity` (sum of effective fills applied to the order).
2. **Idempotency**
Ensure your implementation is idempotent with respect to `eventId`:
- If the input list contains duplicate events with the same `eventId`, only the first occurrence should affect the result; the rest must be ignored.
- If you reprocess the same list of events (or a superset that only adds duplicates), the final results for all orders must remain the same.
3. **Design discussion**
Describe:
- The data structures you use to track orders and to detect duplicate events.
- How your logic updates order state for each event type.
- How you guarantee idempotency in the presence of duplicate events.
- The time and space complexity in terms of the number of events `E` and the number of distinct orders `O`.
You may be asked to implement an interface such as:
```java
class Event {
String eventId;
String orderId;
String type; // values: NEW, FILL, CANCEL
int quantity;
long timestamp;
}
class OrderState {
String state; // values: OPEN, PARTIALLY_FILLED, FILLED, CANCELLED
int totalQuantity;
int filledQuantity;
}
Map<String, OrderState> processEvents(List<Event> events)
```
Quick Answer: This question evaluates algorithmic problem-solving and system correctness skills: the grid task tests graph traversal and shortest-path plus combinatorial collection under constraints, while the event task tests idempotent stream processing, deduplication, and order-state management, spanning algorithms, graph theory, and distributed systems/stream-processing domains. It is commonly asked because it assesses both practical implementation ability and conceptual reasoning — requiring efficient algorithm design for shortest-path and state-space optimization alongside conceptual and practical understanding of idempotency and correctness under retries.
Part 1: Single-item shortest path in a restaurant grid
A restaurant is represented by a 2D grid. The waiter starts at the only cell marked S and can move up, down, left, or right through non-obstacle cells. Cells marked # are blocked. Given the coordinates of one food cell, compute the minimum number of steps from S to that cell. Since every move costs 1, breadth-first search from S finds the shortest path.
Constraints
- 1 <= len(grid) <= 200
- 1 <= len(grid[0]) <= 200
- All rows have the same length.
- grid contains exactly one S.
- target_row and target_col may be assumed to be valid coordinates of an F cell for normal inputs, but returning -1 for invalid or blocked targets is acceptable.
- Movement is allowed only in 4 directions.
Examples
Input: (['S.F', '...', '...'], 0, 2)
Expected Output: 2
Explanation: Move right twice from S to reach the food.
Input: (['S#F', '.#.', '...'], 0, 2)
Expected Output: 6
Explanation: The direct route is blocked, so the waiter must go around the obstacles.
Hints
- Because every move has equal cost, use BFS instead of Dijkstra.
- The first time BFS reaches the target cell, the distance is guaranteed to be minimal.
Part 2: All-items shortest path in a restaurant grid
A restaurant is represented by a 2D grid. The waiter starts at S, cannot pass through # cells, and must collect every food item marked F. The waiter may visit the food cells in any order and may end anywhere after collecting the last item. There are at most 12 food items. Compute the minimum number of steps needed to collect all food items, or -1 if impossible. A good approach is BFS over states of the form row, column, collected_mask, where collected_mask records which food items have been visited.
Constraints
- 1 <= len(grid) <= 100
- 1 <= len(grid[0]) <= 100
- All rows have the same length.
- grid contains exactly one S.
- 0 <= number of F cells <= 12
- Movement is allowed only in 4 directions.
Examples
Input: (['S.F', '...', 'F..'])
Expected Output: 6
Explanation: One optimal route visits the food at the top right, then the food at the bottom left, for 6 total steps.
Input: (['S#F', '###', 'F..'])
Expected Output: -1
Explanation: The waiter cannot reach any food item because obstacles block all paths.
Hints
- Treat each BFS state as both a position and the set of already collected food items.
- Use a bitmask for the collected set: bit i is 1 if food item i has been visited.
Part 3: Idempotent order event processing
You are given a stream of order events in arrival order. Events may be delivered more than once, and duplicates share the same eventId. Process only the first occurrence of each eventId. NEW creates an order, FILL increases its filled quantity if the order is still OPEN or PARTIALLY_FILLED, and CANCEL cancels an OPEN or PARTIALLY_FILLED order. A non-duplicate fill after cancellation must not change the order. For this coding version, events and returned order summaries are encoded as lists of strings to keep the interface simple across languages.
Constraints
- 0 <= len(events) <= 200000
- eventId and orderId are non-empty strings.
- type is one of NEW, FILL, CANCEL.
- quantity is a positive integer represented as a decimal string.
- timestamp is a non-negative integer represented as a decimal string.
- Duplicates always have the same eventId as the original logical event.
- Each order has at most one effective NEW event.
- Non-duplicate FILL events never make filledQuantity exceed totalQuantity before any clamping; fills for already cancelled or filled orders are ignored.
Examples
Input: ([['e1', 'A', 'NEW', '10', '1'], ['e2', 'A', 'FILL', '4', '2'], ['e3', 'A', 'FILL', '6', '3']])
Expected Output: [['A', 'FILLED', '10', '10']]
Explanation: The two fills exactly complete order A.
Input: ([['e1', 'A', 'NEW', '10', '1'], ['e2', 'A', 'FILL', '3', '2'], ['e2', 'A', 'FILL', '3', '2'], ['e3', 'A', 'CANCEL', '1', '3'], ['e4', 'A', 'FILL', '7', '4']])
Expected Output: [['A', 'CANCELLED', '10', '3']]
Explanation: The duplicate fill e2 is ignored. After cancellation, the later non-duplicate fill does not change the order.
Hints
- Always check whether eventId has already been processed before applying the event.
- Maintain a map from orderId to its current state, total quantity, and filled quantity.