Design a Number Container System

Design a Number Container System

1. What is this problem about?

The Design a Number Container System interview question requires implementing a system that associates indices with numbers. You can insert or replace a number at a specific index and query the smallest index that currently contains a specific number. This Design a Number Container System coding problem is a classic "Two-Way Mapping" challenge where you need to look up a value by its key and a key by its value.

2. Why is this asked in interviews?

Amazon and Google ask this to evaluate your ability to maintain Bidirectional Relationships between data points. It tests your proficiency with Hash Table interview patterns for the index-to-number mapping and Ordered Set interview patterns for the number-to-indices mapping. It’s about ensuring consistency across two different internal views of the same data.

3. Algorithmic pattern used

This problem uses two primary maps:

• Map<Integer, Integer> indexToNum: To store which number is at which index.
• Map<Integer, TreeSet<Integer>> numToIndices: For each number, maintain a sorted set of all indices where it appears.
• When change(index, number) is called:
  1. Check if index already had a number. If so, remove index from the old number's TreeSet.
  2. Update indexToNum with the new number.
  3. Add index to the new number's TreeSet.

4. Example explanation

1. change(10, 5): indexToNum[10]=5, numToIndices[5]={10}.
2. change(2, 5): indexToNum[2]=5, numToIndices[5]={2, 10}.
3. find(5): The smallest index in numToIndices[5] is 2. Return 2.
4. change(2, 3): numToIndices[5] becomes {10}, numToIndices[3] becomes {2}.

5. Common mistakes candidates make

• Linear Find: Iterating through all indices to find a number ($O(N)$), which is too slow.
• Consistency Errors: Updating the index-to-number map but forgetting to remove the index from the old number's set.
• Inefficient Sets: Using a list and sorting it every time instead of using a self-balancing tree structure like TreeSet or std::set.

6. Interview preparation tip

For any problem that asks for "the smallest/largest key associated with a value," you need a sorted structure (like a Heap or BST) indexed by that value. If you need to remove specific keys from that sorted structure, a BST-based Set is usually better than a Heap.