Round 1
Questions: Given a sparse bit array A of size M stored in a database. The database provides an API query(L,R) which returns 1 if there is at least one bit equal to one in A[L..R] and 0 otherwise. You want to find all the 1 bits in a reasonable number of queries. E.g. for array 01100000001, positions of 1 bits are {1, 2, 10}. Return the array of all the positions of 1's.
Candidate's Approach
I provided a divide and conquer recursive solution with O(K log N) where K is the number of 1's. However, the interviewer was expecting an O(1) space complexity iterative solution and I was not able to optimize my recursive solution.
Interviewer's Feedback
The feedback was that I was "on the fence" as I took multiple hints and had a slower pace.
Round 2
Questions: You are given an undirected unweighted graph, a start node, and an end node. You need to find the shortest path from start to end node but there are some nodes which are restricted (L), that cannot be part of your path. Example: edges = [{1,2}, {2,3}, {1,4}, {4,5}, {3,5}}, start = 1, end = 3, L = {2}.
Follow Up: There is a special kind of pass to cross the restricted node, which is very costly. Assume there is no possible path from start to end which does not contain restricted nodes. Then find the minimum number of passes you will need to reach the end. There is no need to minimize the path length here.
Candidate's Approach
I asked clarifying questions about the existence of the path. I used BFS and checked if the adjacent node is present in the restricted array. To optimize, I suggested storing the restricted nodes in a set. For the follow-up, I provided a Dijkstra solution using the number of restricted nodes as the first argument in the priority queue. I wrote the code and discussed the time complexity.
Interviewer's Feedback
The HR's exact words were: "It was between okay and good, consider it a positive" (lean hire or hire).
Round 3
Questions: Input: given a URI e.g. /google/storage/var you need to return the list of 10 largest files inside the folder as {sz, url}. Output:
1008372 /google/storage/var/music.mp4 313236 /google/storage/var/www/img.jpg 253964 /google/storage/var/log/voice.mp3 192544 /google/storage/var/lib.txt 152628 /google/storage/var/spool.mp4 152508 /google/storage/var/spool/squid/noice.png 136524 /google/storage/var/spool/squid/00.txt 95736 /google/storage/var/log/mrtg.log 74688 /google/storage/var/log/squid/color.txt 62544 /google/storage/var/cache.txt
You have two helper functions which compute in O(1):
- helper.sz(str): takes the string as input; if it is a file, it returns the size of the file; otherwise, -1.
- helper.list(str): takes a string as input; if it is a folder, it returns a list of all the directories inside it (all the folders and immediate files). If str is a file, it returns null.
Follow Up: Now you need to return the 10 largest folders. Size of folder = sum of all the immediate files inside that folder.
Candidate's Approach
I wrote a recursive code using the helper functions and discussed the time and space complexity. For the follow-up, I wrote recursive code to return the 10 largest folders, but it had some issues, and we ran out of time.
Interviewer's Feedback
The feedback was a lean hire or hire, with HR stating: "It was fine."
Round 4
Questions: You are given a chat log file e.g.
< John > Hi, How is everyone? < Amy> Hello John < Maria > Great, Having my morning coffee < John> Lets meet this weekend < Amy > Woahoo
You need to find out the top N talkative persons with their total word count from the chat log file. You are given a helper function which takes the log file as input and returns the word count of each message.
Example: If N=2, the answer for the above example would be:
[{ 'John', 8 }, { 'Maria', 5 }]
Candidate's Approach
I initially provided a naive solution that iterated over the output from the helper function and used a map to store the names and their counts. Then I sorted it to return the top 10 pairs based on total count. After discussing the time and space complexity, I optimized it using a min-heap priority queue solution to maintain the top N talkative persons.
Interviewer's Feedback
The feedback was positive, and I believe I was hired.