Candidate Records at East Mercia Examinations Board
East Mercia Examinations Board stores records for 25,000 candidates. Each record contains an 8-digit candidate number, a 60-character name, and nine paper marks that are integers from 0 to 100. Records are currently kept in one unsorted binary file of fixed-length 150-byte records. On results day, 400 lookup requests per minute arrive by candidate number; the current system searches sequentially and misses the 2-second response target. The board also needs, for each subject, a ranked list by total mark. Scanned scripts are stored separately as PDFs averaging 2 MB each; there are 225,000 scripts. The board wants to publish results securely and keep the archive for 10 years. A developer proposes an in-memory hash table keyed by candidate number. A second developer proposes sorting the file and using binary search. The board's server has 1 GB of RAM available for the index. A third proposal is to store marks as 32-bit floating point numbers to allow half marks.
1. Compare the in-memory hash table and the sorted-file binary search for results-day lookup. Recommend one, with calculations.
Read the worked answer
Sequential search averages 12,500 record reads per lookup. At 400 requests per minute, about 6.7 per second, that is roughly 83,000 reads per second - far beyond a single disk. Both proposals improve this.
Hash table: 25,000 keys. If each key is a 32-bit integer and each value is a 32-bit file offset, the payload is 25,000 × 8 bytes = 200,000 bytes, about 0.2 MB. At a load factor of 0.7, the table needs about 36,000 slots; with 12 bytes per slot it is still under 0.5 MB, well within 1 GB. Average lookup is O(1), with a few probes for collisions. Chaining or open addressing must be implemented correctly, and the table must be rebuilt if records are inserted.
Sorted file plus binary search: log 2(25,000) ≈ 15 record reads per lookup, so about 100 reads per second at the stated rate. That is feasible if reads are cached, but it requires sorting and keeping the file ordered on updates. It also supports range queries by candidate number, but not ranking by total mark.
Recommendation: hash table for exact candidate-number lookup, with a separate in-memory sort or index for ranked lists. It gives the lowest and most predictable lookup time and fits the RAM budget easily.
2. Explain why 32-bit floating point is a fragile choice for marks, and propose a representation that supports half marks exactly. Include an example.
Read the worked answer
A 32-bit IEEE 754 float stores a binary significand and exponent. Values such as 0.5 are exact because 0.5 = 2⁻¹, so a half mark alone is not the problem. The fragility appears when marks are combined: weightings, percentages or averages introduce values such as 0.1 or 0.2, which have no finite binary representation. For example, in binary floating point, 0.1 + 0.2 is not exactly 0.3; it is a value very close to 0.3. Comparisons such as “is the total exactly 60?” and repeated additions can then fail or drift. Ranking by total is also harder to justify if two mathematically equal totals differ in the last bit.
Better representation: store marks in half-mark units as integers. A mark from 0 to 100 in 0.5 steps becomes 0 to 200, which fits in 8 bits. A total of nine papers is 0 to 1,800, which fits in 11 bits. Convert to a display value only when printing (units / 2). This is exact, smaller than a 32-bit float, and makes equality and ranking reliable. If future weightings are needed, store integer tenths or use fixed-point arithmetic with a documented scale.
3. Estimate the storage for the scanned scripts and discuss whether lossless compression is appropriate for a 10-year archive.
Read the worked answer
Storage estimate: 225,000 scripts × 2 MB = 450,000 MB. Treating 2 MB as decimal, that is 450 GB; if 2 MiB, it is 450,000 MiB ≈ 439 GiB. Add at least one backup copy and preferably an off-site copy, so plan for roughly 1 TB or more before compression. Ten years of retention also means periodic media migration and checksums, not just raw capacity.
Lossless compression is appropriate where it preserves every pixel that might be needed for a mark appeal. However, the benefit depends on the PDF contents. If the scans are already JPEG-compressed colour images, recompressing losslessly may save little. If they are bilevel or grayscale text, lossless JBIG 2 or PNG-style compression can be substantial. Lossy compression is risky for handwriting and annotation: it can remove faint strokes or introduce artefacts that make a remark harder to defend.
Recommendation: sample 500 scripts across subjects, measure lossless compression ratios, verify legibility and checksums, then choose a lossless archive format. Keep the original if compression is marginal. The decision should be based on measured ratio and legal admissibility, not on the assumption that “PDF means compressible”.