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

Time Complexity: Validation-based caching

O(n)

Understanding Time Complexity

When using validation-based caching in REST APIs, we want to know how the time to check and serve cached data changes as requests grow.

We ask: How does the caching validation affect the speed when many requests come in?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Pseudocode for validation-based caching
GET /resource
  if cache exists for resource:
    if cache is still valid:
      return cached response
    else:
      fetch fresh data
      update cache
      return fresh response
  else:
    fetch fresh data
    store in cache
    return fresh response
    

This code checks if cached data is valid before deciding to fetch fresh data or return cached data.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking cache validity and fetching fresh data if needed.
• How many times: Once per request, repeated for each incoming API call.

How Execution Grows With Input

As the number of requests grows, each request does a quick cache check and sometimes fetches fresh data.

Input Size (n)	Approx. Operations
10	10 cache checks, some fresh fetches
100	100 cache checks, some fresh fetches
1000	1000 cache checks, some fresh fetches

Pattern observation: The number of operations grows roughly in direct proportion to the number of requests.

Final Time Complexity

Time Complexity: O(n)

This means the time to handle requests grows linearly with the number of requests, since each request does a quick validation check.

Common Mistake

[X] Wrong: "Cache validation makes the response time constant no matter how many requests come."

[OK] Correct: Each request still needs to check the cache, so the total work grows with the number of requests, even if each check is fast.

Interview Connect

Understanding how caching affects time complexity helps you explain how APIs stay fast under load, a useful skill for real-world backend work.

Self-Check

"What if the cache validation involved a slow database call? How would the time complexity change?"

Practice

1. What is the main purpose of validation-based caching in REST APIs?

easy

A. To encrypt data during transmission

B. To speed up the server response by skipping validation

C. To store data permanently on the client side

D. To check if the data has changed before downloading it again

Solution

1. Step 1: Understand validation-based caching concept

   It is used to avoid downloading data again if it has not changed.

2. Step 2: Identify the main purpose

   The main goal is to check if data changed before downloading again to save bandwidth and time.

3. Final Answer:

   To check if the data has changed before downloading it again -> Option D

4. Quick Check:

   Validation-based caching = check data change before download [OK]

Hint: Remember: caching avoids re-downloading unchanged data [OK]

Common Mistakes:

• Thinking caching stores data permanently
• Confusing caching with encryption
• Assuming caching skips validation

2. Which HTTP header does the client send to ask the server if the cached data is still valid?

easy

A. If-Modified-Since

B. ETag

C. If-None-Match

D. Cache-Control

Solution

1. Step 1: Identify client headers for validation

   The client uses headers to tell the server what version it has.

2. Step 2: Match header for ETag validation

   The If-None-Match header is sent with the ETag value to check if data changed.

3. Final Answer:

   If-None-Match -> Option C

4. Quick Check:

   Client asks with If-None-Match header [OK]

Hint: Client sends If-None-Match with ETag to validate cache [OK]

Common Mistakes:

• Confusing If-Modified-Since with If-None-Match
• Using Cache-Control header for validation
• Thinking ETag is sent by client

3. Given this server response to a client request with If-None-Match: "abc123" header:

HTTP/1.1 304 Not Modified
ETag: "abc123"

What does this response mean?

medium

A. The data has changed and new data is sent

B. The data has not changed; client should use cached data

C. The server does not support caching

D. The client must resend the request without ETag

Solution

1. Step 1: Understand HTTP 304 status meaning

   304 means Not Modified, so data is unchanged since last fetch.

2. Step 2: Interpret ETag match

   ETag matches client's value, so server confirms data is still valid.

3. Final Answer:

   The data has not changed; client should use cached data -> Option B

4. Quick Check:

   304 Not Modified = use cached data [OK]

Hint: 304 status means no new data, use cache [OK]

Common Mistakes:

• Thinking 304 means new data sent
• Confusing 304 with 200 OK
• Assuming server rejects caching

4. A client sends a request with header If-None-Match: "xyz789". The server responds with:

HTTP/1.1 200 OK
ETag: "abc123"
{ "data": "new content" }

What is the likely problem in this interaction?

medium

A. The server sent a different ETag, indicating data changed, so 200 OK is correct

B. The server should respond with 304 Not Modified instead of 200 OK

C. The client sent an invalid ETag header

D. The server response is missing the If-None-Match header

Solution

1. Step 1: Compare client and server ETags

   Client sent "xyz789", server responded with "abc123" which is different.

2. Step 2: Understand server response code

   Since ETags differ, data changed, so server correctly sends 200 OK with new data.

3. Final Answer:

   The server sent a different ETag, indicating data changed, so 200 OK is correct -> Option A

4. Quick Check:

   Different ETag means data changed, send 200 OK [OK]

Hint: Different ETag means new data, so 200 OK is correct [OK]

Common Mistakes:

• Expecting 304 when ETags differ
• Thinking client ETag must match server's
• Confusing If-None-Match with If-Match

5. You want to implement validation-based caching in your REST API. Which sequence correctly describes the interaction between client and server?

hard

A. Client sends request with If-None-Match header; server replies 304 if data unchanged or 200 with new data and ETag if changed

B. Server sends ETag in request; client replies 304 if data unchanged or 200 with new data if changed

C. Client sends ETag in response; server sends If-None-Match header to validate cache

D. Server always sends 200 OK with data and never uses ETag

Solution

1. Step 1: Identify correct client-server header roles

   Client sends If-None-Match with ETag to ask if data changed.

2. Step 2: Understand server response logic

   Server replies 304 if data unchanged, or 200 with new data and new ETag if changed.

3. Final Answer:

   Client sends request with If-None-Match header; server replies 304 if data unchanged or 200 with new data and ETag if changed -> Option A

4. Quick Check:

   Client sends If-None-Match; server replies 304 or 200 [OK]

Hint: Client sends If-None-Match; server replies 304 or 200 with ETag [OK]

Common Mistakes:

• Mixing up who sends ETag and If-None-Match
• Thinking server sends If-None-Match header
• Assuming server never sends 304