Given a score board, implement two methods:
- int addUser(id, score); // return the rank of the added user.
- int findByRank(k); // return the id of the user which is rank k.
addUser(2, 30); // return 1 addUser(5, 10); // return 2 findByRank(2) // return 5 findByRank(1) // return 2 addUser(7, 20); // return 2 findByRank(2); // return 7
There are a lot of ways to solve this problems.
First approach could be to use priority queue to store the ranks O(log(n)) and take k-th eleement with klog(n)
Second could be to use augmented balanced binary search tree, again store with O(log(n)) and take k-the element with O(log(k))
For the interview I am not sure that you can implement balanced tree, maybe binary search tree with augmented data if the second approach is preferred.