İçeriğe geç
Tüm dersler

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
  • 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
  • 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
  • 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ı

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
  • 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

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
  • İ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
  • 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

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
  • 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

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

  • 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

  • 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
  • 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
  • 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
  • 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

Ö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
  • 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
  • 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

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

bytepatterns.com/cheatsheets/patterns — oradaki her satır animasyonlu bir derse bağlı.