Rate limit error responses in Rest API - Time & Space Complexity

Time Complexity: Rate limit error responses

O(n)

Understanding Time Complexity

When a server limits how many requests you can send, it must check each request against the limit.

We want to know how the time to check changes as more requests come in.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Pseudocode for rate limit check
function checkRateLimit(userId) {
  const requests = getRequestsForUser(userId);
  const now = currentTime();
  const windowStart = now - timeWindow;
  const recentRequests = requests.filter(r => r.timestamp >= windowStart);
  if (recentRequests.length > maxAllowed) {
    return errorResponse("Rate limit exceeded");
  }
  return successResponse();
}
    

This code checks how many requests a user made recently and returns an error if they went over the limit.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Filtering the user's request list to find recent requests.
• How many times: Once per check, but the filter checks each past request in the list.

How Execution Grows With Input

As the number of past requests grows, the filter checks more items each time.

Input Size (n)	Approx. Operations
10	10 checks
100	100 checks
1000	1000 checks

Pattern observation: The work grows directly with the number of stored requests.

Final Time Complexity

Time Complexity: O(n)

This means the time to check grows in a straight line with how many past requests there are.

Common Mistake

[X] Wrong: "The rate limit check is always fast and constant time."

[OK] Correct: Because it looks at all past requests, more requests mean more work, so it can slow down.

Interview Connect

Understanding how checking rate limits scales helps you design APIs that stay fast even with many users.

Self-Check

"What if we stored only the count of requests in the time window instead of all timestamps? How would the time complexity change?"

Practice

1. What HTTP status code is commonly used to indicate a rate limit error in REST APIs?

easy

A. 404

B. 429

C. 500

D. 401

Solution

1. Step 1: Understand HTTP status codes for errors

   HTTP status codes in the 400 range indicate client errors. Among them, 429 specifically means too many requests.

2. Step 2: Identify the code for rate limiting

   The 429 status code is defined to signal that the user has sent too many requests in a given time.

3. Final Answer:

   429 -> Option B

4. Quick Check:

   Rate limit error = 429 [OK]

Hint: Remember 429 means too many requests, a rate limit error [OK]

Common Mistakes:

• Confusing 429 with 404 (not found)
• Using 500 which is server error
• Choosing 401 which means unauthorized

2. Which HTTP header is used to tell the client when to retry after hitting a rate limit?

easy

A. Retry-After

B. Authorization

C. Content-Type

D. User-Agent

Solution

1. Step 1: Identify headers related to retry timing

   The Retry-After header is designed to tell clients how long to wait before retrying a request.

2. Step 2: Confirm the correct header for rate limit retry

   Other headers like Content-Type or Authorization do not indicate retry timing.

3. Final Answer:

   Retry-After -> Option A

4. Quick Check:

   Retry timing header = Retry-After [OK]

Hint: Retry-After header tells when to retry after rate limit [OK]

Common Mistakes:

• Choosing Content-Type which describes data format
• Confusing Authorization with retry info
• Selecting User-Agent which identifies client software

3. What will the following HTTP response indicate?

HTTP/1.1 429 Too Many Requests
Retry-After: 120
Content-Type: application/json

{"error": "Rate limit exceeded. Try again later."}

medium

A. The client should retry immediately

B. The client is unauthorized

C. The server encountered an internal error

D. The client sent too many requests and should wait 120 seconds before retrying

Solution

1. Step 1: Analyze the status code and headers

   Status 429 means too many requests. The Retry-After header with value 120 means wait 120 seconds before retrying.

2. Step 2: Interpret the JSON error message

   The message confirms the rate limit was exceeded and advises to try again later.

3. Final Answer:

   The client sent too many requests and should wait 120 seconds before retrying -> Option D

4. Quick Check:

   429 + Retry-After = wait before retry [OK]

Hint: 429 plus Retry-After means wait specified seconds before retry [OK]

Common Mistakes:

• Thinking client can retry immediately
• Confusing 429 with unauthorized error
• Assuming server error from 429

4. A REST API returns this response when rate limit is exceeded:

HTTP/1.1 429 Too Many Requests
Content-Type: application/json

{"error": "Too many requests"}

What is missing to improve client handling?

medium

A. A Retry-After header indicating when to retry

B. Changing status code to 500

C. Adding Authorization header

D. Removing the error message

Solution

1. Step 1: Identify missing headers for rate limit response

   The response lacks the Retry-After header, which helps clients know when to retry.

2. Step 2: Understand why Retry-After is important

   Without Retry-After, clients may retry too soon, causing more errors or confusion.

3. Final Answer:

   A Retry-After header indicating when to retry -> Option A

4. Quick Check:

   Retry-After header missing = add it [OK]

Hint: Add Retry-After header to guide client retry timing [OK]

Common Mistakes:

• Changing status code to 500 which is wrong
• Adding Authorization header unrelated to rate limit
• Removing error message reduces clarity

5. You want to design a REST API rate limit error response that clearly informs clients about the wait time and reason. Which of the following is the best practice?

hard

A. Return status 200 with a JSON error field indicating rate limit

B. Return status 403 with a plain text message 'Rate limit exceeded'

C. Return status 429 with a Retry-After header and a JSON message explaining the limit

D. Return status 500 with a Retry-After header

Solution

1. Step 1: Choose correct status code for rate limiting

   Status 429 is the standard code for rate limit errors, signaling client to slow down.

2. Step 2: Include Retry-After header and clear message

   Retry-After header tells client how long to wait. JSON message improves clarity and user experience.

3. Step 3: Evaluate other options

   403 is forbidden, not rate limit. 200 means success, which is misleading. 500 is server error, not client rate limit.

4. Final Answer:

   Return status 429 with a Retry-After header and a JSON message explaining the limit -> Option C

5. Quick Check:

   429 + Retry-After + clear message = best practice [OK]

Hint: Use 429 + Retry-After + clear JSON message for best rate limit response [OK]

Common Mistakes:

• Using wrong status codes like 403 or 500
• Returning 200 status for errors
• Omitting Retry-After header