← Reddit Interview InsightsSoftware Engineer

Reddit·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Reddit coding round, one problem the whole time. It was a merging/dedup problem built around a fake chat API, which sounds manageable until you read the time complexity constraint and realize they actually want you to know what a k-way merge is.

Questions Asked (1)

Q1

You have a chat application where messages have unique strictly-increasing integer IDs. Given an external API that returns a message plus up to N messages before and after it (a context window), implement a class with a method that takes a list of IDs, fetches the context window for each, and returns a single deduplicated list of messages sorted by ID. The solution must run better than O(M log M) where M is the total number of messages fetched across all windows.

Algorithms & Data StructuresAPI & IntegrationsSystem Design
Author's notes

The dedup and sort parts I got pretty quickly, just throw everything in a set keyed by ID and sort at the end.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the constraints and the API's behavior, then propose a solution that leverages the strictly increasing IDs to merge overlapping context windows efficiently. Use a k-way merge with a min-heap or a two-pointer merge on sorted windows, achieving O(M log K) where K is the number of windows, which is better than O(M log M) when K << M. Finally, discuss deduplication and sorting as part of the merge process.

Pro tip: Mention that if the API returns messages in sorted order, you can merge the windows in O(M log K) using a heap, and if K is small, this is effectively O(M). Also, highlight that deduplication can be done during the merge by skipping duplicate IDs, avoiding a separate pass.

1. Clarify requirements and constraints

Ask about the API's behavior: does it return messages sorted by ID? What is N? Can windows overlap? Are IDs strictly increasing globally? Confirm that M is the total number of messages fetched, including duplicates.

2. Design the data flow

For each input ID, fetch its context window. Collect all windows, noting that each window is a sorted list of messages. The goal is to merge these sorted lists into one sorted, deduplicated list.

3. Choose an efficient merge strategy

Use a min-heap to perform a k-way merge of the sorted windows. Push the first message of each window into the heap, then repeatedly pop the smallest, add to result if not duplicate, and push the next message from that window. This yields O(M log K) time.

4. Handle deduplication and sorting

During the merge, skip messages with IDs already seen (e.g., by comparing with the last added ID). Since the heap ensures global sorted order, the result is sorted and deduplicated without extra sorting.

5. Analyze complexity and edge cases

Explain that O(M log K) is better than O(M log M) when K < M. Discuss edge cases: empty input, overlapping windows, API errors, and large N causing memory issues. Suggest streaming or lazy fetching if needed.

Key Points to Mention

  • The API returns messages in sorted order by ID, enabling efficient merging.
  • Use a min-heap for k-way merge to achieve O(M log K) time complexity.
  • Deduplicate during merge by tracking the last added ID, avoiding a separate set or sort.
  • The number of windows K is typically much smaller than M, so O(M log K) is effectively O(M).
  • Memory considerations: storing all messages may be large; discuss streaming or processing in chunks.
  • Edge cases: empty input, duplicate IDs across windows, API failures, and very large N.

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