We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Servers That Handled Most Number of Requests

Number: 1710

Difficulty: Hard

Paid? No

Companies: Amazon, Capital One, Wish

Problem Description

Given k servers (numbered 0 to k-1) and a series of requests arriving at specific times with given execution durations, assign requests to servers based on a specific assignment strategy. Each request i is ideally assigned to server (i % k). If that server is busy, assign it to the next available server (cycling back to 0 if necessary). If no server is available when a request arrives, the request is dropped. The goal is to determine which server(s) handled the most requests.

Key Insights

  • Each server can process one request at a time.
  • Use an ordered set (or equivalent) to quickly find the next available server with an id >= (i % k). If none exists, wrap around and take the smallest available server.
  • A min-heap helps track busy servers by storing tuples of (finish time, server id).
  • Upon each request, first free all servers in the busy heap that have completed by the current arrival time.
  • Maintain a count array to track the number of requests served by each server.

Space and Time Complexity

Time Complexity: O(n log k), where n is the number of requests. Each request may involve log k operations when searching/updating the available servers and busy heap. Space Complexity: O(k + n) in the worst case for storing server states and request counts.

Solution

The solution involves two main data structures:

  1. An ordered set (or similar structure) of available server IDs. This allows quick access to the smallest available server ID not less than a given starting point. If no such server exists, it wraps around to the smallest server.
  2. A min-heap for busy servers, storing pairs (finish_time, server_id) to know when servers become free.

For each request:

  • Free all servers from the busy heap whose finish time is less than or equal to the arrival time of the current request.
  • Use the ordered set to find the server with the lowest id that is at least (i % k). If not found, choose the smallest server in the set.
  • If an available server is found, update its count, remove it from the available set, and push the pair (arrival_time + load, server_id) into the busy heap.
  • Finally, determine the maximum request count and return all servers with that count.

Code Solutions

import heapq
import bisect

def busiestServers(k, arrival, load):
    n = len(arrival)
    # Sorted list of available servers
    available = list(range(k))
    # Heap to store busy servers: (finish_time, server_id)
    busy = []
    # Count requests for each server
    requests_count = [0] * k

    for i, start in enumerate(arrival):
        # Free all servers whose finish time is <= current time
        while busy and busy[0][0] <= start:
            finish_time, server_id = heapq.heappop(busy)
            # Insert server_id back to available in sorted order
            bisect.insort(available, server_id)
        
        if not available:
            # No server available, drop the request
            continue
        
        # Calculate starting index for the search from i % k
        index = i % k
        # Find the leftmost server in available with id >= index
        pos = bisect.bisect_left(available, index)
        if pos == len(available):
            # If not found, wrap around to the first server in the list
            pos = 0
        
        server_id = available.pop(pos)
        # Update count and busy heap with new finish time
        requests_count[server_id] += 1
        finish_time = start + load[i]
        heapq.heappush(busy, (finish_time, server_id))
    
    # Determine the maximum request count
    max_requests = max(requests_count)
    result = [i for i in range(k) if requests_count[i] == max_requests]
    return result

# Example usage:
print(busiestServers(3, [1,2,3,4,5], [5,2,3,3,3]))  # Output: [1]
← Back to All Questions