← Openai Interview Insights

Openai·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
May 2026

Summary

Coding round at OpenAI for a software engineer role. One problem, a variation on the classic hit counter design, and I ran out of time before even seeing the follow-up. Not my best showing.

Questions Asked (1)

Q1

Design a chat tracking system with two methods: one to record a chat event given a user ID, chat ID, and timestamp, and another to return the count of chat events within the last 15 minutes for a given user and chat.

System DesignAlgorithms & Data Structures
Author's notes

Basically a hit counter problem but the window is anchored to the last recorded event, not the current time.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the requirements and constraints first, then propose a design using a hash map keyed by (userId, chatId) with a deque or circular buffer of timestamps. For the count method, remove timestamps older than 15 minutes and return the size of the buffer.

Pro tip: Discuss trade-offs between memory usage and query speed, and mention that a sliding window with a deque gives O(1) amortized operations per event, which is crucial for high-throughput systems.

1. Clarify Requirements

Ask about expected scale (events per second, number of users/chats), memory constraints, and whether timestamps are monotonic. Confirm that the 15-minute window is sliding and that we need per-user-per-chat counts.

2. Choose Data Structures

Propose a hash map where the key is a composite of userId and chatId, and the value is a deque (double-ended queue) storing timestamps. Explain why a deque is ideal for efficient append and popleft operations.

3. Design Record Method

For record(userId, chatId, timestamp), look up or create the deque for the key, append the timestamp, and optionally prune old timestamps to keep memory bounded. Ensure O(1) time complexity.

4. Design Count Method

For count(userId, chatId), retrieve the deque, remove timestamps older than (current time - 15 minutes) from the front, and return the remaining size. This gives O(k) where k is the number of expired events, amortized O(1).

5. Discuss Optimizations and Edge Cases

Address concurrency (e.g., locking per key), memory management (e.g., eviction of inactive keys), and handling out-of-order timestamps. Mention potential use of a ring buffer or time-bucketed counters for further optimization.

Key Points to Mention

  • Use a hash map with composite key (userId, chatId) for O(1) access.
  • Store timestamps in a deque to efficiently maintain a sliding window.
  • Prune old timestamps during count or record to keep memory usage proportional to active events.
  • Time complexity: O(1) amortized per operation; space complexity: O(N) where N is number of events in the last 15 minutes.
  • Consider concurrency: use fine-grained locks or concurrent data structures if multi-threaded.
  • Handle edge cases: empty deque, out-of-order timestamps, and clock skew.

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