Autoscale a Server Fleet from Throughput Readings
Company: Two Sigma
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You run a service on a fleet of identical servers behind a load balancer. Each server can handle at most `limit` units of throughput. A monitoring system samples the service's total throughput at regular intervals, producing a chronological array `readings`, where `readings[i]` is the total observed throughput during the `i`-th interval.
The fleet starts with exactly **1** server. Process the readings in order. After observing each reading:
- If the reading is less than or equal to the fleet's current total capacity (`number of servers * limit`), do nothing.
- Otherwise, open the **minimum** number of new servers needed so that the total capacity becomes greater than or equal to the reading. New servers are available immediately.
Servers are never shut down once opened, so the fleet size never decreases.
Return an array `fleet` of the same length as `readings`, where `fleet[i]` is the number of servers in the fleet **after** processing `readings[i]`.
### Example
Input: `limit = 10`, `readings = [5, 25, 18, 40, 32]`
| Step | Reading | Capacity before | Action | Servers after |
|------|---------|-----------------|--------|---------------|
| 0 | 5 | 1 × 10 = 10 | none (5 ≤ 10) | 1 |
| 1 | 25 | 1 × 10 = 10 | open 2 servers (capacity 30 ≥ 25) | 3 |
| 2 | 18 | 3 × 10 = 30 | none (18 ≤ 30) | 3 |
| 3 | 40 | 3 × 10 = 30 | open 1 server (capacity 40 ≥ 40) | 4 |
| 4 | 32 | 4 × 10 = 40 | none (32 ≤ 40) | 4 |
Output: `[1, 3, 3, 4, 4]`
### Constraints
- `1 <= readings.length <= 10^5`
- `1 <= limit <= 10^9`
- `0 <= readings[i] <= 10^13` (values may exceed 32-bit integer range)
- The answer array's values fit in a 64-bit integer.
Quick Answer: This question evaluates algorithmic implementation skills and numeric reasoning, focusing on stateful simulation of autoscaling behavior and capacity arithmetic under streaming throughput readings.
You run a service on a fleet of identical servers behind a load balancer. Each server can handle at most `limit` units of throughput. A monitoring system samples the service's total throughput at regular intervals, producing a chronological array `readings`, where `readings[i]` is the total observed throughput during the `i`-th interval.
The fleet starts with exactly **1** server. Process the readings in order. After observing each reading:
- If the reading is less than or equal to the fleet's current total capacity (`number of servers * limit`), do nothing.
- Otherwise, open the **minimum** number of new servers needed so that the total capacity becomes greater than or equal to the reading. New servers are available immediately.
Servers are never shut down once opened, so the fleet size never decreases.
Return an array `fleet` of the same length as `readings`, where `fleet[i]` is the number of servers in the fleet **after** processing `readings[i]`.
### Example
Input: `limit = 10`, `readings = [5, 25, 18, 40, 32]`
| Step | Reading | Capacity before | Action | Servers after |
|------|---------|-----------------|--------|---------------|
| 0 | 5 | 1 x 10 = 10 | none (5 <= 10) | 1 |
| 1 | 25 | 1 x 10 = 10 | open 2 servers (capacity 30 >= 25) | 3 |
| 2 | 18 | 3 x 10 = 30 | none (18 <= 30) | 3 |
| 3 | 40 | 3 x 10 = 30 | open 1 server (capacity 40 >= 40) | 4 |
| 4 | 32 | 4 x 10 = 40 | none (32 <= 40) | 4 |
Output: `[1, 3, 3, 4, 4]`
Constraints
- 1 <= readings.length <= 10^5
- 1 <= limit <= 10^9
- 0 <= readings[i] <= 10^13 (values may exceed 32-bit integer range)
- The answer array's values fit in a 64-bit integer.
Examples
Input: (10, [5, 25, 18, 40, 32])
Expected Output: [1, 3, 3, 4, 4]
Explanation: The worked example. Reading 25 forces 3 servers (capacity 30 >= 25); reading 40 forces 4 servers; sub-capacity readings 18 and 32 leave the fleet unchanged.
Input: (5, [0])
Expected Output: [1]
Explanation: A zero reading is <= the starting capacity of 1 x 5, so no servers are added; the fleet stays at its initial size of 1.
Hints
- The fleet size never decreases, so at each step the new size is the larger of the current size and whatever this reading demands.
- The minimum servers a reading `r` demands on its own is `ceil(r / limit)`. Combine that with the current size using a max.
- Compute the ceiling of a division without floats: `(r + limit - 1) // limit`. Because `limit >= 1`, this is always well-defined.
- Only recompute when `r` exceeds the current capacity `servers * limit`; otherwise carry the previous fleet size forward. Use 64-bit integers to avoid overflow.