Iterator for Combination

Iterator for Combination

1. What is this problem about?

The Iterator for Combination interview question asks you to design a class that generates all possible combinations of a given length k from a sorted string of unique characters. You need to implement next() to return the next lexicographical combination and hasNext() to check if any more combinations exist.

2. Why is this asked in interviews?

Google uses this Iterator for Combination coding problem to test a candidate's mastery of the Iterator interview pattern combined with Backtracking. It evaluates whether you can generate permutations/combinations systematically and manage the "state" of an ongoing search across multiple function calls. It’s a test of lazy vs eager evaluation.

3. Algorithmic pattern used

This problem can be solved in two ways:

1. Eager (Pre-calculation): In the constructor, use a backtracking DFS to generate all combinations and store them in a queue or list. next() and hasNext() then become simple pointer lookups.
2. Lazy (Pointer-based): Maintain an array of indices representing the current combination. When next() is called, find the rightmost index that can be incremented and adjust the indices to the right.

4. Example explanation

String: "abc", $k = 2$.

• Backtracking:
  • Start at index 0: {a}. Add index 1: {a, b}.
  • Add index 2: {a, c}.
  • Start at index 1: {b}. Add index 2: {b, c}. Combinations: "ab", "ac", "bc".
• next() returns "ab".
• next() returns "ac".
• hasNext() is true.

5. Common mistakes candidates make

• Memory Limit: Generating all combinations for a large input ($O(\binom{N}{k})$) in the constructor. If the user only calls next() a few times, this is extremely inefficient.
• Incorrect Order: Failing to return combinations in lexicographical order (sorting the input string first usually fixes this).
• Hard-to-read Logic: Writing complex index-shifting logic for the "lazy" approach instead of using a simpler pre-calculation if constraints allow.

6. Interview preparation tip

Always discuss the trade-offs between Eager and Lazy generation. Eager is easier to implement but uses $O(TotalCombinations)$ space. Lazy is harder to code but uses only $O(K)$ space. Knowing when to use which is a senior-level trait.