This round was quite simple. The interviewer, originally supposed to be a frontend engineer, was replaced by a backend engineer due to unforeseen circumstances. I introduced myself, shared project experiences, technical challenges, and then proceeded to coding. The task was to write a function to find the median. The operations included Add, Remove, and findMedian to add or remove a number in the data structure and find the median among all numbers. Below is an example (Add and Remove operations do not need to return anything, just perform the operation in the structure, while findMedian needs to return the median):
Add 8 -> [8]
Add 4 -> [8, 4]
findMedian -> 6
Add 5 -> [8, 4, 5]
Remove 4 -> [8, 5]
findMedian -> 6.5
The approach involved using a max heap and a min heap as data structures, ensuring their length difference is not greater than 1. By considering parity and comparing the tops of the heaps, the median can be found. The follow-up question was about time complexity before concluding.