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)
Given an array of strings sorted in lexiographic order. Find how many strings matches a given prefix.
Now the string array is fixed but you are getting lots of queries with different patterns. Optimize the solution to handle multiple queries.