← Sesame Interview Insights

Sesame·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Got a technical phone screen for a software engineer role at Sesame AI that was basically one meaty design question the whole time. Interesting problem, more nuanced than it looks at first glance.

Questions Asked (1)

Q1

Design a StreamingMetrics class that ingests ASR (speech recognition) events, each containing a username and word count, and tracks two things: which user produced the longest single sentence, and how many unique users have been seen. 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 fully unpack.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and edge cases, then propose a data structure that supports O(1) ingest and bounded memory. Use a circular buffer to store recent events and a deque to maintain the maximum word count efficiently, along with a hash set for unique users. Discuss trade-offs and potential optimizations.

Pro tip: Mention that the maximum tracking can be done with a monotonic deque, which gives O(1) amortized time per operation, and emphasize that this is a common pattern in streaming algorithms.

1. Clarify Requirements

Ask about the definition of 'longest single sentence' (e.g., by word count), whether ties matter, and if the lookback window is in number of events or time. Confirm that ingest must be O(1) and memory bounded.

2. Design Data Structures

Propose a circular buffer (array) of size N to store the last N events, a hash set to track unique users, and a monotonic deque to maintain the maximum word count in the window. Explain how each supports O(1) operations.

3. Detail Ingest Logic

Describe the steps: add new event to buffer, update unique users set, and update the deque by removing elements from the back that are smaller than the new word count, then adding the new event. If buffer overflows, remove the oldest event and update the deque if necessary.

4. Handle Queries and Edge Cases

Explain how to retrieve the user with the longest sentence (front of deque) and the count of unique users. Discuss edge cases like empty window, duplicate users, and ties.

5. Analyze Complexity and Trade-offs

Confirm O(1) amortized time for ingest and O(N) memory. Discuss alternatives like using a heap (O(log N)) and why deque is better. Mention that unique user count is exact but could be approximated with HyperLogLog if memory is extremely tight.

Key Points to Mention

  • Circular buffer for bounded memory and O(1) insertion/removal.
  • Monotonic deque for O(1) amortized maximum tracking.
  • Hash set for O(1) unique user counting.
  • Handling of window overflow and updating data structures accordingly.
  • Trade-offs between exact and approximate counting for unique users.
  • Amortized O(1) time complexity and O(N) space complexity.

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