radix trading·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

One coding round for a quant researcher role at Radix Trading, focused on C++. The problem involved implementing a rolling median, and from what I can tell the experience varies depending on which research lead you're interviewing with.

Questions Asked (1)

Implement a rolling median in C++.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This is a classic two-heap setup but doing it cleanly in C++ under pressure is a different story.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem requirements (e.g., data type, window size, online vs offline) and then present a solution using two heaps (max-heap for lower half, min-heap for upper half) to maintain the median in O(log n) per insertion and O(1) retrieval. Discuss trade-offs with alternative approaches like balanced BST or order-statistic tree, and mention optimizations for specific cases.

Pro tip: Show awareness of numerical stability and integer overflow when computing the median of two numbers, and mention how to handle even-sized windows by averaging the two middle elements without precision loss.

1. Clarify Requirements

Ask about the expected input size, frequency of queries, whether the window size is fixed or dynamic, and the data type (e.g., integers, doubles). This ensures the solution fits the use case.

2. Choose Data Structures

Select two heaps (max-heap for lower half, min-heap for upper half) as the primary approach, or consider a balanced BST if order statistics are needed. Explain why heaps offer O(log n) insertion and O(1) median retrieval.

3. Outline Algorithm

Describe the insertion process: add to appropriate heap, rebalance sizes so they differ by at most 1, and ensure all elements in max-heap are ≤ those in min-heap. For median, if sizes equal, average the two tops; else return the top of the larger heap.

4. Analyze Complexity and Trade-offs

State time complexity: O(log n) per insertion, O(1) per median query, O(n) space. Compare with alternatives like sorting (O(n log n) per query) or balanced BST (O(log n) per operation but higher constant factors).

5. Discuss Edge Cases and Optimizations

Mention handling of empty data, even/odd counts, and potential optimizations like using a single heap with lazy deletion for sliding windows, or using a Fenwick tree for integer data with known range.

Key Points to Mention

Two-heap approach: max-heap for lower half, min-heap for upper half, with rebalancing to maintain size property.
Time complexity: O(log n) insertion, O(1) median retrieval; space complexity O(n).
Handling even-sized windows by averaging the two middle elements, with attention to integer overflow and floating-point precision.
Alternative data structures: balanced BST (e.g., red-black tree) with order statistics, or Fenwick tree for integer data with known range.
Sliding window variant: use lazy deletion or a balanced BST to support removal of old elements.
Edge cases: empty input, single element, duplicate values, and large datasets requiring memory efficiency.

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