Google | L5 | Round 2
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.
Full Experience
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.
Interview Questions (2)
Count Strings with Prefix (Sorted Array)
Given an array of strings sorted in lexiographic order. Find how many strings matches a given prefix.
Count Strings with Prefix (Multiple Queries Optimized)
Now the string array is fixed but you are getting lots of queries with different patterns. Optimize the solution to handle multiple queries.