Sequentially Ordinal Rank Tracker

Hard
2098.

Sequentially Ordinal Rank Tracker

HardDesignHeap (Priority Queue)Ordered SetGoogle

Sequentially Ordinal Rank Tracker is a hard coding problem on heap and ordered set, asked in Google interviews.

A travel site ranks scenic locations. Each location has a unique name and a score; a location ranks better than another if its score is higher, or if the scores are equal and its name is lexicographically smaller.

Locations are added one at a time, and the site keeps asking for the next one down the ranking: the first get returns the best location, the second get the 2nd best, and so on — each counted over all locations added up to that moment.

Write the class SORTracker:

  • SORTracker() starts with no locations.
  • void add(String name, int score) adds a location.
  • String get() returns the name of the i-th best location added so far, where i is the number of times get has been called, including this call.

get is never called more times than the number of locations added so far.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input
["SORTracker","add","add","get","add","get","add","get","add","get","add","get"] [[],["ooty",4],["goa",3],[],["agra",4],[],["kochi",2],[],["delhi",5],[],["pune",3],[]]
Output
[null,null,null,"ooty",null,"ooty",null,"goa",null,"goa",null,"pune"]
Explanation
First get: ooty is best. After agra (also 4, smaller name) the ranking is agra, ooty, goa, so the 2nd is ooty. Kochi (2) makes goa 3rd. Delhi (5) goes on top: delhi, agra, ooty, goa, kochi — the 4th is goa. Pune ties goa at 3 but comes after it by name, so it is 5th.

Example 2

Input
["SORTracker","add","add","get","get"] [[],["z",1],["a",1],[],[]]
Output
[null,null,null,"a","z"]
Explanation
Equal scores are ranked by name: "a" before "z".

Constraints

  • name consists of lowercase English letters and is unique among all added locations
  • 1 <= name.length <= 10
  • 1 <= score <= 10^5
  • At most 4 * 10^4 calls are made in total to add and get
  • get is called at most as many times as add, counting only the calls made so far
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 */
var SORTracker = function() {
    
};

/**
 * @param {string} name
 * @param {number} score
 * @return {void}
 */
SORTracker.prototype.add = function(name, score) {
    
};

/**
 * @return {string}
 */
SORTracker.prototype.get = function() {
    
};

Sign in to run your own test cases

Sign in

Sequentially Ordinal Rank Tracker — Problem & Solution

Sequentially Ordinal Rank Tracker solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Sequentially Ordinal Rank Tracker is a hard coding problem on heap and ordered set, asked in Google interviews.

  • Difficulty: Hard
  • Topics: Heap, Ordered Set
  • Asked at: Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A travel site ranks scenic locations. Each location has a unique name and a score; a location ranks better than another if its score is higher, or if the scores are equal and its name is lexicographically smaller.

Locations are added one at a time, and the site keeps asking for the next one down the ranking: the first get returns the best location, the second get the 2nd best, and so on — each counted over all locations added up to that moment.

Write the class SORTracker:

  • SORTracker() starts with no locations.
  • void add(String name, int score) adds a location.
  • String get() returns the name of the i-th best location added so far, where i is the number of times get has been called, including this call.

get is never called more times than the number of locations added so far.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input: ["SORTracker","add","add","get","add","get","add","get","add","get","add","get"]
[[],["ooty",4],["goa",3],[],["agra",4],[],["kochi",2],[],["delhi",5],[],["pune",3],[]]
Output: [null,null,null,"ooty",null,"ooty",null,"goa",null,"goa",null,"pune"]
Explanation: First get: ooty is best. After agra (also 4, smaller name) the ranking is agra, ooty, goa, so the 2nd is ooty. Kochi (2) makes goa 3rd. Delhi (5) goes on top: delhi, agra, ooty, goa, kochi — the 4th is goa. Pune ties goa at 3 but comes after it by name, so it is 5th.

Example 2

Input: ["SORTracker","add","add","get","get"]
[[],["z",1],["a",1],[],[]]
Output: [null,null,null,"a","z"]
Explanation: Equal scores are ranked by name: "a" before "z".

Constraints

  • name consists of lowercase English letters and is unique among all added locations
  • 1 <= name.length <= 10
  • 1 <= score <= 10^5
  • At most 4 * 10^4 calls are made in total to add and get
  • get is called at most as many times as add, counting only the calls made so far

Hints for Sequentially Ordinal Rank Tracker

  1. Hint 1

    Sorting on every get is too slow. Notice that the rank asked for only ever moves forward by one.

  2. Hint 2

    Split the locations in two: the i best seen so far (where i = gets so far), and everything else. You only ever need the worst of the first group and the best of the second.

  3. Hint 3

    Two heaps: a heap of the top group with its worst on top, and a heap of the rest with its best on top. add pushes into the top group and then moves that group's worst across; get moves the best of the rest into the top group and returns it.

How to solve Sequentially Ordinal Rank Tracker

Keep the locations split into the i best so far (i = number of get calls) and the rest, each in a heap ordered so that the boundary element is on top: the worst of the best group, and the best of the rest. Each operation moves one element across the boundary.

Approach

  1. Use "better" = higher score, or equal score and smaller name.
  2. best: a heap whose top is the worst location in it. rest: a heap whose top is the best location in it. Both start empty.
  3. add(name, score): push the location into best, then pop best's worst and push it into rest. best keeps its size.
  4. get(): pop the best location of rest, push it into best, and return its name.

Why it works

Invariant: best holds exactly the i best locations added so far and rest all others. When a location is added, the i + 1 candidates in best lose their worst one to rest, so best again holds the i best. On a get, the (i + 1)-th best location overall is the best one outside the top i, i.e. the top of rest; moving it makes best hold the i + 1 best — and it is exactly the location the call must return.

Complexity

  • Time — O(log n) per call
  • Space — O(n)

Pitfalls

  • Each heap needs the full two-key order — by score, then by name — and the two heaps need opposite orders.
  • After an add the answer of the next get may change even though i does not: always route a new location through best so a better newcomer pushes the old boundary element out.

Reference solution

Python

import heapq

class Worst:  # heap entry whose smallest element is the worst-ranked location
    __slots__ = ("score", "name")

    def __init__(self, score, name):
        self.score, self.name = score, name

    def __lt__(self, other):
        return self.score < other.score or (self.score == other.score and self.name > other.name)

class SORTracker:

    def __init__(self):
        self.best = []  # the i best so far; top = the worst of them
        self.rest = []  # everything else as (-score, name); top = the best of them

    def add(self, name: str, score: int) -> None:
        w = heapq.heappushpop(self.best, Worst(score, name))
        heapq.heappush(self.rest, (-w.score, w.name))

    def get(self) -> str:
        s, name = heapq.heappop(self.rest)
        heapq.heappush(self.best, Worst(-s, name))
        return name

Java

class SORTracker {
    private static final class Loc {
        final String name;
        final int score;
        Loc(String name, int score) { this.name = name; this.score = score; }
    }

    // RANK: better locations first — higher score, then smaller name.
    private static final Comparator<Loc> RANK = (a, b) -> a.score != b.score ? Integer.compare(b.score, a.score) : a.name.compareTo(b.name);
    private final PriorityQueue<Loc> best = new PriorityQueue<>(RANK.reversed()); // top = worst of the i best
    private final PriorityQueue<Loc> rest = new PriorityQueue<>(RANK);            // top = best of the rest

    public SORTracker() {
    }

    public void add(String name, int score) {
        best.offer(new Loc(name, score));
        rest.offer(best.poll());
    }

    public String get() {
        Loc x = rest.poll();
        best.offer(x);
        return x.name;
    }
}

C++

class SORTracker {
    // better(a, b): a ranks above b — higher score, then smaller name.
    struct Loc { int score; string name; };
    struct WorstOnTop { bool operator()(const Loc& a, const Loc& b) const {   // a is "less" when a is better
        return a.score > b.score || (a.score == b.score && a.name < b.name); } };
    struct BestOnTop { bool operator()(const Loc& a, const Loc& b) const {    // a is "less" when a is worse
        return a.score < b.score || (a.score == b.score && a.name > b.name); } };
    priority_queue<Loc, vector<Loc>, WorstOnTop> best; // the i best so far
    priority_queue<Loc, vector<Loc>, BestOnTop> rest;  // everything else
public:
    SORTracker() {}

    void add(string name, int score) {
        best.push({score, name});
        rest.push(best.top());
        best.pop();
    }

    string get() {
        Loc x = rest.top();
        rest.pop();
        best.push(x);
        return x.name;
    }
};

JavaScript

// better(a, b): a ranks above b — higher score, or equal score and smaller name.
function sorBetter(a, b) { return a.score > b.score || (a.score === b.score && a.name < b.name); }

// A binary heap whose top is the element for which first(top, x) holds against every x.
function SorHeap(first) { this.a = []; this.first = first; }
SorHeap.prototype.push = function(x) {
    var a = this.a, i = a.length;
    a.push(x);
    while (i > 0) {
        var p = (i - 1) >> 1;
        if (!this.first(x, a[p])) break;
        a[i] = a[p]; i = p;
    }
    a[i] = x;
};
SorHeap.prototype.pop = function() {
    var a = this.a, top = a[0], last = a.pop();
    if (a.length > 0) {
        var i = 0, n = a.length;
        for (;;) {
            var l = 2 * i + 1, r = l + 1, m = i, mv = last;
            if (l < n && this.first(a[l], mv)) { m = l; mv = a[l]; }
            if (r < n && this.first(a[r], mv)) { m = r; }
            if (m === i) break;
            a[i] = a[m]; i = m;
        }
        a[i] = last;
    }
    return top;
};

var SORTracker = function() {
    this.best = new SorHeap(function(x, y) { return sorBetter(y, x); }); // top = worst of the i best
    this.rest = new SorHeap(sorBetter);                                    // top = best of the rest
};

SORTracker.prototype.add = function(name, score) {
    this.best.push({ name: name, score: score });
    this.rest.push(this.best.pop());
};

SORTracker.prototype.get = function() {
    var x = this.rest.pop();
    this.best.push(x);
    return x.name;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 106 heap problems · the whole catalogue

Learn the technique: Heaps and Priority Queues