Cursor-based pagination in Rest API - Time & Space Complexity

Time Complexity: Cursor-based pagination

O(1)

Understanding Time Complexity

When using cursor-based pagination in APIs, it's important to understand how the time to fetch data changes as the data grows.

We want to know how the number of operations grows when retrieving pages of data using a cursor.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

GET /items?cursor=abc123&limit=10

// Server-side:
// 1. Find the position of the cursor in the dataset
// 2. Retrieve the next 10 items after the cursor
// 3. Return these items and a new cursor for the next page
    

This code fetches a page of items starting after a given cursor, returning a fixed number of items each time.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Retrieving a fixed number of items (limit) after the cursor position.
• How many times: Once per page request, fetching only the limited items.

How Execution Grows With Input

Since each request fetches a fixed number of items, the work done stays about the same no matter how large the dataset is.

Input Size (n)	Approx. Operations
10	Fetch 10 items
100	Fetch 10 items
1000	Fetch 10 items

Pattern observation: The number of operations stays constant because the page size is fixed.

Final Time Complexity

Time Complexity: O(1)

This means fetching each page takes about the same time, regardless of how big the whole dataset is.

Common Mistake

[X] Wrong: "Fetching later pages takes longer because the dataset is bigger."

[OK] Correct: Cursor-based pagination fetches a fixed number of items each time, so the time stays steady no matter the dataset size.

Interview Connect

Understanding cursor-based pagination time complexity shows you can reason about efficient data fetching, a useful skill in many real-world API designs.

Self-Check

"What if the server had to scan from the start of the dataset to find the cursor each time? How would the time complexity change?"

Practice

1.

What is the main purpose of cursor-based pagination in REST APIs?

easy

A. To sort data alphabetically before sending

B. To efficiently fetch the next set of data using a marker

C. To cache all data on the client side

D. To send all data in a single response

Solution

1. Step 1: Understand cursor-based pagination concept

   Cursor-based pagination uses a marker (cursor) to fetch the next set of data instead of page numbers.

2. Step 2: Identify the main purpose

   This method helps efficiently retrieve data in chunks and avoid missing or repeating items when data changes.

3. Final Answer:

   To efficiently fetch the next set of data using a marker -> Option B

4. Quick Check:

   Cursor-based pagination = fetch next data with marker [OK]

Hint: Cursor marks position to get next data chunk [OK]

Common Mistakes:

• Confusing cursor with page number
• Thinking it sends all data at once
• Assuming it sorts data alphabetically

2.

Which of the following is the correct way to include a cursor in a REST API request URL?

GET /items?____=abc123

easy

A. cursor

B. limit

C. page

D. offset

Solution

1. Step 1: Identify the query parameter for cursor

   Cursor-based pagination uses a parameter named cursor to mark the position for the next data fetch.

2. Step 2: Match the parameter in the URL

   The URL should include ?cursor=abc123 to pass the cursor value.

3. Final Answer:

   cursor -> Option A

4. Quick Check:

   Cursor parameter in URL = cursor [OK]

Hint: Cursor parameter is usually named 'cursor' [OK]

Common Mistakes:

• Using 'page' or 'offset' which are for offset pagination
• Confusing 'limit' with cursor
• Leaving out the cursor parameter

3.

Given this API response for cursor-based pagination:

{
  "data": ["item4", "item5"],
  "next_cursor": "xyz789"
}

What should the client do to get the next page of data?

medium

A. Send a request with ?cursor=xyz789

B. Send a request with ?page=2

C. Send a request with ?offset=2

D. Send a request with ?limit=2

Solution

1. Step 1: Read the response for next cursor

   The response includes a next_cursor value "xyz789" which marks the next data position.

2. Step 2: Use the cursor in the next request

   The client should send a request with ?cursor=xyz789 to get the next page.

3. Final Answer:

   Send a request with ?cursor=xyz789 -> Option A

4. Quick Check:

   Use next_cursor value as cursor parameter [OK]

Hint: Use next_cursor value as cursor in next request [OK]

Common Mistakes:

• Using page or offset parameters instead of cursor
• Ignoring next_cursor and repeating last request
• Sending limit without cursor

4.

Consider this code snippet for fetching paginated data using cursor-based pagination:

cursor = None
while True:
    response = api.get_items(cursor=cursor)
    process(response.data)
    cursor = response.next_cursor
    if not cursor:
        break

What is the likely bug in this code?

medium

A. It processes data before fetching

B. It does not check if next_cursor exists before assigning

C. It never updates the cursor value

D. It may cause an infinite loop if next_cursor is empty string

Solution

1. Step 1: Analyze the code structure

   The code fetches data, processes it, then assigns cursor = response.next_cursor without checking if next_cursor is empty string.

2. Step 2: Potential infinite loop

   If next_cursor is an empty string, the condition if not cursor will be true and break the loop, so no infinite loop occurs. But if the check is incorrect or cursor is None, it breaks. However, the main issue is if next_cursor is missing, it raises an error.

3. Step 3: Proper handling

   Should check if next_cursor exists and is truthy before assigning and breaking.

4. Final Answer:

   It may cause an infinite loop if next_cursor is empty string -> Option D

5. Quick Check:

   Check for empty or missing cursor carefully [OK]

Hint: Check for empty or missing cursor carefully [OK]

Common Mistakes:

• Assuming next_cursor always exists
• Not breaking loop on missing cursor
• Updating cursor after break

5.

You have an API that returns data with cursor-based pagination. The API returns the following responses in sequence:

1. {"data": ["a", "b"], "next_cursor": "c1"}
2. {"data": ["c", "d"], "next_cursor": "c2"}
3. {"data": ["e"], "next_cursor": null}

You want to collect all items without duplicates even if the API sometimes returns overlapping data due to data changes. Which approach is best?

hard

A. Collect all items in a list and remove duplicates after fetching all pages

B. Fetch only the first page to avoid duplicates

C. Use a set to store items as you fetch each page to avoid duplicates immediately

D. Ignore duplicates and trust API never repeats data

Solution

1. Step 1: Understand overlapping data issue

   Cursor-based pagination can return overlapping items if data changes during pagination, causing duplicates.

2. Step 2: Choose a method to avoid duplicates

   Using a set to store items as they are fetched avoids duplicates immediately and efficiently.

3. Step 3: Evaluate other options

   Removing duplicates after fetching all pages (list) is less efficient. Ignoring duplicates or fetching only first page is incorrect.

4. Final Answer:

   Use a set to store items as you fetch each page to avoid duplicates immediately -> Option C

5. Quick Check:

   Use set to avoid duplicates during fetch [OK]

Hint: Use set to track unique items during pagination [OK]

Common Mistakes:

• Assuming API never returns duplicates
• Removing duplicates only after all data fetched
• Fetching only first page to avoid duplicates