0

Fleet capacity after server id replacements

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Fleet capacity after server id replacements

Companies: Amazon

Difficulty: Medium

Problem statement

A service runs on a fleet of n servers. Each server has an integer id, and a server with id x can handle x requests at a time. The fleet's total capacity is the sum of all server ids.

Servers are swapped out for maintenance, one batch per day. On day j, every server whose id is currently replaced[j] is replaced by a server with id new_id[j]. Servers that received a new id on an earlier day count under their new id. If no server has id replaced[j], nothing changes that day.

Implement:

def get_total_requests(server: list[int], replaced: list[int], new_id: list[int]) -> list[int]

Return a list whose j-th entry is the fleet's total capacity at the end of day j.

Constraints

  • 1 <= n <= 10^5, 0 <= q = len(replaced) = len(new_id) <= 10^5
  • 1 <= server[i], replaced[j], new_id[j] <= 10^9
  • Totals can exceed 32 bits.

Example 1

server   = [4, 4, 9]
replaced = [4, 9, 2]
new_id   = [7, 2, 6]
output   = [23, 16, 20]

Day 1: both 4s become 7, so the fleet is [7, 7, 9] = 23. Day 2: the 9 becomes 2, giving [7, 7, 2] = 16. Day 3: the 2 becomes 6, giving [7, 7, 6] = 20.

Example 2

server   = [3, 3]
replaced = [3, 5]
new_id   = [5, 1]
output   = [10, 2]

The servers renamed to 5 on day 1 are replaced again on day 2.

An O(n * q) simulation is too slow at these limits. Aim for O(n + q).

Approach

The fleet is a multiset of server ids, and a server's id is also its capacity. Each day every server with id old becomes a server with id new, and we report the fleet's total capacity after the swap.

Brute force. Keep the array and, for each day, scan it, rewrite every matching entry, and sum the array. That is O(n) per day and O(n * q) overall. With n and q both up to 10^5 that is 10^10 steps, so it times out. It is still worth saying first, because it pins down the semantics: all servers with that id change, and the answer is the full sum after the change.

Optimal: counts by id plus a running total.

Two observations make each day O(1):

  1. Servers with the same id are interchangeable. We never need to know which positions hold id x, only how many servers have id x. So store count[id].
  2. The total only changes by the servers that were replaced. If c = count[old], the swap removes c * old and adds c * new. So total += c * (new - old).

Each day:

  • c = count.pop(old, 0). If c == 0, nothing changes; the total is the same as yesterday.
  • Otherwise count[new] += c and total += c * (new - old).
  • Append total to the answer.

The pop matters. After the swap no server has id old, so a later day that replaces old must do nothing. It also handles old == new cleanly: we pop c and add the same c back, and the total changes by 0.

Merging is the key behavior. If day 1 turns all 3s into 5s and day 2 turns all 5s into 1s, day 2 must also convert the servers that became 5 on day 1. The count map does this for free, because those servers were merged into count[5].

Invariants.

  • sum(count.values()) == n at all times (servers are renamed, never added or removed).
  • total == sum(id * c for id, c in count.items()) after every day.
  • No key in count has a zero value, so the map holds at most min(n, distinct ids seen) keys.

Python integers do not overflow. In Java or C++, use a 64-bit long for total and for c * (new - old): 10^5 servers with ids up to 10^9 reach 10^14.

Code

from collections import Counter
from typing import Dict, List


def get_total_requests(server: List[int], replaced: List[int], new_id: List[int]) -> List[int]:
    """Return the fleet's total capacity after each day's replacement."""
    if len(replaced) != len(new_id):
        raise ValueError("replaced and new_id must have the same length")

    count: Dict[int, int] = Counter(server)
    total = sum(server)
    answer: List[int] = []

    for old, new in zip(replaced, new_id):
        c = count.pop(old, 0)
        if c:
            count[new] = count.get(new, 0) + c
            total += c * (new - old)
        answer.append(total)
    return answer


class Fleet:
    """Online version: days arrive one at a time, with point queries."""

    def __init__(self, server: List[int]) -> None:
        self.count: Dict[int, int] = Counter(server)
        self.total = sum(server)

    def replace(self, old: int, new: int) -> int:
        c = self.count.pop(old, 0)
        if c:
            self.count[new] = self.count.get(new, 0) + c
            self.total += c * (new - old)
        return self.total

    def servers_with_id(self, server_id: int) -> int:
        return self.count.get(server_id, 0)


def brute_force(server: List[int], replaced: List[int], new_id: List[int]) -> List[int]:
    fleet = list(server)
    answer = []
    for old, new in zip(replaced, new_id):
        fleet = [new if s == old else s for s in fleet]
        answer.append(sum(fleet))
    return answer


if __name__ == "__main__":
    import random

    assert get_total_requests([4, 4, 9], [4, 9, 2], [7, 2, 6]) == [23, 16, 20]
    assert get_total_requests([1, 2, 3], [8], [5]) == [6]          # id not present
    assert get_total_requests([3, 3], [3, 5], [5, 1]) == [10, 2]   # merged servers move together
    assert get_total_requests([6], [6], [6]) == [6]                # same id
    assert get_total_requests([2, 2], [], []) == []                # no days
    for _ in range(300):
        s = [random.randint(1, 6) for _ in range(random.randint(1, 8))]
        q = random.randint(0, 8)
        r = [random.randint(1, 6) for _ in range(q)]
        w = [random.randint(1, 6) for _ in range(q)]
        assert get_total_requests(s, r, w) == brute_force(s, r, w)
    f = Fleet([4, 4, 9])
    assert f.replace(4, 7) == 23 and f.servers_with_id(7) == 2 and f.servers_with_id(4) == 0
    print("ok")

Complexity

  • Build: O(n) time and O(d) space, where d is the number of distinct starting ids.
  • Each day: O(1) expected time (two hash map operations and one multiply-add).
  • Whole run: O(n + q) time, O(n + q) space counting the output list. The map never holds more than n keys, because it only stores ids with a nonzero count.
  • Brute force, for comparison: O(n * q) time, O(n) extra space.

Test cases

  • server = [4, 4, 9], replaced = [4, 9, 2], new_id = [7, 2, 6] -> [23, 16, 20]. Day 1: both 4s become 7 (7 + 7 + 9). Day 2: the 9 becomes 2 (7 + 7 + 2). Day 3: the 2 becomes 6 (7 + 7 + 6).
  • server = [1, 2, 3], replaced = [8], new_id = [5] -> [6]. No server has id 8, so the total stays the same.
  • server = [3, 3], replaced = [3, 5], new_id = [5, 1] -> [10, 2]. Servers renamed on day 1 are replaced again on day 2.
  • server = [6], replaced = [6], new_id = [6] -> [6]. Replacing an id with itself changes nothing.
  • server = [2, 2], no days -> [].
  • Replacing a now-empty id: server = [1], replaced = [1, 1], new_id = [4, 9] -> [4, 4]. After day 1 there are no 1s left.
  • Large values: 10^5 servers of id 10^9, one day replacing 10^9 with 1 -> [10^5]. The intermediate sum is 10^14, so other languages need 64-bit integers.

Follow-ups

  1. Return which positions changed, or the final array. Keep count for totals, plus a union-find or "id -> list of indices" map. With index lists, merge the smaller list into the larger (small-to-large), so each index moves O(log n) times and the whole run is O(n log n + q). At the end, write each list's id back into its positions.
  2. Replace only some servers with a given id (for example, at most k of them, or only those in an index range). The count trick still works for "at most k": move min(k, count[old]). A range condition needs positions, so use a segment tree or a sorted structure per id, and the per-day cost becomes O(log n) times the number of servers moved.
  3. Capacity differs from the id (capacity(id) is a function or table). Keep the same counts and change the delta to c * (capacity(new) - capacity(old)). Nothing else changes.
  4. Queries interleaved with updates, such as "how many servers have id x" or "total capacity of servers with id in [lo, hi]". The first is count[x]. For range queries, keep a Fenwick tree over compressed ids (all ids are known offline from server, replaced and new_id). Each day is two point updates, O(log m).
  5. Undo the last day, or answer "what was the total on day j" after the fact. Store (old, new, c) per day. Undo pops count[new] -= c, restores count[old] = c, and reverses the total delta. Because c was the full count of old, the undo is exact.

Interviewer expectations

Mid-level (L4)

  • Explains the brute force and why O(n * q) is too slow at the stated limits.
  • Finds the count map and the running total, and gets the per-day update right.
  • Handles a missing id and tests with a small hand example.

Senior (L5)

  • Notices the merge behavior (servers renamed earlier are replaced again later) and that old must be cleared, including the old == new case.
  • States invariants, 64-bit overflow in other languages, and O(n + q) total cost without prompting.
  • Checks the fast version against the brute force on random inputs.

Staff (L6+)

  • Generalizes cleanly: capacity tables, range queries with a Fenwick tree over compressed ids, undo via a per-day log.
  • Handles the "which servers" follow-up with small-to-large merging or union-find, and explains the amortized bound.
  • Connects it to fleet operations: batch rollouts, partial rollouts, and auditing what changed per day.

Sign in to comment, vote or remix.