Choosing a Lookup Structure for a 5,000-Record Gradebook
A teacher-built grading application stores 5,000 student records in an unsorted array. A lookup by student ID scans from index 0 until it finds the ID. During grading week the app handles about 80 lookups per minute, with peaks of 200, plus 1,000 grade updates and 200 new records per semester. An alphabetical report by last name is produced once a week. The current average lookup examines 2,500 records; at peak this is about 500,000 record comparisons per minute. The teacher wants faster lookup but also needs the weekly report and cannot afford much extra memory. The app is written in Python and runs on a single school server. A colleague suggests sorting the array once and using binary search, while another suggests a dictionary keyed by student ID.
1. Compare the sorted-array-plus-binary-search proposal with a dictionary keyed by student ID for this workload. Recommend one and justify with operation counts and the weekly report requirement.
Read the worked answer
Sorted array plus binary search: lookup is O(log n), about 13 comparisons for 5,000 records; 200 peak lookups per minute is about 2,600 comparisons per minute, far below 500,000. But inserting 200 new records into a sorted array costs O(n) each, roughly 200 × 2,500 = 500,000 shifts per semester, and updates may also require repositioning if the sort key changes. The weekly report is already sorted by ID, not last name, so it still needs a sort by last name: O(n log n), about 5,000 × 12.3 = 61,500 comparisons. Dictionary keyed by ID: average O(1) lookup and insertion, so 80-200 lookups per minute are trivial; memory overhead is higher, but 5,000 records is small. The dictionary does not maintain order, so keep a separate list and sort once for the weekly report. Recommendation: dictionary for ID lookup plus a list for reporting; the sorted-array approach is a reasonable fallback if memory is extremely tight and inserts are rare.
2. Identify two failure modes or trade-offs the teacher should test before deployment, and describe a fallback if student IDs are not unique or are reused.
Read the worked answer
Failure modes: duplicate or reused student IDs would make a dictionary silently overwrite a record; a hash collision or poor hash function could degrade lookup, though Python's dict handles collisions. ID type mismatch, such as integer versus string, would cause missed lookups. The report could become inconsistent if it is generated while records are updated, so use a snapshot or transaction. Test with duplicate IDs, missing IDs, a full 5,000-record load, peak lookup rate, and a full weekly sort. Fallback: enforce a uniqueness constraint at data entry, use a composite key such as ID plus term, or switch to a sorted array with binary search if ordering is more important than insertion speed. Also add a verification that the dictionary size equals the number of unique IDs.