Fixed window algorithm in Rest API - Practice Problems & Coding Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fixed Window Rate Limiter Check

Consider a fixed window rate limiter that allows 3 requests per 10 seconds. Given the following sequence of request timestamps (in seconds): [1, 2, 3, 11, 12]. What is the output of the rate limiter for each request (True means allowed, False means blocked)?

Rest API

class FixedWindowLimiter:
    def __init__(self, limit, window_size):
        self.limit = limit
        self.window_size = window_size
        self.windows = {}

    def allow_request(self, timestamp):
        window = timestamp // self.window_size
        count = self.windows.get(window, 0)
        if count < self.limit:
            self.windows[window] = count + 1
            return True
        else:
            return False

limiter = FixedWindowLimiter(3, 10)
requests = [1, 2, 3, 11, 12]
results = [limiter.allow_request(t) for t in requests]
print(results)

A [True, True, True, False, False]

B [True, True, True, False, True]

C [True, True, True, True, False]

D [True, True, True, True, True]

💡 Hint

Remember that the fixed window resets counts every window_size seconds.

The first three requests at seconds 1, 2, and 3 fall into window 0 and are allowed. The fourth request at 11 seconds is in window 1 and allowed as count resets to 1. The fifth request at 12 seconds is the second in window 1 (<3) and allowed. Output: [True, True, True, True, True], option D.

🧠 Conceptual

intermediate

Understanding Fixed Window Algorithm Behavior

Which statement best describes a limitation of the fixed window rate limiting algorithm?

A It uses a sliding window to smooth out request rates.

B It can cause bursts of requests at window boundaries, allowing more requests than the limit in a short time.

C It evenly distributes requests over time to prevent any bursts.

D It tracks each request individually to prevent any overuse.

💡 Hint

Think about what happens when one window ends and the next begins.

The fixed window algorithm resets counts at fixed intervals, so requests at the end of one window and start of the next can cause bursts exceeding the limit temporarily.

🔧 Debug

advanced

Identify the Bug in Fixed Window Implementation

What error will the following fixed window rate limiter code produce when calling allow_request(5) twice?

Rest API

class FixedWindowLimiter:
    def __init__(self, limit, window_size):
        self.limit = limit
        self.window_size = window_size
        self.windows = {}

    def allow_request(self, timestamp):
        window = timestamp // self.window_size
        if self.windows[window] < self.limit:
            self.windows[window] += 1
            return True
        else:
            return False

limiter = FixedWindowLimiter(1, 10)
print(limiter.allow_request(5))
print(limiter.allow_request(5))

A KeyError

B TypeError

C False, True

D True, False

💡 Hint

Check what happens when accessing a dictionary key that might not exist.

The code tries to access self.windows[window] without initializing it first, causing a KeyError on the first call.

📝 Syntax

advanced

Syntax Error in Fixed Window Code

Which option contains the correct syntax to increment the count for the current window in a fixed window rate limiter?

Rest API

window = timestamp // window_size
# increment count for window

A windows[window] = windows[window] + 1 or 1

B windows[window] += 1 if window in windows else 1

C windows[window] = windows.get(window, 0) + 1

D windows[window] = windows[window] ? windows[window] + 1 : 1

💡 Hint

Use dictionary get method to provide a default value.

Option C correctly uses get() to provide 0 if the key doesn't exist, then adds 1. Other options have syntax errors or invalid Python syntax.

🚀 Application

expert

Calculate Number of Allowed Requests in Fixed Window

A fixed window rate limiter allows 5 requests per 15 seconds. Given the request timestamps (in seconds): [2, 5, 7, 14, 15, 16, 29, 30], how many requests will be allowed in total?

A 8

B 6

C 5

D 7

💡 Hint

Group requests by their window and count up to the limit per window.

Windows are 0-14, 15-29, 30-44. First window has 4 requests (2,5,7,14) allowed all. Second window has 3 requests (15,16,29), limit 5, so all allowed. Third window has 1 request (30) allowed. Total allowed = 4 + 3 + 1 = 8. But limit is 5 per window, so second window only allows 5 total requests, but it has only 3 requests, so all allowed. Actually, the first window has 4 requests allowed, second window 3 allowed, third window 1 allowed, total 8. So option A is correct.