Amazon Interview Question for SDE-3s


Country: United States




Comment hidden because of low score. Click to expand.
0
of 0 vote

As all the files hold stream of integers, I would design a program that read each file and count the number of each integer in the files. When the program starts, it will create 8 temporary count files to hold the count of all integers each of which will keep counts of 2^29 numbers in sorted order. As each count will be a 64 bit number, each file will be 4GB. 8 files will cover count of all possible numbers.

A program will be designed to read each integer from each file and store integer counts temporarily in a sorted key-pair values such as sorted dictionary Dictionary<int, long>. When the number of element in the dictionary reach a point where it would run out of memory (about 340k element), the program will update the count files by adding the new value to existing one and saved to the same location. The program then clears the dictionary and continues the loop until all input files are read and processed.
When all the input files are processed, the program reads the 8 temporary count files, the output the number of integer to the final output file.

This solution limit is that there are at most 2^64-1 appearance of each number in all the input files

- Dung Nguyen April 16, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be solved with map/reduce paradigm. basically you create K mapper (k is the number of buckets you want to do rough partition sort, say (2^31-1)/20, 20 will be # of mappers) and each mapper covers a range of integers to contain. After mapper tasks, each mapper contains a range of integers and each mapper's bucket is in ascending order. Now create same number of sorter and each sorter is sorting the corresponding mapper's outtput. Each sorter (reducer) will output the sorted result into the final output file. As you see the number of mapper and reducer will match and process streams coming from the file sources. This is a scalable and efficient design with map/reduce paradigm.

- Anonymous June 18, 2019 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More