I am a tier-1 college graduate with 1.5yrs of work-ex. A google recruiter reached out to me. They scheduled my phone-interview a month from the call. Although later, my recruiter pushed for getting me directly to the onsite-interviews, which came through. All my onsite interviews( 4 technical + one googley
ness round) were scheduled on 5 consecutive days.

Preparation : I had started my preparations in 3 months before the interview. By the time of the interviews, i had done roughly 250 questions on Leetcode( 50 - easy , 140-medium , 60-hard). Apart from this, i went through various previous interview experiences. One pro-tip would be to take Leetcode premium and practice company-specific questions. Though none of the interview questions were questions I had seen before(except for one question), company-specific practice gave me a good idea about what difficulty to expect.

Expectations from the interviewer: In onsite interviews, the expectation is to answer two medium questions or one hard question, in order to get a 'strong-hire' feedback. however, I am not the authority to give an objectively correct answer to this and I speak solely from my experience.
You are also judged on speed, communication of idea, code-readabililty, time/space complexity.

Note: I will not be adding solution to the questions in the post, so that one can attempt them on their own. However, please feel free to ask for solutions in the comments to compare solutions :)

Interview Experience :

1. First onsite-interview Question(one medium):
   Given two arrays appointmentTime and appointmentDuration and int numRooms. Each room has an id ranging from 0...n-1. Find the room that gets most appointments if a room can have only one appointment at a time, and each appointment is assigned an available room with the smallest room ID.
   Experience: I was able to come up with the optimal solution in 10min, although i spent way too much time explaining my approach and writing pseudo-code(this is the feedback that i got). Eventually finished coding and discussing the code in 40ish minutes but there wasn't enough time to discuss the second question the interviewer had in mind.

2. Second onsite-interview Question(one hard)
   There is a highway of length m and has n+1 lanes. You are a frog trying to get across the highway. You can either move left, right, up or stay in your current position for 1 unit of time. There are k cars on the highway, {laneNumber, initialPosition, velocity} given. The cars can move in either directions with unit speed. Find the minimum time the frog will take to cross the highway. Also find the worst-case time complexity.
   Assume the initial lane and last lane are empty
   Your frog starts from lane 0 and position x.
   The cars can have either +1 or -1 velocity. Once the car leaves the frame, they don't return.
   Experience: This was my strongest interview. I was able to come up with the optimal solution within 15min and didn't waste much time writing pseudocode, and headed straight to writing the main code.
   Finding the worst case time-complexity was non-trivial and took some discussion before i could reach the right answer. I was done writing the code and discussing the solution within 40min. Interviewer didn't have another question to ask, so ended the interview early. Got an overall positive feedback, although the interviewer noted that I could have named the variables better( yes, you are also judged on the basis of code-readability).

3. Third onsite-interview Questions(one easy , one hard Q)
   Q1. You are given an array of commit IDs. They are in chronological order. There is one bad-commit in the order that renders all subsequent commits bad. You have a isBad(commit#) function that tells if a particular commit is bad or not. You have to find the first bad commit.
   Same as First Bad Version question on leetcode.
   Q2. A question very similar to word-break 2.
   Experience: This was the easiest of the rounds. I had done questions similar to these and was able to code out both solutions within the time given.

4. Fourth onsite-interview Question (one hard question)
   You are sitting on a computer(Main-computer) on a network. The network has a few computers, connected directly or indirectly to you. Each computer has a 'unique' string identifying it( like MAC address). For simplicity you can assume these MAC address are from A-Z. The goal is to find Total number of computers on the network. You cannot access other computers on the network, but you can send a program on the network that EACH computer on the network will install. This program will have a send(string) function and a recieve() function. The send function will send the string passed to the function to all its IMMEDIATE neighbours( it's handled implicitly - no information about neighbours is given). The 'recieve' function takes the string sent from its immediate neighbours. Write a 'recieve' function such that after a while, the Main-computer can print out the total number of computer on the network.

• Somethings i realised after discussing with the interviewer:
  • Note that each computer gets identical send() and recieve() functions.
  • Also, the user has access to the send() function only on the main-computer.
  • Also, there is no global memory that can be accessed by all computers, but each program can access the local memory of the computer it is running on.
  • Also since there are a lot of async calls happening, assume a mutex lock on this memory while in use.
    I realise i am not able to word it in the most lucid way possible, so feel free to ask follow-up questions.
    Experience: This was easily the most difficult question that was asked to me, simply for the fact that it is less of a DSA question and more of a puzzle. I spent majority of the time trying to understand as the question is a little vague. After discussing a few different approaches and their shortcoming, i figured out a way to solve it. Was just barely able to code it out. Didn't have the time to discuss time-complexity, but i don't think the interviewer was looking to discuss that anyway. The interview told me my solution was one of the acceptable solutions. Hopefully someone in the comment will figure out the best way to do this question:)

Verdict: Two weeks after my interviews(including one googliness round) got over, I got an offer and got a team matched.

Hopefully my experience will help someone :) I would be more than happy to answer any questions regarding my interview experience or preparations.