Maximum stability of a server group: Frontier Interview's solution

Question: Maximum stability of a server group

Companies: Amazon

Difficulty: Medium

Problem statement

A cloud provider offers n servers. Server i has two positive integer scores: reliability[i] and availability[i].

A client deploys on any non-empty group of servers. A group is only as available as its weakest member, and its reliabilities add up. So the stability of a group is:

stability = min(availability of servers in the group) * sum(reliability of servers in the group)

Implement get_max_stability(reliability, availability) that returns the largest stability any group can reach. The value can be very large, so return it modulo 10^9 + 7. Pick the group by its true stability, not by the reduced value.

Constraints

1 <= n <= 10^5
len(reliability) == len(availability) == n
1 <= reliability[i], availability[i] <= 10^6

Example 1

reliability  = [2, 3, 1]
availability = [5, 1, 4]
output: 12

Choose servers 0 and 2. The minimum availability is 4 and the reliabilities sum to 3, so the stability is 12. Server 0 alone scores 10, and all three servers score only 6.

Example 2

reliability  = [10, 1]
availability = [1, 100]
output: 100

Server 1 alone scores 100 * 1 = 100. Adding server 0 drops the minimum availability to 1, for a score of 11.

Approach

The score of a group is min(availability) * sum(reliability). The minimum
is the hard part. Fix it instead of searching for it.

Brute force. Try every non-empty subset and score it. That is
O(2^n * n) and only works for tiny inputs. It is still worth saying out
loud, because it gives you a checker for the fast version.

Fix the bottleneck. Suppose the weakest server in the chosen group has
availability a. Then every server with availability >= a can join
without lowering the minimum. Every reliability is positive, so each one
only adds to the sum. So for a fixed a, the best group is all servers
with availability >= a, and its score is a * (sum of their reliabilities).

There are at most n distinct values of a. Sort the servers by
availability, highest first, and keep a running sum of reliability. When
you reach server i, the running sum covers every server at least as
available as it, so availability[i] * running_sum is the score for that
bottleneck. The answer is the largest of these.

Ties. With equal availabilities, the score at the last server of a tie
group already counts the whole group. Earlier scores in the group are
smaller, so they never win, and no special handling is needed.

Modulo. The true maximum can reach about 10^6 * 10^5 * 10^6 = 10^17.
Compare the exact values and take the modulo only once at the end. If you
reduce first, the comparison breaks: a larger product can have a smaller
remainder. In Python this is free. In Java or C++ the product still fits
in a signed 64-bit integer, so use long and reduce at the end.

Invariant. After processing the first i + 1 servers in sorted order,
running_sum equals the total reliability of every server whose
availability is at least availability[i], counting ties already seen.

Code

from heapq import heappush, heappop
from itertools import combinations
from typing import List, Optional

MOD = 10**9 + 7


def get_max_stability(reliability: List[int], availability: List[int]) -> int:
    """Max over non-empty subsets of min(availability) * sum(reliability), mod 1e9+7."""
    if not reliability or len(reliability) != len(availability):
        raise ValueError("need two non-empty arrays of equal length")
    order = sorted(range(len(reliability)), key=lambda i: availability[i], reverse=True)
    running_sum = 0
    best = 0
    for i in order:
        running_sum += reliability[i]
        best = max(best, availability[i] * running_sum)  # exact, no modulo yet
    return best % MOD


def get_max_stability_at_most_k(
    reliability: List[int], availability: List[int], k: int
) -> int:
    """Follow-up: choose at most k servers. Keep the k largest reliabilities seen."""
    order = sorted(range(len(reliability)), key=lambda i: availability[i], reverse=True)
    heap: List[int] = []  # min-heap of chosen reliabilities
    running_sum = 0
    best = 0
    for i in order:
        heappush(heap, reliability[i])
        running_sum += reliability[i]
        if len(heap) > k:
            running_sum -= heappop(heap)
        # Server i may have been popped; then a group with a higher minimum
        # was already scored with at least this sum, so the value is a lower bound.
        best = max(best, availability[i] * running_sum)
    return best % MOD


def brute_force(reliability: List[int], availability: List[int], k: Optional[int] = None) -> int:
    n = len(reliability)
    limit = n if k is None else k
    best = 0
    for size in range(1, limit + 1):
        for group in combinations(range(n), size):
            score = min(availability[i] for i in group) * sum(reliability[i] for i in group)
            best = max(best, score)
    return best % MOD


if __name__ == "__main__":
    import random

    assert get_max_stability([2, 3, 1], [5, 1, 4]) == 12
    assert get_max_stability([7], [9]) == 63
    assert get_max_stability([1, 1, 1], [4, 4, 4]) == 12
    assert get_max_stability([10, 1], [1, 100]) == 100
    big = get_max_stability([10**6] * 10**5, [10**6] * 10**5)
    assert big == (10**6 * 10**11) % MOD
    assert get_max_stability_at_most_k([2, 10, 3, 1, 5, 8], [5, 4, 3, 9, 7, 2], 2) == 60

    for _ in range(500):
        n = random.randint(1, 8)
        rel = [random.randint(1, 20) for _ in range(n)]
        av = [random.randint(1, 20) for _ in range(n)]
        assert get_max_stability(rel, av) == brute_force(rel, av)
        k = random.randint(1, n)
        assert get_max_stability_at_most_k(rel, av, k) == brute_force(rel, av, k)
    print("all tests passed")

Complexity

get_max_stability: O(n log n) time for the sort, then one O(n)
pass. O(n) extra space for the sorted index order.
get_max_stability_at_most_k: O(n log n) for the sort plus
O(n log k) for the heap. O(n + k) space.
Brute force: O(2^n * n) time. Use it only to check small cases.

Test cases

reliability = [2, 3, 1], availability = [5, 1, 4] gives 12.
Bottleneck 5: 5 * 2 = 10. Bottleneck 4: 4 * (2 + 1) = 12.
Bottleneck 1: 1 * 6 = 6.
One server, [7], [9] gives 63.
All availabilities equal, [1, 1, 1], [4, 4, 4] gives 12
(take every server).
One very available server beats a reliable one: [10, 1], [1, 100]
gives 100, not 11.
10^5 servers, all values 10^6: the exact score is 10^17, so the
answer is 10^17 mod (10^9 + 7). This checks that you reduce only at
the end.
At most k = 2: reliability = [2, 10, 3, 1, 5, 8],
availability = [5, 4, 3, 9, 7, 2] gives 60 (servers with
availability 4 and 7, reliability 10 + 5, minimum 4).
Mismatched or empty arrays raise an error. Say this out loud in the
interview even if the platform guarantees valid input.

Follow-ups

At most k servers. For a fixed bottleneck you now want the k
largest reliabilities among the servers at least that available. Walk
in the same sorted order and keep a min-heap of size k. When it grows
past k, drop the smallest. This is the same shape as LeetCode 1383
(maximum performance of a team).
Exactly k servers. Same sweep, but only score once the heap holds
k items, and the current server must stay in the group. Push it, pop
the smallest other item if needed, or score as
availability[i] * (reliability[i] + sum of the top k-1 seen before i).
Return the chosen servers, not just the score. Remember the index in
sorted order where the best score happened. The group is every server up
to that index (or the heap contents at that moment for the k version).
Reliability can be zero or negative. Then "take everything at least
as available" is no longer right. For a fixed bottleneck, add only the
positive reliabilities, and always include the bottleneck server itself
even if its reliability is not positive.
Servers arrive as a stream and you answer after each one. The answer
for a bottleneck a is a * (sum of reliability with availability >= a).
A new server adds its reliability to every bottleneck at or below its
availability. Coordinate-compress availabilities, use a segment tree
with range add and "max of a * sum" kept per node (Li Chao or kinetic
segment tree), or rebuild in batches if updates are rare.

Interviewer expectations

Mid-level (L4)

Explains the brute force, then sees that fixing the minimum makes the
choice obvious.
Writes the sort plus running sum correctly, with ties handled.
Knows the product can overflow 32-bit and reduces modulo only at the end.

Senior (L5)

Proves why taking every server at or above the bottleneck is optimal
(positive reliabilities only add).
Explains why modulo before comparing gives wrong answers.
Solves the at-most-k version with a heap without much prompting and
states its complexity.
Tests against a brute force on small random inputs.

Staff (L6+)

Separates which assumptions the greedy depends on (positive values,
no size limit) and adapts quickly when each one is removed.
Discusses the streaming version and the data-structure trade-offs.
Connects the problem to real capacity planning: the weakest member
limits the whole fleet, so the useful question is which floor to set.