Wireless Generation Interview Question
Software Engineer / DevelopersActually I don't think this answers the question at all for a few reasons. The question is to take an existing HashMap object that contains ID keys and Score values, and return a new HashMap with ID keys and Percentile values. Also percentile is defined as L/N where L is the # of scores below you, and N is the total # of scores.
Here's a possible algorithm to solve this:
1. Define a new class called StudentScore which contains a student id and a student score.
2. Read all entries of the hashmap into a StudentScore array that is the same size as the # of students in the hashmap
3. Sort the array by student scores (using quicksort this is n*log n average case and n^2 worst case).
4. Create a new hashmap to store percentiles
5. Iterate student score array from 0 -> length-1. Add student entries to new hashmap. Your key is the student id, and the value is i/(array.Length -1).
We'll do this the simple way. We can define a Hashset class in C++.
- xedgenes April 07, 2011