Mülakat pattern'leri cheat sheet
Bilmeye değer kodlama mülakatı pattern'leri: her birine ne zaman başvurulur, problem metnindeki ele veren sinyaller ve her biri için bir ders ve pratik.
Güncellendi: 23 patternher biri için bir ders ve pratikTemiz yazdırılır; tarayıcının yazdırma özelliğini kullan
Önce problem metnini oku, sonra sinyalleri tara: aşağıdaki ifadeler bir pattern'i ele veren ifadeler. Maliyet satırı, pattern'in genelde ulaştığı değer; kod yazmaya başlamadan önce yüksek sesle söylenecek sayı.
Diziler ve string'ler
İki pointer
Bir çiftin, bir bölümlemenin ya da palindromun iki uçtan karar verildiği sıralı bir dizi ya da string.
Sinyaller
- sıralı dizi + toplamı hedefe eşit çift / üçlü bul
- tekrar edenleri sil ya da elemanları in-place taşı
- palindrom, ters çevir ya da iki uçtan karşılaştır
Tipik maliyet: O(n) zaman, O(1) alan
- Ders
- İki pointer · Diziler
- Pratik
Kayan pencere
Cevap ardışık bir parça ve onu bir eleman büyütmek ya da küçültmek durumu ucuza günceller.
Sinyaller
- … koşulunu sağlayan en uzun / en kısa substring ya da subarray
- en fazla k farklı, tekrarsız, toplam ≥ hedef
- k boyutundaki her pencere
Tipik maliyet: O(n) zaman, O(k) alan
- Ders
- Kayan pencere · Diziler
- Pratik
Prefix sum
Aynı dizi üzerinde çok sayıda aralık toplamı sorusu ya da toplamı k olması gereken bir subarray (ardışık alt dizi).
Sinyaller
- i ile j arasındaki elemanların toplamı, tekrar tekrar soruluyor
- toplamı k olan subarray'leri say (negatifler olabilir)
- kendisi hariç her şeyin çarpımı
Tipik maliyet: O(n) kurulum, sorgu başına O(1)
- Ders
- Prefix sum · Diziler
- Pratik
Hash map ile arama
Bir döngünün içinde sürekli "bunu daha önce gördüm mü?" ya da "bundan kaç tane var?" diye soruyorsun.
Sinyaller
- toplamı tutan / eşleşen iki öğe (sırasız girdi)
- anagramlar, frekanslar, ilk tekil, tekrar edenler
- öğeleri kanonik bir anahtara göre grupla
Tipik maliyet: O(n) zaman, O(n) alan
- Ders
- Two Sum · Hash tabloları
- Pratik
İkili arama
Girdi sıralı ya da cevapla ilgili evet/hayır sorusu, cevap büyüdükçe tam bir kez değişiyor.
Sinyaller
- sıralı (ya da döndürülmüş sıralı) dizi, O(log n) bekleniyor
- ilk / son konum, ekleme konumu
- … olacak şekilde minimum kapasite / hız / gün
Tipik maliyet: Arama başına O(log n); cevap üzerinde O(Clog R)
- Ders
- İkili arama · Arama
- Pratik
- Tam sayı karekökKolay
- İlk ve son konumOrta
Bağlı listeler ve stack'ler
Hızlı ve yavaş pointer
Döngü, orta nokta ya da sondan k'ıncı eleman gereken bir bağlı liste (linked list) ya da bir değeri sonrakine eşleyen bir fonksiyon.
Sinyaller
- döngüyü tespit et / döngünün başladığı yeri bul
- tek geçişte listenin ortası
- sondan n'inci düğümü sil
Tipik maliyet: O(n) zaman, O(1) alan
- Ders
- Hızlı ve yavaş pointer · Bağlı listeler
- Pratik
- Zincirde döngüKolay
- Sondan n. düğümü silOrta
Monoton stack
Her eleman için ondan büyük ya da küçük olan sonraki (ya da önceki) eleman gerekiyor.
Sinyaller
- sonraki büyük / sonraki daha sıcak / sonraki küçük
- span, görünen binalar, … kadar geçen gün
- histogramdaki en büyük dikdörtgen
Tipik maliyet: O(n) zaman, O(n) alan
- Ders
- Monoton stack · Stack ve kuyruklar
- Pratik
Heap'ler
Top-k elemanlar
Tam bir sıralama değil, en büyük, en küçük, en yakın ya da en sık k tanesi gerekiyor.
Sinyaller
- en büyük k / en küçük k / k'ıncı en büyük
- en yakın k nokta, en sık k eleman
- k'nın küçük kaldığı bir akış
Tipik maliyet: O(n log k) zaman, O(k) alan
- Ders
- Top-k elemanlar · Heap'ler
- Pratik
- En zayıf k ekipKolay
- k. en büyük değerOrta
İki heap
Değişen bir koleksiyonun ortası gerekiyor: alt yarı için bir max-heap, üst yarı için bir min-heap.
Sinyaller
- bir akışın anlık medyanı
- her pencerenin medyanı
- bütçe büyüdükçe alınabilecek en iyi öğeyi seç
Tipik maliyet: Ekleme başına O(log n), medyan başına O(1)
- Ders
- İki heap: anlık medyan · İki heap ve k-way merge
- Pratik
K-way merge
Birkaç sıralı liste var ve onları tek bir sırada ya da hepsinin içindeki k'ıncı öğeyi istiyorsun.
Sinyaller
- k sıralı listeyi / diziyi birleştir
- sıralı bir matristeki k'ıncı en küçük
- her listeden bir öğe içeren en küçük aralık
Tipik maliyet: O(N log k) zaman, O(k) alan
- Ders
- K-way merge · İki heap ve k-way merge
- Pratik
Aralıklar ve greedy
Aralıkları birleştirme
Çakışabilen aralıklar: başlangıca göre sırala, sonra her aralığı en son tutulanla karşılaştırarak bir kez tara.
Sinyaller
- toplantılar, rezervasyonlar, zaman aralıkları, süreler
- çakışan aralıkları birleştir / ekle / say
- minimum oda, maksimum eşzamanlı
Tipik maliyet: O(n log n) zaman (sıralama), O(n) alan
- Ders
- Merge Intervals · Aralıklar
- Pratik
Greedy seçim
O an en iyi seçeneği almak hiçbir zaman geri alınmak zorunda kalmıyor ve nedenini savunabiliyorsun (exchange argument).
Sinyaller
- çakışmayan maksimum etkinlik sayısı
- sona ulaşabilir misin / en az sıçrama
- kümülatif toplamın ≥ 0 kalması gereken dairesel bir rota
Tipik maliyet: Genelde sıralama için O(n log n), sonra O(n)
- Ders
- Greedy ne zaman işe yarar · Greedy algoritmalar
- Pratik
Graflar, grid'ler ve ağaçlar
Genişlik öncelikli arama
Ağırlıksız bir graf ya da grid'de en az adım ya da seviye seviye işlenen her şey.
Sinyaller
- en kısa yol / minimum hamle, her adımın maliyeti aynı
- seviye sırası, en yakın, dakika dakika yayılma
- aynı anda birkaç başlangıç noktası (çok kaynaklı)
Tipik maliyet: O(V + E) zaman, O(V) alan
- Ders
- Genişlik öncelikli arama · Graflar
- Pratik
Derinlik öncelikli arama ve flood fill
Ulaşılabilen her şeyi keşfet: bölgeleri say, bir yapıyı kopyala ya da her yol boyunca bir özelliği kontrol et.
Sinyaller
- ada sayısı / bağlı bölge sayısı
- bağlı bir alanı doldur, boya ya da işaretle
- kökten yaprağa yol toplamları ve özellikleri
Tipik maliyet: O(V + E) zaman, O(V) alan
- Ders
- Derinlik öncelikli arama · Graflar
- Pratik
Topolojik sıralama
Ön koşullu görevler: her bağımlılığa uyan bir sıra ya da böyle bir sıranın olmadığının kanıtı.
Sinyaller
- ön koşullu dersler / build'ler / görevler
- hepsi bitirilebilir mi? (döngü kontrolü)
- ikili kurallardan çıkarılan bir sıra
Tipik maliyet: O(V + E) zaman, O(V) alan
- Ders
- Topolojik sıralama · Graflar
- Pratik
Union-find
Yalnız birleşen gruplar ve tekrar tekrar sorulan "bu ikisi bağlı mı?" soruları.
Sinyaller
- il / arkadaş çevresi / bileşen sayısı
- döngüyü kapatan kenar (gereksiz bağlantı)
- bir anahtarı paylaşan hesapları ya da öğeleri birleştir
Tipik maliyet: İşlem başına O(α(n)), amortize
- Ders
- Disjoint set temelleri · Union-find
- Pratik
Ağırlıklı en kısa yollar
Kenarların maliyetleri farklı: negatif olmayan ağırlıklar için Dijkstra, ağırlıklar negatif olabiliyorsa ya da adım sayısı sınırlıysa Bellman–Ford.
Sinyaller
- en ucuz / en hızlı rota, ağ gecikmesi
- en fazla k durak
- negatif ağırlıklar ya da negatif döngü tespiti
Tipik maliyet: Dijkstra O((V + E) log V), Bellman–Ford O(V·E)
- Ders
- Dijkstra algoritması · Graflar
- Pratik
Trie
Çok sayıda kelime ve çok sayıda prefix (önek) sorusu: otomatik tamamlama, starts-with, tahtada kelime arama.
Sinyaller
- … ile başlayan / prefix / otomatik tamamlama
- grid'deki tüm sözlük kelimelerini bul
- kelimeleri en kısa köklerleriyle değiştir
Tipik maliyet: Kelime başına O(L), O(toplam karakter) alan
- Ders
- Trie temelleri · Trie'lar
- Pratik
Özyineleme ve dinamik programlama
Backtracking
Her geçerli diziliş listelenmeli ya da kısıtlar altında biri aranmalı: seç, özyinele, seçimi geri al.
Sinyaller
- tüm alt kümeler / permütasyonlar / kombinasyonlar
- vezirleri yerleştir, sudoku doldur, kelime bul
- n küçük (≤ ~20)
Tipik maliyet: Üstel: alt kümeler O(2n), sıralamalar O(n!)
- Ders
- Karar ağacı · Backtracking
- Pratik
1D dinamik programlama
i konumundaki cevap önceki birkaç cevaba bağlı ve düz özyineleme aynı işi tekrarlıyor.
Sinyaller
- n'inci basamağa ulaşmanın yol sayısı
- iki komşuyu birden almadan maksimum toplam
- decode ways, tırmanmanın minimum maliyeti
Tipik maliyet: O(n) zaman, güncellenen değişkenlerle O(1)
- Ders
- Climbing Stairs · Dinamik programlama
- Pratik
Knapsack DP
Bir kapasite altında ya da bir hedefi tutturmak için öğe seç; her öğe bir kez (0/1) ya da istediğin kadar (unbounded).
Sinyaller
- en az bozuk para / bir tutarı oluşturmanın yol sayısı
- toplamları eşit iki yarıya böl
- hedefe ulaşmak için + / − ata
Tipik maliyet: O(n·W) zaman, O(W) alan
- Ders
- 0/1 knapsack · Dinamik programlama
String ve grid'lerde 2D DP
Prefix prefix karşılaştırılan iki dizi ya da her hücresi komşularından kurulan bir grid.
Sinyaller
- en uzun ortak alt dizi, edit distance
- grid'de tekil yollar / minimum yol toplamı
- palindromik alt dizi
Tipik maliyet: O(m·n) zaman, tek satırla O(n)
- Ders
- En uzun ortak alt dizi · Dinamik programlama
- Pratik
Bitler
Bit hileleri
Çiftler birbirini götürüyor, bir küme bir tam sayıya sığıyor ya da soru ikinin kuvvetleriyle ilgili.
Sinyaller
- biri hariç her sayı iki kez geçiyor
- O(1) alanla 0…n içindeki eksik sayı
- ikinin kuvveti / 1 olan bitleri say / maske olarak tüm alt kümeler
Tipik maliyet: O(n) zaman, O(1) alan
- Ders
- XOR numaraları · Bit manipülasyonu
- Pratik
- Eksik değerKolay
- İki yalnız değerOrta
bytepatterns.com/cheatsheets/patterns — oradaki her satır animasyonlu bir derse bağlı.