# 脸熟E5上门

*10年经验，面的是 E5

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分钟

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.

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

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