Expiration-based caching in Rest API - Time & Space Complexity

Time Complexity: Expiration-based caching

O(1)

Understanding Time Complexity

When using expiration-based caching in a REST API, we want to know how the time to handle requests changes as more data is cached or expires.

We ask: How does the caching process affect the speed of serving requests as cache size grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

cache = {}

function getData(key) {
  if (key in cache) {
    if (cache[key].expiry > currentTime()) {
      return cache[key].value
    } else {
      delete cache[key]
    }
  }
  let data = fetchFromDatabase(key)
  cache[key] = { value: data, expiry: currentTime() + 300 }
  return data
}
    

This code checks if data is in cache and not expired. If expired or missing, it fetches fresh data and updates the cache.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking if the key exists and if the cached item is expired.
• How many times: This check happens once per request.

How Execution Grows With Input

As the number of cached items grows, each request still checks only one key.

Input Size (number of cached keys)	Approx. Operations per Request
10	1 key check + possible fetch
100	1 key check + possible fetch
1000	1 key check + possible fetch

Pattern observation: The time to check cache does not grow with cache size because it uses direct key lookup.

Final Time Complexity

Time Complexity: O(1)

This means each request takes about the same time to check the cache, no matter how many items are stored.

Common Mistake

[X] Wrong: "Checking if a cached item expired takes longer as the cache grows."

[OK] Correct: The cache uses direct key lookup, so expiration check is done only on the requested item, not all cached items.

Interview Connect

Understanding how caching affects request time helps you design fast APIs and shows you can think about performance clearly.

Self-Check

"What if the cache used a list instead of a key-value store? How would the time complexity change?"

Practice

1. What does the Cache-Control: max-age header do in expiration-based caching?

easy

A. It deletes the cache immediately after the response.

B. It disables caching for the resource.

C. It sets how long the cached data is considered fresh.

D. It forces the client to always fetch new data.

Solution

1. Step 1: Understand the role of Cache-Control header

   The Cache-Control header controls caching behavior for HTTP responses.

2. Step 2: Identify the meaning of max-age directive

   The max-age directive specifies the time in seconds that the response is considered fresh and can be served from cache.

3. Final Answer:

   It sets how long the cached data is considered fresh. -> Option C

4. Quick Check:

   max-age = cache freshness duration [OK]

Hint: Remember max-age sets cache freshness time in seconds [OK]

Common Mistakes:

• Confusing max-age with disabling cache
• Thinking max-age deletes cache immediately
• Assuming max-age forces fresh fetch every time

2. Which of the following is the correct syntax to set a cache expiration of 300 seconds in an HTTP response header?

easy

A. Cache-Control: maxage: 300

B. Cache-Control: max-age=300

C. Cache-Control: expire=300

D. Cache-Control: timeout=300

Solution

1. Step 1: Recall correct Cache-Control syntax

   The Cache-Control header uses directives separated by commas, with max-age specified as max-age=seconds.

2. Step 2: Compare options to correct syntax

   Only Cache-Control: max-age=300 uses the correct format: max-age=300.

3. Final Answer:

   Cache-Control: max-age=300 -> Option B

4. Quick Check:

   Correct header syntax = max-age=seconds [OK]

Hint: Use equal sign (=) with max-age, no spaces [OK]

Common Mistakes:

• Using colon instead of equal sign
• Using incorrect directive names like expire or timeout
• Adding spaces inside the directive

3. Given this HTTP response header:
Cache-Control: max-age=10
What will happen if a client requests the same resource 5 seconds later?

medium

A. The client will use the cached response without contacting the server.

B. The client will ignore the cache and fetch new data from the server.

C. The client will receive a 404 error.

D. The client will refresh the cache but still use old data.

Solution

1. Step 1: Understand max-age meaning

   max-age=10 means the cached data is fresh for 10 seconds after the first fetch.

2. Step 2: Check time elapsed since caching

   5 seconds is less than 10 seconds, so cache is still fresh and valid.

3. Final Answer:

   The client will use the cached response without contacting the server. -> Option A

4. Quick Check:

   Elapsed time < max-age = use cache [OK]

Hint: If request time < max-age, cache is used [OK]

Common Mistakes:

• Assuming cache expires immediately
• Thinking client always fetches new data
• Confusing max-age with cache invalidation

4. You set Cache-Control: max-age=60 but clients still fetch new data every time. What is the likely mistake?

medium

A. The client does not support caching headers.

B. The max-age value should be in milliseconds, not seconds.

C. The resource URL is missing a file extension.

D. The server is sending no-cache header overriding max-age.

Solution

1. Step 1: Check for conflicting headers

   If the server sends a no-cache directive, it forces clients to revalidate or fetch fresh data despite max-age.

2. Step 2: Understand max-age units and client support

   max-age is in seconds, and most clients support caching headers, so these are unlikely causes.

3. Final Answer:

   The server is sending no-cache header overriding max-age. -> Option D

4. Quick Check:

   no-cache overrides max-age [OK]

Hint: Check for no-cache header overriding max-age [OK]

Common Mistakes:

• Confusing seconds with milliseconds for max-age
• Blaming client support without checking headers
• Assuming URL format affects caching

5. You want to cache API responses for 5 minutes but ensure clients always get fresh data after expiration. Which header setup is best?

hard

A. Cache-Control: max-age=300, must-revalidate

B. Cache-Control: max-age=300, no-store

C. Cache-Control: no-cache, max-age=300

D. Cache-Control: max-age=0, public

Solution

1. Step 1: Understand caching for 5 minutes

   max-age=300 sets cache freshness for 300 seconds (5 minutes).

2. Step 2: Ensure fresh data after expiration

   must-revalidate forces clients to check with server after max-age expires before using cached data.

3. Step 3: Evaluate other options

   no-store disables caching, no-cache forces revalidation every time, max-age=0 means no caching.

4. Final Answer:

   Cache-Control: max-age=300, must-revalidate -> Option A

5. Quick Check:

   max-age + must-revalidate = cache then fresh after expiry [OK]

Hint: Use must-revalidate with max-age for fresh data after expiry [OK]

Common Mistakes:

• Using no-store disables caching completely
• Using no-cache forces revalidation every request
• Setting max-age=0 disables caching