Choosing a Data Structure for a Real-Time Fare Ledger
A transit authority processes 2.5 million fare taps per day at peak bursts of 4,000 taps per second. Each tap must be matched to a card balance within 150 ms. Balances are held in memory on a single node with 32 GB RAM; each record is 96 bytes. Operations required are: point lookup by card ID, point update of balance, and an end-of-day sequential reconciliation of all cards in card-ID order. The current implementation uses a balanced binary search tree keyed on a 16-character alphanumeric card ID and is missing the 150 ms target during bursts. A proposal is to switch to a hash table with open addressing.
1. Analyse why the current tree may be missing the latency target and whether the hash table proposal addresses it.
Read the worked answer
Memory footprint. If there are, say, 3 million active cards × 96 bytes ≈ 288 MB of payload, which fits easily in 32 GB. Memory is not the issue; access pattern and comparison cost are.
Tree cost. A balanced BST gives O(log n) lookups. With 3 million keys, log2(3M) ≈ 21.5 comparisons per lookup, each comparing 16-character strings. At 4,000 taps/second this is roughly 86,000 string comparisons per second - feasible in principle, but pointer-chasing across a large tree causes cache misses, and string comparison adds constant-factor cost that can blow the 150 ms budget under burst contention.
Hash table. Open addressing gives O(1) average lookup, typically 1–2 probes, and contiguous memory improves cache locality. This directly targets the latency symptom.
Caveat. Open addressing degrades badly at high load factors and needs careful resizing; the answer should note load-factor management and worst-case clustering rather than claiming hash tables are unconditionally faster.
2. The reconciliation step requires traversal in card-ID order. How should this affect the choice?
Read the worked answer
A hash table does not preserve key order, so end-of-day reconciliation in card-ID order would require extracting all keys and sorting them: O(n log n) once per day. With 3 million cards that is roughly 3M × 21.5 ≈ 64.5 million comparisons - acceptable as a nightly batch, since it is not on the 150 ms critical path.
A balanced tree supports in-order traversal in O(n) with no sort, but pays the O(log n) penalty on every one of 2.5 million daily lookups.
Judgement. The latency-critical path is the per-tap lookup, executed 2.5 million times daily; reconciliation runs once. Optimising the frequent operation and accepting a nightly sort is the better trade-off. A defensible alternative is a hybrid: hash table for the hot path plus a sorted secondary index rebuilt nightly. The answer should justify the choice by frequency of operation, not by asymptotic complexity alone.