Sequentially Ordinal Rank Tracker - Practice Coding Problems

Sequentially Ordinal Rank Tracker - Problem

A scenic location is represented by its name and attractiveness score, where name is a unique string among all locations and score is an integer. Locations can be ranked from the best to the worst. The higher the score, the better the location. If the scores of two locations are equal, then the location with the lexicographically smaller name is better.

You are building a system that tracks the ranking of locations with the system initially starting with no locations. It supports:

Adding scenic locations, one at a time.
Querying the ith best location of all locations already added, where i is the number of times the system has been queried (including the current query).

For example, when the system is queried for the 4th time, it returns the 4th best location of all locations already added.

Note: The test data are generated so that at any time, the number of queries does not exceed the number of locations added to the system.

Implement the SORTracker class:

SORTracker() Initializes the tracker system.
void add(string name, int score) Adds a scenic location with name and score to the system.
string get() Queries and returns the ith best location, where i is the number of times this method has been invoked (including this invocation).

Input & Output

Example 1 — Basic Operations

$ Input: [["SORTracker"],["add","bradford",2],["add","branford",3],["get"],["add","alps",2],["get"],["add","orland",2],["get"],["add","orlando",3],["get"],["add","alpine",2],["get"]]

› Output: [null,null,null,"branford",null,"alps",null,"bradford",null,"bradford",null,"bradford"]

💡 Note: Step by step: 1st get() returns best location (branford,3). 2nd get() returns 2nd best (alps,2 - lexicographically smaller than bradford,2). 3rd get() returns 3rd best (bradford,2). Subsequent queries continue from 3rd position.

Example 2 — Score Ties

$ Input: [["SORTracker"],["add","beach",5],["add","lake",5],["get"],["add","forest",3],["get"]]

› Output: [null,null,null,"beach",null,"beach"]

💡 Note: When scores are equal (beach,5 and lake,5), lexicographically smaller name wins. 1st get() returns "beach", 2nd get() returns "beach" again (still 2nd best overall).

Example 3 — Progressive Ranking

$ Input: [["SORTracker"],["add","mountain",10],["get"],["add","valley",8],["get"],["add","river",12],["get"]]

› Output: [null,null,"mountain",null,"mountain",null,"river"]

💡 Note: 1st get() returns only location (mountain,10). 2nd get() returns 2nd best (mountain,10). When river,12 is added, it becomes best, so 3rd get() returns river,12.

Constraints

1 ≤ name.length ≤ 10
-10⁵ ≤ score ≤ 10⁵
At most 4 × 10⁴ calls total to add and get

Visualization

Tap to expand

Understanding the Visualization

Input

Stream of add(name, score) and get() operations

Ranking

Locations ranked by score (desc), then name (asc)

Query

Return ith best location where i = query number

Key Takeaway

🎯 Key Insight: Use two heaps to efficiently maintain the current query position without sorting all locations repeatedly

Asked in

G Google 23 a Amazon 18 M Microsoft 15 A Apple 12

The key insight is to use two heaps to maintain a dynamic query position efficiently. The two heaps approach maintains O(log n) complexity per operation by keeping better locations in a max-heap and current/worse locations in a min-heap. Best approach: Two Heaps. Time: O((n + q) log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Two Heaps Approach	O((n + q) log n)	O(n)	Use min-heap and max-heap to maintain query position efficiently
Brute Force with Sorting	O(q × n log n)	O(n)	Store all locations and sort them on every query

Two Heaps Approach — Algorithm Steps

Initialize max-heap (left) and min-heap (right)
On add(): insert into appropriate heap based on query position
On get(): increment query count and rebalance heaps
Return top of min-heap (current query position)

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Create max-heap (left) and min-heap (right)

Add Locations

Insert into min-heap, rebalance if needed

Query

Move element from max-heap to min-heap, return top

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LOCATIONS 50000

typedef struct {
    char name[100];
    int score;
} Location;

typedef struct {
    Location heap[MAX_LOCATIONS];
    int size;
} Heap;

void heapifyUp(Heap* h, int idx, int isMax) {
    while (idx > 0) {
        int parent = (idx - 1) / 2;
        int shouldSwap = 0;
        
        if (isMax) {
            if (h->heap[idx].score > h->heap[parent].score ||
                (h->heap[idx].score == h->heap[parent].score && strcmp(h->heap[idx].name, h->heap[parent].name) < 0)) {
                shouldSwap = 1;
            }
        } else {
            if (h->heap[idx].score < h->heap[parent].score ||
                (h->heap[idx].score == h->heap[parent].score && strcmp(h->heap[idx].name, h->heap[parent].name) > 0)) {
                shouldSwap = 1;
            }
        }
        
        if (!shouldSwap) break;
        
        Location temp = h->heap[idx];
        h->heap[idx] = h->heap[parent];
        h->heap[parent] = temp;
        idx = parent;
    }
}

void heapifyDown(Heap* h, int idx, int isMax) {
    while (1) {
        int target = idx;
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;
        
        if (left < h->size) {
            int shouldReplace = 0;
            if (isMax) {
                if (h->heap[left].score > h->heap[target].score ||
                    (h->heap[left].score == h->heap[target].score && strcmp(h->heap[left].name, h->heap[target].name) < 0)) {
                    shouldReplace = 1;
                }
            } else {
                if (h->heap[left].score < h->heap[target].score ||
                    (h->heap[left].score == h->heap[target].score && strcmp(h->heap[left].name, h->heap[target].name) > 0)) {
                    shouldReplace = 1;
                }
            }
            if (shouldReplace) target = left;
        }
        
        if (right < h->size) {
            int shouldReplace = 0;
            if (isMax) {
                if (h->heap[right].score > h->heap[target].score ||
                    (h->heap[right].score == h->heap[target].score && strcmp(h->heap[right].name, h->heap[target].name) < 0)) {
                    shouldReplace = 1;
                }
            } else {
                if (h->heap[right].score < h->heap[target].score ||
                    (h->heap[right].score == h->heap[target].score && strcmp(h->heap[right].name, h->heap[target].name) > 0)) {
                    shouldReplace = 1;
                }
            }
            if (shouldReplace) target = right;
        }
        
        if (target == idx) break;
        
        Location temp = h->heap[idx];
        h->heap[idx] = h->heap[target];
        h->heap[target] = temp;
        idx = target;
    }
}

void push(Heap* h, Location loc, int isMax) {
    h->heap[h->size] = loc;
    h->size++;
    heapifyUp(h, h->size - 1, isMax);
}

Location pop(Heap* h, int isMax) {
    Location result = h->heap[0];
    h->heap[0] = h->heap[h->size - 1];
    h->size--;
    heapifyDown(h, 0, isMax);
    return result;
}

typedef struct {
    Heap maxHeap;
    Heap minHeap;
    int queryCount;
} SORTracker;

SORTracker* createTracker() {
    SORTracker* tracker = malloc(sizeof(SORTracker));
    tracker->maxHeap.size = 0;
    tracker->minHeap.size = 0;
    tracker->queryCount = 0;
    return tracker;
}

void add(SORTracker* tracker, char* name, int score) {
    Location loc;
    strcpy(loc.name, name);
    loc.score = score;
    
    push(&tracker->minHeap, loc, 0);
    
    if (tracker->minHeap.size > tracker->maxHeap.size + 1) {
        Location moved = pop(&tracker->minHeap, 0);
        push(&tracker->maxHeap, moved, 1);
    }
}

char* get(SORTracker* tracker) {
    tracker->queryCount++;
    
    if (tracker->maxHeap.size >= tracker->queryCount) {
        Location moved = pop(&tracker->maxHeap, 1);
        push(&tracker->minHeap, moved, 0);
    }
    
    return tracker->minHeap.heap[0].name;
}

int main() {
    printf("[null]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O((n + q) log n)

Each add and get operation takes O(log n) time

⚡ Linearithmic

Space Complexity

O(n)

Two heaps store all n locations

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Heaps Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler