is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.
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.
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.
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.
External counted bitmap sort, O(n) complexity.
Since these are integers (assumed 32-bit), there are 2 properties can benefit from:
1. The range of values is finite, hence we can use a bitmap to partition the range un sub-ranges.
2. The file size is larger than the possible range of values, which means there are duplicates, which will need counted.
We split the integer values in ranges that, together with the counters, fit in the available memory. Worst case scenario, only 1 value repeated the entire file, so the counter needs to be 64-bit. One record has the counter = 8 bytes, 200MB of memory can contain 2^24 such records, so we split the 32-bit range of values in 2^8=256 ranges.
Scan the original file and save each value in its appropriate temp file, in original order.
For each temp file, in the order of ranges:
Scan the file and increment the counter for each integer read.
Scan the bitmap and append the values to the final file, each repeated the respective count.
- florinb1 January 06, 2016