The Emergency Department Queue at 300 Waiting
Soroka's emergency department registers about 640 patients in a 12-hour night shift. Each patient receives a triage score from 1 (immediate) to 5 (non-urgent), and the "call next" screen must always show the waiting patient with the lowest score; patients with the same score are seen in arrival order. The current implementation keeps a sorted ArrayList and inserts each new patient with binary search plus an array shift; the nurse in charge says the screen sometimes freezes for about a second when the waiting room holds 300 people. About 4% of patients leave the queue before being called (they walk out, or are taken straight to surgery), and today the system finds them by scanning the whole list. There is also a rule that a patient discharged within the last 24 hours who returns must be flagged: a student proposes a HashSet keyed by the ID number typed by the clerk, which is sometimes entered as "012345678", sometimes as "12345678" and sometimes with a hyphen.
1. Choose the data structure for the waiting queue and justify it against the current one. Then comment on the reported one-second freeze: is the ArrayList really the cause?
Read the worked answer
Structure. A binary min-heap (PriorityQueue<Patient>) with comparator (triageScore, arrivalSequence). Insert is O(log n), poll is O(log n). The current sorted ArrayList costs O(n) per insert (the shift after binary search) and O(n) per poll (shifting every element left), and binary search buys nothing because the shift dominates. The arrival sequence number is what makes the order total: without it, ties on score are broken arbitrarily, and two patients with score 3 could be called out of order - a complaint the department cannot answer.
The freeze is not explained by the ArrayList. At n = 300 a shift moves at most 300 references - microseconds, not a second. A one-second pause points elsewhere: re-sorting the entire list on every screen refresh, a database round trip per row while rendering, or recomputing the display in O(n²). The right move is to instrument first (log insert and render durations) and only then rewrite. Switching to a heap is still correct - the workload will grow and the current complexity is wrong - but the candidate who blames the wrong line has not solved the reported problem. Fix the structure and find the real stall.
Also note the policy question hiding here. Strict priority by score means a score-5 patient can wait many hours; if the department wants ageing, the priority becomes a function of waiting time, which is mutable state and cannot be handled by a plain comparator. That needs an indexed heap with re-keying, or recomputation of the key at poll time - a design decision, not a data-structure reflex.
2. About 4% of patients disappear from the queue. Explain how to remove them, comparing lazy deletion with an indexed heap, and state the risk your choice introduces.
Read the worked answer
The problem. java.util.PriorityQueue offers no remove-by-key and no decrease-key; scanning the backing array is O(n) and breaks encapsulation. Two honest options:
Option A - lazy deletion (recommended here). Keep a HashMap<Long, Entry> from patient ID to the heap entry, and give each entry a cancelled flag. Removal is O(1): look up the entry, set the flag. poll() loops, discarding entries whose flag is set until it finds a live one. Each cancelled entry is discarded at most once, so the amortised cost of poll stays O(log n), and removal is O(1) instead of O(n).
Option B - indexed heap. Maintain position[] alongside the array and implement sift-up/sift-down updates; true removal is O(log n) with real memory reclamation. More code, more places to get the index bookkeeping wrong, and the benefit only appears if cancellations are frequent or entries are large.
The risk of Option A is unbounded growth. The heap holds live plus cancelled entries, so a shift with many cancellations keeps dead objects (and their strings, notes and history) reachable, and poll() can traverse a run of cancelled entries. Mitigate: track the live count separately from the heap size and rebuild the heap (O(n)) when cancelled entries exceed, say, 25% of the total, or at shift change. State the bound explicitly: total entries ≤ arrivals + cancellations during one shift, which is small at 640 registrations, so a rebuild threshold is cheap insurance rather than an optimisation.
Either way, the removal must be idempotent and must not resurrect a patient who was already called - a cancelled flag on a polled entry is a data bug that shows up as a patient being called twice.
3. Evaluate the student's HashSet proposal for flagging patients discharged within the last 24 hours, and specify what must be fixed before it is safe to use.
Read the worked answer
The idea is right, the key is wrong. A hash-based set gives O(1) membership and is the correct shape for "was this person here recently?". But everything rests on the key, and here the key is a free-text field a clerk types.
Key normalisation. "012345678", "12345678" and "012-345-678" are the same person and three different keys. Normalise at the boundary and keep exactly one canonical form: strip every non-digit character and left-pad with zeros to a fixed width (Israeli ID numbers are nine digits, so leading zeros are significant and must never be dropped by parsing to int). Normalisation must happen in one place - a PatientId value object with a private constructor and a static parse - otherwise the second entry point will forget.
equals/hashCode. If the key is a String, the default behaviour is fine but fragile; if it is a PatientId, equals and hashCode must be written together and consistently, or lookups silently miss and the flag never fires. A missed flag is a clinical error, not a cosmetic bug.
Validate the checksum first. Israeli ID numbers carry a check digit; a transposed digit should be rejected at the counter, not turned into a distinct key that defeats the whole mechanism. Rejecting bad input is cheaper than any amount of matching cleverness.
Expiry. A HashSet has no notion of time. Either store (id → dischargeTimestamp) in a HashMap and check now - t < 24h on lookup, or use a time-ordered structure (LinkedHashMap in access order, or a deque of discharges) plus a sweep that evicts entries older than 24 hours - otherwise the set grows forever and, worse, a readmission three weeks later is flagged as recent. Eviction must run on a schedule, not only when someone happens to look.