Google Coding Interview Questions: The DP & Graph Bar

Google's coding interview is famous for two things: optimal-complexity data-structures-and-algorithms problems, and a decision process where a hiring committee reviews written feedback rather than your interviewers deciding directly. That second fact changes how you should interview — how clearly you narrate your reasoning matters as much as the final answer, because someone who never met you reads the write-up.

Compared to Meta's speed or Amazon's Leadership Principles, Google over-indexes on dynamic programming and graphs. This guide walks five representative Google problems with worked Python solutions, the full L3–L6 loop, and the narration habits that produce a strong committee packet.

The full interview process

Stage	Format	Notes
Recruiter screen	30 min	Background, target level, team-match later
Phone / virtual screen	45 min, 1-2 problems	Optimal DS&A on a shared doc; narrate complexity
Onsite coding (2-3)	45 min each	Harder DS&A, clean code, edge cases
System design (L5+)	45 min	Scalable architecture and trade-offs
Googleyness & Leadership	45 min	Ambiguity, collaboration, bias to action
Hiring committee	Async review	Reads the written packet and decides — not the interviewers

Problem 1: Number of Islands (graph traversal)

Question: Given a 2D grid of '1' (land) and '0' (water), count the number of islands. An island is connected horizontally or vertically.

The canonical Google grid-traversal problem. Flood-fill each unvisited land cell with BFS or DFS and count how many fills you start.

def numIslands(grid):
    if not grid: return 0
    rows, cols = len(grid), len(grid[0])
    count = 0
    def sink(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'
        sink(r+1, c); sink(r-1, c); sink(r, c+1); sink(r, c-1)
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                sink(r, c)
    return count

Time O(rows×cols), space O(rows×cols) for recursion in the worst case. State out loud that you're mutating the grid to mark visited — if the interviewer says the grid is read-only, switch to a separate visited set.

Follow-up: "What if the grid is too large to fit in memory?" Now you're discussing union-find with disk-backed partitions, or processing row-strips with a boundary merge. Google loves pushing one optimal answer into a systems conversation.

Problem 2: Word Break (dynamic programming)

Question: Given a string s and a dictionary of words, return true if s can be segmented into a space-separated sequence of dictionary words.

A classic Google DP. dp[i] is true if the prefix of length i is segmentable; it's true when some dp[j] is true and s[j:i] is a word.

def wordBreak(s, wordDict):
    words = set(wordDict)
    dp = [False] * (len(s) + 1)
    dp[0] = True
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[-1]

Time O(n²) with O(n) substring checks, space O(n). The interviewer wants you to recognize this is DP and not exponential backtracking. If you start with recursion, they'll nudge you to memoize — arriving at the bottom-up table earns more signal.

Problem 3: Meeting Rooms II (heap / intervals)

Question: Given an array of meeting time intervals, return the minimum number of conference rooms required.

Sort by start time; use a min-heap of end times. A new meeting reuses a room if the earliest-ending meeting has already finished.

import heapq
def minMeetingRooms(intervals):
    if not intervals: return 0
    intervals.sort(key=lambda x: x[0])
    heap = []  # end times
    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heapreplace(heap, end)
        else:
            heapq.heappush(heap, end)
    return len(heap)

Time O(n log n), space O(n). The heap size at the end is the peak concurrency — the answer. Verbalize why sorting by start and tracking ends with a heap is correct; that reasoning is the signal.

Problem 4: Decode Ways (DP with constraints)

Question: A message of digits is encoded with 'A'=1 ... 'Z'=26. Return the number of ways to decode it.

1-D DP where each position can come from a single digit (1-9) or a valid two-digit pair (10-26). Watch the zero edge cases.

def numDecodings(s):
    if not s or s[0] == '0': return 0
    prev, curr = 1, 1
    for i in range(1, len(s)):
        temp = 0
        if s[i] != '0':
            temp += curr
        if 10 <= int(s[i-1:i+1]) <= 26:
            temp += prev
        prev, curr = curr, temp
    return curr

Time O(n), space O(1) by keeping only the last two states. The traps are leading zeros and pairs like '06' (invalid) vs '16' (valid). Google interviewers specifically probe these edge cases.

Patterns Google asks most

Pattern	Frequency	Note
Dynamic programming	~20% of loops	Higher than any other FAANG
BFS / DFS on graphs & grids	~25%	Islands, clone graph, course schedule
Two pointers / sliding window	~20%	Strings and sorted arrays
Heap / intervals	~10%	Meeting rooms, merge k-lists
Binary search on answer	~15%	"Minimize the maximum" framing
Tries / backtracking	~10%	Word search, autocomplete

Common pitfalls specific to Google

• Coding before narrating. A hiring committee reads notes — if you solve silently, your interviewer can't write a strong packet. Talk through the approach and complexity before and during coding.
• Reaching for backtracking when it's DP. Many Google problems have an exponential naive solution and a polynomial DP. Recognizing the overlapping-subproblem structure is the signal they grade.
• Skipping edge cases. Empty input, single element, zeros, and overflow. Google interviewers reserve a follow-up specifically to test whether you check these unprompted.
• Treating Googleyness as a throwaway. The behavioral round is scored and feeds the committee. Have stories about navigating ambiguity and collaborating across teams.

A 4-week prep plan for a Google loop

1. Weeks 1-2: Drill the 15 core patterns with extra weight on DP and graphs.
2. Week 3: Solve mediums while narrating out loud and stating Big-O before coding. Record yourself; if you go silent, that's the bug.
3. Week 4: System design (L5+) and a Googleyness story set — one example each for ambiguity, conflict, and cross-team impact.
4. Throughout: Run a solo mock where you must explain every line as if to someone who isn't in the room — that's literally the hiring committee.

FAQ

Is the Google coding interview really DP-heavy?

Yes. Google over-indexes on dynamic programming and graph traversal relative to other FAANG companies. If your prep time is limited, weight DP and BFS/DFS most heavily, then two pointers and binary-search-on-answer.

Who decides whether I get the Google offer?

A hiring committee reviews the written feedback packet from your interviewers and makes the call - the interviewers themselves don't decide. That's why narrating your reasoning clearly matters so much: someone who never met you reads the notes.

What is 'Googleyness'?

Google's behavioral lens: comfort with ambiguity, collaboration, bias to action, and intellectual humility. It's a scored round that feeds the committee, so prepare real stories - it's not a formality.

How many coding rounds does Google have?

Typically one phone/virtual screen plus two to three onsite coding rounds, with a system design round added for L5 and above, and a Googleyness & Leadership round. Each is 45 minutes.

Can I use an AI assistant to prepare for Google interviews?

Yes for preparation and practice. CoPilot Interview surfaces optimal solutions with Big-O so you can rehearse narrating the why. Always follow each company's stated rules during the actual interview.