*10年经验，面的是 E5

地点在 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.

**Onsite**

Format: 5 轮各45分钟

**第一轮: [Coding]**

- Check if a linked list has loop in it.
- Find the length of longest substring in a given string with no duplicate characters.

**第二轮: [Coding]**

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.

**午饭** :

在自助餐厅吃午饭，然后在campus转了一下

**第三轮: 系统设计**

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.

**第四轮: [Behavioral]**

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/.

**第五轮: [Coding]**

- 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.

**Notes**

面试得写下test cases验证代码，确保验证所有edge case。