Web engineer interview questions shared by candidates
You have 1000 computers. Each computer contains a text file containing 1 billion floating point numbers. Design an algorithm or algorithms for extracting the top 1000 numbers from the entire list. Describe in detail how long it would take to process and why.
Max heap + map reduce.
1. 1000 computers - parallel 2. the problem can be divided into 2 parts. (1) find the top 1000 numbers from that 1 billion numbers in one computer To do this. we just need to use merge sort. Everytime use the left part. With some calculation, the solution for this is actually O(N). n is 1 billion. (2) get that top 1000 from the 1k * 1k list. (easy)
There is a very nice parallel sorting algorithm with a very good iso-effeciency. It is called Sample-sorting. I would use that.
An enumerator is a class with getNextObject method. It encapsulates the container. Write an enumerator. Next, write a new enumerator called chained-enumerator which is initialized by two other enumerators. Finally, how would you make it work with N enumerators. I had to write the logic for getNextObject for the most part (and any other internal state I wanted to manage).
Second question was not really a question but a very healthy session of pair programming where I was speaking and a senior developer was coding. He chose JAVA and we were creating a list data-structure (with add, count, delete) operations. The catch was that we were going to do it TDD style. So I guided him on what kind of test we can write and how to pass that test and so on. We kept doing it and in 45 minutes we had a very well tested working list data structure.
See Interview Questions for Similar Jobs
- Dental Assistant
- Medical Assistant
- Security Guard
- Social Worker
- Registered Nurse
- Human Resource