Just had my first round interview with Citadel for their NXT program. I’m a Senior Software Engineer with 3 years of experience in backend and infrastructure development, and this was my first step in their process.

Question:
Design a data structure that supports two APIs:

insert(num: int)

findMedian(): float

Essentially, this is the classic "Find Median from Data Stream" problem available on LeetCode here.

My approach:

Started with the naive solution using a list and sorting

Then implemented the optimal approach using two heaps: a max heap for the lower half and a min heap for the upper half, maintaining balance and allowing O(log n) insert and O(1) median retrieval.

Missed to notice that I did not have the base condtion if the stream is empty

Felt the session went well overall explained my thought process clearly, wrote working code, and optimized properly.

Result: Rejected the next morning.