← Tinder Interview Insights

Tinder·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
Apr 2026

Summary

Tinder SWE interview, got a classic streaming median problem. Pretty standard stuff if you've seen it before, but the implementation details can trip you up under pressure.

Questions Asked (1)

Q1

Design a data structure that supports adding numbers from a stream one at a time and returning the current median at any point.

Algorithms & Data Structures
Author's notes

I knew the two-heap trick going in, max-heap for the lower half, min-heap for the upper half.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use two heaps: a max-heap for the lower half and a min-heap for the upper half, keeping their sizes balanced. After each insertion, rebalance the heaps and compute the median from the top elements. This yields O(log n) insertion and O(1) median retrieval.

Pro tip: Discuss how you would handle duplicates and large streams, and mention that the two-heap approach is optimal for online median finding. Also, be prepared to compare with alternatives like a self-balancing BST or a Fenwick tree, explaining why heaps are simpler and more efficient here.

1. Clarify requirements and constraints

Ask about the expected number of elements, frequency of median queries, and whether memory is a concern. Confirm that the median is defined as the middle element for odd counts and the average of two middle elements for even counts.

2. Propose the two-heap approach

Explain that you will maintain a max-heap for the lower half and a min-heap for the upper half. The median is either the top of the max-heap (odd total) or the average of the tops (even total).

3. Detail the insertion and rebalancing logic

Describe how to add a new number: push to the appropriate heap based on comparison with the current median, then rebalance so that the size difference between heaps is at most 1. Ensure the max-heap's top is ≤ the min-heap's top.

4. Analyze time and space complexity

State that insertion takes O(log n) due to heap operations, median retrieval is O(1), and space is O(n). Compare with naive approaches like sorting on each query (O(n log n) per query).

5. Discuss edge cases and potential optimizations

Mention handling of empty stream, single element, duplicates, and very large streams. Optionally, discuss using a self-balancing BST or a Fenwick tree for order statistics, but note that heaps are simpler and more efficient for this specific problem.

Key Points to Mention

  • Two heaps: max-heap for lower half, min-heap for upper half
  • Balancing condition: size difference ≤ 1, and max-heap top ≤ min-heap top
  • Median calculation: top of max-heap if odd, average of tops if even
  • Time complexity: O(log n) insertion, O(1) median retrieval
  • Space complexity: O(n)
  • Handling duplicates and large streams

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