Sesame AI·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Got a technical phone screen for a software engineering role at Sesame AI that was basically one meaty design question the whole time. The problem was interesting but the O(1) constraint with bounded memory made it trickier than it looked on the surface.

Questions Asked (1)

Design a StreamingMetrics class that ingests ASR (speech recognition) events, each containing a user ID and word count, and tracks the user with the longest transcribed sentence and the total number of unique users. The constructor takes a lookback window size limiting how many recent events are kept in memory. The ingest method must run in O(1) time and memory must stay bounded.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

This one took me a minute to even parse.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then propose a design using a circular buffer (or deque) to store the last N events and a hash map to track per-user word counts, ensuring O(1) ingest and bounded memory. Explain how to maintain the longest sentence and unique user count efficiently, and discuss trade-offs like handling duplicates and eviction.

Pro tip: Mention that you would use a doubly linked list for the buffer to allow O(1) removal of the oldest event, and a hash map for user counts that is updated on both insertion and eviction to keep the unique user count accurate.

1. Clarify Requirements and Constraints

Ask about the lookback window size (fixed or dynamic), event rate, and whether 'longest transcribed sentence' means maximum word count in a single event or cumulative per user. Confirm that O(1) time and bounded memory are hard requirements.

2. Design Data Structures

Propose a circular buffer (array + head/tail indices) or a doubly linked list to store the last N events. Use a hash map to track per-user word counts for the current window, and maintain variables for the current maximum word count and the user who achieved it.

3. Implement Ingest Logic

On each event, add it to the buffer and update the user's count in the hash map. If the buffer exceeds the window size, evict the oldest event: decrement its user's count (removing the user if count reaches zero) and update the max if the evicted event was the current max.

4. Handle Edge Cases and Optimizations

Discuss handling ties for longest sentence (e.g., keep the most recent or any), and how to efficiently update the max when the current max is evicted (e.g., by scanning the buffer, which is O(N) but N is bounded). Mention that unique user count is the size of the hash map.

5. Analyze Complexity and Trade-offs

Confirm O(1) amortized time for ingest (except occasional O(N) scan for max update, which is acceptable if N is small). Memory is O(N) for the buffer plus O(U) for the hash map, where U ≤ N. Discuss alternatives like using a heap for max, but note that eviction complicates it.

Key Points to Mention

Use a circular buffer or deque to store the last N events, ensuring bounded memory.
Maintain a hash map from user ID to word count in the current window to track unique users and per-user totals.
Keep track of the current maximum word count and the corresponding user ID; update on ingest and eviction.
On eviction, decrement the user's count and remove the user if count becomes zero; if the evicted event was the max, recompute the max by scanning the buffer (O(N) but N is bounded).
Unique user count is simply the number of keys in the hash map.
Discuss trade-offs: O(1) ingest is achieved except for occasional O(N) max recomputation; if strict O(1) is required, consider a different approach like a segment tree or heap with lazy deletion, but that may increase memory or complexity.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.