Status : Undergraduate
Position : New Graduate SDE at Google
Experience : 0 years
Location : Tokyo
Date : May 2020-June 2020
Telephonic Interview :
I think it was a bit easy Question,
A: ('a', 2), ('b', 2), ('a', 2) => aabbaa
B: ('a', 3), ('b', 3) => aaabbb
=> Returns 3, as three characters are different
=> you can assume the strings in the right side are always the same length.
Took, 40mins to solve this problem and interviewer was little happy about how I solved the problem using 2 pointers and discussed all the corner cases too.
Then we discussed a little about what he works at Google.
Virtual On-Site :
Round 1 :
Interviewer wasn't the most happiest person, wasn't even talking properly, was busy in something else only and was having trouble conversing in English.
Question: You are given a board(2D Array) and you have to find whether or not the board has a Effort less than or equal to given effort ( Effort = Maximum Difference of 2 adjacent terms in a path from (0,0) to (n-1,n-1));
I used simple DFS approach with memoization to solve this problem,
Follow up: Can you find the minimum effort in given board?
I used DFS to solve, then he said can we use previously made function to solve this problem?
I quoted Binary Search Approach.
He was unhappy at last don't know why discussed everything and covered all corner cases with dry runs too.
Round 2 :
Got Lucky this time Interviewer was a very beautiful girl, don't know about her but I was very happy.
Question:
Chaining Broadcast Signals
We have a broadcast system with some powered-on routers. When a router receives a message, it broadcasts the same message to all other routers within its wireless range (10 feet). Then, that router shuts down, and can no longer send or receive messages. Given a list of router coordinates, tell me whether Router X can send this signal to Router Y.
We had to check if it possible to send a signal from one router to other.
Constraint: We dont care about whether or not we are reaching destination just take route from one to other only to the nearest one.
Solved with DFS+memoization, She was happy about the approach and told me to improve the Space Complexity and I did the required improvements,
She then asked to make more improvement and I did everything.
Round 3 :
Super Friendly Interviewer and I thought this is my chance to impress.
And then comes the Question
Given N points on an axis x1, x2, x3, …, xN. Each point i has a value p_i. Find a pair (i, j) that maximize p_i + p_j + distance(i,j).
x1 < x2 < x3< …< xN
I dont know what happened to me this was supposed to be Bread and Butter for me but I had hard time dont know why?
Wasn't able to solve the Question on my own! After some Hints I was able to come up with a optimal approach !
I think this is the interview that lead to rejection Horrible.
Round 4 :
This guy straight away jumped onto the Coding part.
Question 1:
Given a unsigned integer find out the value of bits from start to end setbits.
N = 0101101100111...1
0123456789
(start, end) = (2, 5)
ret = 0...00110 6
Did some mistakes and fixed them later while discussing the code.
Follow Up: What all test cases will you make to test this algorithm?
I said, will do obvious test first , then work on all the corner cases including 0,1, Max and Min
Question 2:
Obj[] arr (All objects are unique)
boolean compare(Obj o1, Obj o2);
true if o1 > o2
false if o2 > o1
Given an object array and a compare function which gives above results. Compare function is very expensive. What is the minimum number of calls required to find the second largest object?
Some Words :
First experience of being interviewed was awesome but Acceptance would have made the game! Still I am happy to have a lesson that you have to not just be better of yourself but also get better from others not just for interviews .
PS: Sorry for bad English.