FastPrepDynamic Person Rankings

Dynamic Person Rankings

Google logoGoogle● HardNEW GRADONSITE INTERVIEW
Learn

Problem statement

Process operations on a ranking of people with unique names and unique integer scores.

  • ADD name score inserts a new person.
  • UPDATE name score changes an existing person's score.
  • GET rank returns the person at the one-based rank, where rank 1 is the highest score.

Every operation is valid, and scores remain unique after each update. Return one string name:score for each GET, in operation order.

Function

processRankings(operations: String[][]) → String[]

Examples

Example 1

operations = [["ADD","alice","90"],["ADD","bob","70"],["GET","1"],["UPDATE","bob","95"],["GET","1"],["GET","2"]]return = ["alice:90","bob:95","alice:90"]

Alice starts first. Updating Bob to 95 moves him above Alice.

Example 2

operations = [["ADD","x","-5"],["ADD","y","10"],["ADD","z","0"],["GET","2"]]return = ["z:0"]

Scores in descending order are 10,0,-5.

Example 3

operations = []return = []

No operations produce no rank-query results.

Constraints

  • 0 <= operations.length <= 200000.
  • Names contain 1 through 20 letters or digits.
  • Scores are signed 32-bit integers.
  • GET ranks are valid for the current number of people.

More Google problems

See Google hiring insights
public String[] processRankings(String[][] operations) {
    // Write your code here.
}
operations[["ADD","alice","90"],["ADD","bob","70"],["GET","1"],["UPDATE","bob","95"],["GET","1"],["GET","2"]]
expected["alice:90", "bob:95", "alice:90"]
Checking account…