I applied via referral and a phone screen was scheduled. I answered questions in both phone screens and even ran the code in the editor. It was working out fine. I even optimized the solutions and discussed their complexities.

In one of the solutions, I was asked the complexity of creating a priority queue (binary heap) of size n. I answered O(n), as people often get confused. I remembered this from my algorithms course: it takes linear time, as opposed to the common misbelief of O(n log n) time.

When I stated this, the interviewer asked me twice if I was sure. I affirmed my certainty and explained why it is O(n), but he didn't seem to believe me. Nevertheless, I continued and gave the optimal solution.

After two phone screens, I received a negative response. I'm unsure whether to feel happy or sad about this.

LeetCode medium problems.