Representation and Contracts

Objectives#

• Distinguish indices, stored values, object identity, and structural position.
• State mutation and aliasing behavior for inputs, outputs, and shared objects.
• Declare interval, Unicode, integer-range, tie-breaking, and ordering assumptions.
• Choose a representation whose operations preserve the problem's actual contract.

Model the input before the algorithm#

Clarify whether positions are indices, values are labels, and nodes are objects with identity. Ask whether the input may be mutated, whether duplicate values are distinct items, and whether output order is significant. These answers can change both the data structure and the tests.

Check the reasoning

• Could two different items have the same value?
• Would sorting or in-place marking violate the caller's mutation or ordering contract?

Equal values do not imply the same object#

Two linked-list nodes may both store 7 while occupying different positions and holding different next pointers. Cycle detection, intersection, and visited-node logic usually require node identity, not value equality.

Aliasing means two references reach the same mutable object. Mutating through one reference changes what the other observes. Copy a path or result when siblings must evolve independently; share deliberately when one update is meant to be visible everywhere.

Check the reasoning

• Does equality mean same payload, same object, or same logical key in this problem?
• Which caller-visible object changes after this assignment or mutation?

Use half-open intervals consistently#

The half-open interval [start, end) includes start and excludes end. Its length is end-start, adjacent intervals [a,b) and [b,c) do not overlap, and an empty interval has start=end. This convention aligns naturally with array slicing and one-past-the-end loop bounds when the language uses them.

Do not mix half-open and closed rules. If the domain uses closed appointments, touching endpoints may overlap; if it uses half-open reservations, one ending at t and another starting at t can coexist. State the convention in the contract and test it.

Check the reasoning

• Is the end included, and what is the length formula?
• Do [1,3) and [3,5) overlap under the chosen contract?

Declare machine and ordering assumptions#

A “character” may mean a byte, Unicode code point, or user-perceived grapheme. Indexing and length can differ among these models. Choose the unit required by the prompt and use language operations that implement it; do not silently call UTF-16 code units or UTF-8 bytes characters.

Sums, products, distances, and midpoint arithmetic may exceed the integer range even when each input value fits. Choose a wider or arbitrary-precision representation when required and name the assumption in complexity claims.

When several results compare equally on the primary key, define a deterministic secondary key such as original index, stable insertion sequence, or identifier. A comparator must implement that policy consistently; iteration order from an unordered container is not a tie policy.

Check the reasoning

• What text unit and normalization, if any, does equality use?
• Can an intermediate arithmetic result overflow before the final value is produced?
• Which result wins a tie, and is that order observable?

Worked example: Same value, different node#

List A contains node a1(value 7) followed by shared node x(value 9). List B contains distinct node b1(value 7) followed by the same shared node x. Find the intersection.

Conclusion: Value equality would falsely report the two leading 7 nodes as the intersection. The correct representation compares node identity and treats the shared object - not its payload - as the answer.

Misconception to correct#

If two nodes contain the same value, they are the same node for traversal and intersection problems.

Payload equality and object identity answer different questions. Two nodes can both contain 7 while having different links, ownership, and positions; compare identity when the contract asks whether structure is shared.

Short exercise#

Events are [start, end) reservations. Sort all start/end events to compute peak simultaneous reservations. What should happen when one reservation ends at time 10 and another begins at 10, and what deterministic tie rule implements it?

Put it into practice#

Choose one interval problem and write the endpoint convention, mutation rule, tie policy, integer assumptions, and empty-interval behavior before selecting the scan or event representation.