Design Compressed String Iterator

Design Compressed String Iterator

1. What is this problem about?

The Design Compressed String Iterator interview question involves building a specialized iterator for a compressed string like "L1e2t1c1o1d1e1". In this format, each character is followed by the number of times it repeats. You need to implement next() to return the next uncompressed character and hasNext() to check if more characters exist. This Design Compressed String Iterator coding problem tests your ability to parse and expand data lazily.

2. Why is this asked in interviews?

Google ask this to evaluate your Iterator interview pattern skills and how you handle data streams. It tests whether you can expand the string "on-the-fly" (lazily) rather than uncompressing the whole thing at once, which could use $O( ext{Uncompressed Length})$ memory. It's a test of memory efficiency and string parsing.

3. Algorithmic pattern used

This problem uses Lazy Evaluation and String Parsing.

• Maintain the compressed string and a current index pointer.
• Maintain currentChar and remainingCount variables.
• When next() is called:
  1. If remainingCount > 0, decrement it and return currentChar.
  2. If remainingCount == 0, parse the next character and its following multi-digit count from the string.
  3. If parsing succeeds, return the new character; else return a space.

4. Example explanation

Compressed: "a2b3".

1. next(): Sees 'a', reads count '2'. Returns 'a', remaining=1.
2. next(): remaining > 0. Returns 'a', remaining=0.
3. next(): remaining=0. Sees 'b', reads count '3'. Returns 'b', remaining=2.
4. hasNext(): Returns true since index hasn't reached the end or remaining > 0.

5. Common mistakes candidates make

• Eager Decompression: Uncompressing the entire string into memory. If the input is "a1000000000", the program will crash.
• Parsing multi-digit numbers: Forgetting that the count after a character can be more than one digit (e.g., "a10").
• Pointer Logic: Messing up the index transitions between characters and numbers.

6. Interview preparation tip

Always implement iterators Lazily. Interviewers are checking to see if you can process data without loading the entire resulting dataset into RAM. Use a while loop to parse consecutive digits into a single integer.