Google Interview Experience | University Grad 2026

This document outlines my experience during a technical interview for the Google University Grad 2026 role, focusing on a problem involving a monotonic stack.

The Problem: Trapping Rain Water with Fountains

I was asked a question that was a variation of the classic "Trapping Rain Water" problem.

Problem Statement

You are given a 1D array of integers, surface, representing a height map. You are also given an array of indices, fountains, which are source points for water. Water flows from these fountains to the left and right, filling any areas lower than the fountain's height until it hits a "wall" (a point higher than or equal to the fountain) or the edge of the array. The goal is to determine the final water level across the surface.

Example

• surface = [1, 2, 3, 4]
• fountains = [1, 3] (Fountains at index 1 (height 2) and index 3 (height 4))

My Approach & Performance

Here is a breakdown of my performance during the interview, including timing and thought process.

Approach 1: Brute Force

• Explanation (10 mins): I first described the brute-force solution. For each fountain, simulate the water flow outwards (one pointer to the left, one to the right). Keep track of the maximum water level at each position.
• Complexity:
  • Time: O(N * K) where N is the number of points and K is the number of fountains.
  • Space: O(N) to store the water levels.
• Coding (5 mins): I successfully coded this solution quickly.

Approach 2: Optimal (Monotonic Stack)

• Explanation (10 mins for initial dry run): I identified that the problem could be optimized by pre-calculating the "next greater element" to the left and right for each point. This is a classic use case for a monotonic stack. My initial attempt to dry-run this approach was shaky and took a significant amount of time.
• Reset & Re-explanation (2-3 mins): I took a moment to reset, then successfully explained the logic more clearly.
• Coding (5 mins): I started coding the optimal logic but ran out of time. I was only able to get about halfway through the implementation.
  Like, I coded the logic but did not return the array.
• Complexity:
  • Time: O(N) because the monotonic stack approach processes each element a constant number of times.
  • Space: O(N) for the stack.

Takeaways & Advice for Round 2

So, do any of you have feedback for me for Round 2?
And what are key things I should improve?

Is it hire/lean hire/strong hire?