Friend refferal → https://foobar.withgoogle.com/?eid=3vBMu”
garbage collection algorithm
circular buffer questions
vector
networking
order books, matching egines
order router implementation
HRT phone interview 45 min total No coding ~20 min for discussing projects and asking questions Each problem was followed by complexity analysis
-
kth smallest elements Brute force is an O(nlogn) sort Better solution is to heapify the array, then pop the min element k times, for a complexity of O(n + klogn) Optimal solution is quickselect for average O(n) and worst-case O(n^2) Follow-up question: Complexity analysis of quickselect
-
getMax() on a stack Two stacks, one to track the actual stack and another to track the running maximum No follow-up question because I had seen this problem before, but you can do this with one stack plus constant memory by storing (2 * newMax - prevMax) in the stack (instead of the actual value) when you see a new maximum, and tracking the max in separate variable
-
DS with O(1) add element and O(1) remove random element Removed element must be uniformly random (assume that you have a rand() function that returns a random integer in your specified range) Use a list to represent the numbers you have and a mapping from index to value For the add operation, append to the list and add it to your mapping For the remove operation, use rand() to find the index to remove, then move the last element in the list to the random index. Update the mapping accordingly
-
On the complexity of dynamic arrays What is the complexity of an append operation on a dynamic array and why? What about if you increase the size by 10% instead of doubling the size and why? And since doubling the size is just increasing the size by 100%, at which x% does the average append complexity go from O(n) to O(1)?
https://leetcode.com/problems/maximum-69-number/ https://leetcode.com/problems/convert-integer-to-the-sum-of-two-no-zero-integers/ https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/ https://leetcode.com/problems/detect-pattern-of-length-m-repeated-k-or-more-times/ https://leetcode.com/problems/insert-delete-getrandom-o1/