Design a Number Container System - Solution & Explanation

Problem Overview: You need to design a data structure that supports two operations: change(index, number) which assigns a number to an index, and find(number) which returns the smallest index currently storing that number. The challenge is handling frequent updates while always retrieving the minimum index efficiently.

Approach 1: HashMap + Ordered Set (O(log n) per operation)

Maintain two structures: a hash map indexToNumber that records the current number stored at each index, and another map numberToIndices where each number points to an ordered set of indices. When change(index, number) is called, check if the index already holds a value. If it does, remove that index from the ordered set of the previous number. Then insert the index into the ordered set of the new number and update indexToNumber. The find(number) operation simply returns the smallest element from the ordered set (e.g., TreeSet.first()). Insertions and removals in the ordered set cost O(log n), while lookups in the hash map are O(1). Space complexity is O(n). This approach relies heavily on hash tables and an ordered set structure.

Approach 2: Two HashMaps + Min Heap with Lazy Cleanup (O(log n) amortized)

Instead of maintaining a perfectly clean ordered set, store indices for each number in a min heap. Use indexToNumber to track the latest value assigned to each index, and numberToHeap where each number maps to a min heap of indices. Every time change(index, number) runs, push the index into the heap for that number and update indexToNumber. Old entries are not removed immediately. During find(number), repeatedly check the heap's top element. If the index at the top no longer maps to that number in indexToNumber, discard it. Continue until a valid index appears or the heap becomes empty. Each heap push or pop costs O(log n), and lazy deletion keeps updates simple. Total space complexity remains O(n). This method uses hash tables and a heap (priority queue).

Recommended for interviews: The ordered set solution is the cleanest and easiest to reason about. Interviewers like it because every structure always stays consistent and each operation has a clear O(log n) bound. The heap-based approach is also acceptable and commonly used in languages without a built-in ordered set. Showing both demonstrates strong understanding of data structure design and tradeoffs between strict ordering and lazy cleanup strategies.