Problem1 - API Request Throttling Solution

Topics -: 

• Greedy Algorithms

• Array Sorting

Overview

We need to repeatedly find the smallest available response time, add it to our total, and remove it along with its original adjacent neighbors. Instead of modifying the array directly, which is slow, we can sort the elements by their values while keeping track of their original indices. By iterating through this sorted list and using a boolean array to skip already removed elements, we efficiently simulate the entire process.

Approach

1. Sorting with Indices - To always process the minimum available response time efficiently, we pair each response time with its original array index. We then sort this list of pairs in ascending order based on the response time. This allows us to process the requests greedily without repeatedly scanning the array.

2. Simulating Removals-  We create a boolean array, removed, initially set to false for all indices. We iterate through our sorted list of requests. If the current request's original index is already marked as removed, we simply skip it. If it is not removed, we add its response time to our cumulative total and mark its index, as well as index - 1 and index + 1, as true in our removed array.

Code implementation

function getCumulativeResponseTime(n, responseTimes):
    // Store pairs of {responseTime, originalIndex}
    create an empty array of pairs 'reqs'
    for i from 0 to n - 1:
        reqs.push_back({responseTimes[i], i})
        
    // Sort ascending by response time
    sort(reqs)
    
    // Track which original indices have been removed
    create boolean array 'removed' of size n initialized to false
    totalTime = 0
    
    for each req in reqs:
        val = req.value
        idx = req.index
        
        // If this request hasn't been removed by a neighboring operation
        if removed[idx] == false:
            totalTime = totalTime + val
            
            // Mark the current and immediate original neighbors as removed
            removed[idx] = true
            if idx > 0:
                removed[idx - 1] = true
            if idx < n - 1:
                removed[idx + 1] = true
                
    return totalTime

Time Complexity

• Time: O(N log N) - Sorting the pairs takes O(N \log N) time. The subsequent linear scan and neighbor marking takes O(N) time.
• Space: O(N) - For storing the pairs of values and indices, as well as the boolean removed array.

Problem2 -

Gaming Platform Ranking System Solution

Topics Involved / Prerequisites

• Sorting & Custom Comparators
• Priority Queue (Min-Heap)
• Two Pointers / Grouping

Overview - : We must process participants in ascending order of their expertise so that we only pull scores from people with strictly lower expertise. By maintaining a min-heap of the highest points seen so far, we can instantly access the top count scores to sum up for the current participant. To handle participants with the exact same expertise, we evaluate all ties together before adding their points to the heap for future players.

Approach

1. Sorting by Expertise We bundle each participant's expertise, points, and original index together, and then sort the list in ascending order based on expertise. This guarantees that as we iterate forward, we only ever look at players with lower expertise levels.

2. Maintaining the Top Points (The Min-Heap) We use a Min-Heap to track the highest count points we've seen so far. If our heap exceeds count, the smallest point value will be at the top, making it O(\log C) to remove and keep our running sum accurate. Crucially, players with the exact same expertise level do not count toward each other. We use a nested loop to assign answers to all tied players before we push any of their points into the heap.

struct Player { expertise, points, id }

function getRankingPoints(p, expertise, points, count):
    create array 'players' of size p
    for i from 0 to p - 1:
        players[i] = {expertise[i], points[i], i}
        
    // Sort ascending by expertise
    sort(players) 
    
    create array 'ans' of size p initialized to 0
    create min-heap 'pq' 
    currentSum = 0
    i = 0
    
    while i < p:
        j = i
 
        while j < p AND players[j].expertise == players[i].expertise:
            ans[players[j].id] = currentSum
            j = j + 1
            
        // Add their points into the heap for future players
        for x from i to j - 1:
            pq.push(players[x].points)
            currentSum = currentSum + players[x].points
            
            // Keep only the top 'count' points
            if pq.size() > count:
                currentSum = currentSum - pq.top()
                pq.pop()
                
        i = j
        
    return ans

Time Complexity

• Time: O(N log N) - Sorting the participants takes O(N \log N). Pushing and popping from a heap of max size count takes O(\log C) for each element.
• Space: O(N) - For storing the bundled player structures, the answer array, and the priority queue.