Google | L4 Interview | India

My Google Interview Experience

Background

I have a total experience of 3.9 yrs with Microsoft after passing out from an IIT.

I received a call from Google recruiter on April 13th who saw my profile on LinkedIn and discussed the interview process. After a day, he mailed me saying that I will be handed over to another recruiter. The second recruiter called me and informed that a particular Hiring manager liked my profile and that they want to proceed without phone screen. She wanted to schedule the onsite interviews in the first week of May but I pushed back and asked at least a month time for preparation.

Onsite interview 1 - May 19th

Interviewer is from Chicago from Google cloud team

10min - intro and asked me “Explain one of the technical challenge you faced at work”.
10min - Interviewer explaining the question
25min - Discussing the algorithm + coding + follow ups

/*
Assume that a CircularArray data structure is available for your use, an array-like data structure with fixed capacity.  It provides the following functions.
pushFront(E)/pushBack(E): Push the given element E to the front/back of the instance in O(1).
popFront()/popBack(): Remove the front/back element of the instance and return to the caller in O(1).
insert(index, E): Insert the given element E to the specified index.
set(index, E): Overwrite the element at the specified index with the given element E in O(1).
size()/capacity(): Fetch the current/maximum number of elements stored in the instance.
isFull(): Return true if the instance is full, false otherwise.
get(index): Fetch the value at the specified index in O(1).

/

/*
CircularArraysDeque<int> d {
data = [[0, 1], [2, 3, 4, 5, 6], [6, 7, 8, 9,10], [11, 12]]
circularArrayCapacity = 5
};
d.insert(8, 100);
Answer - data = [[0, 1], [2, 3, 4, 5, 6], [100, 6, 7, 8, 9], [10, 11, 12]]

*/

template <typename TypeName>
class CircularArraysDeque {
private:
// Each element is a CircularArray of fixed capacity.
// All elements are filled to capacity except for the first and the last which need not be full.
std::vector<CircularArray<TypeName>> data;
// The capacity of each of the arrays within data.
int circularArrayCapacity;
public:
// Assume get/push/pop/size functions of a deque already implemented.
void insert(int index, TypeName element) {
}
};

Questions asked

1. Implement this function to provide indexed insertion (handling edge cases properly is imp)
2. Follow up 1 - Time complexity of the insert as a function of C (circularArrayCapacity) and n (total number of elements in the deque)
   Ans. O(C+n/C)
3. Follow up 2 - For a given n(total number of elements in deque) what value of C would minimise the TimeComplexity.
   Ans. C=sqrt(n)

Onsite interview 2 - May 20th

Interviewer from Boston, has 20 yrs experience, likes to talk too much, was disturbing a lot during interview.

Question

You are given N movies and similar movies dataset. Each movie has a rating. Given a target movie T and integer K, return top K rated movies similar to T. (paraphrased as the original question was bigger)

Eg.
Ratings:
A:6
B:7
C:8
D:9

Similarity dataset :
A is similar to B
B is similar to C
Ans - Top1 movie similar to A is C based on the rating.
A is similar to B, C but C has higher rating.

Onsite interview 3 - May 21th

Interviewer from Pittsburgh, has 11 years of experience, typed the question slowly which effectively gave me only 30min to solve.

Question -
A standard deck cards
Rank = A, 2,3,4,.. 10, J,Q, K
Suit = H, S, D, C
Every card is represented by = {Rank, Suit}
eg. "AH", "9C"

A Valid set - if it satisfies one of the 2 properties -
Property 1 - The set has 3 or more cards and they all have the same rank
ex. {"2C", "2H", "2S"}, "2C", "2H", "2S","2D"}
non example - {"2C", "2H"}, {"2C", "2H", "2S", "3D"}

Property 2 - The set has 3 or more cards with the same suit and in subsequent increasing order
ex. {"AC", "2C", "3C"}, {"AC", "2C", "3C","4C","5C"}
non ex: {"AC","2C","4C"}

Given a list of N cards, Write a function to group as many cards as possible using the properties so as to minimise the number of cards left ungrouped
Ex. f({"AC", "2C", "3C", "4C", "3S", "3H"}}) - minimum left ungrouped cards are - {3S,3H}
Possible groups - {"AC", "2C", "3C"} {"AC", "2C", "3C","4C"} etc.

Let me know the solution what you guys have for this problem.

Onsite interview 4 - Googlyness on May 23th

Interviewer from India.
Questions were around Conflict management, do you prefer to work in a team or silos, leadership qualities etc.

Feedback as per recruiter

Round 1 - positive
Round 2 - mixed
Round 3 - negative
Round 4 - positive
She didn't specify it in terms of SH, H, etc., but based on my evaluation, it would be SH, LH, LNH, SH/H. She mentioned that my profile will be moved forward for team matching. Hoping for the best to happen.