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.
