My Google Interview Experience
Background -
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 atleast 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 -
-
Implement this function to provide indexed insertion (handling edge cases properly is imp)
-
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)
- 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 teh 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.