I interviewed for an L4 position at Google last year and wanted to share my experience.
Company: Google
Role: Software Engineer III (L4)
Location: Bangalore, India
Pre-Screen
Problem:
You are given multiple rectangular cakes placed on a table. Each cake is defined by two coordinates: the bottom-left corner and the top-right corner. Imagine drawing a horizontal line (parallel to the x-axis) across the entire table. Your goal is to determine the y-coordinate of this line such that the total area of cake above the line is exactly equal to the total area of cake below it.
Constraints:
N (number of cakes) = 10⁵
X, Y (coordinates) = Large integers, up to 10¹⁰⁰
Examples:
Input: [(1,1), (5,5)]
Output: y = 3
Input: [(1,1), (5,4)], [(2,5), (6,8)]
Output: y = 4
Input: [(1,1), (5,3)], [(2,4), (6,7)], [(7,3), (9,5)]
Output: y = 4.33
Solution:
I solved this problem using binary search on the y-axis. However, I believe there may be a more efficient approach.
Technical Round 1
Problem:
You are given an N × M grid representing students in a classroom. During an exam, some students attempt to pass a note to each other. The teacher monitors the students, and the probability of getting caught depends on the direction and row in which the note is passed. The detection probabilities for adjacent student passes are as follows:
Top row horizontal pass: 90% chance of getting caught (10% success rate).
Vertical pass from top row to second row: 50% chance of getting caught (50% success rate).
Second row horizontal pass: 45% chance of getting caught (55% success rate).
Vertical pass from second row to third row: 25% chance of getting caught (75% success rate).
Third row horizontal pass: 22.5% chance of getting caught (77.5% success rate).
(And so on, with probabilities decreasing further down the rows.)
S -90% - S -90% - S -90% - S - - - M
| | | |
50% 50% 50% 50%
| | | |
S -45% - S -45% - S -45% - S - - - M
| | | |
25% 25% 25% 25%
| | | |
S - 22.5% - S -22.5% - S -22.5% - S - - - M
| | | |
12.5% 12.5% 12.5% 12.5%
| | | |
S -11.25% - S -11.25% - S -11.25% - S - - - M
| | | |
| | | |
N N N NYou are given a specific path (i.e., a sequence of students through which the note is passed). Your task is to compute the overall probability that the note successfully reaches the destination student M without being caught.
The overall probability is the product of the success rates (i.e., 1 - detection probability) for each step in the path.
Examples:
Input: Path: (1,1) → (1,2) → (2,2) → (3,2)
Output: 0.1 × 0.5 × 0.75
Input: Path: (1,1) → (1,2) → (1,3) → (2,3) → (3,3)
Output: 0.1 × 0.1 × 0.5 × 0.75
Input: Path: (1,1) → (2,1) → (3,1) → (3,2) → (3,3)
Output: 0.5 × 0.75 × 0.775 × 0.775
Follow-ups:
- Each student has a sneakiness score. The probability of getting caught is now a function of this score:
- Sneakiness = 1: Base detection probability remains unchanged
- Sneakiness = 0.5: Detection probability increases to the midpoint between the base and twice the base probability.
- Sneakiness = 0: Detection probability doubles.
- Find the safest path (i.e., the path with the highest probability of successfully passing the note).
Solution:
For the first two problems, I iterated through the given path and computed the probability by multiplying the success probabilities at each step.
For the third problem, I proposed using Dijkstra’s algorithm to find the path with the highest probability.
Technical Round 2
Question 1:
You are given a list of ordered sublists, where each sublist represents a sequence of integers that must appear in the same relative order in the final merged list. Your task is to merge these sublists into a single ordered list while preserving the relative order of elements within each sublist.
If multiple valid orderings exist, return any one of them. If merging is impossible due to conflicting constraints, return an empty list.
Examples:
Input: [[1, 2], [2, 3], [3, 4]]
Output: [1, 2, 3, 4]
Input: [[5, 6, 7], [7, 8], [8, 9, 10]]
Output: [5, 6, 7, 8, 9, 10]
Input: [[1, 2], [3, 4], [5, 6]]
Output: [1, 2, 3, 4, 5, 6]
Input: [[1, 2], [3, 1], [2, 4]]
Output: [3, 1, 2, 4]
Invalid Case:
Input: [[1, 2], [3, 1], [2, 4], [4, 3]]
Output: [] (Contradiction: [4 → 3] conflicts with [3 → 1 → 2 → 4]).
Solution:
This is a variation of topological sorting, similar to Leetcode - Course Schedule II.
Question 2:
A variation of Leetcode - Parse Lisp Expression where we need to evaluate an expression.
An expression can contain numbers and the operations ADD, MULT, or SUB.
Examples:
Input: "MULT(4,ADD(1,SUB(10,3)))"
Output: 32
Input: "ADD(1,MULT(2,3))"
Output: 7
Input: "SUB(10,3)"
Output: 7
Solution:
I proposed using two stacks—one for numbers and one for operators—but couldn't fully implement it within the given time.
Technical Round 3
Question:
Design a matchmaking system for an online game (e.g., chess) that pairs players with opponents whose ratings are closest to their own. The system should return the best available match within a rating difference of 100.
Solution:
I proposed using a Binary Search Tree (BST) to efficiently store and manage players waiting for a match. Specifically, I used a TreeSet to maintain player ratings and utilized the ceiling() and floor() methods to find the closest available match within the allowed rating range.
Googliness Round
I was asked behavioral questions such as:
- A time when you dealt with a difficult team member.
- A situation where your leadership approach conflicted with company goals.
- The most challenging project you worked on and how you overcame obstacles.
- How you improved the lives of people around you.
- A time when you went above and beyond your role.
Final Verdict:
I was offered the position—and I accepted it! 🎉