google logo
Google· SDE III

Google | L5 | Round 2

Posted
8 Apr 2025
374 reads

Summary

I had a second round interview at Google for an L5 position, where I was asked two parts of a string prefix matching problem. I discussed binary search and Trie-based approaches, identifying a minor bug in my initial solution.

How it went

Given an array of strings sorted in lexiographic order. Find how many strings matches a given prefix .

I used binary search to find the lowest and highest index in arr where prefix is matched. in one of the loop to check if pattern is prefix of a string or not i missed the check of pattern length > string length. Interviewer pointed it out , not sure how much it will affect my chances

Time complexity logN * Pattern length

Part 2 -> Now string array is fixed but you are getting lots of queries with different pattern.

Created a Trie out of the input string and then use the pattern to match how many string in the trie matches a prefix

Time complexity of preprocessing -> O(N * L) where L is average length of string

Time complexity of query -> O(p)

here i defined trieNode as

TrieNode -value -children[26]

another question came up was to optimisze the space here in that case it was better to use a hashmap instead of an array of 26 fixed length.

Questions asked (2)

  1. 01

    Count Strings with Prefix (Sorted Array)

    Data Structures & Algorithms

    Given an array of strings sorted in lexiographic order. Find how many strings matches a given prefix.

  2. 02

    Count Strings with Prefix (Multiple Queries Optimized)

    Data Structures & Algorithms

    Now the string array is fixed but you are getting lots of queries with different patterns. Optimize the solution to handle multiple queries.

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!