Google | Onsite | Word Break Problem

Posted
21 May 2024
358 reads

Summary

During my Google onsite interview, I was presented with the classic Word Break problem, which I successfully solved using dynamic programming.

How it went

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.

Questions asked (1)

  1. 01

    Word Break Problem

    Data Structures & Algorithms

    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 True if s can be segmented into a space-separated sequence of words from wordDict. Otherwise, return False.

    Example:

    1. Input: s = "leetcode", wordDict = ["leet", "code"]
      • Output: True
      • Explanation: "leetcode" can be segmented into "leet code".
    2. Input: s = "applepenapple", wordDict = ["apple", "pen"]
      • Output: True
      • Explanation: "applepenapple" can be segmented into "apple pen apple".
    3. Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
      • Output: False

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at Google recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!