An array of size k contains integers between 1 and n. You are given an additional scratch array of size n.
Compress the original array by removing duplicates in it. What if k << n?
is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.
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.
the case where K is comparable to n can be solved using counting sort and hence omittin the duplicate counts.the case where k<<n degrades the performance of the counting algo.in that case we can use hash table to map the numbers using an appropriate hash function.do not map the elements in table if they have been already mapped before.
- saumils1987 on September 13, 2010 Edit | Flag Reply