IXL Learning·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Interviewed for a software engineer role at IXL Learning and ran into a classic streaming data problem. The question was more implementation-heavy than I expected for a phone screen.

Questions Asked (1)

Design and implement 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 Structures

Author's notes

I knew the two-heap approach going in but still fumbled the boundary condition when the total count is even.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements (e.g., data types, memory constraints) and then propose a two-heap solution: a max-heap for the lower half and a min-heap for the upper half. Explain how to maintain balance and compute the median in O(1) time with O(log n) insertion.

Pro tip: Mention that this approach is optimal for streaming data and discuss how to handle edge cases like even/odd counts and duplicate values. Also, note that if the stream is static, a simpler approach like sorting could work, but the two-heap method is ideal for dynamic streams.

1. Clarify Requirements

Ask about data types, memory constraints, and whether the median should be exact or approximate. Confirm that the data structure should support dynamic insertion and median retrieval.

2. Propose Two-Heap Approach

Explain that you'll 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 count) or the average of both tops (even count).

3. Detail Insertion Logic

Describe how to add a number: insert into the appropriate heap, then rebalance so the heaps differ in size by at most 1. Ensure the max-heap's top is <= the min-heap's top.

4. Analyze Complexity

State that insertion takes O(log n) time due to heap operations, and finding the median takes O(1) time. Space complexity is O(n) for storing all elements.

5. Discuss Edge Cases and Alternatives

Mention handling of empty stream, even/odd counts, and duplicates. Optionally, discuss alternative approaches like balanced BSTs or sorted lists and their trade-offs.

Key Points to Mention

Two-heap strategy: max-heap for lower half, min-heap for upper half
Balancing condition: sizes differ by at most 1, and max-heap top <= min-heap top
Time complexity: O(log n) for insertion, O(1) for median retrieval
Space complexity: O(n) to store all elements
Handling even and odd number of elements
Edge cases: empty stream, duplicates, and large streams

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