A collection interface promises "give me the element at position i" for every implementation, but one implementation walks a chain of nodes to answer it. Which languages let a caller see that cost difference through the API itself, and which hide it?
answer
- contract says what, not how much
- C++ iterator categories: list has no operator[]
- Rust: no Index for LinkedList
- Scala IndexedSeq vs LinearSeq
- Java RandomAccess = run-time marker
basics
~20 sInterfaces promise behaviour, not cost, so a linked implementation answers index-at-i in linear time behind the same call. C++ and Rust omit indexing from list types entirely; Scala splits IndexedSeq from LinearSeq; Java only adds a RandomAccess marker.
solid answer
~50 sThe cost model is the part of a contract most interfaces cannot express, so languages differ in how much of it they push into the type system. - **C++ STL** encodes it in iterator categories: `std::list` has no `operator[]` at all and only bidirectional iterators, so `std::sort(l.begin(), l.end())` does not compile. Price: cryptic template errors, and generic code must be written against categories. - **Rust** does not implement `Index` for `LinkedList`; you write `.iter().nth(i)`, so the walk is visible at the call site. Price: nothing stops you calling `nth` in a loop. - **Scala** splits `IndexedSeq` from `LinearSeq`, so `apply(i)` exists on both but the static type states the cost. Price: advisory, not enforced. - **Java** lets `LinkedList.get(i)` compile and run linearly; the only signal is the `RandomAccess` marker interface that library code checks at run time. Price: silently quadratic loops. No language encodes full cost, so the residue is documentation and measurement.
code
cpp · 4 linesstd::list<int> l{1, 2, 3};
// l[1]; // does not compile: no operator[]
// std::sort(l.begin(), l.end()); // does not compile: needs random-access iterators
l.sort(); // merge-based member sort insteadgo deeper
Know that the same method name can hide very different costs, and that indexing a chain-based list in a loop is quadratic.
Be able to name at least two languages that encode the cost difference in the API surface (C++ iterator categories, Rust's missing Index) and contrast them with one that does not.
Discuss what a type system can realistically capture, why amortised and cache costs escape all of them, and how you pick parameter types so callers cannot cheaply write the quadratic version.
Frame it as a contract-expressiveness tradeoff: every cost guarantee moved into the type system becomes a compatibility constraint on future implementations, which is why libraries encode categories rather than complexities.
## What is actually leaking An interface is a promise about *what* an operation does, not *how much it costs*. "Return the element at index i" is honoured by a contiguous array in constant time and by a chain of nodes in linear time. Both satisfy the written contract; only one satisfies the contract the caller imagined. That gap is the canonical example of Joel Spolsky's law of leaky abstractions: the implementation detail you were promised not to care about reappears as a performance cliff. The cliff is not linear-versus-constant on one call. It is the composition: a loop that indexes every position turns O(n) into O(n^2). The abstraction did not lie on any single call; it lied about substitutability under composition. ## The design axis: how much cost lives in the type system **C++** made the boldest choice. Iterators are classified into categories (input, forward, bidirectional, random-access), and algorithms state which category they need. `std::list` exposes bidirectional iterators and no subscript operator, so the mistake is not slow, it is a compile error; the standard library also gives `std::list` its own merge-based `sort` member. The cost is paid in error-message quality (the reason C++20 concepts exist) and in generic code needing category-aware overloads. **Rust** takes a quieter version of the same stance: `Index` is implemented where indexing is cheap. `LinkedList` has none, so a caller writes `list.iter().nth(i)` and the traversal is spelled out. The type system does not stop repeated `nth` calls, but the call site no longer reads like array access. **Scala** put the distinction into the collection hierarchy: `IndexedSeq` (Vector, Array) versus `LinearSeq` (List). `apply(i)` exists on both, so it is a documentation-in-types choice rather than an enforcement one — useful for API authors who accept `IndexedSeq` when they intend random access. **Java** allows `LinkedList.get(i)` to compile. The library's answer is `RandomAccess`, a marker interface with no methods that library algorithms test at run time: `Collections.binarySearch` and `shuffle` branch on it and switch to an iterator-based strategy for lists that lack it. That is a run-time work-around for something the type system declined to say, and application code almost never performs the same check. **Python** sidesteps by not offering the tempting shape: `list` is always a dynamic array, and `collections.deque` supports `d[i]` at linear cost with no type-level warning at all — the same leak, unmarked. **Haskell** treats it as library selection: `!!` on a list is documented as linear and idiomatic code reaches for `Data.Sequence` or `Data.Vector` when indexing matters; laziness adds a second cost dimension (a thunk retained rather than a value) that no type expresses either. ## Why nobody encodes cost fully Complexity is not compositional in the way types are: amortised bounds (dynamic array append), cache effects (a vector of small structs beats a node chain even where both are O(1)), and allocator behaviour all matter more than the asymptotic label. A type system that captured all of it would be a cost calculus, and every implementation change would be a breaking API change. So languages pick a cheap subset — categories, trait implementations, hierarchy splits — and leave the rest to documentation. ## Designing around it Accept the narrowest type that carries the cost guarantee you need (`IndexedSeq` rather than `Seq`); iterate rather than index when the interface admits both, because iteration is the operation every sequence implements cheaply; and treat "the interface let me write it" as no evidence that the composition is affordable. Where the language gives you a marker (Java's `RandomAccess`) or a category (C++), let library code branch on it rather than assuming. The leak is not removable — it is only made visible earlier, and "earlier" is the whole design goal.
- Java's RandomAccess has no methods. What is a marker interface like that buying, and what is it failing to buy?It lets library algorithms branch at run time — Collections.binarySearch and shuffle choose an iterator strategy when the list is not RandomAccess. What it fails to buy is any compile-time protection: application code can still index a linked list in a loop, and nothing warns. C++ gets the check at compile time because the constraint lives in iterator categories rather than in a run-time test.
- If your language cannot express cost in types, what can an API author do instead?Narrow the accepted type to one whose implementations all meet the bound (Scala's IndexedSeq, Rust taking a slice rather than any iterable), or expose only the cheap operation — offer iteration and refuse indexing, the way C++'s std::list does. Failing both, document the bound next to the method and add a benchmark, because prose alone is not checked by anything.
saying these in an interview costs you the question
- Claiming complexity is part of every interface contract — in most languages it is prose at best
- Believing constant-factor equality: assuming two O(1) implementations perform alike regardless of memory layout
- Treating the C++ compile error as a language wart rather than the constraint being enforced
- Assuming a marker interface prevents misuse rather than merely enabling a run-time branch in library code