ORIGINAL COMPANY-CONTEXT PRACTICE
Represent a sparse memory-test defect map
Original practice scenario: A hypothetical memory test produces coordinates of failing cells in a very large address space. Compare representations for membership checks, range queries and repeated test runs.
Written for independent practice using company context; this is not a verified question from a company interview.
A REASONED APPROACH
Model answer.
Choose the representation from defect density and query patterns rather than assuming a bitmap is always compact. Memory-test coordinates also need a stable mapping to the tested device and layout.
Work through it
- Normalize coordinates and reject impossible addresses, retaining device, test configuration and run identities so different layouts cannot be accidentally combined.
- Compare a hash set, sorted coordinates and compressed ranges or bitmaps, estimating storage and lookup costs for sparse and clustered failures.
- Define duplicate behavior and implement range aggregation with boundary tests, including empty maps, maximum addresses and repeated observations across runs.
Tradeoffs to discuss
- Hashing offers convenient point lookup but weak ordered scans; sorting improves ranges and compression while increasing update costs.
Common pitfalls
- Repeated failures across runs are evidence over time, not necessarily duplicate entries to discard globally.
- Do not calculate a defect rate without the tested address population and coverage.