Status: 1.5 YOE, B.S CS @ Average public school
Position: Software Engineer (L3) at Google
Location: Austin, TX
Date: Dec 2nd 2021

This was my first time interviewing at any FAANG company. I applied to the role through the Google careers page and got an email from a recruiter about a month later.

For preparation I studied for about a month with a focus on patterns using Leetcode, AlgoMonster, and Sean Prashads Leetcode patterns website. I did ~100 problems, mostly mediums and easies. I probably did around 5 hards in total.

Phone Interview:

• Given an array which can contain duplicates and a given number, write a method which returns the positions of the given number in the array as if the input array was sorted.

  Example: Input: [33, 22, 33, 11, 22] 22
  Output: [1, 2]

• Follow up: What if the number is not provided? Return the indices of the element which appears the most times in the array (as if it was sorted).

  Example: Input: [33, 44, 33, 11, 22]
  Output: [2, 3]

  I was able to brute force the problem with a sort function, then got an O(n) one pass solution. I wasn't able to think up of a solution (or frankly even understand the problem) for the follow up before time ran out, but seems it was good enough to pass the phone screen.

  About a week later I was told I passed the phone screen and scheduled my onsite for 2 weeks from that day.

Onsite:

Round 1 - Behavioral:

• Standard behavioral questions, questions about projects, how I work on a team, how I embody leadership and Googlyness qualities. Nothing too hard

Round 2 - Technical

• You are designing a skyscraper but are very superstitous about the number 4 so you do not include floors with 4 in it. Unfortunately, you've forgotten how many floors are in your building. Given the number of the top floor, how many floors are in the building

  I was able to get the O(n^2) solution that used modulo and checked each number from 1 - n to see if it contained a 4, but wasn't able to get the optimal solution. The interviewer was very helpful and reassuring but the hints he were giving were just not clicking in my head at all. This was the round I definitely messed up the worst on since I didn't even code out the brute force solution. I had an hour break after this round and that gave me some time to be demoralized for a bit :)

Round 3 - Technical

• Remove leaves from a tree, Print out the ordering as you remove them

• Follow up: Remove leaves from a tree. If the parent becomes a leaf, remove it before removing any other leaves *

• Follow up: Remove leaves from a tree. If the parent becomes a leaf, remove the other leaves before removing it

  This question didnt actually require removing the leaves from the tree, but rather was just a disguised tree traversal. The main question was just a reverse Level order traversal and the first follow up was a post order traversal if im not mistaken. Didn't get enough time to do the second followup. The interviewer here was pretty quiet and let me decide how I wanted to implement pretty much everything. Was pretty confident that I passed this round.

Round 4 - Technical

• Design a Cord Data structure that has two types of nodes:

  • Leaf: contains string data and length
  • Internal: contains length and pointers to the left and right children (Children can be Leafs or Internals)

• Follow up: Write a function that takes a Cord root and an index n and returns the nth character in the cord object

  Initially I struggled with this question, as the data structure design part of the question threw me off. I messed up some of the class design for the data structure and the interviewer had to clairify so I could fix it. The second part of the question I got a little faster, but I finished the code in the last minute. The interviewer said it looked okay, but im not too sure if thats because it was correct or if time was up. I feel this one could have gone either way

Round 5 - Technical:

• A task at a data center requires a constant number of CPUs for a constant duration. A task can be represented as follows:

    class Task {
    	public int startTime;
    	public int duration;
    	public int cpus;
    }

  We have a limited number of CPUs so we must ensure we do not use more CPUs than available. Design an algorithm to verify if a given schedule of tasks is valid or not. Your solution should return false if the schedule exceeds the CPUs limit at any point in time, otherwise it returns true.

  I had the idea to calculate end time based on the duration and start time and then replace duration with the newly calculated end time. Then I tried to find overlapping intervals where PCs were used and tried to calculate if the number used was above the max. I was confident this worked until the interviewer pointed out a counter example. I was able to scramble together another solution which I though would work, but I ran out of time on this one as well so I wasn't sure if that was correct either.

This onsite was around christmas time so all the feedback and interviews results came slowly. About a month after interviewing, I got a standard rejection from the recruiter. I of course wasn't pleased, but wasn't exactly surprised either. Though I did some quality studying, my performance was definitely not the best. Round 2 went bad and Round 4 and 5 seemed to be on the fence. However, the prep for this interview alone raised my technical interviewing skills by so much that I can say it was definetly worth my time. I guess I'll try again in a year or so. End of the day, very thankful to have this chance that many try very hard to get.