Google Onsite round 2
Summary
I experienced an onsite interview round at Google which involved a detailed problem on implementing an auto-complete feature for street names.
Full Experience
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.
Interview Questions (1)
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