Here’s a clean version you can use:
Short Question:
How do you design a data structure to efficiently track and retrieve the first non-repeating character in a stream?
Description:
In many data stream problems, characters arrive one by one, and we need to continuously determine the first non-repeating character at any given point.
The challenge is to design a data structure that:
-
Supports real-time updates as new characters arrive
-
Efficiently tracks frequencies of characters
-
Quickly returns the first character that has appeared only once so far
A brute-force approach would re-scan the entire stream after each insertion, which is inefficient. Instead, we need an optimized approach using a combination of data structures to maintain order and frequency.
Approach:
Use:
-
A hash map to store frequency of each character
-
A queue to maintain insertion order
Python Code:
from collections import deque
class FirstNonRepeating:
def __init__(self):
self.freq = {}
self.queue = deque()
def add(self, char):
# Update frequency
self.freq[char] = self.freq.get(char, 0) + 1
# Add to queue
self.queue.append(char)
# Remove repeating characters from front
while self.queue and self.freq[self.queue[0]] > 1:
self.queue.popleft()
def get_first_non_repeating(self):
return self.queue[0] if self.queue else None
# Example usage
stream = FirstNonRepeating()
for ch in "aabcbd":
stream.add(ch)
print(stream.get_first_non_repeating())
