Token bucket algorithm in Rest API - Practice Problems & Coding Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of token bucket refill calculation

Consider a token bucket with capacity 10 tokens and refill rate 2 tokens per second. Initially, the bucket is full. After 3 seconds, how many tokens are in the bucket if 5 tokens were consumed immediately after start?

Rest API

capacity = 10
refill_rate = 2  # tokens per second
initial_tokens = 10
consumed = 5
elapsed_time = 3

# Calculate tokens after elapsed time
new_tokens = min(capacity, initial_tokens - consumed + refill_rate * elapsed_time)
print(new_tokens)

A 10

B 9

C 11

D 7

💡 Hint

Remember the bucket cannot hold more tokens than its capacity.

After consuming 5 tokens, 5 remain. After 3 seconds, 2 tokens per second refill adds 6 tokens. 5 + 6 = 11, but capacity is 10, so final tokens = 10.

🧠 Conceptual

intermediate

Understanding token bucket burst capacity

Which statement best describes the burst capacity in a token bucket algorithm?

A The maximum number of tokens that can be consumed instantly without waiting.

B The rate at which tokens are added to the bucket per second.

C The minimum number of tokens required to start the bucket.

D The time interval between token refills.

💡 Hint

Think about how many requests can be handled at once without delay.

Burst capacity is the bucket's maximum token count, allowing that many requests to be served immediately.

🔧 Debug

advanced

Identify the error in token bucket token consumption code

What error will this code produce when trying to consume tokens from the bucket? ```python capacity = 5 tokens = 3 consume = 4 if tokens >= consume: tokens -= consume else: print("Not enough tokens") ```

A No error, tokens become -1

B Prints 'Not enough tokens' and tokens remain 3

C Raises a TypeError

D SyntaxError due to missing colon

💡 Hint

Check the condition and what happens when tokens are insufficient.

Since tokens (3) are less than consume (4), the else branch runs, printing the message and tokens stay unchanged.

📝 Syntax

advanced

Syntax error in token bucket refill function

Which option contains the correct syntax for a Python function that refills tokens in a bucket?

Rest API

def refill_tokens(current_tokens, capacity, refill_rate, elapsed_time):
    new_tokens = current_tokens + refill_rate * elapsed_time
    if new_tokens > capacity:
        return capacity
    return new_tokens

A

def refill_tokens(current_tokens, capacity, refill_rate, elapsed_time):
    new_tokens = current_tokens + refill_rate * elapsed_time
    if new_tokens > capacity:
    return capacity
    return new_tokens

B

def refill_tokens(current_tokens, capacity, refill_rate, elapsed_time)
    new_tokens = current_tokens + refill_rate * elapsed_time
    if new_tokens > capacity:
        return capacity
    return new_tokens

C

def refill_tokens(current_tokens, capacity, refill_rate, elapsed_time):
    new_tokens = current_tokens + refill_rate * elapsed_time
    if new_tokens > capacity
        return capacity
    return new_tokens

D

def refill_tokens(current_tokens, capacity, refill_rate, elapsed_time):
    new_tokens = current_tokens + refill_rate * elapsed_time
    if new_tokens > capacity:
        return capacity
    return new_tokens

💡 Hint

Check for colons and indentation.

Option D has correct function definition, colons, and proper indentation.

🚀 Application

expert

Calculate tokens after multiple consumption and refill events

A token bucket has capacity 8 tokens and refills at 1 token per second. Initially, it is full. The following events happen: - At 0 seconds, 3 tokens are consumed. - At 2 seconds, 4 tokens are consumed. - At 5 seconds, no consumption. What is the number of tokens in the bucket at 5 seconds?

A 4

B 7

C 6

D 5

💡 Hint

Calculate tokens after each event considering refill and consumption.

Start: 8 tokens At 0s consume 3 → tokens = 5 Refill 2s *1 = 2 tokens → tokens = min(8,5+2)=7 At 2s consume 4 → tokens = 3 Refill 3s *1 = 3 tokens → tokens = min(8,3+3)=6 At 5s no consumption, tokens = 6 But careful: consumption at 2s happens after refill at 2s? Usually consumption happens at event time, so refill from 0 to 2s is 2 tokens, then consume 4 tokens. Tokens at 2s after refill: 7, after consumption: 3 From 2s to 5s refill 3 tokens → 3+3=6 tokens at 5s. So final tokens = 6.

Practice

1.

What is the main purpose of the token bucket algorithm in REST APIs?

easy

A. To encrypt API responses

B. To store user data securely

C. To control the rate of incoming requests by using tokens

D. To manage database connections

Solution

1. Step 1: Understand the token bucket algorithm concept

   The token bucket algorithm limits how many requests can be processed by controlling tokens that refill over time.

2. Step 2: Identify the purpose in REST APIs

   It helps prevent too many requests at once, protecting the server from overload.

3. Final Answer:

   To control the rate of incoming requests by using tokens -> Option C

4. Quick Check:

   Token bucket controls request rate = C [OK]

Hint: Token bucket limits request rate using tokens [OK]

Common Mistakes:

• Confusing token bucket with data storage
• Thinking it encrypts data
• Assuming it manages database connections

2.

Which of the following is the correct way to represent a token bucket refill rate in pseudocode?

1. refill_rate = tokens_per_second
2. refill_rate = seconds_per_token
3. refill_rate = max_tokens * time
4. refill_rate = tokens / max_tokens

easy

A. refill_rate = seconds_per_token

B. refill_rate = tokens_per_second

C. refill_rate = max_tokens * time

D. refill_rate = tokens / max_tokens

Solution

1. Step 1: Understand refill rate meaning

   The refill rate is how many tokens are added per second to the bucket.

2. Step 2: Match with options

   refill_rate = tokens_per_second correctly shows tokens added per second, which is the refill rate.

3. Final Answer:

   refill_rate = tokens_per_second -> Option B

4. Quick Check:

   Refill rate = tokens per second [OK]

Hint: Refill rate means tokens added each second [OK]

Common Mistakes:

• Confusing refill rate with time per token
• Multiplying max tokens by time incorrectly
• Using ratios instead of rates

3.

Given a token bucket with max_tokens = 5, refill_rate = 1 token/second, and an empty bucket at time 0, what is the number of tokens available at time 3 seconds?

medium

A. 3 tokens

B. 5 tokens

C. 0 tokens

D. 1 token

Solution

1. Step 1: Calculate tokens refilled after 3 seconds

   Since refill rate is 1 token per second, after 3 seconds, 3 tokens are added.

2. Step 2: Check max tokens limit

   The bucket max is 5 tokens, so 3 tokens fit without exceeding the max.

3. Final Answer:

   3 tokens -> Option A

4. Quick Check:

   3 seconds * 1 token/sec = 3 tokens [OK]

Hint: Multiply seconds by refill rate, cap at max tokens [OK]

Common Mistakes:

• Assuming bucket fills instantly to max
• Ignoring max token limit
• Using refill rate incorrectly

4.

Consider this pseudocode snippet for token bucket check:
if tokens <= 0:
  reject_request()
else:
  tokens -= 1
  allow_request()
What is the bug in this logic?

medium

A. It should check if tokens > 0 before allowing

B. It should increase tokens instead of decreasing

C. It should reject when tokens > 0

D. It should check if tokens < 1, not <= 0

Solution

1. Step 1: Recall proper token bucket logic

   To consume 1 token, check if tokens >= 1 before decrementing (equivalent to reject if tokens < 1).

2. Step 2: Identify the bug

   The code rejects only if tokens <= 0. For fractional tokens (common in real implementations), if 0 < tokens < 1, it allows the request, decrementing to negative, which is incorrect.

3. Final Answer:

   It should check if tokens < 1, not <= 0 -> Option D

4. Quick Check:

   Reject if tokens < 1 [OK]

Hint: Allow only if tokens >= 1 [OK]

Common Mistakes:

• Using <= 0 instead of < 1 causes off-by-one errors
• Increasing tokens on request instead of decreasing
• Rejecting requests when tokens are available

5.

You want to implement a token bucket that allows bursts of up to 10 requests and refills tokens at 2 tokens per second. If a client sends 15 requests instantly after being idle for 3 seconds, how many requests will be allowed immediately?

hard

A. 6 requests

B. 5 requests

C. 15 requests

D. 10 requests

Solution

1. Step 1: Calculate tokens available after 3 seconds idle

   Refill rate is 2 tokens/second, so after 3 seconds: 2 * 3 = 6 tokens. Max tokens allowed is 10, so bucket fills to 6 tokens.

2. Step 2: Consider burst capacity

   Since the bucket max is 10, if it was full before idle, it would have 10 tokens. But starting empty, after 3 seconds it has 6 tokens.

3. Step 3: Determine allowed requests

   The client sends 15 requests instantly, but only 6 tokens are available, so only 6 requests allowed immediately.

4. Final Answer:

   6 requests -> Option A

5. Quick Check:

   3 sec * 2 tokens/sec = 6 tokens available [OK]

Hint: Tokens = min(max_tokens, refill_rate * idle_time) [OK]

Common Mistakes:

• Assuming bucket always full at max tokens
• Allowing more requests than tokens available
• Ignoring refill rate and idle time