脸熟E5上门

*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]

  1. Check if a linked list has loop in it.
  2. 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]

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

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