地点在 Menlo Park, CA
店面 (45 分钟):
Wildcard Matching similar to https://leetcode.com/problems/wildcard-matching/ but with only ‘?’ wildcard but for a list of patterns and words.
My solution was to traverse linearly for each word against each pattern. I have been asked if I can optimize further. I proposed building prefix tree for all words. But didn’t had time to implement it.
Format: 5 轮各45分钟
- Check if a linked list has loop in it.
- Find the length of longest substring in a given string with no duplicate characters.
Question was similar to https://leetcode.com/problems/task-scheduler/. But instead of optimizing the number of cycles I have been asked to find out total amount of time it takes to process the tasks with out rearranging them.
Time complexity of my solution was O(N) - N is the number of tasks and space complexity was O(T) - T is number of types of tasks.
I have been asked if I can optimize further on space if cooling period is very low. I proposed a different solution with O(K) as space complexity and O(NK) as time complexity. But didn’t had time to implement it.
Design facebook mesenger for 1 Billion daily active users and each user sends 45 msgs per day.
https://www.educative.io/courses/grokking-the-system-design-interview/B8R22v0wqJo has pretty good solution for this.
Deep dive into my latest project and questions around how I interacted with fellow team members, product manager and if there were any conflicts at any point of time. If there were any conflicts how did I resolve them.
There was a follow up coding question similar to https://leetcode.com/problems/search-a-2d-matrix/.
- Whats the optimal way to represent sparse vectors - most of the elements in vector are zeros - proposed on storing only non zero values along with its index. Given two such vectors find the product of them.
Proposed and implemented a solution of complexity O(M+N). As a follow up asked me to redesign my solution if size of one the vectors is very small. Implemented a solution of complexity O(MlogN).
- Given a binary tree convert it to double linked list in level order traversal manner. Didn’t had time to complete this.
面试得写下test cases验证代码，确保验证所有edge case。