Huawei Interview Question for Software Engineer / Developers






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

external merge sort

- Anonymous June 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Read 2GB (= 2 file) of the data in main memory and sort by some conventional method, like quicksort.
2. Write the sorted data to disk.
3. Repeat steps 1 and 2 until all of the data is in sorted 2 GB chunks (there are 10 GB / 2 GB = 5 chunks), which now need to be merged into one single output file.
4. Read the first 1 GB of each sorted chunk into input buffers in main memory and allocate the remaining 5 GB for an output buffer. (In practice, it might provide better performance to make the output buffer larger and the input buffers slightly smaller.)
5. Perform a merge and store the result in the output file. If the output buffer is full, write it to the final sorted file, and empty it.
6. If any of the 5 input buffers gets empty, fill it with the next 1 GB of its associated 2 GB sorted chunk until no more data from the chunk is available.
This is the key step that makes external merge sort work externally -- because the merge algorithm only makes one pass sequentially through each of the chunks, each chunk does not have to be loaded completely; rather, sequential parts of the chunk can be loaded as needed.

- compskiguy January 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In step(4), how can u bring 1GB from each of the sorted chunks(in ur case 5) into main memory(which is 2GB). I guess you will have to divide the main memory into no. of chunk groups i.e. 5 (which comes to 2Gb/5 = 400MB each). Now from each of the sorted chunk get 400MB of data into the main memory, merge it and put back in output buffer. Now as the 400MB chunks get empty, get the next 400MB chunk from its sorted chunk and repeart the process. Correct me if i m wrong.

- Ashwin February 20, 2013 | 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