I recently gave google interviews for bangalore/Hyderabad opennings and was asked following questions:
Phone Interview:
Design LRU Cache : I used Ordered Dictionary in Python to do the implementations. The feedback was good
Onsite Interviews:
Round 1: Given a list of people each with a preference of activites from the set [A, B, C, D, E ] I had to divide them in team of 5 people such that maximum people got their preferences. Getting preferrence was not a requirement but a good to be in situation:
For implementation I divided people into 5 buckets and then assigned the people for each team for each activity.
Feedback: Need to be more logical, code readability not good and the edge cases not covered,( Though I dry ran on the edge cases and examples shared by the interviewer )
Round 2: Given a list of cafes and the starting point for each friend and the list of adjacent points we need to return the cafe that minimizes the maximum distance any friend has to travel to reach the cafe
My solution: Worked on the multi source bfs approach coded it , shared the output and dry ran on the examples and edge cases: Feedback for this round was good
Round 3: You are given a dump of log with timestamp and name of people who became friends
timestamp1, p1, p2
timestamp2, p2, p3
timestamp3, p3, p4
timsetamp4, p5, p1
you need to tell the timestamp when everyone became friends:
My solution: Treat the logs as an edge for the graphs with timestamps as the weight and run union find to get the timestamp where everyone becomes friend I wasn't able to optimise it beyond the usual implementation of union find.
Wrote the solution dry ran on the example shared had few minutes told the interviewer he can ask the follow up question if he wants. The interviewer asked about the 6 link problem. Basically the theory that states that any 2 people will be connected with each other between 6 links. How would I test this theory.
I told him if we were checking on two people we would use BFS if we want to test on everyone we can test using multisource BFS.
Feedback: Negative was told that I need to be more structured, logical and there was no time for the follow up question.