Solve restaurant path and order event tasks

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:

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)

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

Example 1

Input: (['S.F', '...', '...'], 0, 2)
Output: 2

Explanation: Move right twice from S to reach the food.

Example 2

Input: (['S#F', '.#.', '...'], 0, 2)
Output: 6

Explanation: The direct route is blocked, so the waiter must go around the obstacles.

Hints

1. Because every move has equal cost, use BFS instead of Dijkstra.
2. 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

Example 1

Input: (['S.F', '...', 'F..'])
Output: 6

Explanation: One optimal route visits the food at the top right, then the food at the bottom left, for 6 total steps.

Example 2

Input: (['S#F', '###', 'F..'])
Output: -1

Explanation: The waiter cannot reach any food item because obstacles block all paths.

Hints

1. Treat each BFS state as both a position and the set of already collected food items.
2. 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

Example 1

Input: ([['e1', 'A', 'NEW', '10', '1'], ['e2', 'A', 'FILL', '4', '2'], ['e3', 'A', 'FILL', '6', '3']])
Output: [['A', 'FILLED', '10', '10']]

Explanation: The two fills exactly complete order A.

Example 2

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

1. Always check whether eventId has already been processed before applying the event.
2. Maintain a map from orderId to its current state, total quantity, and filled quantity.