I was given a log file of conversation like this: "maria: hi, john: hello hi bye bye, maria: pls dont go" and a helper function parse_log that would process the file so I would get a list like this: [('maria', 1), ('john', 4), ('maria', 3)] calculating the wordcount per message. I had to return top N talkative users.

I used a dictionary to calculate wordcount per person and then made a min heap with "-" to simulate a max heap. The issue is I made a heap of size P (number of people) instead of capping the heap at N (number of top users we need). I finished coding with 20-25 minutes left and then the interviewer pointed to a portion of my code and said I have a bug there. I figured it out immediately. She pointed to another portion for another bug, I took a while but figured it out and fixed it. It can be considered syntactical. Then she asked me to provide some test cases which I did (ties, empty list from parse_log etc). Then she asked me for time complexity which I explained and generalized to O(M log U) where M = messages and U=users.

The biggest issue is that the time complexity could greatly be reduced if I used a heap of size N i.e. O(M log N) which is significant for when N<<U. How bad was this round?