Which input constraints should you clarify before choosing an interview algorithm?

Input size, value range, ordering, duplicates, allowed mutations, and the exact output. These determine which operations are affordable and which assumptions are valid.

What does a loop invariant describe?

A property that holds at a defined point in every iteration. Show it holds initially, survives an iteration, and implies the result when the loop ends.

When analyzing nested loops, why can multiplying their written bounds overestimate runtime?

The loops may share progress. If an inner pointer only advances across the input once, its total work can be O(n), even inside an outer loop.

What is the difference between auxiliary space and total space?

Auxiliary space counts extra working storage. Total space also includes the input and, depending on the stated convention, the output. State which measure you report.

What does amortized O(1) mean for an operation sequence?

The total cost of m operations is O(m), even if some individual operations are expensive. It is a sequence-wide bound, not a probability claim.

How does a counterexample help evaluate a proposed greedy rule?

One valid input where the rule fails disproves it. Try small cases that force a locally attractive choice to block a better later choice.

Why should an algorithm's correctness argument address termination separately?

Preserving the right property is not enough if the loop never stops. Identify a bounded measure that moves strictly toward termination.

What runtime lower bound follows from returning k separate results?

At least Ω(k) time to emit them, or more if each result has multiple elements. Include output size when analyzing enumeration algorithms.

What should you say when quoting expected O(1) hash-table lookup?

It assumes a suitable hash distribution and controlled load factor. It is not a worst-case guarantee; hashing a long key can also cost time.

Which edge cases best expose index and boundary errors?

Empty input, one element, all equal elements, and answers at either end. Also check the smallest input that enters each branch.

Why can sorting be an invalid optimization even when it reduces later search work?

Sorting may destroy required order or original indices. Preserve the needed information or choose an approach that respects the input contract.

What does an exchange argument establish in a greedy proof?

That an optimal solution can be changed to include the greedy choice without making its objective worse. The remaining problem must still fit the same reasoning.

Why can recursion use O(n) space even without an explicit collection?

Each active call occupies a stack frame. A chain of n calls can therefore need O(n) auxiliary space.

What evidence should accompany a faster solution after presenting brute force?

Name the repeated work or discarded search space, explain why the shortcut is safe, and give the resulting time and space bounds.

What makes an array useful when a problem repeatedly accesses positions by index?

Constant-time indexed access in the usual RAM model. Inserting or removing near the front can still require shifting O(n) elements.

What should 'one character' mean before solving a string problem?

Clarify whether the unit is a byte, code unit, Unicode code point, or user-perceived character. Indexing and length depend on that choice.

An unsorted array needs a duplicate-existence check. Which structure fits?

A hash set of values seen so far. Stop when a value is already present; expected O(n) time and O(n) space.

For two-sum on an unsorted array, what should a hash map store?

Previously seen values mapped to their indices. For each value x, look for target − x before inserting x, so the same position is not reused.

When does a frequency array beat a hash map for counting?

When keys come from a small known integer or character range. Direct indexing gives predictable access with space proportional to that range.

Why is repeated concatenation risky when constructing a long immutable string?

Each append may copy the existing prefix, producing quadratic total work. Collect pieces and join them, or use an appropriate mutable builder.

How can you group anagrams without comparing every pair of words?

Map a canonical character signature to a group. Sorted characters work; a frequency tuple works when the alphabet and character rules are fixed.

What information does a set lose compared with a frequency map?

Multiplicity. A set can answer whether a value exists but cannot distinguish one occurrence from several.

How can a hash set support finding the longest consecutive integer run in expected O(n) time?

Start scanning a run only at values whose predecessor is absent. Each distinct value then belongs to one forward scan; iterate distinct values.

Why can a mutable object be a dangerous hash-map key?

Changing fields used by its hash or equality can make the stored entry unreachable by ordinary lookup. Use immutable keys or stable key values.

An array contains only integers from 0 through k. When is counting sort attractive?

When k is small enough: count each value and reconstruct the order in O(n + k) time with O(k) count storage. General arbitrary keys need another approach.

How can a single scan find both the minimum value and its earliest index?

Keep the current minimum and index; update only on a strictly smaller value. Updating on equality would select a later occurrence.

How do you compare two strings as multisets of characters?

Compare character counts under the same character interpretation. Order does not matter, but every character's multiplicity does.

Why does a hash collision not imply that two keys are equal?

A hash compresses many possible keys into fewer codes. A correct table also checks key equality when resolving collisions.

When is sorting a useful preprocessing step for detecting duplicate values?

When reordering is allowed and O(n log n) time is acceptable. Equal values become adjacent, so a scan finds duplicates without a separate hash set.

What is the key distinction between a subarray and a subsequence?

A subarray is contiguous. A subsequence preserves relative order but may skip positions. Sliding-window methods usually depend on contiguity.

For an unsorted two-sum query, how do hashing and sorting trade off?

Hashing gives expected O(n) time with O(n) extra storage. Sorting plus two pointers costs O(n log n) time and requires care with original indices and mutation.

How can a frequency map detect whether any permutation of a string can be a palindrome?

Count odd frequencies. At most one character may have an odd count; all other occurrences must form mirrored pairs.

Why must compound hash keys encode boundaries unambiguously?

Naive concatenation can merge different tuples into the same key, such as (1, 23) and (12, 3). Use tuples or a length-aware encoding.

What does coordinate compression preserve about numeric values?

Their relative order and equality, by replacing distinct sorted values with ranks. It does not preserve numeric distances or sums.

How can you compute products except self without division?

Combine the product strictly before each position with the product strictly after it. Prefix and suffix passes handle zeros; use a numeric type large enough for the products.

Why can a count of matching pairs overflow even when every input value fits in an integer?

The number of matching pairs can grow quadratically with the input length. Size the result type for the count, not just the input values.

A sorted array needs a pair with a target sum. Which search pattern fits?

Opposite-end two pointers. Compare the endpoint sum with the target and move the endpoint that can move the sum in the needed direction.

What invariant supports in-place removal of unwanted array values with read and write pointers?

The prefix before write contains exactly the retained values from the processed input, in order. Read scans every input position once.

How can two pointers check a palindrome without constructing a reversed string?

Compare matching elements from opposite ends and move inward. Any mismatch rejects it; the pointers meeting or crossing completes the check.

When does a fixed-size sliding window apply?

When every candidate is a contiguous block of the same length and its summary can be updated as one element enters and one leaves.

What invariant should a longest-window algorithm restore after adding a new rightmost element?

The current window satisfies the required constraint. Move the left boundary and update state until validity returns, then consider its length.

Why is moving the left pointer safe when a sorted-array endpoint sum is too small?

With that left value, every candidate at or before the current right endpoint gives an equally small or smaller sum. The left position cannot form a valid pair.

How does a three-way partition maintain separate regions?

Track a low region, a middle region, an unclassified region, and a high region. Each step shrinks the unclassified region by placing one element correctly.

How do you update the sum when a fixed-size window moves one position?

Subtract the outgoing value and add the incoming value. After initializing the first window, all moves together take O(n) time.

Why can a variable sliding window run in O(n) despite a nested shrink loop?

Each boundary advances at most n times. With constant-time state updates, the total number of additions and removals is linear.

For the longest substring without repeated characters, what window state is useful?

Character counts or last-seen positions. Move the left boundary past the conflicting occurrence while ensuring it never moves backward.

Why does opposite-end target-sum search fail on a generally unsorted array?

Moving an endpoint no longer changes the sum predictably. The algorithm can discard a valid pair because the order-based elimination proof is missing.

A positive-number array needs the shortest nonempty subarray with sum at least a positive T. When should the left boundary move?

While the current sum is at least T, record the length and remove the leftmost value. Positive values make further shrinking reduce the sum predictably.

For windows with at most k distinct values, what must happen when an outgoing count becomes zero?

Remove that value from the active distinct set or decrement the distinct counter. A zero count must not still count as present.

What changes when a fixed-window length exceeds the input length?

There is no complete window. Return the contract's empty or missing-result value instead of treating a partial block as a valid candidate.

How do you merge two sorted arrays with forward pointers?

Repeatedly take the smaller unconsumed element, then append the remaining suffix. Each element is consumed once, giving O(m + n) time.

Coding Interview Patterns Flashcards: Signals, Invariants & Complexity

Practice coding interview patterns with 210 English flashcards on problem signals, invariants, complexity, edge cases, and choosing between approaches. Language-agnostic DSA review to pair with hands-on coding.

Tác giả Open Study Contributor

Về bộ thẻ này

Coding interview patterns become useful when you can explain why an approach fits. These 210 English flashcards practice recognizing problem signals, stating invariants, checking prerequisites, comparing approaches, and diagnosing a broken assumption.

The sequence starts with constraints and complexity, then moves through arrays, strings, hashing, two pointers, sliding windows, prefix sums, binary search, intervals, stacks, linked lists, trees, heaps, tries, graphs, union-find, topological sorting, backtracking, greedy choices, dynamic programming, and bit techniques. Each topic builds from its basic idea toward the conditions that make it work.

Cards map short scenarios to candidate patterns, named patterns to invariants and costs, and failed assumptions to explanations or alternatives. Selected contrast prompts distinguish neighboring ideas such as subarrays and subsequences, BFS and DFS, or greedy choice and dynamic programming. Mechanical reverse cards, problem-number recall, language-specific API memorization, and full solution listings are excluded because they add little to this reasoning-focused review. Answer each prompt before turning the card, then test the idea by coding a fresh example.

This is a language-agnostic companion to practical DSA exercises. It complements the Blind 75 Python solutions deck by teaching reusable reasoning across problems. It was authored independently in English, not translated or paraphrased from another catalog package.

The questions, answers, organization, metadata, and original generated cover are released under CC0 1.0 to the extent applicable rights exist. Algorithm facts are common knowledge; no commercial deck text or third-party media was copied. This is an independent study resource with no affiliation to an employer or interview platform.

Thẻ trong bộ này

Thẻ 1
Câu hỏi
Which input constraints should you clarify before choosing an interview algorithm?
Câu trả lời
Input size, value range, ordering, duplicates, allowed mutations, and the exact output. These determine which operations are affordable and which assumptions are valid.
Thẻ 2
Câu hỏi
What does a loop invariant describe?
Câu trả lời
A property that holds at a defined point in every iteration. Show it holds initially, survives an iteration, and implies the result when the loop ends.
Thẻ 3
Câu hỏi
When analyzing nested loops, why can multiplying their written bounds overestimate runtime?
Câu trả lời
The loops may share progress. If an inner pointer only advances across the input once, its total work can be O(n), even inside an outer loop.
Thẻ 4
Câu hỏi
What is the difference between auxiliary space and total space?
Câu trả lời
Auxiliary space counts extra working storage. Total space also includes the input and, depending on the stated convention, the output. State which measure you report.
Thẻ 5
Câu hỏi
What does amortized O(1) mean for an operation sequence?
Câu trả lời
The total cost of m operations is O(m), even if some individual operations are expensive. It is a sequence-wide bound, not a probability claim.
Thẻ 6
Câu hỏi
How does a counterexample help evaluate a proposed greedy rule?
Câu trả lời
One valid input where the rule fails disproves it. Try small cases that force a locally attractive choice to block a better later choice.
Thẻ 7
Câu hỏi
Why should an algorithm's correctness argument address termination separately?
Câu trả lời
Preserving the right property is not enough if the loop never stops. Identify a bounded measure that moves strictly toward termination.
Thẻ 8
Câu hỏi
What runtime lower bound follows from returning k separate results?
Câu trả lời
At least Ω(k) time to emit them, or more if each result has multiple elements. Include output size when analyzing enumeration algorithms.
Thẻ 9
Câu hỏi
What should you say when quoting expected O(1) hash-table lookup?
Câu trả lời
It assumes a suitable hash distribution and controlled load factor. It is not a worst-case guarantee; hashing a long key can also cost time.
Thẻ 10
Câu hỏi
Which edge cases best expose index and boundary errors?
Câu trả lời
Empty input, one element, all equal elements, and answers at either end. Also check the smallest input that enters each branch.
Thẻ 11
Câu hỏi
Why can sorting be an invalid optimization even when it reduces later search work?
Câu trả lời
Sorting may destroy required order or original indices. Preserve the needed information or choose an approach that respects the input contract.
Thẻ 12
Câu hỏi
What does an exchange argument establish in a greedy proof?
Câu trả lời
That an optimal solution can be changed to include the greedy choice without making its objective worse. The remaining problem must still fit the same reasoning.
Thẻ 13
Câu hỏi
Why can recursion use O(n) space even without an explicit collection?
Câu trả lời
Each active call occupies a stack frame. A chain of n calls can therefore need O(n) auxiliary space.
Thẻ 14
Câu hỏi
What evidence should accompany a faster solution after presenting brute force?
Câu trả lời
Name the repeated work or discarded search space, explain why the shortcut is safe, and give the resulting time and space bounds.
Thẻ 15
Câu hỏi
What makes an array useful when a problem repeatedly accesses positions by index?
Câu trả lời
Constant-time indexed access in the usual RAM model. Inserting or removing near the front can still require shifting O(n) elements.
Thẻ 16
Câu hỏi
What should 'one character' mean before solving a string problem?
Câu trả lời
Clarify whether the unit is a byte, code unit, Unicode code point, or user-perceived character. Indexing and length depend on that choice.
Thẻ 17
Câu hỏi
An unsorted array needs a duplicate-existence check. Which structure fits?
Câu trả lời
A hash set of values seen so far. Stop when a value is already present; expected O(n) time and O(n) space.
Thẻ 18
Câu hỏi
For two-sum on an unsorted array, what should a hash map store?
Câu trả lời
Previously seen values mapped to their indices. For each value x, look for target − x before inserting x, so the same position is not reused.
Thẻ 19
Câu hỏi
When does a frequency array beat a hash map for counting?
Câu trả lời
When keys come from a small known integer or character range. Direct indexing gives predictable access with space proportional to that range.
Thẻ 20
Câu hỏi
Why is repeated concatenation risky when constructing a long immutable string?
Câu trả lời
Each append may copy the existing prefix, producing quadratic total work. Collect pieces and join them, or use an appropriate mutable builder.
Thẻ 21
Câu hỏi
How can you group anagrams without comparing every pair of words?
Câu trả lời
Map a canonical character signature to a group. Sorted characters work; a frequency tuple works when the alphabet and character rules are fixed.
Thẻ 22
Câu hỏi
What information does a set lose compared with a frequency map?
Câu trả lời
Multiplicity. A set can answer whether a value exists but cannot distinguish one occurrence from several.
Thẻ 23
Câu hỏi
How can a hash set support finding the longest consecutive integer run in expected O(n) time?
Câu trả lời
Start scanning a run only at values whose predecessor is absent. Each distinct value then belongs to one forward scan; iterate distinct values.
Thẻ 24
Câu hỏi
Why can a mutable object be a dangerous hash-map key?
Câu trả lời
Changing fields used by its hash or equality can make the stored entry unreachable by ordinary lookup. Use immutable keys or stable key values.
Thẻ 25
Câu hỏi
An array contains only integers from 0 through k. When is counting sort attractive?
Câu trả lời
When k is small enough: count each value and reconstruct the order in O(n + k) time with O(k) count storage. General arbitrary keys need another approach.
Thẻ 26
Câu hỏi
How can a single scan find both the minimum value and its earliest index?
Câu trả lời
Keep the current minimum and index; update only on a strictly smaller value. Updating on equality would select a later occurrence.
Thẻ 27
Câu hỏi
How do you compare two strings as multisets of characters?
Câu trả lời
Compare character counts under the same character interpretation. Order does not matter, but every character's multiplicity does.
Thẻ 28
Câu hỏi
Why does a hash collision not imply that two keys are equal?
Câu trả lời
A hash compresses many possible keys into fewer codes. A correct table also checks key equality when resolving collisions.
Thẻ 29
Câu hỏi
When is sorting a useful preprocessing step for detecting duplicate values?
Câu trả lời
When reordering is allowed and O(n log n) time is acceptable. Equal values become adjacent, so a scan finds duplicates without a separate hash set.
Thẻ 30
Câu hỏi
What is the key distinction between a subarray and a subsequence?
Câu trả lời
A subarray is contiguous. A subsequence preserves relative order but may skip positions. Sliding-window methods usually depend on contiguity.
Thẻ 31
Câu hỏi
For an unsorted two-sum query, how do hashing and sorting trade off?
Câu trả lời
Hashing gives expected O(n) time with O(n) extra storage. Sorting plus two pointers costs O(n log n) time and requires care with original indices and mutation.
Thẻ 32
Câu hỏi
How can a frequency map detect whether any permutation of a string can be a palindrome?
Câu trả lời
Count odd frequencies. At most one character may have an odd count; all other occurrences must form mirrored pairs.
Thẻ 33
Câu hỏi
Why must compound hash keys encode boundaries unambiguously?
Câu trả lời
Naive concatenation can merge different tuples into the same key, such as (1, 23) and (12, 3). Use tuples or a length-aware encoding.
Thẻ 34
Câu hỏi
What does coordinate compression preserve about numeric values?
Câu trả lời
Their relative order and equality, by replacing distinct sorted values with ranks. It does not preserve numeric distances or sums.
Thẻ 35
Câu hỏi
How can you compute products except self without division?
Câu trả lời
Combine the product strictly before each position with the product strictly after it. Prefix and suffix passes handle zeros; use a numeric type large enough for the products.
Thẻ 36
Câu hỏi
Why can a count of matching pairs overflow even when every input value fits in an integer?
Câu trả lời
The number of matching pairs can grow quadratically with the input length. Size the result type for the count, not just the input values.
Thẻ 37
Câu hỏi
A sorted array needs a pair with a target sum. Which search pattern fits?
Câu trả lời
Opposite-end two pointers. Compare the endpoint sum with the target and move the endpoint that can move the sum in the needed direction.
Thẻ 38
Câu hỏi
What invariant supports in-place removal of unwanted array values with read and write pointers?
Câu trả lời
The prefix before write contains exactly the retained values from the processed input, in order. Read scans every input position once.
Thẻ 39
Câu hỏi
How can two pointers check a palindrome without constructing a reversed string?
Câu trả lời
Compare matching elements from opposite ends and move inward. Any mismatch rejects it; the pointers meeting or crossing completes the check.
Thẻ 40
Câu hỏi
When does a fixed-size sliding window apply?
Câu trả lời
When every candidate is a contiguous block of the same length and its summary can be updated as one element enters and one leaves.
Thẻ 41
Câu hỏi
What invariant should a longest-window algorithm restore after adding a new rightmost element?
Câu trả lời
The current window satisfies the required constraint. Move the left boundary and update state until validity returns, then consider its length.
Thẻ 42
Câu hỏi
Why is moving the left pointer safe when a sorted-array endpoint sum is too small?
Câu trả lời
With that left value, every candidate at or before the current right endpoint gives an equally small or smaller sum. The left position cannot form a valid pair.
Thẻ 43
Câu hỏi
How does a three-way partition maintain separate regions?
Câu trả lời
Track a low region, a middle region, an unclassified region, and a high region. Each step shrinks the unclassified region by placing one element correctly.
Thẻ 44
Câu hỏi
How do you update the sum when a fixed-size window moves one position?
Câu trả lời
Subtract the outgoing value and add the incoming value. After initializing the first window, all moves together take O(n) time.
Thẻ 45
Câu hỏi
Why can a variable sliding window run in O(n) despite a nested shrink loop?
Câu trả lời
Each boundary advances at most n times. With constant-time state updates, the total number of additions and removals is linear.
Thẻ 46
Câu hỏi
For the longest substring without repeated characters, what window state is useful?
Câu trả lời
Character counts or last-seen positions. Move the left boundary past the conflicting occurrence while ensuring it never moves backward.
Thẻ 47
Câu hỏi
Why does opposite-end target-sum search fail on a generally unsorted array?
Câu trả lời
Moving an endpoint no longer changes the sum predictably. The algorithm can discard a valid pair because the order-based elimination proof is missing.
Thẻ 48
Câu hỏi
A positive-number array needs the shortest nonempty subarray with sum at least a positive T. When should the left boundary move?
Câu trả lời
While the current sum is at least T, record the length and remove the leftmost value. Positive values make further shrinking reduce the sum predictably.
Thẻ 49
Câu hỏi
For windows with at most k distinct values, what must happen when an outgoing count becomes zero?
Câu trả lời
Remove that value from the active distinct set or decrement the distinct counter. A zero count must not still count as present.
Thẻ 50
Câu hỏi
What changes when a fixed-window length exceeds the input length?
Câu trả lời
There is no complete window. Return the contract's empty or missing-result value instead of treating a partial block as a valid candidate.
Thẻ 51
Câu hỏi
How do you merge two sorted arrays with forward pointers?
Câu trả lời
Repeatedly take the smaller unconsumed element, then append the remaining suffix. Each element is consumed once, giving O(m + n) time.
Thẻ 52
Câu hỏi
Why must a minimum-cover substring track multiplicities of required characters?
Câu trả lời
A target can require the same character more than once. A set of required characters would mark an undersupplied window as complete.
Thẻ 53
Câu hỏi
How can counting subarrays with exactly k distinct values, for k ≥ 1, use an at-most helper?
Câu trả lời
Compute atMost(k) − atMost(k − 1). The helper counts all valid subarrays ending at each right boundary after restoring the distinct-value limit.
Thẻ 54
Câu hỏi
Why can a negative value break the usual shortest-sum sliding-window argument?
Câu trả lời
Removing it increases the sum, and adding one can decrease the sum. The monotonic relation between window size and sum no longer holds.
Thẻ 55
Câu hỏi
What does 'fast and slow pointers' mean when removing duplicates from a sorted array?
Câu trả lời
A read pointer scans candidates while a write pointer marks the next unique slot. Sorting makes equal values adjacent, so the retained prefix can stay compact.
Thẻ 56
Câu hỏi
What invariant prevents overwriting unread data during a backward merge into spare array capacity?
Câu trả lời
The suffix after the write pointer already contains the largest merged elements. Filling from the end leaves the remaining source elements unread and intact.
Thẻ 57
Câu hỏi
Why is 'find a contiguous range' alone insufficient to justify a variable sliding window?
Câu trả lời
You also need a safe boundary-movement rule. Check how adding and removing elements affect the condition; contiguity by itself gives no such guarantee.
Thẻ 58
Câu hỏi
After restoring an at-most window's validity, why are there right − left + 1 valid subarrays ending at right?
Câu trả lời
Every suffix starting between left and right is valid when removing elements cannot violate the constraint. Count those starts, including the one-element suffix.
Thẻ 59
Câu hỏi
How can you avoid duplicate value pairs in a sorted two-pointer enumeration?
Câu trả lời
After emitting a pair, skip equal values on both sides. First confirm the output wants unique value pairs, since index-pair counting needs different handling.
Thẻ 60
Câu hỏi
When does a character-frequency sliding window detect an anagram of a pattern?
Câu trả lời
When the window has the pattern's length and identical character counts. Maintain count differences or a mismatch counter as the window moves.
Thẻ 61
Câu hỏi
What does a prefix-sum array P mean when P[0] = 0?
Câu trả lời
P[i] is the sum of the first i input elements. The extra zero represents the empty prefix and makes ranges beginning at index 0 work uniformly.
Thẻ 62
Câu hỏi
When is binary search valid on a Boolean predicate over ordered candidates?
Câu trả lời
When the predicate changes at most once, such as false then true. The search uses that monotonic boundary to discard a whole interval.
Thẻ 63
Câu hỏi
Which workload favors a difference array?
Câu trả lời
Many range additions followed by final value reconstruction. Mark each range's start and end changes, then take one prefix sum.
Thẻ 64
Câu hỏi
In a lower-bound search over [lo, hi), what does hi initially equal for an n-element array?
Câu trả lời
n, an exclusive boundary. The result can equal n when no element is at least the target, so do not index the array without checking.
Thẻ 65
Câu hỏi
For a static array, how do prefix sums answer the half-open range [l, r)?
Câu trả lời
Return P[r] − P[l]. Building P takes O(n) time and space; each range-sum query then takes O(1).
Thẻ 66
Câu hỏi
How can prefix sums count subarrays whose sum equals k when negative values are allowed?
Câu trả lời
For each current prefix p, add the number of earlier prefixes equal to p − k, then record p. A frequency map gives expected O(n) time.
Thẻ 67
Câu hỏi
Why is binary-searching an answer different from binary-searching an input array?
Câu trả lời
The candidates are possible result values. A feasibility check tells which side contains the boundary, even if the original input is unsorted.
Thẻ 68
Câu hỏi
How does a difference array encode an addition of v to [l, r)?
Câu trả lời
Add v at l and subtract v at r, using a boundary slot when needed. The reconstructed prefix totals apply v only within that range.
Thẻ 69
Câu hỏi
For lower bound, how should equality with the target move the search boundary?
Câu trả lời
Move hi to mid. An equal element is a candidate, but an earlier equal or qualifying element may still exist.
Thẻ 70
Câu hỏi
Why initialize the prefix-frequency map with zero appearing once?
Câu trả lời
It represents the empty prefix before the array. This lets a subarray starting at index 0 contribute to the count.
Thẻ 71
Câu hỏi
Why are plain prefix sums inconvenient for many interleaved point updates and range-sum queries?
Câu trả lời
Changing one value can invalidate a long suffix of prefix sums. A Fenwick tree or segment tree can support both operations in O(log n).
Thẻ 72
Câu hỏi
How can you binary-search the minimum capacity needed to finish ordered work within a deadline?
Câu trả lời
Define whether a capacity suffices, prove larger capacities remain feasible, bracket a feasible answer, and search for the first feasible capacity.
Thẻ 73
Câu hỏi
What must every binary-search iteration do to guarantee termination?
Câu trả lời
Strictly shrink the candidate interval while preserving the boundary invariant. Mixing inclusive and exclusive update rules can leave the same interval unchanged.
Thẻ 74
Câu hỏi
For the longest subarray with a specified sum, which occurrence of each prefix sum should you retain?
Câu trả lời
The earliest index. For a later endpoint, it gives the longest matching span; overwriting it with a later occurrence can shorten the answer.
Thẻ 75
Câu hỏi
What runtime should you report for binary search with a nonconstant feasibility check?
Câu trả lời
O(C log R), where C is one check's cost and R is the number of discrete candidates. Include any preprocessing separately.
Thẻ 76
Câu hỏi
How can prefix sums turn a longest balanced binary subarray into an equal-prefix problem?
Câu trả lời
Map one symbol to +1 and the other to −1. Equal prefix sums enclose a zero-sum range with equal counts of the two symbols.
Thẻ 77
Câu hỏi
What is upper bound in a sorted array?
Câu trả lời
The first position whose value is strictly greater than the target, or n if none exists. Lower bound instead finds the first value at least the target.
Thẻ 78
Câu hỏi
Why must a prefix-sum counting algorithm query before recording the current prefix?
Câu trả lời
Recording first can count the empty subarray ending at the current boundary, especially for target zero. Query only earlier prefixes for nonempty ranges.
Thẻ 79
Câu hỏi
How do you safely compute a midpoint in a fixed-width integer search?
Câu trả lời
Use lo + (hi − lo) / 2 with integer division when the nonnegative difference fits the type. Choose bounds or a wider type that also keep the subtraction safe.
Thẻ 80
Câu hỏi
Why can duplicate values degrade searching a rotated sorted array to O(n)?
Câu trả lời
Equal endpoints and midpoint can hide which side is sorted. Some cases permit discarding only one boundary element at a time.
Thẻ 81
Câu hỏi
What preprocessing usually simplifies merging overlapping intervals?
Câu trả lời
Sort by start coordinate. Keep the current merged interval and either extend its end or emit it when the next interval starts beyond it.
Thẻ 82
Câu hỏi
Which data structure matches nested bracket validation?
Câu trả lời
A stack of unmatched opening brackets. Each closing bracket must match the most recent unmatched opener, and the stack must be empty at the end.
Thẻ 83
Câu hỏi
A problem asks for each element's next greater element. Which pattern is promising?
Câu trả lời
A monotonic stack of unresolved positions. A new larger value resolves the smaller pending values it overtakes.
Thẻ 84
Câu hỏi
Why must interval endpoint conventions be explicit?
Câu trả lời
Touching endpoints overlap for closed intervals, but adjacent half-open intervals do not. The convention changes merge tests and event ordering.
Thẻ 85
Câu hỏi
How can a sweep line find the maximum number of simultaneous intervals?
Câu trả lời
Turn starts and ends into signed events, sort by coordinate, and track the running active count. Handle same-coordinate ties according to the endpoint convention.
Thẻ 86
Câu hỏi
Why is one pass after sorting enough to merge intervals?
Câu trả lời
No later interval starts earlier than the next one being inspected. Once that start is beyond the current end, future intervals cannot bridge the gap.
Thẻ 87
Câu hỏi
What information should a stack store for next-greater distances?
Câu trả lời
Indices, so the distance is currentIndex − previousIndex. Values alone do not identify positions or distinguish repeated occurrences.
Thẻ 88
Câu hỏi
Why is counting opening and closing brackets insufficient to validate their sequence?
Câu trả lời
Counts ignore order and nesting. A closing bracket may appear before its opener, or bracket types may cross despite balanced totals.
Thẻ 89
Câu hỏi
For half-open intervals [start, end), how should equal-time starts and ends affect room counts?
Câu trả lời
Process ends before starts, or aggregate their net change before evaluating the active count for the next segment. A room freed at time t can be reused at t.
Thẻ 90
Câu hỏi
Why is a monotonic-stack algorithm often O(n) even though one step can pop many items?
Câu trả lời
Each item is pushed once and popped at most once. Summed across the scan, stack operations are linear.
Thẻ 91
Câu hỏi
How can a stack help simplify an absolute filesystem path lexically?
Câu trả lời
Process components: ignore empty components and '.', pop for '..' when possible, and push ordinary names. This lexical result does not resolve symbolic links.
Thẻ 92
Câu hỏi
How can a monotonic deque find each sliding-window maximum?
Câu trả lời
Keep candidate indices in decreasing value order. Remove expired indices from the front and dominated values from the back; the front gives the maximum.
Thẻ 93
Câu hỏi
What mistake can lose coverage when merging an interval contained inside the current one?
Câu trả lời
Replacing the current end with the new end. Use the larger end so a nested interval cannot shrink the merged coverage.
Thẻ 94
Câu hỏi
For a strictly next-greater query, what should happen to an equal-valued stack entry?
Câu trả lời
Do not resolve it with the equal value. With a decreasing stack of unresolved indices, pop only when the new value is strictly greater.
Thẻ 95
Câu hỏi
What event allows a monotonic stack to finalize a rectangle in a histogram?
Câu trả lời
A shorter bar supplies a right limit for taller bars being popped. A popped bar's candidate span starts after the new stack top, or at index 0 if the stack is empty. Handle equal heights consistently.
Thẻ 96
Câu hỏi
What comparison detects overlap between two nonempty half-open intervals?
Câu trả lời
max(start1, start2) < min(end1, end2). A strict comparison excludes intervals that only touch.
Thẻ 97
Câu hỏi
How does a stack support evaluating a postfix arithmetic expression?
Câu trả lời
Push operands; for an operator, pop its right operand and then its left operand, compute, and push the result. Preserve order for subtraction and division.
Thẻ 98
Câu hỏi
Why can a newer value dominate an older value in a sliding-window maximum deque?
Câu trả lời
If the newer value is at least as large, it expires no earlier and is never worse as a future maximum. The older candidate can be removed.
Thẻ 99
Câu hỏi
How can you merge two already sorted lists of disjoint intervals to find their intersections?
Câu trả lời
Compare one interval from each list, emit any overlap, then advance the one with the earlier end. Total time is O(m + n).
Thẻ 100
Câu hỏi
Why must a histogram stack algorithm handle bars still pending after the scan?
Câu trả lời
Those bars may extend to the array's end and contain the largest rectangle. Flush them using the end boundary or a suitable sentinel.
Thẻ 101
Câu hỏi
What must you save before reversing a singly linked list node's next pointer?
Câu trả lời
Its original next node. Otherwise rewiring can lose access to the remaining list.
Thẻ 102
Câu hỏi
Why does a dummy head simplify linked-list insertion and deletion?
Câu trả lời
It supplies a predecessor even when the real head changes. The same pointer update can handle both the first node and interior nodes.
Thẻ 103
Câu hỏi
How do fast and slow pointers detect a cycle in a singly linked list?
Câu trả lời
Advance one pointer one step and the other two. A meeting implies a cycle; reaching null with the fast pointer means the list terminates.
Thẻ 104
Câu hỏi
What does a recursive binary-tree traversal use for auxiliary space?
Câu trả lời
O(h) call-stack space, where h is tree height. This is O(log n) for a balanced tree but O(n) for a chain.
Thẻ 105
Câu hỏi
During iterative list reversal, what do prev and current represent?
Câu trả lời
prev heads the reversed processed prefix; current heads the unprocessed suffix. Rewire one node while preserving access to the suffix.
210 thẻ
Coding Interview Patterns Flashcards: Signals, Invariants & Complexity
Học bộ thẻ này miễn phí
Nibomo sẽ mở ra để bạn bắt đầu học.
Thẻ 106
Câu hỏi
How can you remove the nth node from the end of a list in one pass?
Câu trả lời
Start lead at the head and lag at a dummy head. Advance lead n nodes, then move both until lead is null; remove lag.next. Reject invalid n according to the input contract.
Thẻ 107
Câu hỏi
Which tree traversal naturally computes a value that depends on both children's results?
Câu trả lời
Postorder. Process left and right subtrees before combining their results at the parent.
Thẻ 108
Câu hỏi
How can you locate a cycle's entry after Floyd's two-speed pointers meet?
Câu trả lời
Reset one pointer to the head and move both one step at a time. Their next meeting is the entry; this follows from the distances modulo the cycle length.
Thẻ 109
Câu hỏi
What is the difference between tree depth and tree height?
Câu trả lời
Depth measures distance from the root to a node; height measures the longest downward distance to a leaf. State whether distances count edges or nodes.
Thẻ 110
Câu hỏi
How can you merge two sorted linked lists using O(1) auxiliary node storage?
Câu trả lời
Relink the smaller current node onto the result tail, advancing that list. Attach the remaining suffix when one list ends; existing nodes are reused.
Thẻ 111
Câu hỏi
When is breadth-first traversal more natural than depth-first traversal on a tree?
Câu trả lời
When results are grouped by depth or you need the nearest qualifying node by edge count. A queue processes one distance layer before the next.
Thẻ 112
Câu hỏi
Why must linked-list intersection compare node identity rather than node value?
Câu trả lời
Intersection means sharing the same node object and suffix. Separate nodes can hold equal values without the lists intersecting.
Thẻ 113
Câu hỏi
Why is checking only immediate children insufficient to validate a binary search tree?
Câu trả lời
A descendant can satisfy its parent yet violate an ancestor's constraint. Carry inherited lower and upper bounds, with an explicit duplicate policy.
Thẻ 114
Câu hỏi
What is the lowest common ancestor of two nodes in a rooted tree?
Câu trả lời
The deepest node that is an ancestor of both, allowing a node to be its own ancestor.
Thẻ 115
Câu hỏi
What property makes inorder traversal useful in a binary search tree?
Câu trả lời
It visits keys in sorted order under the tree's duplicate policy. In a strict BST, each visited key must be greater than the previous one.
Thẻ 116
Câu hỏi
Why must maximum tree-path sum separate its returned value from its global candidate?
Câu trả lời
The parent can extend only one downward branch. A complete path considered at the current node may join both children, but that fork cannot be extended upward.
Thẻ 117
Câu hỏi
How can two pointers find the intersection of two acyclic singly linked lists without measuring lengths?
Câu trả lời
After reaching a list's end, switch that pointer to the other head. Each traverses both lengths, so they meet at the shared node or at null.
Thẻ 118
Câu hỏi
What extra information makes preorder serialization unambiguous for an arbitrary binary tree?
Câu trả lời
Explicit null-child markers or another equivalent shape encoding. Values in preorder alone do not determine the structure.
Thẻ 119
Câu hỏi
Why can repeated subtree-height calculations make a tree-balance check O(n²)?
Câu trả lời
The same descendants may be scanned from many ancestors. Return height and balance together in one postorder traversal to visit each node once.
Thẻ 120
Câu hỏi
How does BST ordering guide a lowest-common-ancestor search for two existing distinct keys?
Câu trả lời
Move left if both keys are smaller and right if both are larger. The first split, or a node matching one key, is their lowest common ancestor.
Thẻ 121
Câu hỏi
What runtime does a search in an ordinary unbalanced BST guarantee?
Câu trả lời
O(h), where h is its height, and O(n) in the worst case. Logarithmic search requires a balance guarantee or a stated expected-shape assumption.
Thẻ 122
Câu hỏi
When computing a root-to-leaf path sum, why is reaching a null child insufficient for success?
Câu trả lời
A valid endpoint must be a leaf with no children. A missing child beside an existing child does not finish a root-to-leaf path.
Thẻ 123
Câu hỏi
What does a min-heap guarantee about its root and children?
Câu trả lời
The root is a minimum element, and each parent is no larger than its children. The whole array representation is not sorted.
Thẻ 124
Câu hỏi
A stream needs the k largest values seen so far. Which heap should you maintain?
Câu trả lời
A min-heap of at most k values. Its root is the smallest retained value, so a larger arrival can replace it.
Thẻ 125
Câu hỏi
What shared structure does a trie store?
Câu trả lời
Prefixes of keys. Following one edge per symbol reaches a key's prefix node, while a terminal marker distinguishes a complete stored key.
Thẻ 126
Câu hỏi
What are the usual binary-heap costs for peek, insertion, and root removal?
Câu trả lời
Peek is O(1); insertion and root removal are O(log n). Moving a changed element along one root-to-leaf path restores heap order.
Thẻ 127
Câu hỏi
How can a heap merge k sorted input streams?
Câu trả lời
Keep each nonempty stream's next element in a min-heap. Emit the minimum and replace it with that stream's next item. With k streams and N total elements, O(k + N log k) time includes initialization for k ≥ 2.
Thẻ 128
Câu hỏi
Why is bottom-up heap construction O(n), not O(n log n)?
Câu trả lời
Most nodes are near the leaves and can move only a short distance. Summing each node's possible sift-down work across all heights is linear.
Thẻ 129
Câu hỏi
How do two heaps support a running median?
Câu trả lời
Keep the lower half in a max-heap and the upper half in a min-heap, with sizes differing by at most one and every lower value no greater than every upper value.
Thẻ 130
Câu hỏi
What is a trie's lookup cost for a key of length L?
Câu trả lời
O(L) when each child transition is O(1). Child maps or ordered child containers can change that transition cost; space depends on stored prefixes and representation.
Thẻ 131
Câu hỏi
Why does a trie node need a terminal marker even if it has children?
Câu trả lời
A stored key can be a prefix of another key. The marker distinguishes a complete word from a prefix that merely leads to longer words.
Thẻ 132
Câu hỏi
When does sorting make more sense than a top-k heap?
Câu trả lời
When you need the entire sorted order or k is close to n and a full sort is acceptable. A heap's advantage is strongest when only a small retained subset is needed.
Thẻ 133
Câu hỏi
Why does a priority queue not by itself support efficient arbitrary deletion?
Câu trả lời
The heap efficiently exposes only its root. Removing another item needs its position, an indexed-heap design, or a lazy-deletion scheme with cleanup.
Thẻ 134
Câu hỏi
What output cost remains after a trie reaches a requested prefix?
Câu trả lời
Enumerating matching completions still costs time proportional to the visited subtree and emitted text. Prefix lookup does not make all autocomplete results free.
Thẻ 135
Câu hỏi
How can a priority queue break tied priorities without comparing the payloads?
Câu trả lời
Attach a unique increasing sequence number and compare priority first, then sequence number. Equal-priority items can then leave in insertion order without requiring an order on their payloads.
Thẻ 136
Câu hỏi
Why can a trie use more memory than a hash set of complete strings?
Câu trả lời
Nodes and child containers have overhead, especially for sparse branches. Shared prefixes save repeated symbols but do not guarantee a smaller representation.
Thẻ 137
Câu hỏi
What should graph modeling identify before choosing a traversal?
Câu trả lời
The states as vertices and legal transitions as edges, including direction and cost. A grid cell, word, or puzzle configuration can be a vertex.
Thẻ 138
Câu hỏi
When does ordinary BFS find a shortest path?
Câu trả lời
When every edge has the same nonnegative cost, including the unweighted case. Processing vertices by distance layer makes first discovery a shortest-edge-count path.
Thẻ 139
Câu hỏi
What is the space cost of an adjacency list compared with an adjacency matrix?
Câu trả lời
A list uses O(V + E) space; a matrix uses O(V²). A matrix gives constant-time edge lookup, while lists efficiently enumerate actual neighbors.
Thẻ 140
Câu hỏi
Which pattern finds all vertices reachable from a start vertex?
Câu trả lời
DFS or BFS with a visited set. Each reachable vertex and edge is processed a bounded number of times with adjacency lists.
Thẻ 141
Câu hỏi
What role does a parent map play in shortest-path traversal?
Câu trả lời
It records the predecessor used to reach each state. After reaching the target, follow parents backward and reverse the sequence to recover a path.
Thẻ 142
Câu hỏi
Why should BFS mark a vertex visited when enqueuing it?
Câu trả lời
To prevent several parents from adding it before its first removal. First enqueue already fixes its distance in an unweighted graph.
Thẻ 143
Câu hỏi
When is Dijkstra's algorithm appropriate?
Câu trả lời
For shortest paths with nonnegative edge weights. Its greedy finalization relies on no later path reducing a settled distance through a negative edge.
Thẻ 144
Câu hỏi
How can a grid traversal avoid confusing physical cells with full search states?
Câu trả lời
Include all information that changes future moves in the visited key, such as remaining obstacle removals or collected keys. Position alone may merge different states.
Thẻ 145
Câu hỏi
How do you detect a directed cycle with DFS?
Câu trả lời
Track unvisited, active, and finished vertices. An edge to an active vertex closes a cycle on the current recursion path.
Thẻ 146
Câu hỏi
Why can DFS with a visited set fail to find a shortest unweighted path?
Câu trả lời
Its first discovered route may follow a deep detour. DFS reachability order is not distance order; BFS provides that guarantee.
Thẻ 147
Câu hỏi
What does a topological ordering guarantee?
Câu trả lời
For every directed edge u → v, u appears before v. Such an ordering exists exactly when the directed graph is acyclic.
Thẻ 148
Câu hỏi
Why should stale priority-queue entries be skipped in a common Dijkstra implementation?
Câu trả lời
A vertex can receive a better distance after an older entry was pushed. Skip an entry whose stored distance differs from the current best distance.
Thẻ 149
Câu hỏi
For an undirected simple graph, why does DFS ignore the edge back to its parent when detecting cycles?
Câu trả lời
That edge is the same tree edge traversed in reverse, not a new cycle. A different already-visited neighbor indicates a cycle.
Thẻ 150
Câu hỏi
What does union-find answer efficiently?
Câu trả lời
Whether elements belong to the same connected component while components are merged. It does not store the actual connecting paths.
Thẻ 151
Câu hỏi
How does Kahn's algorithm build a topological ordering?
Câu trả lời
Enqueue all zero-indegree vertices, repeatedly remove one, and decrement its outgoing neighbors' indegrees. Enqueue each neighbor when its indegree becomes zero.
Thẻ 152
Câu hỏi
Which shortest-path algorithm handles edges weighted only 0 or 1 without a heap?
Câu trả lời
0–1 BFS with a deque. Push a relaxed zero-cost neighbor to the front and a one-cost neighbor to the back, preserving distance order.
Thẻ 153
Câu hỏi
Why is a boolean visited flag usually wrong for Dijkstra at first enqueue?
Câu trả lời
The first tentative distance need not be the shortest. Allow improvements; a vertex becomes settled when its smallest current distance is removed from the queue.
Thẻ 154
Câu hỏi
How do path compression and union by size or rank affect union-find complexity?
Câu trả lời
Together they give O(α(n)) amortized time per operation, where α is the inverse Ackermann function. The bound is effectively tiny for practical input sizes.
Thẻ 155
Câu hỏi
What does processing fewer than V vertices in Kahn's algorithm reveal?
Câu trả lời
A directed cycle remains. No vertex in the cyclic remainder can reach indegree zero after all removable dependencies are processed.
Thẻ 156
Câu hỏi
How can BFS compute distance from every grid cell to the nearest source?
Câu trả lời
Initialize the queue with all sources at distance zero. This multi-source BFS expands the nearest-source distance layers together.
Thẻ 157
Câu hỏi
Why can a topological ordering be nonunique?
Câu trả lời
Several vertices may currently have no remaining prerequisites. Choosing them in different orders can produce different valid orderings.
Thẻ 158
Câu hỏi
What happens when union-find receives an edge whose endpoints already share a representative?
Câu trả lời
The edge connects vertices already in one component. In incremental construction of an undirected forest, adding it creates a cycle.
Thẻ 159
Câu hỏi
Which algorithm can handle negative edge weights and detect a reachable negative cycle?
Câu trả lời
Bellman–Ford. Repeatedly relax all edges; an improvement after V − 1 full rounds indicates a negative cycle reachable from the source.
Thẻ 160
Câu hỏi
Why does traversal need an outer loop to count every connected component of an undirected graph?
Câu trả lời
One traversal reaches only one component. Start another traversal from each still-unvisited vertex and increment the component count.
Thẻ 161
Câu hỏi
How can topological order simplify shortest paths in a weighted DAG?
Câu trả lời
Relax each vertex's outgoing edges in topological order. Every predecessor is processed first, so negative weights are allowed and total time is O(V + E).
Thẻ 162
Câu hỏi
When should you use BFS or DFS instead of union-find for connectivity?
Câu trả lời
When the graph is static and you need traversal details such as paths or component members. Union-find is especially useful for repeated incremental edge additions and connectivity queries.
Thẻ 163
Câu hỏi
What is the difference between a minimum spanning tree and a shortest-path tree?
Câu trả lời
A minimum spanning tree minimizes total connecting edge weight. A shortest-path tree preserves shortest routes from a chosen source; neither objective implies the other.
Thẻ 164
Câu hỏi
Why can stopping at the first meeting be unsafe in bidirectional BFS with arbitrary node-by-node expansion?
Câu trả lời
A first meeting under an arbitrary expansion order may not minimize the combined distances. Use a layer-based stopping rule that accounts for both search depths.
Thẻ 165
Câu hỏi
Which signal suggests backtracking rather than a single greedy choice?
Câu trả lời
The task asks for all valid arrangements, or choices must be tried and undone because no safe local choice is known. Build a partial candidate and explore legal extensions.
Thẻ 166
Câu hỏi
What belongs in a backtracking state?
Câu trả lời
Enough information to determine legal next choices and recognize completion, such as the current position, chosen items, and remaining constraints.
Thẻ 167
Câu hỏi
What makes a pruning condition safe?
Câu trả lời
It proves that no completion of the current partial state can satisfy the goal or improve the required objective. A guess about likely failure is insufficient.
Thẻ 168
Câu hỏi
How do combinations differ from permutations during generation?
Câu trả lời
Combinations ignore order, so restrict future choices to later positions. Permutations care about order, so track which positions are already used.
Thẻ 169
Câu hỏi
What should be true after a backtracking recursive call returns?
Câu trả lời
The caller's mutable search state is restored exactly to its pre-choice state. Undo additions and constraint updates before trying a sibling choice.
Thẻ 170
Câu hỏi
When generating unique subsets from sorted values, how do you skip duplicates safely?
Câu trả lời
At one recursion depth, skip a value equal to the previous sibling candidate. Still allow equal values at deeper levels when the input provides multiple copies.
Thẻ 171
Câu hỏi
Why can backtracking output alone require exponential time?
Câu trả lời
A set with n distinct elements has 2^n subsets. Explicitly listing all subsets cannot be polynomial in n; copying their contents adds further cost.
Thẻ 172
Câu hỏi
Why should a completed mutable candidate usually be copied before saving it?
Câu trả lời
Later backtracking steps will modify the working candidate. Saving only a reference can make all recorded answers reflect subsequent changes.
Thẻ 173
Câu hỏi
What is the main risk of memoizing backtracking solely by the current index?
Câu trả lời
Different histories can leave different remaining choices or constraints. The memo key must include every part of the state that affects future results.
Thẻ 174
Câu hỏi
For selecting the most nonoverlapping intervals, which greedy choice is justified?
Câu trả lời
Choose the available interval with the earliest finishing time, then continue with compatible intervals. This leaves at least as much room for the remaining selections.
Thẻ 175
Câu hỏi
What is the difference between greedy choice and dynamic programming?
Câu trả lời
Greedy commits to a choice proven safe without exploring all alternatives. DP evaluates and combines subproblem alternatives when that local commitment is not justified.
Thẻ 176
Câu hỏi
Why does choosing the largest coin repeatedly fail for some coin systems?
Câu trả lời
The locally largest coin can leave an expensive remainder. With denominations 1, 3, 4 and amount 6, greedy uses 4 + 1 + 1, while 3 + 3 uses fewer coins.
Thẻ 177
Câu hỏi
How does a farthest-reachable frontier solve reachability in a nonnegative jump-length array?
Câu trả lời
Scan positions no farther than the current frontier and extend it with each reachable index plus its jump length. If the next position lies beyond the frontier, progress is impossible.
Thẻ 178
Câu hỏi
Why does choosing the shortest interval not always maximize the number of nonoverlapping intervals?
Câu trả lời
A short interval can cross the boundary between two compatible intervals and block both. Duration alone does not measure the future scheduling space it consumes.
Thẻ 179
Câu hỏi
What must be proved before pruning a combination-sum branch because its sum exceeds the target?
Câu trả lời
Remaining choices cannot reduce the sum. The pruning is safe for nonnegative additions under the stated goal, but negative numbers can make it invalid.
Thẻ 180
Câu hỏi
How does branch and bound differ from ordinary feasibility pruning?
Câu trả lời
It uses a bound on the best objective reachable from a partial state. Prune only when that bound cannot beat the best complete answer already found.
Thẻ 181
Câu hỏi
What question distinguishes a greedy proof from evidence that a heuristic often works?
Câu trả lời
Can every discarded alternative be ruled out for all valid inputs? Examples and benchmarks support a heuristic, but do not establish the safe-choice property.
Thẻ 182
Câu hỏi
Why is earliest-finish interval scheduling insufficient when intervals have different rewards?
Câu trả lời
Maximizing count and maximizing reward are different objectives. A single high-reward interval can beat several low-reward intervals, so weighted scheduling needs more information.
Thẻ 183
Câu hỏi
Which combination of properties makes dynamic programming promising?
Câu trả lời
Repeated subproblems and a recurrence that combines their results. Define a state whose answer is independent of the path used to reach it.
Thẻ 184
Câu hỏi
What should a DP state definition say before you write a recurrence?
Câu trả lời
Exactly what one table entry means, including its input boundary and any remaining resource or constraint. Ambiguous states lead to mismatched transitions.
Thẻ 185
Câu hỏi
How do top-down memoization and bottom-up tabulation differ?
Câu trả lời
Memoization computes states on demand through calls and caches them. Tabulation processes states in an explicit dependency order, often avoiding recursion overhead.
Thẻ 186
Câu hỏi
What determines the runtime of a DP with a finite state table?
Câu trả lời
The number of states actually evaluated times the work per state, plus preprocessing and output reconstruction. Count transitions rather than just table dimensions.
Thẻ 187
Câu hỏi
Why are base cases part of a DP's meaning rather than convenient initial values?
Câu trả lời
They encode valid empty or smallest subproblems. A wrong base value can invent impossible solutions or remove legitimate ones from every later transition.
Thẻ 188
Câu hỏi
For 0/1 knapsack compressed to one capacity array, why iterate capacities downward?
Câu trả lời
Each item must be used at most once. Descending order reads the previous item's state instead of reusing an update made for the current item.
Thẻ 189
Câu hỏi
When can a DP table be compressed to a few rows or variables?
Câu trả lời
When future states depend only on a bounded slice of earlier states. Keep those dependencies until their last use; reconstruction may need additional storage.
Thẻ 190
Câu hỏi
What recurrence models choosing nonadjacent values for maximum sum?
Câu trả lời
At each position, compare skipping it with taking it plus the best result before its neighbor. The base cases must specify whether choosing nothing is allowed.
Thẻ 191
Câu hỏi
What DP state counts paths through a blocked grid when moves are only right or down?
Câu trả lời
The number of ways to reach each cell from above or from the left. Blocked cells contribute zero; initialize an unblocked starting cell to one.
Thẻ 192
Câu hỏi
For unbounded knapsack, why can capacities run upward within an item's pass?
Câu trả lời
Reusing the current item's updated smaller-capacity result is allowed. Ascending order lets that item contribute more than once.
Thẻ 193
Câu hỏi
How can loop order change coin-change counting from combinations to ordered sequences?
Câu trả lời
Processing coin types outside amounts builds combinations without ordering them. Processing amounts outside all coin choices counts different last-coin sequences separately.
Thẻ 194
Câu hỏi
What is the key distinction between longest common subsequence and longest common substring?
Câu trả lời
A subsequence may skip characters; a substring must stay contiguous. Their DP transitions differ because a substring match cannot carry through a mismatch.
Thẻ 195
Câu hỏi
Why is O(nW) knapsack called pseudopolynomial?
Câu trả lời
It is polynomial in the numeric capacity W, but W can be exponential in the number of bits used to encode it. It is not polynomial in input bit length.
Thẻ 196
Câu hỏi
For longest increasing subsequence, what does tails[length − 1] represent in the O(n log n) method?
Câu trả lời
The smallest possible final value of an increasing subsequence of that length among processed values. The tails array itself need not be one actual subsequence.
Thẻ 197
Câu hỏi
Why do counting and minimization DPs use different unreachable-state values?
Câu trả lời
A count uses zero ways. A minimization state needs an explicit unreachable marker or infinity so an impossible predecessor cannot look like a cheap solution.
Thẻ 198
Câu hỏi
What state supports edit distance between two strings?
Câu trả lời
The minimum edits needed to transform one prefix into the other. Transitions account for insertion, deletion, and replacement or a matching final character.
Thẻ 199
Câu hỏi
How can a DP recover one chosen solution instead of only its score?
Câu trả lời
Store predecessor or choice information, or recompute choices from the full table. Walk backward from the final state to reconstruct the selected decisions.
Thẻ 200
Câu hỏi
Why must an LIS implementation choose its binary-search boundary according to strictness?
Câu trả lời
For a strictly increasing subsequence, replace the first tail at least equal to the value. A nondecreasing subsequence instead uses the first strictly greater tail.
Thẻ 201
Câu hỏi
What operation tests whether bit i of a nonnegative integer mask is set?
Câu trả lời
Check whether mask AND (1 shifted left by i) is nonzero. Ensure i is inside the integer representation's supported bit range.
Thẻ 202
Câu hỏi
Why does XOR recover a unique value when every other value occurs exactly twice?
Câu trả lời
Equal values cancel because x XOR x = 0, and XOR is associative and commutative. XORing all values leaves the single unpaired value.
Thẻ 203
Câu hỏi
What does x AND (x − 1) do for a positive integer x?
Câu trả lời
It clears x's lowest set bit. Repeating it counts set bits in time proportional to the number of set bits.
Thẻ 204
Câu hỏi
When does a bitmask make a useful DP state?
Câu trả lời
When a small set of items is either included or excluded and future choices depend on that subset. n items give 2^n possible masks, so n must be small.
Thẻ 205
Câu hỏi
How do you set a bit and clear a bit without changing the others?
Câu trả lời
Set bit i with mask OR (1 shifted left by i). Clear it with mask AND the bitwise complement of that single-bit mask, respecting the chosen word width.
Thẻ 206
Câu hỏi
What makes a memoized recurrence invalid when it depends on mutable global state omitted from the key?
Câu trả lời
The same key can have different answers under different global conditions. Include the relevant state in the key or remove that dependency.
Thẻ 207
Câu hỏi
What condition recognizes a power of two among integers?
Câu trả lời
x > 0 and x AND (x − 1) = 0. The positivity check excludes zero, which also makes the bitwise expression zero.
Thẻ 208
Câu hỏi
Why does bitwise complement need a width convention in language-agnostic reasoning?
Câu trả lời
Complement flips all bits in the representation. Fixed-width and arbitrary-precision signed integers can produce different-looking values; mask to the intended width when necessary.
Thẻ 209
Câu hỏi
How can two unique values be recovered when every other value occurs twice?
Câu trả lời
XOR all values, choose a set bit in that nonzero result, and partition by that bit. XOR within each group; the two unique values fall into different groups.
Thẻ 210
Câu hỏi
Why is memoization alone insufficient to handle cyclic state dependencies?
Câu trả lời
A call may revisit an unfinished state before any value is cached. Use cycle handling or a problem-specific iterative method; ordinary DAG-style DP assumes an acyclic dependency order.

An abstract row of teal and amber tiles connects to a branching tree and a small network of nodes on a dark blue background.

210 thẻ