First Unique Number in a Stream

Problem Statement

Design a data structure that maintains a queue of integers and can efficiently return the first unique (non-repeated) number in the queue.

Implement:

1. showFirstUnique() — Return the first unique integer in the queue, or -1 if none exists
2. add(value) — Add a value to the end of the queue

Constraints

• 1 <= value <= 10^8
• At most 5 * 10^4 calls to add and showFirstUnique
• Both operations should be efficient (aim for O(1) amortized)

Example

FirstUnique fu = new FirstUnique([2, 3, 5]);
fu.showFirstUnique();  // returns 2
fu.add(5);             // queue: [2,3,5,5]
fu.showFirstUnique();  // returns 2
fu.add(2);             // queue: [2,3,5,5,2]
fu.showFirstUnique();  // returns 3 (2 is no longer unique)
fu.add(3);
fu.showFirstUnique();  // returns -1 (nothing unique)

What the Interviewer Expects

1. Track frequency + order — a HashMap for counts, and a structure to maintain insertion order of unique elements.
2. Optimal: LinkedHashSet / Doubly Linked List + HashMap:
   • HashMap of value → count
   • An ordered set of currently-unique values
   • On add: increment count. If it becomes non-unique, remove from the ordered set.
   • showFirstUnique: return the head of the ordered set (O(1))
3. Uber values production-ready code — clean structure, edge cases handled. Even a correct solution can fail on messy code.

Follow-ups

1. What if you also need removeFirst() (dequeue)?
2. What if you need the first unique in the last K elements only (sliding window)?
3. How would you handle this in a multi-threaded producer-consumer setting?
4. What's the space complexity, and can you reduce it?