Bloomberg Interview Question
Technical Question: It was based on e-commerce setup. So there are n Order receiving servers which are receiving orders from customers and there is one another server which fetches orders from the these servers and processes them in sequence. n order receiving servers ( each server has m orders): A : 1 3 6 ... B : 2 5 7 9 ... C : 4 8 10 .... -- -- -- n There is no collision when order receiving servers are receiving orders and the orders are queued up on these servers. The Order Processing server need to process these orders in order, means the server will process order 1 from server A, then 2 from Server B, then 3 from Server A and so on... How the Order Processing server can do this in most efficient way? Also implement the setup
Interview Answer
Anonymous
I said the Order Processing server can maintain a Min Heap. It fetches 1 order from each server , so total n orders at a time, put all the orders into a Min-Heap and then while processing just do one Extract Min Operation. It will take O(m*n log2(n) + n) time to process all the orders. As min Heap will contain at most n orders at any time , we have to perform m*n (total orders) to process all the orders. Is there any different approach that we can do better than this?