Design a Score Board


  • 0
    Y

    Given a score board, implement two methods:

    1. int addUser(id, score); // return the rank of the added user.
    2. int findByRank(k); // return the id of the user which is rank k.

    Example:

    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
    

  • 1

    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.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.