I have answered it using heaps. She told me she's expecting more optimal approach. In the end, i asked her what could the better approach than using heaps and she answered saying to use 'Priority Queue'. I was pretty much shocked to understand that the interviewer doesn't know that both are same. 'Priority Queues are nothing but using heaps. There's nothing else' I explained her saying that priority queue is just one fancy name for what i already implemented using. She asked me another question to which i answered using graphs and she's convinced here. Also i found her going away from the interview session and rejoining after sometime after my second question. The interview is done and i didn't get the position. PS: i gave optimal solutions to both the problems asked and i wasn't asked any other questions. The only thing here is the lack of knowledge of the interviewer!