Coding Interview Patterns Flashcards: Signals, Invariants & Complexity

Cartes de ce paquet

1. Carte 1

   Question

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

   Réponse

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

2. Carte 2

   Question

   What does a loop invariant describe?

   Réponse

   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.

3. Carte 3

   Question

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

   Réponse

   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.

4. Carte 4

   Question

   What is the difference between auxiliary space and total space?

   Réponse

   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.

5. Carte 5

   Question

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

   Réponse

   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.

6. Carte 6

   Question

   How does a counterexample help evaluate a proposed greedy rule?

   Réponse

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

7. Carte 7

   Question

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

   Réponse

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

8. Carte 8

   Question

   What runtime lower bound follows from returning k separate results?

   Réponse

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

9. Carte 9

   Question

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

   Réponse

   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.

10. Carte 10

    Question

    Which edge cases best expose index and boundary errors?

    Réponse

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

11. Carte 11

    Question

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

    Réponse

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

12. Carte 12

    Question

    What does an exchange argument establish in a greedy proof?

    Réponse

    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.

13. Carte 13

    Question

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

    Réponse

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

14. Carte 14

    Question

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

    Réponse

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

15. Carte 15

    Question

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

    Réponse

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

16. Carte 16

    Question

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

    Réponse

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

17. Carte 17

    Question

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

    Réponse

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

18. Carte 18

    Question

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

    Réponse

    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.

19. Carte 19

    Question

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

    Réponse

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

20. Carte 20

    Question

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

    Réponse

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

21. Carte 21

    Question

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

    Réponse

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

22. Carte 22

    Question

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

    Réponse

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

23. Carte 23

    Question

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

    Réponse

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

24. Carte 24

    Question

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

    Réponse

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

25. Carte 25

    Question

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

    Réponse

    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.

26. Carte 26

    Question

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

    Réponse

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

27. Carte 27

    Question

    How do you compare two strings as multisets of characters?

    Réponse

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

28. Carte 28

    Question

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

    Réponse

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

29. Carte 29

    Question

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

    Réponse

    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.

30. Carte 30

    Question

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

    Réponse

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

31. Carte 31

    Question

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

    Réponse

    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.

32. Carte 32

    Question

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

    Réponse

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

33. Carte 33

    Question

    Why must compound hash keys encode boundaries unambiguously?

    Réponse

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

34. Carte 34

    Question

    What does coordinate compression preserve about numeric values?

    Réponse

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

35. Carte 35

    Question

    How can you compute products except self without division?

    Réponse

    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.

36. Carte 36

    Question

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

    Réponse

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

37. Carte 37

    Question

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

    Réponse

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

38. Carte 38

    Question

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

    Réponse

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

39. Carte 39

    Question

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

    Réponse

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

40. Carte 40

    Question

    When does a fixed-size sliding window apply?

    Réponse

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

41. Carte 41

    Question

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

    Réponse

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

42. Carte 42

    Question

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

    Réponse

    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.

43. Carte 43

    Question

    How does a three-way partition maintain separate regions?

    Réponse

    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.

44. Carte 44

    Question

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

    Réponse

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

45. Carte 45

    Question

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

    Réponse

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

46. Carte 46

    Question

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

    Réponse

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

47. Carte 47

    Question

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

    Réponse

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

48. Carte 48

    Question

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

    Réponse

    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.

49. Carte 49

    Question

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

    Réponse

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

50. Carte 50

    Question

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

    Réponse

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

51. Carte 51

    Question

    How do you merge two sorted arrays with forward pointers?

    Réponse

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

52. Carte 52

    Question

    Why must a minimum-cover substring track multiplicities of required characters?

    Réponse

    A target can require the same character more than once. A set of required characters would mark an undersupplied window as complete.

53. Carte 53

    Question

    How can counting subarrays with exactly k distinct values, for k ≥ 1, use an at-most helper?

    Réponse

    Compute atMost(k) − atMost(k − 1). The helper counts all valid subarrays ending at each right boundary after restoring the distinct-value limit.

54. Carte 54

    Question

    Why can a negative value break the usual shortest-sum sliding-window argument?

    Réponse

    Removing it increases the sum, and adding one can decrease the sum. The monotonic relation between window size and sum no longer holds.

55. Carte 55

    Question

    What does 'fast and slow pointers' mean when removing duplicates from a sorted array?

    Réponse

    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.

56. Carte 56

    Question

    What invariant prevents overwriting unread data during a backward merge into spare array capacity?

    Réponse

    The suffix after the write pointer already contains the largest merged elements. Filling from the end leaves the remaining source elements unread and intact.

57. Carte 57

    Question

    Why is 'find a contiguous range' alone insufficient to justify a variable sliding window?

    Réponse

    You also need a safe boundary-movement rule. Check how adding and removing elements affect the condition; contiguity by itself gives no such guarantee.

58. Carte 58

    Question

    After restoring an at-most window's validity, why are there right − left + 1 valid subarrays ending at right?

    Réponse

    Every suffix starting between left and right is valid when removing elements cannot violate the constraint. Count those starts, including the one-element suffix.

59. Carte 59

    Question

    How can you avoid duplicate value pairs in a sorted two-pointer enumeration?

    Réponse

    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.

60. Carte 60

    Question

    When does a character-frequency sliding window detect an anagram of a pattern?

    Réponse

    When the window has the pattern's length and identical character counts. Maintain count differences or a mismatch counter as the window moves.

61. Carte 61

    Question

    What does a prefix-sum array P mean when P[0] = 0?

    Réponse

    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.

62. Carte 62

    Question

    When is binary search valid on a Boolean predicate over ordered candidates?

    Réponse

    When the predicate changes at most once, such as false then true. The search uses that monotonic boundary to discard a whole interval.

63. Carte 63

    Question

    Which workload favors a difference array?

    Réponse

    Many range additions followed by final value reconstruction. Mark each range's start and end changes, then take one prefix sum.

64. Carte 64

    Question

    In a lower-bound search over [lo, hi), what does hi initially equal for an n-element array?

    Réponse

    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.

65. Carte 65

    Question

    For a static array, how do prefix sums answer the half-open range [l, r)?

    Réponse

    Return P[r] − P[l]. Building P takes O(n) time and space; each range-sum query then takes O(1).

66. Carte 66

    Question

    How can prefix sums count subarrays whose sum equals k when negative values are allowed?

    Réponse

    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.

67. Carte 67

    Question

    Why is binary-searching an answer different from binary-searching an input array?

    Réponse

    The candidates are possible result values. A feasibility check tells which side contains the boundary, even if the original input is unsorted.

68. Carte 68

    Question

    How does a difference array encode an addition of v to [l, r)?

    Réponse

    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.

69. Carte 69

    Question

    For lower bound, how should equality with the target move the search boundary?

    Réponse

    Move hi to mid. An equal element is a candidate, but an earlier equal or qualifying element may still exist.

70. Carte 70

    Question

    Why initialize the prefix-frequency map with zero appearing once?

    Réponse

    It represents the empty prefix before the array. This lets a subarray starting at index 0 contribute to the count.

71. Carte 71

    Question

    Why are plain prefix sums inconvenient for many interleaved point updates and range-sum queries?

    Réponse

    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).

72. Carte 72

    Question

    How can you binary-search the minimum capacity needed to finish ordered work within a deadline?

    Réponse

    Define whether a capacity suffices, prove larger capacities remain feasible, bracket a feasible answer, and search for the first feasible capacity.

73. Carte 73

    Question

    What must every binary-search iteration do to guarantee termination?

    Réponse

    Strictly shrink the candidate interval while preserving the boundary invariant. Mixing inclusive and exclusive update rules can leave the same interval unchanged.

74. Carte 74

    Question

    For the longest subarray with a specified sum, which occurrence of each prefix sum should you retain?

    Réponse

    The earliest index. For a later endpoint, it gives the longest matching span; overwriting it with a later occurrence can shorten the answer.

75. Carte 75

    Question

    What runtime should you report for binary search with a nonconstant feasibility check?

    Réponse

    O(C log R), where C is one check's cost and R is the number of discrete candidates. Include any preprocessing separately.

76. Carte 76

    Question

    How can prefix sums turn a longest balanced binary subarray into an equal-prefix problem?

    Réponse

    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.

77. Carte 77

    Question

    What is upper bound in a sorted array?

    Réponse

    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.

78. Carte 78

    Question

    Why must a prefix-sum counting algorithm query before recording the current prefix?

    Réponse

    Recording first can count the empty subarray ending at the current boundary, especially for target zero. Query only earlier prefixes for nonempty ranges.

79. Carte 79

    Question

    How do you safely compute a midpoint in a fixed-width integer search?

    Réponse

    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.

80. Carte 80

    Question

    Why can duplicate values degrade searching a rotated sorted array to O(n)?

    Réponse

    Equal endpoints and midpoint can hide which side is sorted. Some cases permit discarding only one boundary element at a time.

81. Carte 81

    Question

    What preprocessing usually simplifies merging overlapping intervals?

    Réponse

    Sort by start coordinate. Keep the current merged interval and either extend its end or emit it when the next interval starts beyond it.

82. Carte 82

    Question

    Which data structure matches nested bracket validation?

    Réponse

    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.

83. Carte 83

    Question

    A problem asks for each element's next greater element. Which pattern is promising?

    Réponse

    A monotonic stack of unresolved positions. A new larger value resolves the smaller pending values it overtakes.

84. Carte 84

    Question

    Why must interval endpoint conventions be explicit?

    Réponse

    Touching endpoints overlap for closed intervals, but adjacent half-open intervals do not. The convention changes merge tests and event ordering.

85. Carte 85

    Question

    How can a sweep line find the maximum number of simultaneous intervals?

    Réponse

    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.

86. Carte 86

    Question

    Why is one pass after sorting enough to merge intervals?

    Réponse

    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.

87. Carte 87

    Question

    What information should a stack store for next-greater distances?

    Réponse

    Indices, so the distance is currentIndex − previousIndex. Values alone do not identify positions or distinguish repeated occurrences.

88. Carte 88

    Question

    Why is counting opening and closing brackets insufficient to validate their sequence?

    Réponse

    Counts ignore order and nesting. A closing bracket may appear before its opener, or bracket types may cross despite balanced totals.

89. Carte 89

    Question

    For half-open intervals [start, end), how should equal-time starts and ends affect room counts?

    Réponse

    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.

90. Carte 90

    Question

    Why is a monotonic-stack algorithm often O(n) even though one step can pop many items?

    Réponse

    Each item is pushed once and popped at most once. Summed across the scan, stack operations are linear.

91. Carte 91

    Question

    How can a stack help simplify an absolute filesystem path lexically?

    Réponse

    Process components: ignore empty components and '.', pop for '..' when possible, and push ordinary names. This lexical result does not resolve symbolic links.

92. Carte 92

    Question

    How can a monotonic deque find each sliding-window maximum?

    Réponse

    Keep candidate indices in decreasing value order. Remove expired indices from the front and dominated values from the back; the front gives the maximum.

93. Carte 93

    Question

    What mistake can lose coverage when merging an interval contained inside the current one?

    Réponse

    Replacing the current end with the new end. Use the larger end so a nested interval cannot shrink the merged coverage.

94. Carte 94

    Question

    For a strictly next-greater query, what should happen to an equal-valued stack entry?

    Réponse

    Do not resolve it with the equal value. With a decreasing stack of unresolved indices, pop only when the new value is strictly greater.

95. Carte 95

    Question

    What event allows a monotonic stack to finalize a rectangle in a histogram?

    Réponse

    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.

96. Carte 96

    Question

    What comparison detects overlap between two nonempty half-open intervals?

    Réponse

    max(start1, start2) < min(end1, end2). A strict comparison excludes intervals that only touch.

97. Carte 97

    Question

    How does a stack support evaluating a postfix arithmetic expression?

    Réponse

    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.

98. Carte 98

    Question

    Why can a newer value dominate an older value in a sliding-window maximum deque?

    Réponse

    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.

99. Carte 99

    Question

    How can you merge two already sorted lists of disjoint intervals to find their intersections?

    Réponse

    Compare one interval from each list, emit any overlap, then advance the one with the earlier end. Total time is O(m + n).

100. Carte 100

     Question

     Why must a histogram stack algorithm handle bars still pending after the scan?

     Réponse

     Those bars may extend to the array's end and contain the largest rectangle. Flush them using the end boundary or a suitable sentinel.

101. Carte 101

     Question

     What must you save before reversing a singly linked list node's next pointer?

     Réponse

     Its original next node. Otherwise rewiring can lose access to the remaining list.

102. Carte 102

     Question

     Why does a dummy head simplify linked-list insertion and deletion?

     Réponse

     It supplies a predecessor even when the real head changes. The same pointer update can handle both the first node and interior nodes.

103. Carte 103

     Question

     How do fast and slow pointers detect a cycle in a singly linked list?

     Réponse

     Advance one pointer one step and the other two. A meeting implies a cycle; reaching null with the fast pointer means the list terminates.

104. Carte 104

     Question

     What does a recursive binary-tree traversal use for auxiliary space?

     Réponse

     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.

105. Carte 105

     Question

     During iterative list reversal, what do prev and current represent?

     Réponse

     prev heads the reversed processed prefix; current heads the unprocessed suffix. Rewire one node while preserving access to the suffix.

     

     210 cartes

     Coding Interview Patterns Flashcards: Signals, Invariants & Complexity

     Réviser ce paquet gratuitement

     Nibomo s'ouvre pour que vous puissiez commencer à réviser.

106. Carte 106

     Question

     How can you remove the nth node from the end of a list in one pass?

     Réponse

     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.

107. Carte 107

     Question

     Which tree traversal naturally computes a value that depends on both children's results?

     Réponse

     Postorder. Process left and right subtrees before combining their results at the parent.

108. Carte 108

     Question

     How can you locate a cycle's entry after Floyd's two-speed pointers meet?

     Réponse

     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.

109. Carte 109

     Question

     What is the difference between tree depth and tree height?

     Réponse

     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.

110. Carte 110

     Question

     How can you merge two sorted linked lists using O(1) auxiliary node storage?

     Réponse

     Relink the smaller current node onto the result tail, advancing that list. Attach the remaining suffix when one list ends; existing nodes are reused.

111. Carte 111

     Question

     When is breadth-first traversal more natural than depth-first traversal on a tree?

     Réponse

     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.

112. Carte 112

     Question

     Why must linked-list intersection compare node identity rather than node value?

     Réponse

     Intersection means sharing the same node object and suffix. Separate nodes can hold equal values without the lists intersecting.

113. Carte 113

     Question

     Why is checking only immediate children insufficient to validate a binary search tree?

     Réponse

     A descendant can satisfy its parent yet violate an ancestor's constraint. Carry inherited lower and upper bounds, with an explicit duplicate policy.

114. Carte 114

     Question

     What is the lowest common ancestor of two nodes in a rooted tree?

     Réponse

     The deepest node that is an ancestor of both, allowing a node to be its own ancestor.

115. Carte 115

     Question

     What property makes inorder traversal useful in a binary search tree?

     Réponse

     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.

116. Carte 116

     Question

     Why must maximum tree-path sum separate its returned value from its global candidate?

     Réponse

     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.

117. Carte 117

     Question

     How can two pointers find the intersection of two acyclic singly linked lists without measuring lengths?

     Réponse

     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.

118. Carte 118

     Question

     What extra information makes preorder serialization unambiguous for an arbitrary binary tree?

     Réponse

     Explicit null-child markers or another equivalent shape encoding. Values in preorder alone do not determine the structure.

119. Carte 119

     Question

     Why can repeated subtree-height calculations make a tree-balance check O(n²)?

     Réponse

     The same descendants may be scanned from many ancestors. Return height and balance together in one postorder traversal to visit each node once.

120. Carte 120

     Question

     How does BST ordering guide a lowest-common-ancestor search for two existing distinct keys?

     Réponse

     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.

121. Carte 121

     Question

     What runtime does a search in an ordinary unbalanced BST guarantee?

     Réponse

     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.

122. Carte 122

     Question

     When computing a root-to-leaf path sum, why is reaching a null child insufficient for success?

     Réponse

     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.

123. Carte 123

     Question

     What does a min-heap guarantee about its root and children?

     Réponse

     The root is a minimum element, and each parent is no larger than its children. The whole array representation is not sorted.

124. Carte 124

     Question

     A stream needs the k largest values seen so far. Which heap should you maintain?

     Réponse

     A min-heap of at most k values. Its root is the smallest retained value, so a larger arrival can replace it.

125. Carte 125

     Question

     What shared structure does a trie store?

     Réponse

     Prefixes of keys. Following one edge per symbol reaches a key's prefix node, while a terminal marker distinguishes a complete stored key.

126. Carte 126

     Question

     What are the usual binary-heap costs for peek, insertion, and root removal?

     Réponse

     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.

127. Carte 127

     Question

     How can a heap merge k sorted input streams?

     Réponse

     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.

128. Carte 128

     Question

     Why is bottom-up heap construction O(n), not O(n log n)?

     Réponse

     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.

129. Carte 129

     Question

     How do two heaps support a running median?

     Réponse

     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.

130. Carte 130

     Question

     What is a trie's lookup cost for a key of length L?

     Réponse

     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.

131. Carte 131

     Question

     Why does a trie node need a terminal marker even if it has children?

     Réponse

     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.

132. Carte 132

     Question

     When does sorting make more sense than a top-k heap?

     Réponse

     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.

133. Carte 133

     Question

     Why does a priority queue not by itself support efficient arbitrary deletion?

     Réponse

     The heap efficiently exposes only its root. Removing another item needs its position, an indexed-heap design, or a lazy-deletion scheme with cleanup.

134. Carte 134

     Question

     What output cost remains after a trie reaches a requested prefix?

     Réponse

     Enumerating matching completions still costs time proportional to the visited subtree and emitted text. Prefix lookup does not make all autocomplete results free.

135. Carte 135

     Question

     How can a priority queue break tied priorities without comparing the payloads?

     Réponse

     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.

136. Carte 136

     Question

     Why can a trie use more memory than a hash set of complete strings?

     Réponse

     Nodes and child containers have overhead, especially for sparse branches. Shared prefixes save repeated symbols but do not guarantee a smaller representation.

137. Carte 137

     Question

     What should graph modeling identify before choosing a traversal?

     Réponse

     The states as vertices and legal transitions as edges, including direction and cost. A grid cell, word, or puzzle configuration can be a vertex.

138. Carte 138

     Question

     When does ordinary BFS find a shortest path?

     Réponse

     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.

139. Carte 139

     Question

     What is the space cost of an adjacency list compared with an adjacency matrix?

     Réponse

     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.

140. Carte 140

     Question

     Which pattern finds all vertices reachable from a start vertex?

     Réponse

     DFS or BFS with a visited set. Each reachable vertex and edge is processed a bounded number of times with adjacency lists.

141. Carte 141

     Question

     What role does a parent map play in shortest-path traversal?

     Réponse

     It records the predecessor used to reach each state. After reaching the target, follow parents backward and reverse the sequence to recover a path.

142. Carte 142

     Question

     Why should BFS mark a vertex visited when enqueuing it?

     Réponse

     To prevent several parents from adding it before its first removal. First enqueue already fixes its distance in an unweighted graph.

143. Carte 143

     Question

     When is Dijkstra's algorithm appropriate?

     Réponse

     For shortest paths with nonnegative edge weights. Its greedy finalization relies on no later path reducing a settled distance through a negative edge.

144. Carte 144

     Question

     How can a grid traversal avoid confusing physical cells with full search states?

     Réponse

     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.

145. Carte 145

     Question

     How do you detect a directed cycle with DFS?

     Réponse

     Track unvisited, active, and finished vertices. An edge to an active vertex closes a cycle on the current recursion path.

146. Carte 146

     Question

     Why can DFS with a visited set fail to find a shortest unweighted path?

     Réponse

     Its first discovered route may follow a deep detour. DFS reachability order is not distance order; BFS provides that guarantee.

147. Carte 147

     Question

     What does a topological ordering guarantee?

     Réponse

     For every directed edge u → v, u appears before v. Such an ordering exists exactly when the directed graph is acyclic.

148. Carte 148

     Question

     Why should stale priority-queue entries be skipped in a common Dijkstra implementation?

     Réponse

     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.

149. Carte 149

     Question

     For an undirected simple graph, why does DFS ignore the edge back to its parent when detecting cycles?

     Réponse

     That edge is the same tree edge traversed in reverse, not a new cycle. A different already-visited neighbor indicates a cycle.

150. Carte 150

     Question

     What does union-find answer efficiently?

     Réponse

     Whether elements belong to the same connected component while components are merged. It does not store the actual connecting paths.

151. Carte 151

     Question

     How does Kahn's algorithm build a topological ordering?

     Réponse

     Enqueue all zero-indegree vertices, repeatedly remove one, and decrement its outgoing neighbors' indegrees. Enqueue each neighbor when its indegree becomes zero.

152. Carte 152

     Question

     Which shortest-path algorithm handles edges weighted only 0 or 1 without a heap?

     Réponse

     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.

153. Carte 153

     Question

     Why is a boolean visited flag usually wrong for Dijkstra at first enqueue?

     Réponse

     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.

154. Carte 154

     Question

     How do path compression and union by size or rank affect union-find complexity?

     Réponse

     Together they give O(α(n)) amortized time per operation, where α is the inverse Ackermann function. The bound is effectively tiny for practical input sizes.

155. Carte 155

     Question

     What does processing fewer than V vertices in Kahn's algorithm reveal?

     Réponse

     A directed cycle remains. No vertex in the cyclic remainder can reach indegree zero after all removable dependencies are processed.

156. Carte 156

     Question

     How can BFS compute distance from every grid cell to the nearest source?

     Réponse

     Initialize the queue with all sources at distance zero. This multi-source BFS expands the nearest-source distance layers together.

157. Carte 157

     Question

     Why can a topological ordering be nonunique?

     Réponse

     Several vertices may currently have no remaining prerequisites. Choosing them in different orders can produce different valid orderings.

158. Carte 158

     Question

     What happens when union-find receives an edge whose endpoints already share a representative?

     Réponse

     The edge connects vertices already in one component. In incremental construction of an undirected forest, adding it creates a cycle.

159. Carte 159

     Question

     Which algorithm can handle negative edge weights and detect a reachable negative cycle?

     Réponse

     Bellman–Ford. Repeatedly relax all edges; an improvement after V − 1 full rounds indicates a negative cycle reachable from the source.

160. Carte 160

     Question

     Why does traversal need an outer loop to count every connected component of an undirected graph?

     Réponse

     One traversal reaches only one component. Start another traversal from each still-unvisited vertex and increment the component count.

161. Carte 161

     Question

     How can topological order simplify shortest paths in a weighted DAG?

     Réponse

     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).

162. Carte 162

     Question

     When should you use BFS or DFS instead of union-find for connectivity?

     Réponse

     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.

163. Carte 163

     Question

     What is the difference between a minimum spanning tree and a shortest-path tree?

     Réponse

     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.

164. Carte 164

     Question

     Why can stopping at the first meeting be unsafe in bidirectional BFS with arbitrary node-by-node expansion?

     Réponse

     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.

165. Carte 165

     Question

     Which signal suggests backtracking rather than a single greedy choice?

     Réponse

     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.

166. Carte 166

     Question

     What belongs in a backtracking state?

     Réponse

     Enough information to determine legal next choices and recognize completion, such as the current position, chosen items, and remaining constraints.

167. Carte 167

     Question

     What makes a pruning condition safe?

     Réponse

     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.

168. Carte 168

     Question

     How do combinations differ from permutations during generation?

     Réponse

     Combinations ignore order, so restrict future choices to later positions. Permutations care about order, so track which positions are already used.

169. Carte 169

     Question

     What should be true after a backtracking recursive call returns?

     Réponse

     The caller's mutable search state is restored exactly to its pre-choice state. Undo additions and constraint updates before trying a sibling choice.

170. Carte 170

     Question

     When generating unique subsets from sorted values, how do you skip duplicates safely?

     Réponse

     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.

171. Carte 171

     Question

     Why can backtracking output alone require exponential time?

     Réponse

     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.

172. Carte 172

     Question

     Why should a completed mutable candidate usually be copied before saving it?

     Réponse

     Later backtracking steps will modify the working candidate. Saving only a reference can make all recorded answers reflect subsequent changes.

173. Carte 173

     Question

     What is the main risk of memoizing backtracking solely by the current index?

     Réponse

     Different histories can leave different remaining choices or constraints. The memo key must include every part of the state that affects future results.

174. Carte 174

     Question

     For selecting the most nonoverlapping intervals, which greedy choice is justified?

     Réponse

     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.

175. Carte 175

     Question

     What is the difference between greedy choice and dynamic programming?

     Réponse

     Greedy commits to a choice proven safe without exploring all alternatives. DP evaluates and combines subproblem alternatives when that local commitment is not justified.

176. Carte 176

     Question

     Why does choosing the largest coin repeatedly fail for some coin systems?

     Réponse

     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.

177. Carte 177

     Question

     How does a farthest-reachable frontier solve reachability in a nonnegative jump-length array?

     Réponse

     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.

178. Carte 178

     Question

     Why does choosing the shortest interval not always maximize the number of nonoverlapping intervals?

     Réponse

     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.

179. Carte 179

     Question

     What must be proved before pruning a combination-sum branch because its sum exceeds the target?

     Réponse

     Remaining choices cannot reduce the sum. The pruning is safe for nonnegative additions under the stated goal, but negative numbers can make it invalid.

180. Carte 180

     Question

     How does branch and bound differ from ordinary feasibility pruning?

     Réponse

     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.

181. Carte 181

     Question

     What question distinguishes a greedy proof from evidence that a heuristic often works?

     Réponse

     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.

182. Carte 182

     Question

     Why is earliest-finish interval scheduling insufficient when intervals have different rewards?

     Réponse

     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.

183. Carte 183

     Question

     Which combination of properties makes dynamic programming promising?

     Réponse

     Repeated subproblems and a recurrence that combines their results. Define a state whose answer is independent of the path used to reach it.

184. Carte 184

     Question

     What should a DP state definition say before you write a recurrence?

     Réponse

     Exactly what one table entry means, including its input boundary and any remaining resource or constraint. Ambiguous states lead to mismatched transitions.

185. Carte 185

     Question

     How do top-down memoization and bottom-up tabulation differ?

     Réponse

     Memoization computes states on demand through calls and caches them. Tabulation processes states in an explicit dependency order, often avoiding recursion overhead.

186. Carte 186

     Question

     What determines the runtime of a DP with a finite state table?

     Réponse

     The number of states actually evaluated times the work per state, plus preprocessing and output reconstruction. Count transitions rather than just table dimensions.

187. Carte 187

     Question

     Why are base cases part of a DP's meaning rather than convenient initial values?

     Réponse

     They encode valid empty or smallest subproblems. A wrong base value can invent impossible solutions or remove legitimate ones from every later transition.

188. Carte 188

     Question

     For 0/1 knapsack compressed to one capacity array, why iterate capacities downward?

     Réponse

     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.

189. Carte 189

     Question

     When can a DP table be compressed to a few rows or variables?

     Réponse

     When future states depend only on a bounded slice of earlier states. Keep those dependencies until their last use; reconstruction may need additional storage.

190. Carte 190

     Question

     What recurrence models choosing nonadjacent values for maximum sum?

     Réponse

     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.

191. Carte 191

     Question

     What DP state counts paths through a blocked grid when moves are only right or down?

     Réponse

     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.

192. Carte 192

     Question

     For unbounded knapsack, why can capacities run upward within an item's pass?

     Réponse

     Reusing the current item's updated smaller-capacity result is allowed. Ascending order lets that item contribute more than once.

193. Carte 193

     Question

     How can loop order change coin-change counting from combinations to ordered sequences?

     Réponse

     Processing coin types outside amounts builds combinations without ordering them. Processing amounts outside all coin choices counts different last-coin sequences separately.

194. Carte 194

     Question

     What is the key distinction between longest common subsequence and longest common substring?

     Réponse

     A subsequence may skip characters; a substring must stay contiguous. Their DP transitions differ because a substring match cannot carry through a mismatch.

195. Carte 195

     Question

     Why is O(nW) knapsack called pseudopolynomial?

     Réponse

     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.

196. Carte 196

     Question

     For longest increasing subsequence, what does tails[length − 1] represent in the O(n log n) method?

     Réponse

     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.

197. Carte 197

     Question

     Why do counting and minimization DPs use different unreachable-state values?

     Réponse

     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.

198. Carte 198

     Question

     What state supports edit distance between two strings?

     Réponse

     The minimum edits needed to transform one prefix into the other. Transitions account for insertion, deletion, and replacement or a matching final character.

199. Carte 199

     Question

     How can a DP recover one chosen solution instead of only its score?

     Réponse

     Store predecessor or choice information, or recompute choices from the full table. Walk backward from the final state to reconstruct the selected decisions.

200. Carte 200

     Question

     Why must an LIS implementation choose its binary-search boundary according to strictness?

     Réponse

     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.

201. Carte 201

     Question

     What operation tests whether bit i of a nonnegative integer mask is set?

     Réponse

     Check whether mask AND (1 shifted left by i) is nonzero. Ensure i is inside the integer representation's supported bit range.

202. Carte 202

     Question

     Why does XOR recover a unique value when every other value occurs exactly twice?

     Réponse

     Equal values cancel because x XOR x = 0, and XOR is associative and commutative. XORing all values leaves the single unpaired value.

203. Carte 203

     Question

     What does x AND (x − 1) do for a positive integer x?

     Réponse

     It clears x's lowest set bit. Repeating it counts set bits in time proportional to the number of set bits.

204. Carte 204

     Question

     When does a bitmask make a useful DP state?

     Réponse

     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.

205. Carte 205

     Question

     How do you set a bit and clear a bit without changing the others?

     Réponse

     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.

206. Carte 206

     Question

     What makes a memoized recurrence invalid when it depends on mutable global state omitted from the key?

     Réponse

     The same key can have different answers under different global conditions. Include the relevant state in the key or remove that dependency.

207. Carte 207

     Question

     What condition recognizes a power of two among integers?

     Réponse

     x > 0 and x AND (x − 1) = 0. The positivity check excludes zero, which also makes the bitwise expression zero.

208. Carte 208

     Question

     Why does bitwise complement need a width convention in language-agnostic reasoning?

     Réponse

     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.

209. Carte 209

     Question

     How can two unique values be recovered when every other value occurs twice?

     Réponse

     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.

210. Carte 210

     Question

     Why is memoization alone insufficient to handle cyclic state dependencies?

     Réponse

     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.

210 cartes

Coding Interview Patterns Flashcards: Signals, Invariants & Complexity

Réviser ce paquet gratuitement

Nibomo s'ouvre pour que vous puissiez commencer à réviser.