Trexquant·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Trexquant SWE interview had at least one technical coding problem focused on streaming data and efficient median tracking. Pretty standard algorithmic round but the implementation details matter a lot here.

Questions Asked (1)

Design a data structure in C++ that supports adding integers from a stream and querying the median at any point, with efficient time complexity for both operations.

Algorithms & Data Structures

Author's notes

Classic two-heap setup, one max-heap for the lower half and one 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. For each incoming integer, insert into the appropriate heap and rebalance so the size difference is at most one. The median is then either the top of the larger heap or the average of the two tops.

Pro tip: Mention that this approach gives O(log n) insertion and O(1) median query, and discuss how to handle duplicates and integer overflow when averaging. Also, briefly compare with alternatives like a self-balancing BST or order-statistic tree to show depth.

1. Clarify requirements

Confirm that the data structure should support addNum(int) and findMedian() operations, and discuss expected time complexity and memory constraints.

2. Choose data structures

Select two heaps: a max-heap for the lower half and a min-heap for the upper half. Explain why heaps are ideal for maintaining the median dynamically.

3. Define insertion logic

Describe the algorithm: add to max-heap if num <= max-heap top, else to min-heap; then rebalance by moving the top element from the larger heap to the other if sizes differ by more than one.

4. Define median query

If heaps are equal size, median is the average of the two tops; otherwise, it's the top of the larger heap. Discuss handling of integer division and overflow.

5. Analyze complexity and edge cases

State time complexities: O(log n) for insertion, O(1) for median. Mention edge cases: empty stream, single element, duplicates, and large numbers.

Key Points to Mention

Two-heap approach with max-heap for lower half and min-heap for upper half
Balancing condition: size difference at most 1
Time complexity: O(log n) for addNum, O(1) for findMedian
Space complexity: O(n)
Handling duplicates and integer overflow when averaging
Alternative approaches: self-balancing BST, order-statistic tree, or sorted array (with trade-offs)

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