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 thei-th best location added so far, whereiis the number of timesgethas 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 locations1 <= name.length <= 101 <= score <= 10^5At most 4 * 10^4 calls are made in total to add and getget is called at most as many times as add, counting only the calls made so far
Hints for Sequentially Ordinal Rank Tracker
Hint 1
Sorting on every
getis too slow. Notice that the rank asked for only ever moves forward by one.Hint 2
Split the locations in two: the
ibest seen so far (wherei= gets so far), and everything else. You only ever need the worst of the first group and the best of the second.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.
addpushes into the top group and then moves that group's worst across;getmoves 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
- Use "better" = higher score, or equal score and smaller name.
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.add(name, score): push the location intobest, then popbest's worst and push it intorest.bestkeeps its size.get(): pop the best location ofrest, push it intobest, 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
addthe answer of the nextgetmay change even thoughidoes not: always route a new location throughbestso 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 nameJava
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