Choosing Data Structures for a Bike-Share Repair System
CityCycle runs 12,500 bikes from 480 stations. Maintenance staff need to (1) look up a bike’s full repair history by bike ID, (2) list all repairs at a station between two dates for a warranty audit, and (3) select the most urgent repair next. The current spreadsheet holds 90,000 repair records, and a station-and-date filter takes about 6 seconds. Two students propose a hash table keyed by bike ID and a balanced binary search tree keyed by station and date. A priority queue is also suggested for the repair queue. Records can share the same station and date. The system must run on a low-spec tablet and support 20 concurrent users.
1. Select an abstract data structure for each of the three operations and justify your choice using expected time complexity and the data characteristics.
Read the worked answer
For operation (1), a hash table keyed by bike ID is appropriate. Exact-key lookup is O(1) on average; with 90,000 records and a load factor kept below about 0.75, collisions are manageable. The key is unique and queries are exact, which is the hash table’s strength. For operation (2), a balanced binary search tree keyed by station and date supports an in-order range query in O(log n + k), where k is the number of returned records. A hash table cannot do range queries efficiently because hashing destroys order; you would have to scan all 90,000 records. For operation (3), a priority queue - usually a binary heap - gives O(log n) insertion and O(log n) extract-min for urgency. A sorted array would give O(1) extract but O(n) insertion, which is poor when repairs arrive continuously. The tablet’s low specification favours these structures because they avoid full scans; 90,000 records is small enough for memory, but the implementation should avoid unnecessary object overhead.
2. The station-and-date tree must handle duplicate keys, because several repairs can share the same station and date. Explain two ways to handle duplicates and one consequence of each.
Read the worked answer
One option is to make the key composite: station ID, date, and a unique repair ID. This guarantees uniqueness and keeps the tree balanced, but range queries must use the station-and-date prefix and then filter or traverse the matching subtree; the repair ID must be ordered consistently. A second option is to allow each tree node to hold a list of records with the same station and date. This preserves one key per station-date and makes the range query return whole buckets, but a bucket can become long if many repairs occur on one day, so the effective search within the bucket may degrade to O(m). A third option, a multiset or duplicate-allowing tree, is possible but complicates deletion and balancing. For the warranty audit, the composite-key approach is usually cleaner because it keeps every record individually addressable and avoids long buckets, at the cost of slightly more complex range logic.
3. A colleague claims the hash table alone is sufficient because “we can just scan for the date range.” Evaluate this claim for 90,000 records and 20 concurrent users.
Read the worked answer
Scanning 90,000 records per range query is O(n). If each record check is cheap, one scan might take milliseconds in memory, but 20 concurrent users issuing repeated audits multiply the work, and the tablet’s slower CPU and limited memory bandwidth make the constant factor worse. The current spreadsheet takes about 6 seconds for a station-and-date filter, which shows the practical cost of repeated scanning over this data size. A hash table also cannot return results in date order without an extra sort, which adds O(k log k). The claim is only defensible if range queries are extremely rare and the data fits comfortably in memory. For a warranty audit that may run repeatedly, a balanced BST is the better fit: it narrows the search to the relevant station and date interval and returns records in order. The hash table remains the right structure for bike-ID lookup, so the system should use both, not one alone.