Coding Interview Tip #1: Let Input Size Determine Your Algorithm

Why Input Size Matters

One of the most common mistakes in coding interviews is jumping straight into coding without examining the input constraints.

Experienced candidates often spend the first 30 seconds answering a simple question:

How large can n become?

The answer immediately eliminates many possible solutions.

For example:

In many interview problems, multiple solutions exist. The best solution is usually the one that matches the input size.

Example: Two Sum (LeetCode #1)

Suppose the interviewer asks:

Given an array of integers, return the indices of two numbers that add up to a target.

Option 1: Brute Force

Check every pair.

for i in range(n):
    for j in range(i + 1, n):
        ...

Time Complexity: O(n²)

Option 2: Hash Map

Store previously seen numbers.

for i in range(n):
    if target - nums[i] in seen:
        ...

Time Complexity: O(n)

Which One Is Better?

It depends on n.

If:

n = 50

Both solutions are acceptable.

But if:

n = 100,000

Then:

O(n²) ≈ 10,000,000,000 operations

Impossible.

While:

O(n) ≈ 100,000 operations

Easy.

Get Beyond51’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

The input size tells us which solution is practical.

Gold Rule: Remember 10⁷

Many interviewers and competitive programmers use the following rule of thumb:

A modern CPU can perform roughly 10⁸ simple operations per second in C++.

However:

• 10⁸ is a theoretical upper limit
• 10⁷ is a safer target
• Python is typically 3–10× slower than C++

For Python interviews:

When evaluating a solution, always estimate:

Input Size × Complexity

and compare it against:

10⁷ operations

Classic Algorithms vs Input Size

n ≤ 20

Possible:

• Backtracking
• DFS Enumeration
• Bitmask Search
• O(2ⁿ)
• O(n!)

Examples:

• N-Queens
• Subsets
• Permutations

n ≤ 100

Possible:

• Dynamic Programming
• Floyd-Warshall
• O(n³)

Examples:

• All-Pairs Shortest Path
• Matrix DP

n ≤ 1,000

Possible:

• O(n²)
• Graph Traversal
• DP

Examples:

• Longest Increasing Subsequence (DP version)
• Grid Problems

n ≤ 100,000

Possible:

• Sorting
• Binary Search
• Heap
• Union Find

Target:

O(n log n)

Examples:

• Merge Intervals
• Top K Elements
• Search Problems

n ≥ 1,000,000

Possible:

• Linear Scan
• Prefix Sum
• Sliding Window
• Hash Table

Target:

O(n)

Examples:

• Two Sum
• Maximum Subarray
• Longest Substring Without Repeating Characters

Interview Shortcut

When you see a problem, ask yourself:

1. What is the maximum value of n?
2. What complexity can n afford?
3. Which algorithms fit within that complexity?
4. Only then start coding.

This approach often narrows dozens of possible solutions down to just one or two.

Conclusion

The fastest way to choose the right algorithm is not by memorizing hundreds of patterns.

It’s by understanding the input size.

Before writing code, estimate:

n
↓
Allowed Complexity
↓
Candidate Algorithms
↓
Implementation

Remember:

Input size doesn’t just describe the problem.

It often tells you the solution.