Шпаргалка по распознаванию шаблонов

Игра на распознавание паттернов за 60 секунд

# The recognition process
recognition_steps = [
    '1. Read the problem once fully (do not start coding)',
    '2. Identify the data structure: array, string, tree, graph, matrix?',
    '3. Identify the ask: find min/max, count ways, enumerate, detect cycle...?',
    '4. Note the constraint: n<=20 (bitmask), sorted (binary search), DAG (topo sort)?',
    '5. Map signal -> pattern',
    '6. State the pattern and complexity to the interviewer before coding',
    '7. Handle edge cases mentally before writing',
]
for step in recognition_steps:
    print(step)

Признаки 1–3: паттерны для массивов и строк

# Quick recognition: array/string signals
signals = [
    ('Sorted array, find element',           'Binary search O(log n)'),
    ('Find two elements summing to K',        'Sort+two-ptr O(n log n) or hash O(n)'),
    ('Longest subarray with property P',      'Sliding window (variable size) O(n)'),
    ('Max sum contiguous subarray',           'Kadane algorithm O(n)'),
    ('Anagram/permutation check',             'Frequency map (Counter) O(n)'),
    ('Contains duplicate',                    'Hash set O(n)'),
    ('Merge two sorted arrays/lists',         'Two pointers O(n+m)'),
    ('Rotate / shift array',                  'Reverse trick O(n) in-place'),
    ('Next permutation',                      'Find rightmost ascent + swap + reverse'),
    ('Maximum product subarray',              'Track max and min (handles negatives)'),
]
for signal, pattern in signals:
    print(f'{signal:45s} => {pattern}')

Признаки 4–6: паттерны для деревьев и графов

# Tree/graph signal recognition
tree_graph_signals = [
    ('Level-order / minimum depth / word ladder',    'BFS with deque'),
    ('All paths / path sum / all permutations tree',  'DFS recursive'),
    ('Cycle detection (undirected)',                  'DFS with parent / DSU'),
    ('Cycle detection (directed) / course schedule', 'DFS three-color / Kahn topo sort'),
    ('Shortest path weighted graph',                  'Dijkstra (non-neg) / Bellman-Ford (neg)'),
    ('All-pairs shortest path',                       'Floyd-Warshall O(V^3)'),
    ('Topological order',                             'Kahn BFS topo sort'),
    ('Min spanning tree',                             'Kruskal (DSU) / Prim (heap)'),
    ('Dynamic connectivity / union-find',             'DSU path compression + union by rank'),
    ('Autocomplete / prefix search',                  'Trie'),
    ('BST kth smallest / range sum',                  'In-order DFS'),
]
for signal, pattern in tree_graph_signals:
    print(f'{signal:50s} => {pattern}')

Признаки 7–9: признаки динамического программирования

# DP signal recognition
dp_signals = [
    ('Number of ways to climb stairs / decode string',  '1D DP (Fibonacci-like)'),
    ('Minimum cost to reach end / coin change',          '1D DP (greedy fails)'),
    ('Longest increasing subsequence',                   '1D DP O(n^2) or patience sort O(n log n)'),
    ('Longest common subsequence of two strings',        '2D DP O(mn)'),
    ('Edit distance between two strings',                '2D DP O(mn) (LCS variant)'),
    ('Partition array into two equal subsets',           '0/1 knapsack boolean DP'),
    ('Fill knapsack with max value under weight limit',  '0/1 knapsack optimisation DP'),
    ('Burst balloons / matrix chain multiplication',     'Interval DP'),
    ('Palindrome partitioning minimum cuts',             'Interval DP + prefix palindrome'),
    ('Rob houses in circle',                             '1D DP × 2 (linear sub-problems)'),
]
for signal, pattern in dp_signals:
    print(f'{signal:55s} => {pattern}')

Признаки 10–12: признаки задач с кучами, стеками и жадными алгоритмами

# Heap / stack / greedy signals
heap_stack_greedy = [
    ('Top-K frequent elements',               'Min-heap size K: O(n log k)'),
    ('Kth largest in array',                   'Max-heap pop K times: O(n + k log n)'),
    ('Streaming median',                       'Two heaps (max + min): O(log n) per insert'),
    ('Merge K sorted lists',                   'Min-heap of (val, list_idx): O(n log k)'),
    ('Next greater element',                   'Monotonic decreasing stack: O(n)'),
    ('Largest rectangle in histogram',         'Monotonic increasing stack: O(n)'),
    ('Sliding window maximum',                 'Monotonic decreasing deque: O(n)'),
    ('Trapping rain water',                    'Two pointers OR monotonic stack: O(n)'),
    ('Jump game reachability / minimum jumps', 'Greedy range expansion: O(n)'),
    ('Merge overlapping intervals',            'Sort by start, linear scan: O(n log n)'),
    ('Gas station circular',                   'Greedy: start from reset point: O(n)'),
    ('Task scheduler with cooldown',           'Greedy: sort by frequency: O(n log n)'),
]
for signal, pattern in heap_stack_greedy:
    print(f'{signal:45s} => {pattern}')

Признаки 13–15: поиск с возвратом и побитовые операции

# Backtracking and bit signals
bt_bit_signals = [
    ('Generate all subsets of array',              'Backtracking O(n * 2^n) / bitmask'),
    ('Generate all permutations',                  'Backtracking O(n * n!)'),
    ('Combination sum with target',                'Backtracking with pruning'),
    ('Word search in grid',                        'Backtracking DFS on grid O(m*n*4^L)'),
    ('N-queens placement',                         'Backtracking with column/diag sets'),
    ('Find single unique element (all others x2)', 'XOR all: O(n) O(1)'),
    ('Missing number in 0..n',                     'XOR or sum formula: O(n) O(1)'),
    ('Count set bits in n',                        'n &= n-1 loop or DP O(n)'),
    ('Check power of two',                         'n > 0 and n & (n-1) == 0'),
    ('Travelling salesman (n<=20)',                'Bitmask DP O(2^n * n^2)'),
    ('Number with max XOR in array',               'Trie on binary representation'),
]
for signal, pattern in bt_bit_signals:
    print(f'{signal:50s} => {pattern}')

Анализ ограничений: о чём говорит N

# Constraint -> acceptable complexity -> algorithm family
complexity_map = [
    ('n <= 20',      'O(2^n) or O(n!)',  'Bitmask DP, backtracking/permutations'),
    ('n <= 500',     'O(n^3)',            'Floyd-Warshall, cubic DP, brute force'),
    ('n <= 5000',    'O(n^2)',            'Quadratic DP, bubble/insertion sort'),
    ('n <= 100000',  'O(n log n)',         'Merge sort, heap, binary search, topo sort'),
    ('n <= 1000000', 'O(n)',              'Linear DP, two pointers, sliding window, hash'),
    ('n <= 10^8',    'O(n) tight',        'Only simplest O(n) — no large constants'),
    ('n <= 10^18',   'O(log n) or O(1)', 'Math / number theory, binary search on answer'),
]
print(f'{'Constraint':15s} {'Complexity':15s} {'Algorithm Family'}')
print('-'*70)
for constraint, complexity, algorithms in complexity_map:
    print(f'{constraint:15s} {complexity:15s} {algorithms}')

Задача → паттерн: блиц-практика

# Quick-fire pattern recognition answers
problems = [
    ('Sorted array: two elements sum to K',
     'Two pointers (left from start, right from end): O(n)'),
    ('Tree diameter (longest path)',
     'DFS returning (height, max_diameter) pair: O(n)'),
    ('Task scheduler with cooldown k',
     'Greedy: (max_freq - 1)*(k+1) + count_of_max_freq: O(n log n)'),
    ('Longest palindromic substring',
     'Expand around centre OR Manacher: O(n^2) or O(n)'),
    ('Missing number in 1..n',
     'XOR all indices and values: O(n) O(1)'),
    ('Number of islands in binary grid',
     'BFS/DFS flood fill counting connected components: O(m*n)'),
    ('Decode string like 3[a2[bc]] -> aaabcbcaabcbc',
     'Stack to handle nested brackets: O(n)'),
    ('Valid parentheses [(){[]}]',
     'Stack push open, pop+match on close: O(n)'),
]
for problem, solution in problems:
    print(f'Q: {problem}\nA: {solution}\n')

Тревожные признаки: когда паттерн не срабатывает

# Red flags and recovery strategies
red_flags = [
    ('TLE on large n',               'Check complexity; switch from O(n^2) to O(n log n) or O(n)'),
    ('WA with greedy',               'Find a counter-example; switch to DP or prove exchange arg'),
    ('DP table huge',                'State compression (bitmask/rolling array) or different state'),
    ('BFS gives wrong shortest path', 'Check if edges have weights; use Dijkstra instead'),
    ('Stack overflow in recursion',  'Add memoisation or convert to iterative with explicit stack'),
    ('Off-by-one in binary search',  'Use half-open intervals [lo, hi); verify with 2-element test'),
    ('DSU wrong answer',             'Check 0-indexed vs 1-indexed; check union direction'),
    ('Backtracking TLE',             'Add pruning conditions; ensure undo step is correct'),
]
print('Pattern | Recovery')
print('-'*70)
for flag, recovery in red_flags:
    print(f'{flag:40s} => {recovery}')

Как объяснять распознавание паттернов на собеседованиях

# Interview communication template
def communicate_approach(problem, pattern, time_complexity, space_complexity, edge_cases):
    print(f'Problem: {problem}')
    print(f'Pattern: {pattern}')
    print(f'Time: {time_complexity}, Space: {space_complexity}')
    print(f'Edge cases to handle: {", ".join(edge_cases)}')
    print()

# Example communications
communicate_approach(
    problem='Find longest substring without repeating characters',
    pattern='Sliding window with a set tracking current window characters',
    time_complexity='O(n)',
    space_complexity='O(min(n, alphabet_size))',
    edge_cases=['empty string', 'all same characters', 'all unique characters']
)

communicate_approach(
    problem='Given sorted matrix, find if target exists',
    pattern='Binary search or staircase search (top-right corner): eliminate row or column each step',
    time_complexity='O(m + n)',
    space_complexity='O(1)',
    edge_cases=['empty matrix', 'single element', 'target at corners']
)

Формирование словаря распознавания паттернов

# Personal pattern note template
pattern_notes = [
    {'signal': 'sorted array + two sum',     'pattern': 'two pointers',          'example': 'LC 167 Two Sum II'},
    {'signal': 'longest X without repeating', 'pattern': 'sliding window + set',  'example': 'LC 3 Longest Substring'},
    {'signal': 'max sum subarray',            'pattern': 'Kadane',                'example': 'LC 53 Max Subarray'},
    {'signal': 'permutations/subsets',        'pattern': 'backtracking',          'example': 'LC 46 Permutations'},
    {'signal': 'tree path sum',               'pattern': 'DFS with accumulator', 'example': 'LC 112 Path Sum'},
    {'signal': 'course schedule',             'pattern': 'Kahn topo sort',        'example': 'LC 207 Course Schedule'},
    {'signal': 'top-K elements',              'pattern': 'min-heap size K',       'example': 'LC 215 Kth Largest'},
]
print(f'{'Signal':40s} {'Pattern':30s} {'Example'}')
print('-'*90)
for note in pattern_notes:
    print(f'{note["signal"]:40s} {note["pattern"]:30s} {note["example"]}')

Быстрая проверка

Итоги урока