Google | Onsite | Word Break Problem
Summary
During my Google onsite interview, I was presented with the classic Word Break problem, which I successfully solved using dynamic programming.
Full Experience
My onsite interview experience at Google primarily revolved around a single coding challenge. I was given the Word Break problem and tasked with determining if a given string could be segmented into a space-separated sequence of words from a provided dictionary. I started by discussing my thought process, outlining a dynamic programming approach, and then proceeded to implement the solution while explaining the time and space complexities.
Interview Questions (1)
Word Break Problem
Problem Description:
Given a non-empty string s and a dictionary of words wordDict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
Input:
- A string
s(non-empty). - A list of words
wordDict.
Output:
- Return
Trueifscan be segmented into a space-separated sequence of words fromwordDict. Otherwise, returnFalse.
Example:
- Input:
s = "leetcode",wordDict = ["leet", "code"]- Output:
True - Explanation:
"leetcode"can be segmented into"leet code".
- Output:
- Input:
s = "applepenapple",wordDict = ["apple", "pen"]- Output:
True - Explanation:
"applepenapple"can be segmented into"apple pen apple".
- Output:
- Input:
s = "catsandog",wordDict = ["cats", "dog", "sand", "and", "cat"]- Output:
False
- Output: