Statelessness requirement in Rest API - Time & Space Complexity

Time Complexity: Statelessness requirement

O(n)

Understanding Time Complexity

When building REST APIs, statelessness means each request is independent and carries all needed info.

We want to see how this affects the work the server does as requests come in.

Scenario Under Consideration

Analyze the time complexity of the following REST API request handler.

GET /items?id=123

// Server receives request
// Parses query parameters
// Looks up item by id in database
// Returns item data as response

This code handles one request by fetching an item using its id from storage.

Identify Repeating Operations

Each request triggers these steps:

• Primary operation: Database lookup by id
• How many times: Once per request

There are no loops or recursion inside a single request; work depends on the request size.

How Execution Grows With Input

Each request is handled separately, so work grows linearly with number of requests.

Number of Requests (n)	Approx. Operations
10	10 database lookups
100	100 database lookups
1000	1000 database lookups

Pattern observation: More requests mean proportionally more work, but each request cost stays the same.

Final Time Complexity

Time Complexity: O(n)

This means the total work grows directly with the number of requests, since each is handled independently.

Common Mistake

[X] Wrong: "The server remembers past requests, so handling new ones gets faster."

[OK] Correct: Statelessness means the server does not keep info between requests, so each request takes similar time.

Interview Connect

Understanding statelessness helps you explain how APIs scale and why each request cost matters on its own.

Self-Check

"What if the server started caching results between requests? How would the time complexity change?"

Practice

1. What does the statelessness requirement in REST APIs mean?

easy

A. Each request from client to server must contain all information needed to understand and process it.

B. The server must remember all previous requests from the client.

C. The server stores user session data between requests.

D. The client does not need to send any authentication information after the first request.

Solution

1. Step 1: Understand statelessness in REST

   Statelessness means the server does not keep any client context between requests.

2. Step 2: Identify what each request must contain

   Each request must have all data needed to process it, including authentication and parameters.

3. Final Answer:

   Each request from client to server must contain all information needed to understand and process it. -> Option A

4. Quick Check:

   Statelessness = All info in each request [OK]

Hint: Remember: server forgets past requests, all info sent every time [OK]

Common Mistakes:

• Thinking server stores session data
• Assuming client sends partial info only once
• Confusing statelessness with authentication persistence

2. Which of the following HTTP request examples follows the statelessness principle?

easy

A. POST /login HTTP/1.1\nHost: example.com\nCookie: sessionid=abc123

B. GET /profile HTTP/1.1\nHost: example.com

C. GET /profile HTTP/1.1\nHost: example.com\nReferer: /home

D. GET /profile HTTP/1.1\nHost: example.com\nAuthorization: Bearer token123

Solution

1. Step 1: Check if request contains all needed info

   GET /profile HTTP/1.1\nHost: example.com\nAuthorization: Bearer token123 includes Authorization header, so server can authenticate without stored session.

2. Step 2: Compare with other options

   POST /login HTTP/1.1\nHost: example.com\nCookie: sessionid=abc123 relies on cookies, which imply server state. Options B and D lack explicit authentication info.

3. Final Answer:

   GET request with Authorization header carrying token -> Option D

4. Quick Check:

   Auth info in request = stateless [OK]

Hint: Look for Authorization header in request to confirm statelessness [OK]

Common Mistakes:

• Assuming cookies mean statelessness
• Ignoring missing auth info in requests
• Confusing Referer header with authentication

3. Consider this REST API server behavior: It does not store any client session data. A client sends two requests:
1. GET /data?user=123&token=abc
2. GET /data?user=123
What will happen on the second request?

medium

A. The server rejects the request due to missing authentication token.

B. The server processes the request successfully using stored session data.

C. The server processes the request ignoring authentication.

D. The server crashes because of missing parameters.

Solution

1. Step 1: Analyze statelessness and authentication

   Since server is stateless, it does not remember previous tokens; each request must include token.

2. Step 2: Check second request parameters

   Second request lacks token parameter, so server cannot authenticate and must reject it.

3. Final Answer:

   Server rejects request due to missing authentication token. -> Option A

4. Quick Check:

   Missing token means reject request [OK]

Hint: Every request needs auth info; missing it causes rejection [OK]

Common Mistakes:

• Assuming server remembers token from first request
• Thinking server ignores missing token
• Believing server crashes on missing params

4. A developer wrote this REST API code snippet to handle user requests:

def handle_request(request):
    if 'session_id' in server_memory:
        user = server_memory['session_id']
        return f"Hello, {user}!"
    else:
        return "Unauthorized"

What is the main problem related to statelessness here?

medium

A. The code does not check for authentication token in the request.

B. The code correctly implements statelessness by using server memory.

C. The code stores session data on the server, violating statelessness.

D. The code uses request parameters properly for authentication.

Solution

1. Step 1: Identify server memory usage

   The code checks 'session_id' in server_memory, meaning it stores client state on server.

2. Step 2: Compare with statelessness principle

   Statelessness forbids server from storing client session data between requests.

3. Final Answer:

   Code stores session data on server, violating statelessness. -> Option C

4. Quick Check:

   Server storing session = stateful, not stateless [OK]

Hint: Stateless means no server memory of client sessions [OK]

Common Mistakes:

• Thinking server memory use is allowed
• Ignoring missing token checks
• Assuming code is stateless because it returns a string

5. You are designing a REST API for a shopping cart. To keep it stateless, which approach is best to track the user's cart items across requests?

hard

A. Store the cart items in a server-side session linked to the user ID.

B. Require the client to send the full cart data with each request.

C. Save the cart data in a database and keep session ID on server memory.

D. Use cookies to store cart items and rely on server to read them.

Solution

1. Step 1: Understand statelessness in API design

   Statelessness means server does not keep client state; all info must come with each request.

2. Step 2: Evaluate options for cart tracking

   Require the client to send the full cart data with each request. requires the client to send the full cart data with each request, fitting statelessness. Options A, B, and C rely on server or cookies storing state.

3. Final Answer:

   Require client to send full cart data with each request. -> Option B

4. Quick Check:

   Client sends all data = stateless API [OK]

Hint: Keep server stateless by sending all data from client every time [OK]

Common Mistakes:

• Using server sessions to store cart
• Assuming cookies make API stateless
• Relying on server memory for user data