Stop a Burst Without Stopping Everyone.

Today’s challenge

Build the solution

Write a function called rate_limit(times_ms, capacity, refill_ms).

Return contract: A dictionary with accepted and rejected, each a list of zero-based request indexes.

Input bounds: 0–500 timestamps in nondecreasing order; timestamps 0–1,000,000; capacity 1–20; refill_ms 1–10,000.

Keep the supplied driver below your implementation. It reads one JSON object and prints your return value as JSON. The driver may also probe the behaviour described above; those probe fields are part of the test input.

Start at time zero with capacity tokens. One token is added at each global time refill_ms, 2 * refill_ms, and so on, up to capacity.
Before each request, apply every refill due by its timestamp, then accept it if a token is available and consume one token.
Process requests in their given order, including requests with identical timestamps. Report accepted and rejected request indexes.

The Twist: A long idle period cannot store more than capacity tokens. Refill timing is anchored at zero, not at the last accepted request.

Sample

Input

{"capacity":2,"refill_ms":10,"times_ms":[0,0,0,9,10,10,20]}

Expected output

{"accepted":[0,1,4,6],"rejected":[2,3,5]}

day-5.py

Python 3

def rate_limit(times_ms, capacity, refill_ms):
    # Implement the challenge here. Keep the input/output driver below.
    raise NotImplementedError("Implement this challenge")


if __name__ == "__main__":
    import json
    raw_input = input()
    payload = json.loads(raw_input)
    original_payload = json.loads(raw_input)
    arguments = {key: payload[key] for key in ['times_ms', 'capacity', 'refill_ms'] if key in payload}
    result = rate_limit(**arguments)
    print(json.dumps(result, sort_keys=True, separators=(",", ":"), allow_nan=False))

Tab inserts four spaces. Press Escape, then Tab to move to the next control, or Shift+Tab to move to the previous control.

Output

Run your code to see the result here.