2 Coding. 2 System Design. 1 EM.

Sys Design A:
Design a system where users can visit content and view live posts on the content.

Sys Design B:
Imagine that users have profiles on Facebook and they can set their statuses. Each user has a status. The status is just a piece of text. How would you design a system allowing user to search the status?

Coding A:
Given two lists of sorted, disjoint intervals, merge them to find their union.
Follow up: K-many lists. ((sum elements) * log(K) solution is optimal)

Given a binary tree where each node has a digit, find sum of all the paths where numbers are formed by traversing the tree from top to bottom.
Follow up: What if you can have numbers larger than 10 in the nodes? (Use log_10 to find the power...)

Coding B:

1. Vertical traversal of a binary tree. Easy peasy.
2. Design a structure that can do insert which will insert an element into the collection and popRandom which will randomly pop an element from the structure with equal probability.
   I used an array with a random index to select the element for popRandom. Swap the randomly selected element with the tail and then pop the tail for O(1) popRandom.
   Then the interviewer and I started to chat and then he remembered a followup to the second question...
   What if we want to assign weights to the elements? e.g. insert(num 1, weight 20), insert(num 2, weight 1) should give you a 1/21 chance of popping a 2 and a 20/21 chance of popping a 1.

Engineering Values:

• Talk about a disagreement that you had where you insisted on your position, and you turned out to be wrong

• Talk about a project that you're proud of and why.

• Talk about a project that you're not proud of and why.

• Talk about something cool you do outside of work that you find enriching.

• Talk about a time where you tried to help someone.

• Talk about a time where you came into a project with lots of ambiguity

• What areas do you want to develop yourself personally in?