Status: Software Engineer, 10 years of experience
Position: E5 at Facebook
Location: Menlo Park, CA
Date: September 10, 2019

Technical phone screen (45 min):

• Wildcard Matching similar to https://leetcode.com/problems/wildcard-matching/ but with only '?' wildcard and 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 rounds 45 min each
Result: Still waiting

Round 1: [Coding]

• https://leetcode.com/problems/linked-list-cycle/
• https://leetcode.com/problems/longest-substring-without-repeating-characters/

Round 2: [Coding]

• Question was similar to https://leetcode.com/problems/task-scheduler/.

Problem :
Given a char array representing tasks CPU need to do. It contains Integers where different integers represent different tasks. Tasks has to be done in original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.

However, there is a non-negative cooling interval K that means between two same tasks, there must be at least K intervals that CPU are doing different tasks or just be idle.

You need to return the total amount of time CPU will take to finish all the given tasks.

Example:

Input: tasks = ["1","2","1","2","2","1"], n = 2
Output: 9
Explanation: 1-2-idle-1-2-idle-idle-2-1

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. Interviewer was fine even if time complexity is a bit high. 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.

Lunch:

• Had lunch at cafeteria and went for a walk around campus.

Round 3: [System Design]

• Design Facebook Mesenger for 1 Billion daily active users and each user sends 45 msgs per day.

Round 4: [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.
• Leftmost column index of 1

Round 5: [Coding]

• Dot product of sparse vectors 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).
• https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/ (premium)
  Didn't had time to complete this.

Notes

• For coding questions interviewer expects you to validate your solution for few test cases. Make sure to validate for all edge case scenarios.
• Practicing on LeetCode really helped me and for system desgin go through https://www.educative.io/courses/grokking-the-system-design-interview and Tech Dummies - Narendra L videos on youtube.