October 2024
Round 1: 45minutes (Tech)

He was 5minutes late (but did not give extra time). It started with the introduction and then we moved to the problem.

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.

I gave a divide and conquor recursive solution with O(KlogN) where k is number of 1's.
He was expecting an O(1) space complexity iterative solution, was not able to optimize the recursive solution.

Feedback : On the fence (took multiple hints, and slower pace)

PS: you will find the solution to this problem in some other leetcode discuss, yes google repeats question

Round 2: Tech(45min) + Googleyness(15min)
Similar to first round It started with the introduction and then we moved to the problem.

You are given a 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 can not be part of your path.
example: edges =[{1,2}, {2,3}, {1,4}, {4,5}, {3,5}}, start = 1, end = 3, L ={2}

I asked some clarifying questions - does the path always exist?
This was very standard problem- used BFS and while visiting the adjNodes I checked if the adjNode is present in the restricted array.
He asked to optimize it a bit, so i said we'll store the restricted node in a set. he told me to update the code accordigly.
Then I was asked Time and space complexities.

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.

I gave a dijkestra solution with no of restricted nodes as the first argument in the priority queue.
wrote the code and then discussed the time complexity.
He seem satisfied with both the codes.

googleyness

• What is the most rewarding part of developing something for you
• In your internship you have worked with other people, was there a time when you had conflicting persectives with your teammates. how did you handled that.
  • Were your suggestions considered?
• Have you worked upon something which has very strict deadlines, how did you manage it
• If you are working on a project with 4 other people and everyone has contributed equally but one person takes all the credits what will you do
  •  do you think it will affect his relationship with you or with the other teammates.
    Then he asked if I had any questions, I aksed him few questions

Feedback: exact words of Hr: "It was between okay and good, consider it a positive" (I guess lean hire or hire)

Round 3: Tech(45min) + Googleyness(15min)

It was a long question but had simple implementation, Google intentionally makes such description to confuse candidates, I'll try to write as much as I remember.

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 computes in O(1)

1. helper.sz(str). takes the string as input if it is a file it returns the size of the file otherwise -1
2. 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 imidiate files). If str is a file it returns null.

I wrote a recursive code using these helper functions, then we discussed the time and space complexity.

Follow Up
Now you need to return the 10 largest folders
size of folder = sum of all the imidiate files inside that folder

Wrote the recursive code for this one, but it had some issues, we were out of time so moved on to googleyness.

Googleyness

• Have you even been a situation where you had to make a tough decision, what things did you considered.
• Strict timeline same question as last interview
  *If you have have any questions - I asked few questions

Feedback: Lean Hire / Hire (HR: It was fine)

EDIT: Got Call for round 4

(November 2024)
Round 4: 45minutes (Tech)

It wad lengthy problem statement, I'll try to share the best I remember.
You are given a chat log file e.g
< John > Hi, How is everyone?
< Amy> Hello John
< Maria > Great, Having my morning cofee
< 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 return the word count of each message, so for the above example the helper function will return [{'John', 4}, { 'Amy', 2}, {'Maria', 5}, {'John', 4}, {'Amy', 1}].

Answer for the above example if N=2 => [{'John', 8}, {'maria', 5}]

I first gave a naive solution where we iterate over the output from helper function and use a map to store the name and keep adding the cnt. then we sort it and return the top 10 pairs based on total count.
Then we discuss the time and space complexity, they he asked me if I could optimize it, then I presented a min heap priority queue solution where instead of sorting, we are using a priority queue of size N, which contains the top N talkive person so far.
I wrote the code and did dry run and then we discussed the time complexity.

Feedback: Hire (I think), HR: It was overall positve

Upvote if you find it helpful :)

Edit (March'25): I got rejected ( My offer was approved but the recruiter said they do not have the business approvals (head count), their hiring priority has changed, the rejection has nothing to do with the interview feedbacks, the feedback was positive but they can not extend an offer)

sed lyf