Bound keyset pagination and continuation rules

Clarify the observable contract

A continuation token describes the last ordered key returned, not a page number. This in-memory fixture assumes unique immutable integer IDs and returns IDs strictly greater than after, ordered ascending. Page size is constrained to one through three. The result array is bounded, but this LINQ implementation may still enumerate and sort a much larger input; it is not an indexed database query.

The unique ID is both an ordering key and a continuation boundary in this fixture. Strict greater-than means the previous last row is not repeated. An empty result has no last row, so a caller must not derive a continuation by blindly indexing the final element of every response.

Walk through the verified program

The first request has no continuation and returns IDs one and two despite the unsorted source. Reusing two as after returns three and four. A requested size four is rejected before enumeration. No next token is fabricated when the consumer has no returned last row, and null is distinct from an actual integer boundary.

Sorting occurs after filtering, which means the continuation is interpreted against the entire current source rather than against its incidental array position. The first result is one,two and the second three,four even though the physical input begins with ID two. This distinguishes keyset semantics from Skip on an unsorted source.

using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;

var rows=new[]{new Row(2,"b"),new Row(1,"a"),new Row(4,"d"),new Row(3,"c")};
var first=Page(rows,null,2); var second=Page(rows,first[^1].Id,2);
Console.WriteLine("first:"+string.Join(",",first.Select(x=>x.Id))); Console.WriteLine("next:"+string.Join(",",second.Select(x=>x.Id)));
bool rejected=false; try { Page(rows,null,4); } catch(ArgumentOutOfRangeException) { rejected=true; } Console.WriteLine("limit rejected:"+rejected.ToString().ToLowerInvariant());
static Row[] Page(IEnumerable<Row> rows,int? after,int size) { if(size is <1 or >3) throw new ArgumentOutOfRangeException(nameof(size)); return rows.Where(x=>after is null || x.Id>after.Value).OrderBy(x=>x.Id).Take(size).ToArray(); }
sealed record Row(int Id,string Name);

Account for time, storage and allocations

For n source rows and m matching rows, filtering examines O(n) values and ordered-prefix evaluation buffers O(m) candidates. A full-sort baseline costs O(m log m), while .NET LINQ can optimize Take with partial selection; exact comparison behavior is implementation-dependent. An indexed ordered data source has another cost model. The small result page does not establish bounded total memory or an index seek.

Describe input size, matching-row count and requested page size separately. The accepted page limit is a response bound; it does not prevent OrderBy from buffering qualifying values. An interview answer should avoid claiming database-index complexity for a LINQ-to-Objects pipeline that has no database or index.

Review assumptions and likely defects

Nonunique ordering keys can skip or repeat rows across pages unless a unique secondary key becomes part of the token. Concurrent inserts and deletes also require an explicit consistency policy. Local arrays provide no snapshot token, authorization boundary or tamper-resistant continuation encoding.

If IDs are not unique, a token containing only ID cannot distinguish tied rows and may skip remaining ties. The function assumes uniqueness rather than validating it, which is appropriate only when another boundary guarantees it. A production token must also bind to the query and security context it continues.

Practice one: discriminate edge cases

Insert a new row below and above the first continuation, then predict the next page. Hint: strict greater-than excludes earlier keys; that behavior is not the same as a frozen snapshot. Test the final empty page without indexing its last element.

After receiving first page one,two, insert a new ID between earlier keys only if the domain permits such IDs, and add another ID beyond two. Explain which appears in the next page and which is permanently behind the cursor. This makes the absence of snapshot semantics concrete rather than merely warning that data can change.

Practice two: defend an extension

Design a timestamp-plus-ID continuation with a signed token and an indexed backing store. Define lexicographic comparison, tenant binding and expiry. Separate the bounded returned page from database work and explain which consistency guarantees remain unprovided.

A composite timestamp-and-ID token should use lexicographic comparison in exactly the same directions as the result order. Encode and authenticate the token with query and tenant context, then validate size and expiry before using it. An indexed backing store is a separate implementation choice whose plan and consistency behavior need real verification.

Evaluate correctness and interview reasoning

The solution is rigorous only when its unique-key, stable-key and page-size assumptions are visible. The tested code demonstrates deterministic continuation over an owned in-memory source and rejects an oversized request before enumeration. It deliberately does not demonstrate signed tokens, server authorization, index seeks or a durable snapshot. A senior explanation separates response bounds from total query work and describes what concurrent writes do to the cursor contract. The related multi-file project adds composite ordering and explicit uniqueness checks as independent exercises, rather than quietly granting those properties to this smaller function.