We pay for user submitted tutorials and articles that we publish. Anyone can send in a contributionLearn More
The sixth of the series of programming job interview challenge is out. Other then commenting the solution, I remind you that you can post the solution on your blog and get a link next week!
Here is the solution to the previous challenge:
Two-way merge sort (External Sorting) : The idea is breaking the big file into subfiles, sorting them and than merging them back together. In the first pass read one page at a time, the records in the page are sorted (quicksort for example) and the page is written back to disk. in subsequent passes, each pair of sorted output from the previous pass are read and merged to produce sorted subfile twice as long:
1. Read each page, Sort it, Write it back
2. while more than one sorted subfile:
while subfiles from previous pass left to merge:
– Choose next two subfiles from previous pass
– Read each subfile into a memory page (one page at a time)
– Merge the subfiles (remember each of them is already sorted), write output to a memory page
– Write output page to disk when needed.
Note that 3 pages are enough to run this algorithm. (do you see why?)
Heiko Hatzfeld provided a nice solution in his blog including c# implementation, notice you used 4 pages in the MergeSort stage, you could write one output file each time it is full.
Martin Ankerl also provided few correct and simple solutions, I liked his simple post.
From the commenters:
Kirill Sorokin, Jonathan Gilbert, Jonas Christensen, Heiko Hatzfeld, Tim C, Chris Jobson, and Sh4DoW provided a full and correct answer.
Amgel, Edward Shen, Per, Kris Warkentin answered merge sort but didn’t provide the full algorithm.
Alex, Your solution will produce the correct answer, however it is much less efficient in terms of IO access. since you don’t know if values are uniformly spread across the file you might end up with some very small temp files and some very large once, and might cause lots of reduced disk accesses.
Mark Bradshaw provided a bubble sort variation, a bit less efficient than merge sort.
Poul Foged Nielsen the simple bubble sort would be very inefficient.
And now let’s head on to this week’s question:
Look at the following Code segment written in C#:
What will be typed into the console? And WHY? Hopefully you will “play fair” and won’t type it in Visual Studio to see the output, you are in a job interview after all…
But the main issue of the question is the why.
The answer in now published in the 7th question in the series.
Tags :answerchallengecorrecteficienthi techimagesjob interviewmemorymerge sortpixelproblemprogrammingquestionsolution
Copyright © 2012 Dev102.com
Breeze : Designed by Amit Raz and Nitzan Kupererd