First Unique Number

First Unique Number

1. What is this problem about?

The First Unique Number interview question is a design task for a data stream. You need to implement a class that can:

1. add(value): Add a new number to the stream.
2. showFirstUnique(): Return the value of the first number that has been added to the stream exactly once. If no unique number exists, return -1.

2. Why is this asked in interviews?

Uber and Meta ask this to test your ability to maintain Ordered Uniqueness. It requires a combination of data structures to achieve $O(1)$ for both operations. It evaluations your knowledge of Linked List interview patterns and Hash Table interview patterns working together (similar to an LRU cache).

3. Algorithmic pattern used

This problem is best solved using a Hash Map + Doubly-Linked List or a Hash Map + Queue.

• The "LRU" Style Approach:
  • Map<Integer, Node>: Maps a value to its node in a doubly-linked list.
  • Set<Integer> isDuplicate: Tracks numbers that have appeared more than once.
  • add:
    • If in isDuplicate, ignore.
    • If in the Map, remove from list and add to isDuplicate.
    • If new, add to map and append to the end of the linked list.
  • showFirstUnique: Return the head of the linked list.

4. Example explanation

1. add(2), add(3), add(2)
   • add(2): Unique: [2].
   • add(3): Unique: [2, 3].
   • add(2): 2 is now a duplicate. Remove from unique. Unique: [3].
2. showFirstUnique(): Returns 3.
3. add(3): 3 is now a duplicate. Unique: [].
4. showFirstUnique(): Returns -1.

5. Common mistakes candidates make

• Linear Search: Iterating through the whole stream for showFirstUnique ($O(N)$), which is too slow for frequent calls.
• Incomplete Deletion: Forgetting to handle the case where a number was unique but becomes a duplicate later.
• Queue bloat: Using a simple queue and not removing duplicates from the front until showFirstUnique is called (Lazy Deletion). While valid, it can use more memory than the linked list approach.

6. Interview preparation tip

Practice combining data structures. Problems that require "First seen," "Most recent," or "Unique in order" almost always use a Map combined with a sequential structure like a Queue or Linked List.