Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Project: choose structures for a dispatch board

Last updated: 5 Oct 202616 min read
project
IntermediateBy AITrove Editorial

Design the in-memory data structures for a fictional depot dispatch board. A display sequence records shipments S-47, S-52, and S-61. A keyed status index distinguishes North/S-47 from South/S-47. Pallets P-47, P-52, and P-61 leave in arrival order unless an explicit priority policy chooses a different job. The project asks for the data structure behind each operation, its invariant, and a cost statement. It does not claim durable delivery or user authorization from an in-memory container.

Choose by operation

Use a resizable array when indexed display reads dominate and middle inserts are rare. Use a scoped hash-map key for shipment status, not shipment ID alone. Use a deque for FIFO pallet pickup; use a heap of priority, arrival, and job ID when urgency overrides arrival order while ties remain fair. A doubly linked list only helps if a node reference is already known, such as through a separate map. A hash set can deduplicate event IDs, but the raw scan log remains available for audit.

Verify behavior

Insert S-58 into display position one and record the shift cost. Verify that North/S-47 and South/S-47 return different statuses. Pop P-47 first from the FIFO queue. For equal priority jobs J-52 and J-61, pop the earlier arrival first. State what happens on an empty queue, a duplicate event, and a backlog beyond the in-memory capacity. Do not imply that a local pop proves a remote worker completed the job.

Output
Sequence: S-47, S-58, S-52, S-61 after a middle insert.
Status keys: (north, S-47) and (south, S-47) are distinct.
FIFO: P-47 leaves before P-52 and P-61.
Priority tie: J-52 leaves before J-61 by arrival sequence.
Release check: no accidental cross-depot key collision.

Cost and review

The array gives O(1) indexed reads and O(n) middle insertion. The hash map gives expected O(1) keyed lookup, while the deque gives O(1) endpoint operations. Heap push and pop cost O(log n). Every structure uses O(n) storage for n active records, and duplicate references across structures increase memory further. Review synchronization if one update touches the display list and status index together; a fast structure with inconsistent state is still incorrect.

Common Mistakes

  • Do not use one shipment ID across tenants as a unique key.
  • Do not use list.pop(0) for a large FIFO backlog.
  • Do not promise a heap orders equal-priority jobs without a tie field.

Connected lessons

data structures
projects
Storage details