← Trexquant Interview Insights

Trexquant·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
May 2026Remote

Summary

Trexquant had me implement a median finder on a live integer stream, pretty much a classic two-heap problem but the pressure of doing it cleanly under time made it trickier than I expected.

Questions Asked (1)

Q1

Design a data structure that supports adding numbers from a stream one at a time and returning the median of all numbers seen so far at any point.

Algorithms & Data StructuresSystem Design
Author's notes

I knew the two-heap approach going in but fumbled the rebalancing logic during the actual implementation.

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) to maintain the median in O(log n) insertion and O(1) lookup. Explain the balancing invariant and how to handle even/odd counts, then discuss trade-offs with alternative approaches like sorted arrays or balanced BSTs.

Pro tip: Emphasize that the two-heap solution is optimal for streaming data because it avoids re-sorting and handles large streams efficiently; also mention that in real systems you might need to handle duplicates and consider memory constraints.

1. Clarify requirements and constraints

Ask about the expected number of elements, whether duplicates are allowed, and if the median needs to be returned as a float or exact value. Confirm that the data structure should support dynamic insertion and median retrieval.

2. Propose a naive approach and its limitations

Mention that a simple approach like keeping a sorted list and inserting in O(n) or re-sorting each time is inefficient for large streams. This sets the stage for a more optimal solution.

3. Present the two-heap solution

Describe using a max-heap for the smaller half and a min-heap for the larger half. Explain that after each insertion, you balance the heaps so their sizes differ by at most one, and the median is either the top of the larger heap or the average of both tops.

4. Analyze complexity and edge cases

State that insertion takes O(log n) time due to heap operations, and median retrieval is O(1). Discuss edge cases: empty stream, one element, even/odd counts, and duplicate values.

5. Discuss alternatives and trade-offs

Briefly mention other approaches like using a balanced binary search tree (O(log n) insertion, O(log n) median) or a self-balancing tree with order statistics, and compare their pros and cons in terms of implementation complexity and performance.

Key Points to Mention

  • Two-heap approach: max-heap for lower half, min-heap for upper half
  • Balancing invariant: sizes differ by at most 1
  • Median calculation: if sizes equal, average of tops; else top of larger heap
  • Time complexity: O(log n) insertion, O(1) median retrieval
  • Space complexity: O(n) to store all elements
  • Handling duplicates and edge cases (empty stream, single element)

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