Google New Grad Onsite: Maze, Character Bag, Top-K Pair Sums, and Directed Cycle

Role: Software Engineer, New Grad
Result: Waitlisted
Report time: March 2026

The loop contained four technical rounds plus behavioral questions. The candidate described the base problems as mostly LeetCode Medium, with follow-ups testing optimization and tradeoffs.

Round 1: shortest maze path with one block removal

A grid has a start in the top-left, an end in the bottom-right, free cells, and blocked cells. Find a shortest path.

The follow-up allows converting one blocked cell to free. The candidate compared brute-force BFS for every block with a single BFS over state visited[row][col][usedRemoval].

Corner cases included start equal to end and self loops.

Practice: Shortest Maze Path With One Block Removal

Round 2: construct a target from a character bag

Given a source string and a target string, determine whether the target can be formed from the available source characters by comparing frequency counts.

For a very large bag, the follow-up compared a fixed integer array for a small alphabet with a HashMap for a large character set.

Practice: Construct Target String From a Character Bag

Round 3: top-K pair sums

Given one integer array, generate results for pairs of elements, retaining repeated values when they arise from valid pairs.

The follow-up asks for the k largest pair sums. The candidate sorted the array, used a max-heap to advance through the largest combinations, targeted O(k log n), and tracked states to avoid duplicate heap pushes.

Practice: Top K Pair Sums From One Array

Round 4: shortest directed cycle through a start node

Given a directed graph and a starting node, find the shortest cycle that leaves the node and returns to it.

The candidate used BFS and a parent map to recover the path. A self loop must be handled as the shortest possible cycle.

Practice: Shortest Directed Cycle Through a Start Node

Behavioral interview

Topics included a challenging project, its biggest challenge, result and impact, cross-team collaboration, competing customer requirements, and a mistake.