So, I appeared the most hyped Google Interviews and these are not what I expected.

Phone Screen [Elimination Round]

• You have a very very big number 2123470299109372 and a given integer k [let's say k=6], you need to find largest k digit number which is a subsequence of the original number. ans=999372

  • Similar to this, where any of the array is empty

  • Or may be this, but reverse

Gave a very lame solution at first (digit dp), then while coding realized that better solution exists. But interviewer didn't listen may be or somewhat communication issue from my end, so ended up optimizing digit dp.

At last I explained what I was trying to do with the montotic stack approach (the better one) and interviwer also agreed yeah this would've been better. Anyways, Interviewer was very smart so he got this quickly and interview ended on a somewhat normal to good note.

Recruiter called after a week, and told You have Cleared, Prepare for Onsite. But I was like why and how I cleared this?

Anyways Let's move on....

Onsite : Guaranteed 4 rounds (also its not actually 'onsite', they should change the name)

Onsite 1

Couldn't find any similar question link. Let me know if there is any.

• You are given the shift timings of several waiters in a restaurant. Each waiter has a shift start time, and a shift end time. Your task is to find all non-overlapping intervals during which the set of waiters on duty remains the same.

Input

Output

• Solution I gave a very basic one, which runs in $O(N^2)$ . Interviwer didn't ask any optimization, I also didn't thought about it. After interview I solved the question again with different approach. Solved in $O(N\log N)$. Anyways followups were -
  • What if same person appears twice or more? Chnage minimal code to accomodate this.
  • TC / SC and a full dry run

Onsite 2

• Design, Implement and Test a Tree, which is built on the following rules

  • You are given a list of strings: ["apple", "app", "bat", "batter", "battle", "cat"]

  • The root of the tree is an empty string.

  • For any string in the list, if there exists another string that is a prefix of it, then the shorter string becomes the parent node of the longer string. If there are multiple possible parents, choose the longest prefix as the parent.

  • For example, "app" is a prefix of "apple", so "app" becomes the parent of "apple".

Your task is to build and represent this tree structure.

           ""
         / | \
      app bat cat
      /   /  \
 apple  batter battle

• I propsed two solutions, one using map so that string to Node mapping I can find quickly. The other one using Trie
• No respose from interviewer, so I decided to take the easier route, (the map). My thought was Trie would've taken longer time to implement.
• So question has 3 parts Desgin, Implement and Test.
  • Design was mostly the discussion, what I would choose, how I would solve, time complexity etc.
  • Implement was the coding part. Interviewer pointed out some improvements, accomodated those
  • Test was new for me. This was not dry run. I had to write some test cases and what is the expectation from the test. Found out some normal cases, some breaking edge cases and presented those.
• And Interview Done.

Onsite 3

• It was a real life question. The Android pattern lock, if you scaled it to have $N\ast M$ dots [N rows and M cols], how many different patterns can be created. Rules -
  • At least 2 dots should be connected.
  • Dots can be connected in 4 directions - left, right, top and bottom
  • One dot can be used once.
  • Pattern can be of any length.
• Problem is simple, use backtrack and visited grid. Gave the approach, solved it easily and also had to do dry run. Recursive dru run is hard :(
  Follow ups were -
  • Next banger comes is Give me an estimate of how big will this final answer be?. Gave a rough estimate by visualizing the recursive tree, but its very hard to give an answer. Branches can end at any length, but he seems satisfied with the approach I told to calculate to estimation.
  • Next If I enable 8 directional movement, (means corners are now available), how will you change your code?. I changed the direction array. Also give estimation for this, gave similar way.
  • Next If now user can move from any point in grid to any other point in grid (no need of neighbours), how much will be estimation?. This was easy. It can be easily calculated using PnC.
• Interview Done

G&L Round

• 5-6 questions were asked. Got grinded very hard in the last 2 questions. STAR method is needed to answer these questions. This is a good resouce for this round.

Verdict: Whatever it is, just declare it fast

• Interviews itself took 3-4 months. At this point, my interest is gone for L3
• Experience: 2years
• Used to be an Expert in CF and Guardian in LC, before these GPT kids came to contest arena.
• Already in a MNC where current_base >= highest_possible_base_of_google_L3

EDIT

Verdict: Cracked the Interviews with all positive

They really declared it fast, I didn't expect this too.
Awaiting team match now

EDIT 2: Got offer

Offer Details

Note:

Those who thinks Google Interview is just about DSA, please share them this post. Yes there are questions from monotonic stack or Trie, but Pnc, answer estimation, design and test etc are also being asked. Go spam your influencer Bhaiyya's and Didi's to also teach about these.