
You are given two independent coding tasks.
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:
m
and
n
for the grid dimensions.
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.
Answer the following subproblems:
(targetRow, targetCol)
of a single food item (an
F
cell).
S
to that cell.
-1
.
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.
-1
if it is impossible.
k ≤ 12
food items in the grid.
For this task:
m
,
n
, and the number of items
k
.
int shortestPathToOneItem(char[][] grid, int targetRow, int targetCol)
int shortestPathToAllItems(char[][] grid)
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
.
OPEN
, with
filledQuantity = 0
.
FILL
– fills
quantity
units of an existing
OPEN
or
PARTIALLY_FILLED
order.
filledQuantity
increases.
filledQuantity == totalQuantity
, the order state becomes
FILLED
.
FILL
events for an order that is already fully filled or cancelled, except for duplicated events.
CANCEL
– cancels an existing order.
OPEN
or
PARTIALLY_FILLED
, its state becomes
CANCELLED
.
Assumptions:
orderId
arrive in non-decreasing
timestamp
order.
eventId
as the original.
You are asked to:
orderId
, output:
state
in {
OPEN
,
PARTIALLY_FILLED
,
FILLED
,
CANCELLED
}.
totalQuantity
(from the corresponding
NEW
event).
filledQuantity
(sum of effective fills applied to the order).
eventId
:
eventId
, only the first occurrence should affect the result; the rest must be ignored.
E
and the number of distinct orders
O
.
You may be asked to implement an interface such as: