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):
add(name: str, score: int)
: adds a location with its name and score to the data structure. If the data structure has more thank
elements, remove the smallest element with the lowest score. If two locations have the same score, keep the location with the alphabetically smaller name.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
andCompareRightMaxHeap
that compare the scores and names of two given locations. - The min heap (
l
) stores the largestk
locations, sorted by their scores. - The max heap (
r
) stores the removed locations (i.e., locations with scores smaller than the topk
).
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}
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.