Status: New grad(2017 - 2021), Tier-3 college
Position: L3
Location: Banglore/Hyderabad

I was contacted by a Google recruiter in last week of July saying that they liked my coding profiles and asked me if i am interested to interview with them, to which i said yes.

About me: I am a competitive programmer & i participates regularly on Codeforces, Atcoder and Google Kickstarts.

Phone round with recrutier:

• After that the recrutier scheduled a phone round in second week of August, in which she asked questions similiar to this post and i passed it.
  

Phone screen:

• This was scheduled in first week of September and i was asked leetcode jump game - iv which i solved quickly. I passed this round with positive feedback. It took around a week to get the feedback and another one more week to schedule onsite(virtual).

After phone there were going to be 3 Virtual Onsite coding round and if their feedback was positive then Googleyness & 1 more coding round was going to happen.

My first three Virtual Onsite were in first week of October.

Round 1:

• In this round i was asked a constructive problem. It goes like this:
  Let's say we have a permutation P of length n(n = 5 here) = [3, 5, 1, 4, 2]
  Now we delete elements from this permutation P from 1 to n in order and write their index to
  another array Q. When an element is deleted, remaining elements are shifted to left by 1.
  Initial: P = [3, 5, 1, 4, 2], Q = []
  delete 1, P = [3, 5, 4, 2], Q = [3] (index of 1 was 3 so write 3(bcz it's index of 1) in Q)
  delete 2, P = [3, 5, 4], Q = [3, 4]
  delete 1, P = [5, 4], Q = [3,4,1]
  delete 1, P = [5], Q = [3, 4, 1, 2]
  delete 1, P = [], Q = [3, 4, 1, 2, 1]

  Now given Q, we have to restore P.

  I gave a Nlog^N solution using fenwick tree and binary search.
  He asked me a follow up in which i have to optimize space.

Round 2:
- I was asked a simple dfs on grid and dijkstra on grid with some constraints on movements.

Round 3:
1) I was asked LCA of binary tree.
2) in follow up we are also given parent pointers of binary tree and we have to optimize space.

It took exactly 2 weeks to get feedback and recruiter said it mixed(positive + negative).
Feedback: Solutions were not optimal and code structure should be improved but they were
moving forward with remaining two interviews.
Googleyness and remaining 1 coding round was scheduled after a week.

Round 4(Googleness & leadership):
1) suppose you want to build a new product, how will you make sure that it's customers do not
leave it.(assume they have purchased it and using it and then we have to make sure they
don't leave).
2) If your team and some other team is working on same project and later you came to know
that some other team is also working, (it will be duplicate work and efforts & time) what
will you do?
3) If you planned a trip and some coworkers are not going/interested, how will you
handle it?
4) Tell me about a time when you handled multiple tasks?

Round 5:
In this round i was asked a probability question, medium-hard(atleast imo because i s**ks
at probability). I was able to solve it and code it. It took 45 minutes and then he asked me a
follow up and i answered & he asked details about my solution but didn't told me if my sol
is correct or not but imo he seems satisfied.

problem:
Consider a class as a grid of size N * M. Students pass notes to their adjacent students.
Given p = probability of a student getting caught when passing notes to a adjacent 
student in same row.
q = probability of a student getting caught when passing notes to a adjacent 
student in same column.
Here p and q are given for first row. as we go down the row the probability p and q
reduce by 2.
let p = 0.5, q = 0.2;
in row 1, p = 0.5, q = 0.2
in row 2, p = 0.5/2, q = 0.2/2
in row 3, p = (0.5/2)/2, q = (0.2/2)/2
Now we are given a path (r1, c1) -> (r2, c2) ... (rk, ck) (Note:  any two 
consecutive cells in the path are adjacent(left/right/up/down)).
We have to calculate the probability of not getting caught if we start from 
(r1, c1) and end at (rk, ck) following the path given.
Interviewer didn't explained any sample and asked me to treat it as a math problem
instead of a coding problem and then solve it & later think about code.

Follow up: if we are given coordinates of startting and ending cell instead of path then how 
will you calculate the maximum probability to reach (rk, ck) from (r1, c1) using only
Left, RIght, Up, Down moves.

After a week i received the overall feedback(via phone call with recruiter):
It's a reject. 
Feedback: 1) solutions should have been more optimal.
She even said that all my interviewers gave this feedback that my solutions 
were not optimal, which i disagree because except first round in which my 
solution was Nlog^2N, in all other rounds my solutions were optimal
(atleast from an interview perspective) and i told her that it's not the 
case except 1st interview and asked her to be more specific, then 
she said she can't share this specifically to a particular interview
and she can tell only overall feedback, so i said ok. 
2)your coding practices are	not good(i am not satisfied about this coding 
practice feedback because i use	C++ and never use macros even in
competitive programming and use proper	indentation, i follow [this](http://users.csc.calpoly.edu/~cstaley/General/CStyle.htm) format in my codes). 
i will try remembring the codes which i wrote and try to find what went wrong.

Recruiter told me that i can reapply after 9 months of cooldown period. 

Takeaways: Google wants to hire the best so try to give as optimal solution as possible.