Round 1
Questions: 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 word count per message. I had to return top N talkative users.
Candidate's Approach
- Used a dictionary to calculate word count per person.
- Created a min heap with "-" to simulate a max heap.
- Initially made a heap of size P (number of people) instead of capping it at N (number of top users needed).
- Finished coding with 20-25 minutes left.
- Identified and fixed bugs pointed out by the interviewer.
- Provided test cases including ties and empty list from
parse_log. - Explained time complexity as O(M log U) where M = messages and U = users.
- Acknowledged that time complexity could be reduced to O(M log N) if using a heap of size N.
Interviewer's Feedback
- The interviewer pointed out bugs in the code, which were identified and fixed by the candidate.
- The candidate was able to provide relevant test cases.
- The interviewer engaged in a discussion about time complexity.