Google Onsite round 2

Posted
17 Apr 2025
368 reads

Summary

I experienced an onsite interview round at Google which involved a detailed problem on implementing an auto-complete feature for street names.

How it went

Auto-complete feature:

  • a list of known street names.
  • each street name: a counter for popularity.
  • the user enters a string, treat it as a prefix of street names.
  • we return a list of at most K best matched street names.

known street names: [{steven rd, 1}, {stevenson st, 2}, {ford ave, 3}] user: "ste" => matches: [{steven rd, 1}, {stevenson st, 2}] K=2 => steven rd, stevenson st (same matches as asked) K=1 => stevenson st (more matches than asked) K=3 => steven rd, stevenson st (less matches than asked)

user: "f" or "fo" or "for" or "ford" => ford ave

If there are more than k matches, then return the top k popular streets.

Questions asked (1)

  1. 01

    Auto-complete Feature for Street Names

    Data Structures & Algorithms

    Design and implement an auto-complete feature given:

    • A list of known street names, each with a counter for popularity.
    • When a user enters a string, treat it as a prefix of street names.
    • Return a list of at most K best matched street names, prioritized by popularity if more than K matches exist.

    Example: known street names: [{steven rd, 1}, {stevenson st, 2}, {ford ave, 3}] user: "ste" => matches: [{steven rd, 1}, {stevenson st, 2}] If K=2 => steven rd, stevenson st If K=1 => stevenson st (top 1 by popularity) If K=3 => steven rd, stevenson st (only 2 matches)

    user: "f" or "fo" or "for" or "ford" => ford ave

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!