Google L3 TPS And Onsite Interview Experience.

Anonymous User

1741

Application Process-

Q1 -> (Don't Remember Much) Given two dice A,B, return how many times dice A wins, where dice A will win when the number shown on the dice A is strictly greater than that on dice B i.e say A=[2,4,4] and B=[1,2,3], then the number of A wins is 2-> (1) 4-> (1,2,3) 4-> (1,2,3) therefore => 7 wins. A and B both are sorted
Approach: First thought of using a upper/lower bound approach, but interviewer suggested something to do in O(n) so, used a stack, that stores the elements of B and for every ith element of A, pop the elements out whichever are greater than A's ith element, the current stack size would be added to the final answer.
Later I suggested to go with a two pointer approach.
Follow-up: Given K dices, with N faces, determine the dice with maximum win.
Suggested to use a priority_queue where will be storing the dice values and its id (index of dice) and then storing the dice values in hash map (to check for duplicates), and using these values, we can check number of wins for each dice.

Got a call from a recruiter within 2 days, but somehow missed it. Got another call after a week for onsite availability
ONSITE 1 (45 min): Given two source A, B and one destination D in a unweighted graph. Determine the number of minimum distinct edges that both A and B will cover to reach D

Interviewer wasn't interested in the brute force, suggested to come with optimised.
Suggested some approaches, but interviewer wasn't satisfied. He gave me hints. But I wasn't able to grasp. He wrote a formula, that to find the minimum edges, we can calculate the edges from A,B,D to every ith node and the minimum edges would be A-i+B-i+D-i (A-i => edges from A to i).
Then I suggested to use BFS to calculate the distance. He then asked me to code. I coded that and interviewer was okay with the code.

ONSITE 2 (45 min): Given a sparse binary array and an api that returns true if there exits atleast single one between the (i,j) i.e query(i,j) (query=> API) will return true if there is a single one between i and j. Determine the positions of 1 in the array.

Got nervous as the interview was a little strict, took 10 mins to realise that its a binary search problem. Suggested to use that approach and use the api for query(low,mid) and query(mid+1,high) and then recurse through the function if left is true and/or right is true.
Messed up at the Time complexity. The interviewer wasn't giving me time and at first I said its log(n), but then I realised, that if both left and right are true, then we will recurse through both.
After many discussion, Interviewer said that it would be KlogN, K=> number of Ones. I realised, that but the interviewer confused me a lot and I was only getting nervous

ONSITE 3 (45 min): Given M sequence of numbers, create one sequence where every element follows the same order as present in every sequence. If its not possible to create a unique sequence, return {}

Was thinking of approaches, but then the interviewer hinted that its something related to dependency. Then i realised its topological sorting question. I coded my solution and the interviewer was satisfied.
Q2: Given an array of start time for N processes that have the same duration of completion. Given M CPUs, determine the minimum time when all processes will be completed.
Suggested an binary search approach, to determine the lower bound for the process start time when no CPU is available. This number will tell us when the process would start. BUT I messed up here, I didn't realise that, if the lower bound is not zero (index) then the index CPUs would be freed up by then, and the process would start from its expected start time
Didn't got much time to discuss, but coded the solution in 5-8 minutes, and then later realised my mistake ;-)

Its been almost 2 weeks, and I haven't heard any feedback from the Recruiter yet. Can anyone suggest what should I do in this case?

Comments (9)