Inputs, Outputs, and Constraints: Specifying the Problem Precisely

Why Inputs, Outputs, and Constraints Matter

A program is a contract: given some inputs, it must produce specific outputs, while respecting constraints (rules, limits, and allowed operations). If any part of that contract is vague, different people can implement “correct” solutions that behave differently.

A precise specification helps you:

• Choose the right algorithm and data structures.
• Know what to validate and what to assume.
• Handle edge cases consistently.
• Estimate feasibility under time/memory limits.

A Consistent Specification Template

Use the same structure every time you define a problem:

• Problem statement: one paragraph describing what must be computed.
• Inputs/Outputs table: names, types, formats, and examples.
• Constraints and edge cases: limits, rules, and tricky scenarios.

When you read a problem, your job is often to extract these items; when you write a problem, your job is to state them explicitly.

Example 1: Sum of a List (and Why Constraints Change Everything)

Problem statement

Given a list of integers, compute the sum of all numbers in the list and return the result.

Continue in our app.

You can listen to the audiobook with the screen off, receive a free certificate for this course, and also have access to 5,000 other free online courses.

Or continue reading below...

Download the app

Constraints and edge cases

• List length: What is the maximum n? (e.g., 0 ≤ n ≤ 10^7)
• Value range: What is the range of each integer? (e.g., -10^9 to 10^9)
• Empty list: If numbers is empty, should the sum be 0?
• Overflow: If values and n are large, a 32-bit integer may overflow. Specify whether to use 64-bit or arbitrary precision.
• Input validity: Are non-integers possible, or can you assume clean input?

How constraints affect solution choices

• If n is small, any straightforward loop works.
• If n can be very large (millions), you still use a loop, but you must consider performance and memory (streaming input vs storing all values).
• If overflow is possible, you must choose a wider type or define behavior (error, wraparound, big integers).

Example 2: “Find the Maximum” with Ambiguity Removed

Problem statement

Given a non-empty list of integers, return the largest integer in the list.

Constraints and edge cases

• Non-empty: Explicitly state n ≥ 1. If empty lists are allowed, define what to return (error? null?).
• Duplicates: If multiple elements share the maximum, returning the value is unambiguous. If returning an index, specify which one (first? last?).
• Range: Value range affects numeric type choice.

Step-by-step: refining a vague spec

Vague version: “Find the max number.” Missing details often include:

• What if the list is empty?
• Are there non-integer values?
• Do we return the value or the position?
• If positions, which one when tied?

Refined version answers each question explicitly in constraints.

Example 3: Output Format Constraints (Rounding and Ties)

Problem statement

Given a list of real numbers, compute the average and output it rounded to exactly two decimal places.

Constraints and edge cases

• Empty list: If no values are provided, define behavior (error? 0.00?).
• Rounding rule: Specify half-up, half-even (banker’s rounding), or language default.
• Output type: If you require exactly two decimals, output is often best specified as a formatted string.
• Precision: Floating-point arithmetic can introduce tiny errors; constraints may require decimal arithmetic.

How constraints affect solution choices

• If rounding must be exact and predictable, you may need decimal-based arithmetic rather than binary floating point.
• If the output must be a string with two decimals, you must specify formatting (e.g., 2 becomes "2.00").

Example 4: Constraints That Force an Algorithm Choice

Problem statement

Given a list of integers, determine whether any two distinct elements sum to a target value.

Constraints and edge cases

• Distinct elements: You cannot reuse the same element twice unless it appears twice in the list.
• n limit: e.g., 1 ≤ n ≤ 200,000.
• Time limit: e.g., must run under 1 second.
• Memory limit: e.g., 256 MB.
• Duplicates: If target = 10 and list contains one 5, answer is false; if it contains two 5s, answer is true.

How constraints affect solution choices

Two common approaches:

• Check all pairs: O(n²) time, low extra memory. Works only if n is small (e.g., n ≤ 5,000).
• Use a set of seen values: O(n) expected time, O(n) memory. Needed when n is large and time is tight.

Notice how the specification must include n, time, and memory constraints to justify the intended approach.

Example 5: Allowed Operations as a Constraint

Problem statement

Given a non-negative integer, return the number of 1 bits in its binary representation, without converting the number to a binary string.

Constraints and edge cases

• Allowed operations: Bitwise operations allowed; string conversion not allowed.
• Range: e.g., 0 ≤ x ≤ 2³² − 1.
• x = 0: Output should be 0.

How constraints affect solution choices

• If conversion to string is allowed, a simple approach is counting characters in the binary string.
• If it is disallowed, you must use bitwise logic (shifts, masks, or bit tricks). The constraint directly changes the solution space.

Checklist: Questions to Ask to Complete a Specification

• Input format: Where does input come from (function args, file, user)? How is it structured?
• Output format: Exact type and formatting (decimals, separators, casing, ordering).
• Ranges: Maximum sizes and value bounds.
• Validity: Can you assume valid input? If not, what errors or defaults?
• Edge cases: Empty inputs, single element, duplicates, negative values, extreme bounds.
• Performance: Time and memory limits; expected complexity.
• Allowed operations: Restrictions on libraries, data structures, or conversions.

Practice Tasks: Find Missing Constraints and Remove Ambiguity

Task 1: “Normalize Names”

Vague problem statement: “Normalize a list of names.”

Your job: Write a precise specification using the template.

• Define inputs: Is it a list of strings? Can it include null/empty strings? Are there leading/trailing spaces?
• Define outputs: Do you return a new list or modify in place? What is “normalized” (trim spaces, title case, remove punctuation)?
• Add constraints: Maximum number of names? Maximum length? Allowed characters? Locale rules (e.g., Turkish dotted i)?
• Edge cases: Multiple spaces, hyphenated names, apostrophes, all-caps input.

Task 2: “Second Largest Number”

Vague problem statement: “Find the second largest number in an array.”

Identify missing constraints:

• What if the array has fewer than 2 elements?
• If the largest value appears multiple times, is the second largest the same value or the next distinct value?
• Are numbers integers only? What about floats and NaN?
• What should be returned: value, index, or both?

Refine it: Write a final problem statement, an inputs/outputs table, and a constraints list that resolves each ambiguity.

Task 3: “Merge Two Sorted Lists”

Vague problem statement: “Merge two sorted lists.”

Identify missing constraints:

• Sorted ascending or descending?
• Are duplicates allowed and preserved?
• Are the lists already fully in memory, or are they streams/iterators?
• Must the merge be stable (preserve original relative order for equal elements)?
• What are the size limits (n, m), and what time/memory limits apply?

Refine it: Specify input types, output type, ordering rules, and complexity expectations (e.g., O(n+m)).

Task 4: “Compute a Discount”

Vague problem statement: “Compute the discounted price.”

Identify missing constraints:

• Inputs: original price, discount rate, coupon rules, taxes?
• Rounding: round at each step or only at the end? To cents? Which rounding rule?
• Bounds: Can discount exceed 100%? Can price be negative?
• Output: numeric type, currency formatting, and whether to include currency symbol.

Refine it: Produce a specification that would let two programmers implement the same behavior.

Task 5: Constraint-driven choice

Problem statement: “Given a list of integers, return true if any value repeats.”

Create two versions of the constraints and explain (briefly) how they change the solution choice:

• Version A: n ≤ 5,000, memory is very limited.
• Version B: n ≤ 2,000,000, time is strict, memory is moderate.

For each version, specify inputs/outputs and list constraints/edge cases (e.g., negative numbers, large ranges, duplicates frequency).