Google | L3 New Grad | Hyderabad, Bangalore | Feb 2022
Status: 2022 grad, Tier-3 college
Position: Software Engineer, 2022 Start
Phone Screening Round (45 mins): DSA
Interview started with a small introduction and the interviewer sraight away jumped to the problems.
1. String Replacements
Here is the link to the problem: https://leetcode.com/problems/find-and-replace-in-string/
Class Replacement{
int start;
string before;
string after;
}
start: start index
before: substring that is present at the star index
after: Replace the before substring with after substring.
Given a string and replacement queries. Return a string after performing all the replacements.
Ex:
Input: num foo;
replacements: [
{start: 0, before: "num", after: "number"},
{start: 4, before: "foo", after: "bar"}
]
Output: "number bar;"
MyApproach:
I discussed different approached with the interviewer. Finally, I told the concantenation approach.
For every replacement query, we do
string ans = s.subtr(0, start) + after + s.substr(start+before.size());
swap(ans,s);
And finally return s. For this to work our queries need to be sorted in decreasing order of start index.
The interviewer was satisfied.
2. Cards
A card has 4 attributes (shape, size, color, shading). You have been given 3 such cards. A set of three cards is said to be valid if for each attribute either
a. All 3 cards have same value
b. All 3 cards have different value.
Write a funtions valid_set() that takes in a set of cards and returns if the set is valid.
Ex:
Input:
[
{1,1,2,3},
{1,2,2,3},
{1,3,2,3}
]
Output: True
Explanation:
Each card is represented as row and each attribute is represented as column.
For the first attribute (0th column), all cards have same value.
For second attribute(1st column), all attributes have different value.
For third attribute (2nd column), all attributes have same value.
For 4th attribute(3rd column), all attributes have same value.
For all the attributes, all cards either have same value or different value. So this set is valid.
As number of cards is 3 and number of attributes is 4, constant space and time solution was expected.
My Approach:
We cam simply take the input as a 3x4 matrix and traverse the matrix in column major format. We can use if-else statements to check the condition or we can also use set.
3. Cards Follow up
Given n number of cards, return 3 valid cards set if they exists. (Validity rules expained above)
As number of cards given is N, I was able to come up with a O(N*N) time and O(N) space solution. Please let me know if you come up with a better solution.
My Approach:
First I told the brute force approach with O(NNN) TC.
For optimizing it further, we can use two for loops for iterating over ever pair of card.
Using those two cards, try to construct the third card and check if it is present in the given arr.
We can use unordered_set to optimize the search.
Onsite Round- 1 (45 mins): DSA
The interviewer jumped directly to the problems without any introduction or any greetings.
1. Longest Arithmatic Sequence
Given a root of a binary tree and an integer, you need to find the length of the largest arithmatic sequence of nodes in the tree.
Constrain: Each subsequent node in the sequence should belong to a lower level that the previous node.
Note that the longest sequence need not start from root.
I discussed the approach and gave a correct solution. Interviewer as satisfied and he asked me to code it. I made some minor mistakes while coding.
2. Longest Arithmatic Sequence Follow up
After coding the solutions for previous problem, interviewer asked me what would be the solution if the constrain is removed.
Discussed the approach and he asked me to code it. Finished the code very close to the end time.
Onsite Round- 2 (60 mins): DSA + Googlyness
The interviewer seemed really off, dont know why. He gave his introduction very grumpily and asked me to give my introduction. Then he jumped into the coding question.
1. Find unpainted segments
Given a series of segments of length 1. Initially all of the segments are unpainted. Given queries of the form [left, right], return the number of unpainted segments in the range and then paint all the segments in that range.
I gave the brute force solution. Interviewer asked me to optimize it. I discussed a Segment Tree approach. he want convinced and kept telling me something is wrong. He seemed frustracted. Finally, as the time was running out, he asked me to code it. I could only write the segment tree code in the time.
2. Googlyness Round
a. Tell me about a situation when you went above and beyond od what was expected of you?
b. What would you do when you have to ship a feature tomorrow and it starts failing for certain group of users the day before?
Result / Feedback : Awaited......
Overall Experience:
I have read many interview experiences saying that Google interviewers are very friendly and helpful. Well, my experience was slightly on the opposite side. None of the interviewer seemed friendly and welcoming. But its always a nice experience to interview for such a big company. The process definitely takes care of the candidate and its need. A session is scheduled before the rounds to let you know what Google expects from you. You can also reshedule the interviews is there is some emergency.
Tips:
Have a good hold on Data Structure and algorithms. I have realised that Google asks questions that fall in a sweet spot above the level of normal DSA questions and below the level of hard Competitive Programming questions. So having a bit of CP experience is always a plus.