Scheda di riferimento per il riconoscimento dei pattern
Colleghi 15 segnali comuni dei problemi (array ordinato, necessità di tutte le combinazioni, massimizzazione del valore con un vincolo e così via) ai pattern algoritmici che li risolvono più rapidamente.
Scheda di riferimento per il riconoscimento dei pattern è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
La sfida di riconoscimento dei pattern in 60 secondi
In un colloquio reale, dopo aver letto un problema, dispone di circa 60 secondi per identificare il pattern algoritmico applicabile, prima che l'intervistatore si aspetti che inizi a scrivere codice. Questa è la competenza più importante da sviluppare: non memorizzare le implementazioni, ma riconoscere quale strumento utilizzare.
Il riconoscimento dei pattern nasce dal collegamento tra i segnali del problema (le parole e i vincoli presenti nella descrizione) e le famiglie di algoritmi note. Una volta identificato il pattern, l'implementazione diventa un esercizio di compilazione di un template. Questa lezione è un cheat sheet sistematico dei 15 segnali più comuni e dei relativi pattern.
# 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)Segnali 1-3: pattern per array e stringhe
I segnali più frequenti nei problemi su array e stringhe:
- Array ordinato + trovare un target → Binary search O(log n)
- Trovare una coppia o tripletta la cui somma è un target → Two pointers O(n) se l'array è ordinato, hash map O(n) se non è ordinato
- Subarray o substring più lungo/più corto che soddisfa una condizione → Sliding window O(n)
- Somma massima/minima di un subarray contiguo → Algoritmo di Kadane O(n)
- Rilevamento dei duplicati → Hash set O(n) oppure ordinamento O(n log n)
Se l'array è ordinato, consideri sempre innanzitutto la binary search. Array non ordinato + somma target + O(n) = quasi sempre una hash map per cercare il complemento.
# 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}')Segnali 4-6: pattern per alberi e grafi
Segnali dei problemi su alberi e grafi e relativi pattern:
- Attraversamento livello per livello / shortest path in un grafo non pesato → BFS con deque O(V+E)
- Esplorare tutti i percorsi / rilevare cicli / ordine DFS → DFS ricorsiva o iterativa O(V+E)
- BST + proprietà dell'ordine in-order (k-esimo elemento, ordine ordinato) → DFS in-order O(n)
- Lowest common ancestor → Discesa ricorsiva con tracciamento del percorso O(n)
- Componenti connesse / unire due gruppi → DSU O(n × alpha(n))
# 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}')Segnali 7-9: segnali della programmazione dinamica
I segnali della DP sono i più difficili da riconoscere. Cerchi queste parole chiave:
- 'Numero di modi per...' → DP di conteggio (somma dei conteggi dei sottoproblemi)
- 'Costo minimo/massimo per ottenere...' → DP di ottimizzazione (si prende il minimo/massimo dei sottoproblemi)
- 'Possiamo ottenere...' (fattibilità) → DP booleana (OR dei sottoproblemi)
- Sottoproblema definito da due indici di stringa → DP 2D (LCS, distanza di edit)
- Scegliere o saltare elementi con un vincolo di capacità → DP knapsack
- Struttura ottimale dei sottoproblemi + sottoproblemi sovrapposti → Verifichi nell'albero della ricorsione la presenza di chiamate ripetute → DP
# 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}')Segnali 10-12: segnali per heap, stack e greedy
Segnali dei problemi che richiedono heap, monotonic stack e greedy:
- Elementi Top-K / k-esimo maggiore o minore → Heap (min-heap per i K elementi maggiori, max-heap per il k-esimo elemento minore) O(n log k)
- Mediana in streaming → Due heap (max-heap della metà inferiore + min-heap della metà superiore)
- Elemento successivo maggiore/minore → Monotonic stack O(n)
- Rettangolo di area massima / trapping water → Monotonic stack O(n)
- Interval scheduling / massimizzare gli intervalli non sovrapposti → Greedy (ordinare per orario di fine)
# 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}')Segnali 13-15: backtracking e manipolazione dei bit
Segnali dei problemi che richiedono backtracking e manipolazione dei bit:
- Generare tutti i sottoinsiemi / le permutazioni / le combinazioni → Backtracking O(2^n o n!)
- Soddisfare vincoli (N-queens, Sudoku) → Backtracking con pruning
- Trovare un elemento mancante / unico → XOR O(n), spazio O(1)
- Enumerare tutti i sottoinsiemi di un insieme piccolo (n ≤ 20) → Enumerazione con bitmask 2^n
- Contare i bit impostati / verificare se una potenza di due → Bit tricks (n & (n-1))
- DP con compressione dello stato su un insieme piccolo → Bitmask DP O(2^n × n)
# 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}')Analisi dei vincoli: cosa indica N
Il vincolo sulla dimensione dell'input n indica direttamente la complessità temporale accettabile e, di conseguenza, la famiglia di algoritmi:
- n ≤ 20: O(2^n) o O(n!) sono accettabili — bitmask DP, backtracking
- n ≤ 500: O(n³) è accettabile — Floyd-Warshall, DP brute-force
- n ≤ 5000: O(n²) è accettabile — DP ingenua, ordinamento quadratico
- n ≤ 10^6: è necessaria O(n log n) — merge sort, heap, binary search
- n ≤ 10^8: è necessaria O(n) — two pointers, sliding window, DP lineare
Questa analisi dei vincoli dovrebbe essere il primo passo dopo aver letto il problema, prima di scegliere un algoritmo.
# 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}')Problema → pattern: esercitazione rapida
Si eserciti su questo collegamento finché non diventerà automatico. Legga ogni descrizione del problema e identifichi il pattern prima di guardare la soluzione. La velocità è importante: durante un colloquio dovrebbe identificare il pattern in meno di 60 secondi:
- 'Dato un array ordinato, determinare se esistono due elementi la cui somma è K'
- 'Dato un albero, trovare il diametro (il percorso più lungo tra due nodi qualsiasi)'
- 'Dati n task con cooldown k, trovare il numero minimo di intervalli della CPU'
- 'Data una stringa, trovare la substring palindromica più lunga'
- 'Dato 1..n con un elemento mancante, trovare il numero mancante'
# 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')Segnali d'allarme: quando il pattern non funziona
Anche gli ingegneri esperti possono scegliere inizialmente il pattern sbagliato. Riconosca questi segnali che indicano che l'approccio attuale non è corretto e cambi strategia:
- Il Suo O(n²) supera i test piccoli, ma va in TLE con input grandi → serve una hash map, una binary search o una struttura monotonic
- Il Suo approccio greedy fallisce davanti a un controesempio → provi la DP
- Lo spazio degli stati della Sua DP è troppo grande → cerchi una dimostrazione greedy o una definizione dello stato più efficace
- La Sua BFS restituisce una risposta errata → verifichi se serve Dijkstra (pesato) invece di BFS (non pesato)
- Il codice genera eccezioni di puntatore nullo → aggiunga i casi base e i controlli per i casi limite prima di implementare
# 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}')Comunicare il riconoscimento dei pattern nei colloqui
Durante i colloqui, esplicitare il proprio riconoscimento del pattern dimostra competenza e offre all'intervistatore la possibilità di guidarLa se si sta muovendo nella direzione sbagliata. Utilizzi questa struttura:
- 'Noto che l'array è ordinato, quindi sto pensando alla binary search...'
- 'Il problema chiede il subarray massimo, quindi è un problema classico dell'algoritmo di Kadane...'
- 'Ci servono tutti i sottoinsiemi possibili, il che suggerisce il backtracking con un albero della ricorsione...'
- 'Il vincolo n ≤ 20 mi dice che 2^n = 1M è accettabile, quindi potrebbe funzionare la bitmask DP...'
Dopo aver dichiarato il pattern, indichi la complessità temporale e spaziale prima di scrivere una sola riga di codice. In questo modo dimostra di considerare l'efficienza prima dell'implementazione.
# 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']
)Costruire il proprio vocabolario dei pattern
Il modo più rapido per sviluppare il riconoscimento dei pattern consiste nel risolvere i problemi in serie tematiche, non in modo casuale. Dedichi una settimana esclusivamente ai problemi di sliding window. Poi passi ai problemi con two pointers. Quindi affronti i problemi di DP. Risolvere rapidamente 20 problemi dello stesso tipo sviluppa l'intuizione necessaria per riconoscere quel pattern a colpo d'occhio.
Dopo ogni problema, scriva una 'pattern note' di una riga: il segnale del problema e il pattern che ha attivato. Costruisca il Suo cheat sheet personale. Dopo aver risolto 200 problemi in serie tematiche, riconoscerà circa il 90% dei problemi da colloquio in meno di 30 secondi; il restante 10% richiede un'analisi attenta anche agli ingegneri esperti.
# 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"]}')Verifica rapida
Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: il riconoscimento dei pattern collega i segnali dei problemi alle famiglie di algoritmi: un array ordinato suggerisce la binary search, 'tutti i sottoinsiemi' suggerisce il backtracking e 'costo minimo' suggerisce la DP; inoltre, il vincolo n indica la complessità accettabile: n ≤ 20 consente O(2^n), mentre n ≤ 10^6 richiede O(n log n) o una complessità migliore e verbalizzare il pattern e la complessità prima di scrivere codice dimostra competenza e consente all'intervistatore di fornire un feedback. Ora metterà in pratica il riconoscimento dei pattern con problemi di simulazione di colloquio a tempo, di difficoltà facile e media.
Domande Frequenti
La lezione «Scheda di riferimento per il riconoscimento dei pattern» è gratuita?
Sì — il testo completo di «Scheda di riferimento per il riconoscimento dei pattern» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Scheda di riferimento per il riconoscimento dei pattern»?
Colleghi 15 segnali comuni dei problemi (array ordinato, necessità di tutte le combinazioni, massimizzazione del valore con un vincolo e così via) ai pattern algoritmici che li risolvono più rapidame… Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.
Quanto tempo richiede la lezione «Scheda di riferimento per il riconoscimento dei pattern»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Scheda di riferimento per il riconoscimento dei pattern
- Colloquio simulato a tempo: problemi facili e medi
- Gestione dei casi limite e comunicazione durante il colloquio
- Analisi guidata di problemi difficili: Word Ladder II e Alien Dictionary