Google On-Campus Interview Experience — Selected

Before I begin, only DSA questions were asked throughout the Google interview process. Not a single question related to OS, DBMS, CNS, OOP, System Design, or even the resume was asked. So, if you're preparing for Google, this experience gives you a clear idea of what to focus on.

The process consisted of 4 rounds, including DSA interviews and Googliness & Leadership (G&L) rounds.

Round 1 — Online Coding Test (HackerEarth)

All students were eligible for Round 1, with no restrictions based on CPI or active backlogs.

Q1 — String Partitioning (30 points)

You are given a string S of length N, consisting of digits from '0' to '9'. You need to partition the string into K substrings such that:

• Each substring starts with an even digit and ends with an odd digit.

• Each substring has a length of at least M.

Determine the total number of ways to partition the string into K substrings. Return the answer modulo 10^9 + 7.

Sample Input:

• N = 9

• M = 2

• K = 3

• S = "454569421"

Output: 3

The three valid partitions are:

1. 45 | 45 | 69421

2. 4545 | 69 | 421

3. 45 | 4569 | 421

Approach: Dynamic Programming using recursion and memoization.

Q2 — Special Paths in an N-ary Tree (30 points)

You are given an N-ary tree with N nodes, where each node has a value associated with it, provided in the form of an array.

A path is called special if it satisfies the following conditions:

• Every node in the path is traversed exactly once.

• The value of the starting node is equal to the value of the ending node.

• The starting node and ending node must be different.

• The values of all nodes in the path must not exceed the value of the starting node.

Count the total number of special paths in the tree. Two paths are considered different if they contain at least one different node.

Approach: A naive approach was sufficient because the constraints were not tight.

Verdict: Selected for interviews! A total of 19 students out of 370 were shortlisted from the batch.

Round 2 — Online Interview (Google Meet)

Duration: 45 minutes

Only one DSA question was asked.

Q1 — Minimum Operations to Equalize Building Heights

You are given an array where each element represents the number of floors in a building.

In one operation, you can remove one floor from any building. After a certain number of operations, the number of floors in every building must be either zero or equal to some specific non-negative integer K.

Find the minimum number of operations required and the corresponding value of K.

Sample Input:

arr = [1, 3, 4, 7, 8, 9]

Output:

• Minimum operations = 11

• K = 7

• Final array = [0, 0, 0, 7, 7, 7]

Approach: Prefix Sum.

The interview was conducted on a platform called Google Interview. The interviewer first asked me to explain my approach, and after that, I was asked to code the solution.

One challenging aspect was the coding environment, which was similar to Notepad:

• Auto-indentation was disabled.

• Auto-completion was disabled.

• Suggestions were disabled.

This was intentionally done to assess how cleanly a candidate could write code.

Important Tip: Write clean code with proper indentation. Use self-explanatory variable names such as my_turn and next_person instead of short names such as mt and np.

Round 3 — Online Interview (Google Meet)

Duration: 45 minutes for DSA, followed by 15 minutes for the G&L round.

DSA Round

Q1 — Frog Probability in an N-ary Tree

You are given an N-ary tree where each node can have anywhere from zero to n children.

A frog starts at the root node. From its current node, it can jump to any child with equal probability. The frog can remain at its current node only if it is a leaf node; otherwise, it must jump to one of its children.

For every node, determine the probability that the frog will be present at that node after an infinite amount of time.

Inference: Only leaf nodes will have non-zero probabilities. All non-leaf nodes will have a probability of zero.

Approach: Simple DFS.

Suppose the frog reaches an arbitrary node x with probability Px, and node x has m children.

The probability of jumping from node x to any of its children is 1/m.

Therefore, the probability of reaching any child node from the root is:

Py = Px × (1/m)

Store the probability of reaching each node in the result array. Finally, set the probabilities of all non-leaf nodes to zero.

I was able to code this approach on the Google Interview platform in approximately 20 minutes, and the interviewer was satisfied.

Follow-up Question — What if the tree were a Directed Acyclic Graph (DAG)?

Approach: DFS on outgoing edges.

In a DAG, the probability of reaching the current node x from the root is the sum of the probabilities of all paths arriving through its incoming edges.

We should move to the children of node x only after all its incoming edges have been traversed.

The interviewer was satisfied with both my approach and my code. This was a green flag from his side and boosted my confidence.

G&L Round 1 — Googliness and Leadership

Duration: 15 minutes

Question:

You are working on a project with a team of 10 members. Everyone contributes equally and performs to the best of their abilities. However, the team leader takes all the credit during meetings with senior managers.

What would you do in this situation?

Verdict: 10 candidates out of the 19 shortlisted students were selected for Round 4.

Round 4 — Online Interview (Google Meet)

Duration: 45 minutes for DSA, followed by 15 minutes for the G&L round.

DSA Round

Q1 — Signal Transmission Between Routers

Assume a Cartesian coordinate system. You are given the coordinates of K routers. Every router can send and receive signals.

One router is designated as the Source, and another is designated as the Destination. You are also given a range R.

When a router sends a signal, all routers within distance R receive it and retransmit the signal. Think of R as the radius of a circle around each router.

Determine whether the Destination router will receive a signal transmitted by the Source router.

Approach: Breadth-First Search (BFS).

1. Start BFS from the Source router.

2. Calculate the distance between the current router and all unvisited routers.

3. If an unvisited router is within range R, add it to the queue and mark it as visited.

4. Continue BFS until the queue is empty.

5. Check whether the Destination router has been visited.

I coded this solution on the Google Interview platform.

Follow-up Question:

If there are too many queries involving different sources and destinations, would it be feasible to run BFS for every query? What would you do instead?

Answer: Memoize the solutions. Run BFS only when the result is not already available in the cache.

The interviewer was satisfied with the solution and did not ask me to code the follow-up because of time constraints.

G&L Round 2 — Googliness and Leadership

Duration: 15 minutes

Question:

Since you actively participate in extracurricular activities, have you ever taken a new initiative, such as organizing an event or doing something similar?

What was people's reaction, and how did you deal with those who opposed your initiative?

Pro Tips

• Be polite and humble.

• Avoid using negative words.

• Don't try to be over-smart.

• Keep your answers direct and to the point.

Final Verdict

Received an offer from Google! 🎉

Five candidates received offers out of the 10 who reached the final round.

This was my Google on-campus interview experience. I hope it helps other students prepare for their interviews and understand what to expect from the process.