Smallest Number in Infinite Set

Smallest Number in Infinite Set

What is this problem about?

The "Smallest Number in Infinite Set" interview question asks you to design a data structure that represents a set containing all positive integers [1, 2, 3, ...]. The set must support two operations: popSmallest(), which removes and returns the smallest integer, and addBack(num), which adds a number back into the set if it's not already there. This "Smallest Number in Infinite Set coding problem" tests your ability to manage an "infinite" structure using finite resources.

Why is this asked in interviews?

Amazon and Google ask this to evaluate your choice of data structures for "Design" type problems. You can't actually store an infinite set, so you must track the "boundary" of the set and any numbers that have been added back. It tests your proficiency with Min-Heaps and Hash Sets (to avoid duplicates).

Algorithmic pattern used

This follows the "Design and Heap (Priority Queue) interview pattern".

1. Maintain a variable current_min representing the smallest integer that has never been popped.
2. Maintain a Min-Heap added_back_heap for numbers that were popped and then added back.
3. Maintain a Hash Set added_back_set to ensure addBack only adds unique numbers.

• popSmallest: If the heap is not empty, pop from the heap (and remove from the set). Otherwise, return current_min and increment it.
• addBack(num): If num < current_min and num is not in the set, add it to both the heap and the set.

Example explanation

1. SmallestInfiniteSet starts with all positive integers. current_min = 1.
2. popSmallest(): Return 1. current_min = 2.
3. popSmallest(): Return 2. current_min = 3.
4. addBack(1): 1 is less than 3. Heap: [1], Set: {1}.
5. popSmallest(): Heap is not empty. Return 1. Set: {}, Heap: [].
6. popSmallest(): Heap empty. Return 3. current_min = 4.

Common mistakes candidates make

A common mistake is adding a number back that is already in the infinite part of the set (i.e., num >= current_min), which is redundant. Another error is not using a set alongside the heap, leading to duplicate numbers in the heap and incorrect popSmallest results. Some candidates also forget that the heap should only contain numbers smaller than the current_min.

Interview preparation tip

When designing a system that handles a continuous range plus exceptions, use a "boundary" variable for the range and a specialized data structure (like a Heap or Balanced BST) for the exceptions. This is a very efficient "Design interview pattern" seen in memory management and scheduler simulations.