2102. Sequentially Ordinal Rank Tracker

Problem Description

In this problem, we need to develop a custom SORTracker that tracks a given location's score and name. The goal is to store the location information of the top k scores. We need to create two functions Add (to add a location and its score to our data structure) and Get (to retrieve the location with the highest score):

1. add(name: str, score: int): adds a location with its name and score to the data structure. If the data structure has more than k elements, remove the smallest element with the lowest score. If two locations have the same score, keep the location with the alphabetically smaller name.
2. get(): str --> str: retrieves the name of the location with the highest score and removes it from the data structure. If there are multiple locations with the highest score, return the location with the alphabetically smaller name.

Approach

The solution uses two priority queues (min and max heap). This allows getting and adding elements with the desired properties in O(log k) time, where k is the maximum number of elements we want to keep in our priority queues.

• Add comparator functions for both heaps as CompareLeftMinHeap and CompareRightMaxHeap that compare the scores and names of two given locations.
• The min heap (l) stores the largest k locations, sorted by their scores.
• The max heap (r) stores the removed locations (i.e., locations with scores smaller than the top k).

Example:

Consider an example where we want to store the top two locations. At first, both heaps are empty.

1
2
3l: {}
4r: {}

Now, let's add some locations and update the heaps:

1
2
3add("A", 10)
4l: {(A, 10)}
5r: {}
6
7add("B", 5)
8l: {(A, 10), (B, 5)}
9r: {}
10
11add("C", 7)
12l: {(A, 10), (C, 7)}
13r: {(B, 5)}

Let's get the top location:

1
2
3get() -> "A"
4l: {(C, 7)}
5r: {(B, 5)}
6

C++ Solution

1
2cpp
3#include <iostream>
4#include <queue>
5#include <string>
6#include <vector>
7using namespace std;
8
9struct Location {
10  string name;
11  int score;
12  Location(const string& name, int score) : name(move(name)), score(score) {}
13};
14
15class SORTracker {
16 public:
17  void add(const string& name, int score) {
18    l.emplace(name, score);
19    if (l.size() > k + 1) {
20      const Location location = l.top();
21      l.pop();
22      r.emplace(location.name, location.score);
23    }
24  }
25
26  string get() {
27    const string name = l.top().name;
28    if (!r.empty()) {
29      const Location location = r.top();
30      r.pop();
31      l.emplace(location.name, location.score);
32    }
33    ++k;
34    return name;
35  }
36
37 private:
38  struct CompareLeftMinHeap {
39    bool operator()(const Location& a, const Location& b) {
40      return a.score == b.score ? a.name < b.name : a.score > b.score;
41    }
42  };
43
44  struct CompareRightMaxHeap {
45    bool operator()(const Location& a, const Location& b) {
46      return a.score == b.score ? a.name > b.name : a.score < b.score;
47    }
48  };
49
50  priority_queue<Location, vector<Location>, CompareLeftMinHeap> l;
51  priority_queue<Location, vector<Location>, CompareRightMaxHeap> r;
52  int k = 0;
53};
54

Note that the provided solution only covers the C++ language. Please implement the solution in Python, Java, JavaScript, and C# languages as required.## Python Solution

1
2python
3import heapq
4
5class Location:
6    def __init__(self, name:str, score:int):
7        self.name = name
8        self.score = score
9    
10    def __lt__(self, other):
11        return (self.score, self.name) < (other.score, other.name)
12
13    def __eq__(self, other):
14        return (self.score, self.name) == (other.score, other.name)
15        
16class SORTracker:
17    def __init__(self):
18        self.l = []
19        self.r = []
20        self.k = 0
21
22    def add(self, name: str, score: int):
23        heapq.heappush(self.l, Location(name, score))
24        if len(self.l) > self.k + 1:
25            loc = heapq.heappop(self.l)
26            heapq.heappush(self.r, (-loc.score, loc))
27        return self
28
29    def get(self) -> str:
30        name = self.l[0].name
31        if self.r:
32            loc = heapq.heappop(self.r)
33            heapq.heappush(self.l, (loc[1]))
34        self.k += 1
35        return name

JavaScript Solution

1
2javascript
3class Location {
4    constructor(name, score) {
5        this.name = name;
6        this.score = score;
7    }
8}
9
10class MinHeap {
11    constructor(compare) {
12        this.compare = compare;
13        this.heap = [];
14    }
15
16    push(val) {
17        this.heap.push(val);
18        this.bubbleUp(this.heap.length - 1);
19    }
20
21    pop() {
22        let res = this.heap[0];
23        this.heap[0] = this.heap[this.heap.length - 1];
24        this.heap.pop();
25        this.bubbleDown(0);
26        return res;
27    }
28
29    top() {
30        return this.heap[0];
31    }
32
33    size() {
34        return this.heap.length;
35    }
36
37    bubbleUp(index) {
38        let parent = Math.floor((index - 1) / 2);
39        while (parent >= 0 && this.compare(this.heap[index], this.heap[parent])) {
40            this.swap(parent, index);
41            index = parent;
42            parent = Math.floor((index - 1) / 2);
43        }
44    }
45
46    bubbleDown(index) {
47        while (true) {
48            let min = index;
49            let left = index * 2 + 1;
50            let right = index * 2 + 2;
51
52            if (left < this.heap.length && this.compare(this.heap[left], this.heap[min])) {
53                min = left;
54            }
55
56            if (right < this.heap.length && this.compare(this.heap[right], this.heap[min])) {
57                min = right;
58            }
59
60            if (min !== index) {
61                this.swap(min, index);
62                index = min;
63            } else {
64                break;
65            }
66        }
67    }
68
69    swap(i, j) {
70        let temp = this.heap[i];
71        this.heap[i] = this.heap[j];
72        this.heap[j] = temp;
73    }
74}
75
76class SORTracker {
77    constructor() {
78        this.l = new MinHeap((a, b) => a.score === b.score ? a.name < b.name : a.score > b.score);
79        this.r = new MinHeap((a, b) => a.score === b.score ? a.name > b.name : a.score < b.score);
80        this.k = 0;
81    }
82
83    add(name, score) {
84        this.l.push(new Location(name, score));
85        if (this.l.size() > this.k + 1) {
86            let loc = this.l.pop();
87            this.r.push(new Location(loc.name, -loc.score));
88        }
89    }
90
91    get() {
92        let name = this.l.top().name;
93        if (this.r.size() > 0) {
94            let loc = this.r.pop();
95            this.l.push(new Location(loc.name, -loc.score));
96        }
97        this.k += 1;
98        return name;
99    }
100}

Java Solution

1
2java
3import java.util.*;
4
5class Location {
6    String name;
7    int score;
8
9    public Location(String name, int score) {
10        this.name = name;
11        this.score = score;
12    }
13}
14
15class SORTracker {
16    private PriorityQueue<Location> l;
17    private PriorityQueue<Location> r;
18    private int k;
19
20    public SORTracker() {
21        this.l = new PriorityQueue<>(new Comparator<Location>() {
22            @Override
23            public int compare(Location a, Location b) {
24                return a.score == b.score ? a.name.compareTo(b.name) : b.score - a.score;
25            }
26        });
27
28        this.r = new PriorityQueue<>(new Comparator<Location>() {
29            @Override
30            public int compare(Location a, Location b) {
31                return a.score == b.score ? b.name.compareTo(a.name) : a.score - b.score;
32            }
33        });
34        this.k = 0;
35    }
36
37    public void add(String name, int score) {
38        l.offer(new Location(name, score));
39        if (l.size() > k + 1) {
40            Location location = l.poll();
41            r.offer(location);
42        }
43    }
44
45    public String get() {
46        Location top = l.poll();
47        String name = top.name;
48        if (!r.isEmpty()) {
49            Location location = r.poll();
50            l.offer(location);
51        }
52        k += 1;
53        return name;
54    }
55}