What is Interview Forge?

Interview Forge helps you practice mock interviews, follow study plans, track career goals, review learning analytics, and prepare across 36 pages.

Word Break at Google — Interview Guide

How to approach Word Break in a Google interview: the optimal approach, what Google interviewers look for, and company-specific tips.

Updated 2026-09MediumDynamic Programming

The problem at Google

Given a string and a dictionary of words, determine whether the string can be segmented into a space-separated sequence of dictionary words.

Google uses this problem to assess algorithmic rigor and generalist problem-solving. Expect Google-specific follow-ups that tie the solution back to production reasoning and the company's engineering bar.

Key concepts

dp[i] = true if s[0:i] can be segmented.
Transition: dp[i] is true if some j < i has dp[j] true and s[j:i] is in the dictionary.
A trie over the dictionary speeds up the substring lookup for large dictionaries.

Approach

def word_break(s, word_dict):
    words = set(word_dict)
    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]

Complexity

Metric	Value
Time	O(n²) with set lookup
Space	O(n)

Unlock the full guide

Premium members get every DSA, system design, company and role interview guide — plus AI practice, mock interviews, and analytics.

Unlock with Premium