Round 5:
This was an offline round. 3 question were shared on mail and had to revert with a solution.
1. Algo question:
· N people, M restaurants, on a one-dimensional street. All the people are to meet at one restaurant, find the restaurant, where total travel distance from all people to that restaurant is the shortest among all restaurants.
· The problem can be solved with brutal force with O(n*m) complexity. The question is how to solve it faster than brutal force.
· Describe the algorithm, and why it is better than brutal force. Coding is not required
2. Coding question:
· Binary tree in memory (not sorted, not balanced), write code to serialize the binary tree to disk, then deserialize from disk and re-construct in memory.
· Runnable code is required. You may use any language you like. You may also decide the format on disk.
3. System design:
· 1 million backend server that serves search traffic (think it as search service by google).
· 10k frontend servers – the FE servers intend to act as load balance the incoming traffic to the BE servers.
· Incoming traffic to the 10k FE servers are not balanced: there can be cold FE servers and hot FE servers
· Design the system/algorithm, where the traffic to BE servers are balanced.
· The design should be within today’s computer architecture, ideally without centralized components.