FastPrepToken Bucket Request Decisions
Problems/Token Bucket Request Decisions

Token Bucket Request Decisions

Datadog logoDatadog● MediumFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: The firsthand report names a token-bucket interview task without its full prompt. This exercise supplies a strict, initially full token bucket with integer timestamps and refill rate, weighted request costs, ordered decisions and finite bounds. These rules are authored practice details; the original framework and exact callable interface are unknown. The named task matches the report at about 65%.

Apply a token-bucket rate limiter to requests in input order. At time zero the bucket holds capacity tokens. It gains refillRate tokens per time unit, up to capacity.

Before request i, refill for the time since the previous request, starting from time zero for the first request. If at least costs[i] tokens are available, accept the request and remove that many tokens. Otherwise reject it and remove no tokens. A rejected request still establishes the time used for the next refill. Requests at the same timestamp are processed in input order without an intervening refill.

Return one integer per request: 1 for accepted and 0 for rejected. A zero-cost request is always accepted. A cost above capacity can never be accepted. An empty request list returns an empty array.

Function

tokenBucketDecisions(capacity: int, refillRate: int, arrivalTimes: int[], costs: int[]) → int[]

Examples

Example 1

capacity = 5refillRate = 2arrivalTimes = [0,0,1,3]costs = [4,2,2,5]return = [1,0,1,1]

Start with 5 tokens. The first request uses 4, leaving 1. The next request at time zero needs 2 and is rejected. At time 1, refill to 3, accept cost 2, and keep 1. By time 3, refill reaches the cap of 5, so cost 5 is accepted.

Example 2

capacity = 3refillRate = 0arrivalTimes = [0,5,5,100]costs = [3,0,1,3]return = [1,1,0,0]

The first request empties the bucket. A zero-cost request is accepted, but the refill rate is zero, so later positive costs remain rejected even after long waits.

Example 3

capacity = 2refillRate = 3arrivalTimes = [0,10]costs = [3,2]return = [0,1]

Cost 3 exceeds the bucket capacity and is rejected. At time 10 the bucket is still capped at 2; cost 2 is accepted.

Constraints

  • 1 <= capacity <= 1000000000
  • 0 <= refillRate <= 1000000000
  • 0 <= arrivalTimes.length <= 200
  • arrivalTimes.length == costs.length
  • 0 <= arrivalTimes[i] <= 1000000000; arrival times are nondecreasing.
  • 0 <= costs[i] <= 1000000000

More Datadog problems

  • Query Log MatchPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
  • Delete a Filesystem TreePHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
  • Grouped-Query Attention Forward PassPHONE SCREEN · Seen Jun 2026
All Datadog interview questionsSee Datadog hiring insights
Saved
public int[] tokenBucketDecisions(int capacity, int refillRate, int[] arrivalTimes, int[] costs) {
    // Write your code here.
}
Checking account…