A few days back, I got the opportunity to interview with Google, and I’m sharing the problems that were asked during the rounds.

Phone Screen Round:
You are given several strings, each consisting of the characters 'A', 'B', 'C', and 'D'. The task involves performing a sequence of operations on a larger string also made of the same characters. The operation removes occurrences of these smaller strings from the larger string until none of the smaller strings are left as substrings. The string is considered "bad" if multiple possible final results can be produced by removing the substrings in different orders. Determine if a "bad" string exists.

example

4
CBA
ACB
AD
CAB
Answer: Yes

3
A
B
C
Answer: No

I solved the problem using the Aho-Corasick algorithm
Verdict: Qualified for onsite.

Round 1:
You are given an undirected graph where each vertex has an interval [i, j] written on it. Two vertices are connected by an edge if their intervals overlap. Your task is to find the number of spanning trees in this graph.

example:
2
1 2
1
Output: 8

I was able to solve the problem with a time complexity of O(N^3).

Verdict: Strong hire.

Round 2:
You are given multiple rectangles, each represented by four integers (x1, y1, x2, y2). The task is to calculate the total area covered by the union of these rectangles.

I was able to solve the problem in 30 minutes. It's a very standard problem, and I solve this and similar problems involving circles every time I work on geometry problems.

Verdict: Hire.

Round 3:
You are given a sequence of numbers and need to transform it into another target sequence by performing operations. In each operation, you can replace a number with its remainder when divided by a chosen integer. The cost of each operation depends on the chosen integer. The goal is to determine if it's possible to transform the sequence into the target sequence and, if so, to find the minimum cost.

example:
3
19 10 14
0 3 4
Output: 160

Verdict: Lean hire.

Round 4:
You are given an infinite series of switches, each labeled with a number starting from 1. Initially, some switches are turned on, while others are turned off. Your task is to turn all the switches off.

You can perform the following operation multiple times:

Choose a prime number p (where p >= 3).
Select p consecutive switches and toggle their states (i.e., if a switch is on, it will turn off; if it is off, it will turn on).
Your goal is to determine the minimum number of operations required to turn all switches off.

Input:
2
4 5
Output:
2
Explanation: One way to achieve the goal in two operations is:
Choose p=5 and toggle switches 1, 2, 3, 4, and 5.
Choose p=3 and toggle switches 1, 2, and 3.

Input:
9
1 2 3 4 5 6 7 8 9
Output:
3
Explanation: A possible way to achieve the goal in three operations is:
Choose p=3 and toggle switches 1, 2, and 3.
Choose p=3 and toggle switches 4, 5, and 6.
Choose p=3 and toggle switches 7, 8, and 9.

After thinking for a couple of minutes, I solved the problem using bipartite matching."
verdict: Hire.

Overall, all five rounds went really well for me. All questions, except one, were new to me. Even the familiar ones required math wrangling, which I thoroughly enjoyed. However, the final verdict was Reject. They rejected me primarily due to missing code quality and structure, highlighting that even a single lean hire at Google could lead to rejection.