Google | L3 New Grad | Hyderabad, Bangalore | Feb 2022
Summary
I interviewed for an L3 New Grad Software Engineer position at Google in February 2022. The process involved a phone screen and two onsite rounds, covering Data Structures & Algorithms and a 'Googlyness' behavioral segment. Despite the interviewers not being as friendly as expected, I found the overall interview process to be well-structured and an interesting experience.
Full Experience
Phone Screening Round (45 mins): DSA
My interview started with a small introduction, and the interviewer immediately presented the problems.
-
String Replacements
I discussed different approaches with the interviewer and settled on a concatenation method. For each replacement query, I performed:string ans = s.subtr(0, start) + after + s.substr(start + before.size()); swap(ans, s);. For this to work efficiently, the queries need to be sorted in decreasing order of start index. The interviewer seemed satisfied with my approach. -
Cards
I proposed taking the input as a 3x4 matrix and traversing it in column-major format. I could use if-else statements or a set to check the validity condition. This approach was expected to be constant space and time given the fixed number of cards and attributes. -
Cards Follow up
For n number of cards, I first described the brute-force O(N^3) time complexity approach. To optimize, I suggested using two for loops to iterate over every pair of cards. With these two cards, I could construct the third valid card and check its presence in the given array using an unordered_set for O(1) average time lookups. This led to an O(N^2) time and O(N) space solution.
Onsite Round- 1 (45 mins): DSA
The interviewer jumped directly into the problems without any introductions.
-
Longest Arithmetic Sequence
I discussed my approach and provided a correct solution. The interviewer was satisfied and asked me to code it. I made some minor mistakes during coding but eventually corrected them. -
Longest Arithmetic Sequence Follow up
After coding the previous solution, the interviewer asked for the approach if the constraint (subsequent node in sequence belongs to a lower level) was removed. I discussed the revised approach and managed to code it just as the time was running out.
Onsite Round- 2 (60 mins): DSA + Googlyness
This interviewer seemed quite distant. After a grumpy introduction from their side, I introduced myself, and we moved straight to the coding question.
-
Find Unpainted Segments
I initially proposed a brute-force solution. When asked to optimize, I discussed a Segment Tree approach. The interviewer didn't seem convinced and kept pointing out perceived flaws. As time was short, I proceeded to code the Segment Tree solution, completing only the implementation within the allotted time. -
Googlyness Round
This segment involved behavioral questions:- Tell me about a situation when you went above and beyond what was expected of you?
- What would you do when you have to ship a feature tomorrow, and it starts failing for a certain group of users the day before?
Overall Experience:
I had read many interview experiences mentioning Google interviewers being friendly and helpful, but my experience was somewhat different. None of the interviewers seemed particularly friendly or welcoming. However, it's always a valuable experience to interview for such a large company. The process itself is well-organized and candidate-focused, including a preparatory session before the rounds to explain Google's expectations and flexibility for rescheduling if needed.
Interview Questions (8)
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;"
Class Replacement{
int start;
string before;
string after;
}
start: start index
before: substring that is present at the start index
after: Replace the before substring with after substring.
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 the same value, OR
b. All 3 cards have different values.
Write a function 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 a row and each attribute as a column.
For the first attribute (0th column), all cards have the same value.
For the second attribute (1st column), all attributes have different values.
For the third attribute (2nd column), all attributes have the same value.
For the 4th attribute (3rd column), all attributes have the same value.
Since for all attributes, all cards either have the same value or different values, this set is valid.
As the number of cards is 3 and the number of attributes is 4, a constant space and time solution was expected.
Given n number of cards, return 3 valid cards set if they exist. (Validity rules explained above for 'Valid Set of Cards')
Given a root of a binary tree, you need to find the length of the largest arithmetic sequence of nodes in the tree. Constraint: Each subsequent node in the sequence should belong to a lower level than the previous node. Note that the longest sequence need not start from the root.
After coding the solution for the previous problem, the interviewer asked what the solution would be if the constraint (each subsequent node in the sequence should belong to a lower level than the previous node) was removed.
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 that range and then paint all the segments in that range.
Tell me about a situation when you went above and beyond what was expected of you?
What would you do when you have to ship a feature tomorrow and it starts failing for a certain group of users the day before?
Preparation Tips
Tips for Preparation:
It's crucial to have a strong grasp of Data Structures and Algorithms. I've found that Google's questions often fall into a 'sweet spot' – slightly above typical DSA problems but not as hard as competitive programming challenges. Therefore, having some competitive programming experience can be a significant advantage.
LinkedIn and Job Search Tips:
- Try to connect with employees of the companies you're interested in. This can increase the likelihood of your profile being recommended to recruiters.
- If you're an undergraduate, make sure your resume is prominently displayed on your profile. Don't passively wait for recruiters to DM you; make it easy for them to find your information.
- Refrain from 'shitposting' (e.g., posting about solving 3 problems today). Instead, share achievements you are genuinely proud of. Excessive or low-quality posts might lead to your connections unfollowing or muting you.
- Ultimately, once a recruiter views your profile, the quality of your resume is paramount.
Beyond LinkedIn, cold emailing is also an effective way to secure interview opportunities. Find a recruiter's email, send your resume with a brief introduction, and highlight your major achievements. Persistence and consistent follow-ups are key.