google logo
Google· SDE1 OA

GOOGLE SDE1 OA Questions

Posted
25 Apr 2025
386 reads

Summary

This post provides the two algorithmic questions encountered during a Google SDE1 Online Assessment.

How it went

The online assessment for a Google SDE1 role included two distinct coding challenges. The first problem involved designing a search suggestion system with custom sorting based on popularity and lexicographical order. The second problem required finding the minimum flips to make a binary string alternating, using a fixed-length flip window.

Questions asked (2)

  1. 01

    Search Suggestions System with Popularity and Lexicographical Order

    Data Structures & Algorithms

    You are given a list of products, where each product is a string. You are also given a searchWord. After each character typed, return the top k suggestions of product names that match the typed prefix.

    Each product also has an associated popularity score (Map<String, Integer>). Suggestions should be returned in order of:

    • Highest popularity score
    • If scores are equal, return the lexicographically smaller product.

    You must return suggestions after each character of searchWord. Handle up to 1e5 products and optimize for performance.

    Test Case:

    products = ["apple", "appetizer", "application", "app", "apply", "banana", "appstore"]
    popularity = {
        "apple": 80,
        "appetizer": 70,
        "application": 90,
        "app": 90,
        "apply": 85,
        "banana": 60,
        "appstore": 90
    }
    searchWord = "app"
    k = 3
    

    Expected Output:

    [
      ["app", "application", "appstore"],     # 'a'
      ["app", "application", "appstore"],     # 'ap'
      ["app", "application", "appstore"]      # 'app'
    ]
    
  2. 02

    Minimum Flips to Alternate Binary String (K Flip Window)

    Data Structures & Algorithms

    You are given a binary string s. In one operation, you can flip a subarray of length exactly k (flip all bits in that subarray). Return the minimum number of such operations needed to make the string alternating (i.e., no two adjacent bits are the same). If it's not possible, return -1.

    Test Case: s = "00010111"

    k = 3

    Expected Output : 2

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!