İçeriğe geç

Python mülakat cheat sheet

Mülakatçının beklediği Python: veri yapısı maliyetleri, sıralama, string'ler, itertools, tuzaklar ve on şablon; her snippet yazdırdığı çıktıyla.

Güncellendi: 54 snippet, her biri çalıştırıldı10 şablonTemiz yazdırılır; tarayıcının yazdırma özelliğini kullan

Bu sayfadaki her snippet tam basıldığı gibi çalıştırıldı ve altındaki çıktı Python'ın yazdırdığı şey. Python 3.9 ve sonrası için yazıldı; daha yeni bir sürüm isteyen birkaç satır bunu belirtir. Maliyetler CPython'ındır: avg ya da amortized yazmıyorsa en kötü durum.

Veri yapıları ve maliyetleri

Bir cevabın kurulduğu yerleşik tipler ve collections tipleri. Her kart, altındaki yapı için Big-O cheat sheet'teki satıra bağlanır.

  • list

    Dinamik bir dizi: sonda hızlı, başta yavaş.

    list: işlem maliyetleri
    İşlemZaman
    a[i], a[i] = x, len(a)O(1)
    append(x), pop()O(1) amortized
    insert(0, x), pop(0)O(n)
    x in a, a.index(x)O(n)
    a[i:j] (kopyalar)O(k)
    sort(), sorted(a)O(n log n)
    a = [3, 1, 4]
    a.append(1)      # O(1) amortized
    a.insert(0, 9)   # O(n): shifts every item
    print(a)
    print(a.pop(), a.pop(0))  # O(1), O(n)
    print(4 in a)    # O(n) scan

    Çıktı

    [9, 3, 1, 4, 1]
    1 9
    True

    Döngüde baştan pop etmek toplamda O(n²) tutar; deque kullan.

    Ders
    Dizi temelleri · Diziler
  • dict

    Bir hash map. Anahtarlar hashable olmalı; dolaşma ekleme sırasını izler.

    dict: işlem maliyetleri
    İşlemZaman
    d[k], d[k] = v, del d[k]O(1) avgO(n) worst
    k in d, d.get(k, default)O(1) avg
    anahtarları / öğeleri dolaşO(n)
    d = {"b": 2}
    d["a"] = 1
    print(d.get("z", 0), "a" in d)
    d.setdefault("c", []).append(3)
    print(d)
    print(list(d))    # insertion order

    Çıktı

    0 True
    {'b': 2, 'a': 1, 'c': [3]}
    ['b', 'a', 'c']

    Olmayan bir anahtarda d[k] KeyError fırlatır; get ve setdefault fırlatmaz.

    Ders
    Hash tablosu temelleri · Hash tabloları
  • set

    O(1)'de “bunu gördüm mü?”. Sıra yok, tekrar yok.

    set: işlem maliyetleri
    İşlemZaman
    add, remove, x in sO(1) avg
    a | b, a & b, a - b (boyutlar m, n)O(m + n)
    seen = {3, 1}
    seen.add(2)
    print(2 in seen, len(seen))
    a, b = {1, 2, 3}, {2, 3, 4}
    print(sorted(a & b), sorted(a | b))
    print(sorted(a - b), sorted(a ^ b))

    Çıktı

    True 3
    [2, 3] [1, 2, 3, 4]
    [1] [1, 4]

    Bir set'i sorted üzerinden yazdır; sırası dilin parçası değil. {} boş bir dict'tir; boş set set().

    Ders
    Hash tablosu temelleri · Hash tabloları
  • deque

    from collections import deque

    Kuyruğun kendisi: iki uçta da O(1). BFS'nin yapısı.

    deque: işlem maliyetleri
    İşlemZaman
    append, appendleftO(1)
    pop, popleftO(1)
    ortadaki q[i]O(n)
    from collections import deque
    q = deque([1, 2])
    q.appendleft(0)
    q.append(3)
    print(q.popleft(), q.pop(), q)
    last3 = deque(maxlen=3)
    for x in range(5):
        last3.append(x)
    print(last3)

    Çıktı

    0 3 deque([1, 2])
    deque([2, 3, 4], maxlen=3)

    maxlen öbür uçtan atar: bedavaya sabit boyutlu bir pencere.

    Ders
    Kuyruk temelleri · Stack ve kuyruklar
  • heapq

    import heapq

    Düz bir liste üzerinde ikili MIN-heap. Max-heap için negatiflerini push et.

    heapq: işlem maliyetleri
    İşlemZaman
    heapify(a)O(n)
    heappush, heappopO(log n)
    a[0] (min'e bakma)O(1)
    nsmallest(k, a), nlargest(k, a)O(n log k)
    import heapq
    h = [5, 1, 8, 3]
    heapq.heapify(h)
    heapq.heappush(h, 0)
    print(heapq.heappop(h), h[0])
    print(heapq.nsmallest(2, [5, 1, 8, 3]))
    m = []                   # max-heap
    for x in [5, 1, 8]:
        heapq.heappush(m, -x)
    print(-m[0])

    Çıktı

    0 1
    [1, 3]
    8

    (priority, count, item) tuple'ları push et; böylece bir eşitlik asla iki öğeyi karşılaştırmaz.

    Ders
    Heap temelleri · Heap'ler
  • Counter

    from collections import Counter

    Sayılardan oluşan bir dict: frekanslar, anagramlar, “en sık k”.

    Counter: işlem maliyetleri
    İşlemZaman
    Counter(iterable)O(n)
    c[x] (yoksa 0)O(1) avg
    most_common(k)O(n log k)
    from collections import Counter
    c = Counter("banana")
    print(c)
    print(c["a"], c["z"])     # missing -> 0
    print(c.most_common(2))
    print(Counter("listen") == Counter("silent"))

    Çıktı

    Counter({'a': 3, 'n': 2, 'b': 1})
    3 0
    [('a', 3), ('n', 2)]
    True
    Ders
    Frekans sayma · Hash tabloları
  • defaultdict

    from collections import defaultdict

    Olmayan bir değeri ilk okumada kuran bir dict: tek satırda gruplama.

    defaultdict: işlem maliyetleri
    İşlemZaman
    d[k] (yoksa oluşturur)O(1) avg
    geri kalan her şeyas dict
    from collections import defaultdict
    groups = defaultdict(list)
    for w in ["eat", "tea", "tan"]:
        groups["".join(sorted(w))].append(w)
    print(dict(groups))
    print(groups["zzz"], len(groups))

    Çıktı

    {'aet': ['eat', 'tea'], 'ant': ['tan']}
    [] 3

    groups["zzz"]'yi yalnız okumak bile onu ekledi. Üyeliği in ile test et.

    Ders
    Anagramları gruplama · Hash tabloları
  • OrderedDict

    from collections import OrderedDict

    O(1)'de yeniden sıralanabilen bir dict: birkaç satırda LRU cache.

    OrderedDict: işlem maliyetleri
    İşlemZaman
    move_to_end(k)O(1)
    popitem(last=False)O(1)
    geri kalan her şeyas dict
    from collections import OrderedDict
    lru = OrderedDict()
    for k in "abc":
        lru[k] = k.upper()
    lru.move_to_end("a")      # a is now newest
    lru.popitem(last=False)   # evict the oldest
    print(list(lru.items()))

    Çıktı

    [('c', 'C'), ('a', 'A')]

    Düz bir dict de ekleme sırasını korur (3.7+), ama move_to_end'i yoktur.

    Ders
    LRU cache · Low-level design

Dilimleme ve comprehension'lar

a[start:stop:step] aralık dışı bir sınırda asla hata fırlatmaz ve her zaman yeni bir liste kurar: k öğe için O(k) zaman ve bellek. Comprehension, liste, dict ya da set kuran deyimsel döngüdür; generator ifadesi hiçbir şey kurmaz.

  • Dilimler

    a = [0, 1, 2, 3, 4, 5]
    print(a[1:4], a[-2:], a[:2])
    print(a[::2], a[::-1])
    print(a[10:], a[4:1])   # no IndexError

    Çıktı

    [1, 2, 3] [4, 5] [0, 1]
    [0, 2, 4] [5, 4, 3, 2, 1, 0]
    [] []
  • Dilim bir kopyadır

    a = [1, 2, 3]
    b = a[:]          # new list, O(n)
    b.append(4)
    print(a, b)
    s = "interview"
    print(s[::-1], s[2:5])
    a[1:3] = [7]      # slice assignment
    print(a)

    Çıktı

    [1, 2, 3] [1, 2, 3, 4]
    weivretni ter
    [1, 7]

    Kopya sığdır (shallow): iç içe listeler paylaşılır (bkz. Sık tuzaklar).

  • List, dict ve set comprehension'ları

    nums = [3, 8, 1, 6]
    print([x * x for x in nums if x % 2 == 0])
    print({x: x % 3 for x in nums})
    print(sorted({x % 3 for x in nums}))
    print([x if x > 2 else 0 for x in nums])
    print(sum(x for x in nums))  # generator

    Çıktı

    [64, 36]
    {3: 0, 8: 2, 1: 1, 6: 0}
    [0, 1, 2]
    [3, 8, 0, 6]
    18

    Filtre if'i döngüden sonra gelir; a if c else b seçimi döngüden önce.

  • Grid'ler: kur, düzleştir, transpoze et

    rows, cols = 2, 3
    grid = [[0] * cols for _ in range(rows)]
    grid[0][0] = 1
    print(grid)
    print([v for row in grid for v in row])
    print([list(c) for c in zip(*grid)])

    Çıktı

    [[1, 0, 0], [0, 0, 0]]
    [1, 0, 0, 0, 0, 0]
    [[1, 0], [0, 0], [0, 0]]

    İç içe döngüler soldan sağa, önce dıştaki okunur; yani onları yazacağın sırayla.

DerslerDizi temelleriIn-place ters çevirme

Sıralama

Timsort: en kötü durumda O(n log n), zaten sıralı veride O(n) ve KARARLI: eşit anahtarlar girdi sıralarını korur, çok geçişli sıralamaları çalıştıran da budur. sorted() herhangi bir iterable alır ve yeni bir liste döndürür; list.sort() in-place sıralar ve None döndürür.

  • sorted() vs .sort()

    a = [3, 1, 2]
    b = sorted(a)     # new list
    print(a, b)
    r = a.sort()      # in place
    print(a, r)
    print(sorted("cab"), sorted((3, 1)))

    Çıktı

    [3, 1, 2] [1, 2, 3]
    [1, 2, 3] None
    ['a', 'b', 'c'] [1, 3]

    a = a.sort() klasik bug'dır: a artık None.

  • key= and reverse=

    words = ["kiwi", "fig", "banana", "apple"]
    print(sorted(words, key=len))
    print(sorted(words, key=len, reverse=True))
    print(max(words, key=len))

    Çıktı

    ['fig', 'kiwi', 'apple', 'banana']
    ['banana', 'apple', 'kiwi', 'fig']
    banana

    Anahtar her karşılaştırmada değil, her öğe için bir kez hesaplanır.

  • Birkaç anahtar, karışık yönler

    people = [("ana", 31), ("ben", 25),
              ("cy", 31)]
    # age descending, then name ascending
    key = lambda p: (-p[1], p[0])
    print(sorted(people, key=key))
    from operator import itemgetter
    print(sorted(people, key=itemgetter(1)))

    Çıktı

    [('ana', 31), ('cy', 31), ('ben', 25)]
    [('ben', 25), ('ana', 31), ('cy', 31)]

    Tuple anahtarın içinde bir sayının yönünü çevirmek için negatifini al; string'lerin negatifi alınamaz, onun yerine iki kez sırala.

  • Kararlılık: iki kez sırala, önce ikincil anahtarla

    rows = [("b", 2), ("a", 1), ("c", 2),
            ("d", 1)]
    print(sorted(rows, key=lambda r: r[1]))
    rows.sort(key=lambda r: r[0], reverse=True)
    rows.sort(key=lambda r: r[1])
    print(rows)

    Çıktı

    [('a', 1), ('d', 1), ('b', 2), ('c', 2)]
    [('d', 1), ('a', 1), ('c', 2), ('b', 2)]

    Eşitler girdi sırasını korur, bu yüzden ikinci geçiş her sayının içinde ilk geçişin sırasını korur.

  • functools.cmp_to_key

    from functools import cmp_to_key
    def cmp(a, b):
        if a + b > b + a:
            return -1          # a goes first
        return 1 if a + b < b + a else 0
    nums = ["3", "30", "34", "5", "9"]
    nums.sort(key=cmp_to_key(cmp))
    print("".join(nums))

    Çıktı

    9534330

    Hiçbir anahtarın ifade edemediği bir sıra için (“largest number”). Negatifse önce a, pozitifse önce b, 0 eşit.

DerslerSıralama temelleriHangi sıralama ne zaman?

String'ler

String'ler immutable'dır: her “değişiklik” yenisini kurar. Çıktıyı parçalardan oluşan bir liste olarak kur ve bir kez join et; in-place düzenlemen gerekiyorsa string'i listeye çevir.

  • join vs +=

    parts = ["a", "b", "c"]
    s = ""
    for p in parts:
        s += p        # may copy s every time
    print(s, "-".join(parts))
    print(",".join(str(n) for n in [1, 2, 3]))

    Çıktı

    abc a-b-c
    1,2,3

    Döngüdeki += O(n²) olabilir: CPython bazen yerinde uzatır ama bunu hiçbir şey garanti etmez. join tek bir O(n) geçiştir.

  • f-string'lerPython 3.8+

    name, score = "ana", 7 / 3
    print(f"{name!r} scored {score:.2f}")
    print(f"[{name:>6}] [{name:<6}] [{42:05d}]")
    print(f"{255:b} {255:x} {1234567:,}")
    x = 5
    print(f"{x=}, {x * 2=}")

    Çıktı

    'ana' scored 2.33
    [   ana] [ana   ] [00042]
    11111111 ff 1,234,567
    x=5, x * 2=10

    {x=} ifadeyi ve değerini yazdırır; beyaz tahtada kodu adım adım yürütürken debug için kullanışlı.

  • Mülakatçıların beklediği metotlar

    s = "  Hello, World  "
    print(s.strip().lower())
    print("a,b,,c".split(","), "a b  c".split())
    print("abc123".isalnum(), "123".isdigit())
    print("level".startswith("le"))
    print("banana".count("an"))
    print("banana".find("x"), "banana".index("n"))
    print("a-b-c".replace("-", ""), "ab" * 3)

    Çıktı

    hello, world
    ['a', 'b', '', 'c'] ['a', 'b', 'c']
    True True
    True
    2
    -1 2
    abc ababab

    Argümansız split() art arda gelen boşluklarda böler ve boş parçaları atar. find -1 döndürür; index ValueError fırlatır.

  • Sayı olarak karakterler; bir string'i düzenlemek

    print(ord("a"), chr(ord("a") + 2))
    counts = [0] * 26
    for ch in "abca":
        counts[ord(ch) - ord("a")] += 1
    print(counts[:3])
    s = "cat"
    try:
        s[0] = "b"
    except TypeError:
        print("immutable")
    chars = list(s)
    chars[0] = "b"
    print("".join(chars))

    Çıktı

    97 c
    [2, 1, 1]
    immutable
    bat

DerslerString temelleriKelimeleri ters çevirme

İterasyon araçları

İndeksler üzerinde değil, değerler üzerinde döngü kur. İndeks de gerekiyorsa enumerate, birkaç diziyi birlikte dolaşmak için zip, yoksa özyinelemeyle yazacağın kombinatorik için itertools. itertools fonksiyonları lazy'dir: görmek için onları list() ile sar.

  • enumerate ve zip

    for i, ch in enumerate("ab", start=1):
        print(i, ch)
    names, ages = ["ana", "ben", "cy"], [31, 25]
    print(list(zip(names, ages)))  # shortest wins
    print(dict(zip(names, ages)))

    Çıktı

    1 a
    2 b
    [('ana', 31), ('ben', 25)]
    {'ana': 31, 'ben': 25}

    zip kısa olan girdide sessizce durur. zip(..., strict=True) bunun yerine hata fırlatır, ama yalnız 3.10'dan itibaren.

  • Transpoze ve komşu çiftler

    m = [[1, 2, 3], [4, 5, 6]]
    print(list(zip(*m)))       # transpose
    a = [1, 4, 9, 16]
    print([y - x for x, y in zip(a, a[1:])])

    Çıktı

    [(1, 4), (2, 5), (3, 6)]
    [3, 5, 7]

    itertools.pairwise ikinci satırı 3.10'dan itibaren yapar; zip(a, a[1:]) her yerde çalışır.

  • product, permutations, combinations

    import itertools as it
    print(list(it.product("ab", repeat=2)))
    print(list(it.permutations([1, 2, 3], 2)))
    print(list(it.combinations([1, 2, 3], 2)))
    print(len(list(it.permutations(range(5)))))

    Çıktı

    [('a', 'a'), ('a', 'b'), ('b', 'a'), ('b', 'b')]
    [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
    [(1, 2), (1, 3), (2, 3)]
    120

    n! permütasyon ve C(n, k) kombinasyon: n ≤ 10 için sorun yok, n = 30 için asla.

  • accumulate: kümülatif toplamlar, maksimumlar, çarpımlarPython 3.8+

    from itertools import accumulate
    import operator
    a = [3, 1, 4, 1, 5]
    print(list(accumulate(a)))
    print(list(accumulate(a, max)))
    print(list(accumulate(a, operator.mul)))
    print(list(accumulate(a, initial=0)))

    Çıktı

    [3, 4, 8, 9, 14]
    [3, 3, 4, 4, 5]
    [3, 3, 12, 12, 60]
    [0, 3, 4, 8, 9, 14]

    initial=0, baştaki sıfırıyla birlikte prefix sum dizisini verir.

  • groupby: eşit anahtarların kesintisiz grupları

    from itertools import groupby
    s = "aaabccdd"
    print([(k, len(list(g)))
           for k, g in groupby(s)])
    words = ["bob", "amy", "bill", "al"]
    for k, g in groupby(sorted(words), key=len):
        print(k, list(g))

    Çıktı

    [('a', 3), ('b', 1), ('c', 2), ('d', 2)]
    2 ['al']
    3 ['amy']
    4 ['bill']
    3 ['bob']

    Yalnız YAN YANA olan öğeleri gruplar: liste uzunluğa göre değil isme göre sıralandığı için 3 iki kez görünüyor. Grupladığın anahtarla sırala.

DerslerPermütasyon ve kombinasyonAlt kümeler

Özyineleme sınırları ve memoization

CPython tail call'ları optimize etmez ve bir özyinelemeyi yaklaşık bin frame'de RecursionError ile durdurur. 10⁵ düğümlü bir yol üzerinde DFS ya da 10⁴ derinliğinde memoize edilmiş bir DP için daha büyük bir sınır değil, açık bir stack ya da aşağıdan yukarı bir tablo gerekir.

  • Sınıra takılmak

    def depth(n):
        return 0 if n == 0 else 1 + depth(n - 1)
    print(depth(500))
    try:
        depth(100_000)
    except RecursionError:
        print("RecursionError")

    Çıktı

    500
    RecursionError

    CPython'da varsayılan 1000 frame; kesin sayı bir implementasyon detayı, cevabında onu yazdırma.

  • sys.setrecursionlimit — dikkatle

    import sys
    sys.setrecursionlimit(3_000)
    def depth(n):
        return 0 if n == 0 else 1 + depth(n - 1)
    print(depth(2_000))

    Çıktı

    2000

    Python'ın sayacını yükseltir, altındaki C stack'ini değil. Bu sayfanın çalıştırıldığı Windows makinesinde aynı fonksiyon 3.000 derinlikte süreci bir stack overflow ile çökertti; yakalanacak bir RecursionError yoktu. Bunu söyle, sonra iteratif sürümü öner.

  • functools.lru_cache

    from functools import lru_cache
    @lru_cache(maxsize=None)
    def fib(n):
        if n < 2:
            return n
        return fib(n - 1) + fib(n - 2)
    print(fib(80))
    print(fib.cache_info())
    fib.cache_clear()   # between test cases

    Çıktı

    23416728348467685
    CacheInfo(hits=78, misses=81, maxsize=None, currsize=81)

    Yaklaşık 8 × 10¹⁶ yerine 81 farklı çağrı. @functools.cache aynı şeyin 3.9'dan itibaren gelen kısa yazımıdır.

  • Cache'lenen argümanlar hashable olmalı

    from functools import lru_cache
    @lru_cache(maxsize=None)
    def total(items):
        return sum(items)
    try:
        total([1, 2])
    except TypeError:
        print("list: unhashable")
    print(total((1, 2)))   # pass a tuple

    Çıktı

    list: unhashable
    3

    Listeleri, cache'li bir fonksiyona ulaşmadan önce tuple'a (ya da indekslere) çevir.

DerslerÖzyineleme temelleriCall stackKendi call stack'inTail call'lar ve döngüler

Tam sayı ve float tuzakları

Python'da // ve %, C, Java ve JavaScript'teki gibi sıfıra doğru değil, eksi sonsuza doğru yuvarlar. Tam sayılar asla taşmaz; float'lar IEEE double'dır, onları bir toleransla karşılaştır.

  • Negatiflerle // ve %

    print(7 // 2, -7 // 2)
    print(int(-7 / 2), -7 % 2)
    print(divmod(-7, 2))
    a, b = 7, 2
    print(-(-a // b), (a + b - 1) // b)  # ceil

    Çıktı

    3 -4
    -3 1
    (-4, 1)
    4 4

    -7 // 2 -4'tür (aşağı yuvarlama); int(-7 / 2) -3'tür (float üzerinden kırpma, büyük sayılarda yanlış). Yukarı yuvarlama kalıpları tam sayıda kalır.

  • Tam sayılar asla taşmaz

    print(2 ** 100)
    print(10 ** 18 + 1 == 10 ** 18)
    MOD = 10 ** 9 + 7
    print(2 ** 64 % MOD)
    print(pow(3, 200, MOD))     # fast modular pow

    Çıktı

    1267650600228229401496703205376
    False
    582344008
    136318165

    Problem “10⁹+7 modunda döndür” diyorsa yine de ilerledikçe mod al: büyük tam sayı aritmetiği O(1) değildir.

  • Sentinel olarak math.inf

    import math
    best = math.inf
    for x in [5, 3, 8]:
        best = min(best, x)
    print(best, -math.inf < -10 ** 100)
    print(float("inf") == math.inf)
    nan = math.inf - math.inf
    print(nan, nan == nan)

    Çıktı

    3 True
    True
    nan False

    math.inf bir float'tır: cevap tam sayı olmak zorundaysa -1 (ya da bir int) döndür.

  • Float eşitliği ve yuvarlama

    import math
    print(0.1 + 0.2 == 0.3, 0.1 + 0.2)
    print(math.isclose(0.1 + 0.2, 0.3))
    print(round(2.5), round(3.5), round(2.675, 2))
    print(int("42") + int(3.9), 7 / 7)

    Çıktı

    False 0.30000000000000004
    True
    2 4 2.67
    45 1.0

    round yarımları çifte yuvarlar ve 2.675 aslında 2.67499…'dur. / her zaman float döndürür.

DerslerModüler aritmetikHızlı üs alma

Bit hileleri

Python tam sayılarının sabit bir genişliği yoktur; bu yüzden ~x, -x - 1'dir ve güvenebileceğin bir taşma yoktur. Problem 32 bitlik tam sayı varsayıyorsa 0xFFFFFFFF ile maskeyi kendin uygula.

  • Temel hileler

    x = 0b10110
    print(bin(x), x & 1, x >> 1, x << 2)
    print(bin(x & (x - 1)))  # drop lowest 1
    print(x & -x)             # lowest set bit
    print(bin(x).count("1"))  # set bits

    Çıktı

    0b10110 0 11 88
    0b10100
    2
    3

    x.bit_count() 3.10'dan itibaren 1 olan bitleri sayar; bin(x).count("1") her yerde çalışır.

  • İkinin kuvvetleri ve bit maskeleri

    def is_pow2(n):
        return n > 0 and n & (n - 1) == 0
    print([n for n in range(1, 20) if is_pow2(n)])
    mask = 0
    for i in [0, 3]:
        mask |= 1 << i           # set bit i
    print(bin(mask), (mask >> 3) & 1)
    print(bin(mask & ~1))        # clear bit 0

    Çıktı

    [1, 2, 4, 8, 16]
    0b1001 1
    0b1000

    Python'da &, =='den daha sıkı bağlanır (C ve Java'nın tersi), bu yüzden n & (n - 1) == 0 çalışır. Yine de parantez koy: okuyan kişi C ile düşünüyor olabilir.

  • XOR ve her alt küme

    from functools import reduce
    from operator import xor
    print(reduce(xor, [4, 1, 2, 1, 2]))
    items = ["a", "b", "c"]
    n = len(items)
    subsets = []
    for m in range(1 << n):
        picked = [items[i] for i in range(n)
                  if m >> i & 1]
        subsets.append("".join(picked))
    print(subsets)

    Çıktı

    4
    ['', 'a', 'b', 'ab', 'c', 'ac', 'bc', 'abc']

    x ^ x = 0 her çifti götürür. 0 … 2ⁿ−1 maskeleri, 2ⁿ alt kümenin ta kendisidir.

  • Negatif sayılar ve 32 bitlik görünümler

    print(~5, -5 >> 1)
    print(bin(-5 & 0xFFFFFFFF))
    print((5).bit_length(), (255).bit_length())

    Çıktı

    -6 -3
    0b11111111111111111111111111111011
    3 8

    -5 >> 1 -3'tür: sağa kaydırma, // gibi aşağı yuvarlar.

Derslerİkili sayılar ve bit seviyesinde işlemlerMaskeler ve ikinin kuvvetiXOR numaralarıKüme olarak bit maskesi

Sık tuzaklar

Python mülakatçısının gözünü diktiği bug'lar. Her biri şaşırtıcı bir şey yazdırır; düzeltmesi altındaki satırlarda.

  • Mutable varsayılan argümanlar

    def add(x, into=[]):     # one list, shared
        into.append(x)
        return into
    print(add(1), add(2))
    def add_fixed(x, into=None):
        into = [] if into is None else into
        into.append(x)
        return into
    print(add_fixed(1), add_fixed(2))

    Çıktı

    [1, 2] [1, 2]
    [1] [2]

    Varsayılan değer bir kez, def çalıştığında hesaplanır. None kullan ve listeyi içeride kur.

  • Geç bağlanan closure'lar

    fs = [lambda: i for i in range(3)]
    print([f() for f in fs])  # all see last i
    fs = [lambda i=i: i for i in range(3)]
    print([f() for f in fs])

    Çıktı

    [2, 2, 2]
    [0, 1, 2]

    Closure değişkeni ÇAĞRILDIĞINDA okur. Mevcut değeri varsayılan argüman olarak bağla.

  • is vs ==

    a = [1, 2]
    b = [1, 2]
    print(a == b, a is b)  # equal, not same
    c = a
    c.append(3)
    print(a, a is c)
    x = None
    print(x is None)        # the right use of is

    Çıktı

    True False
    [1, 2, 3] True
    True

    is “aynı nesne mi?” diye sorar. Küçük int'lerde ve kısa string'lerde doğru görünebilir, ama yalnız CPython onları cache'lediği için; değerleri asla onunla karşılaştırma.

  • Shallow copy'ler ve [[0] * n] * m

    import copy
    grid = [[0] * 2] * 2     # two refs, ONE row
    grid[0][0] = 1
    print(grid)
    a = [[1], [2]]
    b = a[:]         # = list(a) = a.copy()
    c = copy.deepcopy(a)
    a[0].append(9)
    print(b, c)

    Çıktı

    [[1, 0], [1, 0]]
    [[1, 9], [2]] [[1], [2]]

    Grid'leri comprehension ile kur. a[:], list(a) ve a.copy() yalnız dıştaki listeyi kopyalar.

  • Dict sırası garantilidir; set sırası değil

    d = {}
    for k in ["b", "c", "a"]:
        d[k] = True
    print(list(d))          # insertion order
    d.pop("c")
    d["c"] = 1              # now last
    print(list(d))
    print(sorted({"b", "c", "a"}))

    Çıktı

    ['b', 'c', 'a']
    ['b', 'a', 'c']
    ['a', 'b', 'c']

    Ekleme sırası 3.7'den beri dilin parçası. Var olan bir anahtarı güncellemek yerini korur; silip yeniden eklemek onu sona taşır.

  • Üzerinde dolaşırken bir dict'i değiştirmek

    d = {"a": 1, "b": 2}
    try:
        for k in d:
            del d[k]
    except RuntimeError:
        print("RuntimeError")
    d = {"a": 1, "b": 2}
    for k in list(d):       # loop over a copy
        del d[k]
    print(d)

    Çıktı

    RuntimeError
    {}

    Liste hata fırlatmaz; sessizce öğe atlar. Bir kopya üzerinde dolaş ya da yeni bir koleksiyon kur.

10 mülakat şablonu

Cevapların çoğunun üstüne kurulduğu iskeletler, Python'ın doğal yazımıyla; her biri dersiyle ve pratik yapacağın bir problemle. Mülakat pattern'leri cheat sheet'inde, bir problemin hangisini istediğini söyleyen sinyaller var.

  • İki pointer

    Sıralı bir dizi ve iki uçtan karar verilen bir çift, bölümleme ya da palindrom.

    Maliyet: O(n) zaman, O(1) alan

    def pair_sum(a, target):    # a is sorted
        i, j = 0, len(a) - 1
        while i < j:
            s = a[i] + a[j]
            if s == target:
                return i, j
            if s < target:
                i += 1
            else:
                j -= 1
        return None
    print(pair_sum([1, 3, 4, 6, 9], 10))

    Çıktı

    (0, 4)
    Ders
    İki pointer · Diziler
  • Kayan pencere

    Cevap ardışık bir parça ve bir ucu kaydırmak durumu ucuza günceller.

    Maliyet: O(n) zaman, O(k) alan

    def longest_unique(s):
        last = {}
        start = best = 0
        for i, ch in enumerate(s):
            if last.get(ch, -1) >= start:
                start = last[ch] + 1
            last[ch] = i
            best = max(best, i - start + 1)
        return best
    print(longest_unique("abcabcbb"))

    Çıktı

    3
    Ders
    Kayan pencere · Diziler
  • deque ile BFS

    Ağırlıksız bir graf ya da grid'de en az adım; seviye seviye.

    Maliyet: O(V + E) zaman, O(V) alan

    from collections import deque
    def bfs(graph, src):
        dist = {src: 0}
        q = deque([src])
        while q:
            u = q.popleft()
            for v in graph[u]:
                if v not in dist:  # on push
                    dist[v] = dist[u] + 1
                    q.append(v)
        return dist
    g = {1: [2, 3], 2: [4], 3: [4], 4: []}
    print(bfs(g, 1))

    Çıktı

    {1: 0, 2: 1, 3: 1, 4: 2}

    list.pop(0) bunu O(V²) yapardı. Düğümü pop edildiğinde değil, kuyruğa eklendiğinde işaretle.

  • DFS, özyinelemeli ve iteratif

    Bağlı olan her şeye ulaş; flood fill, adalar, döngü kontrolleri, yollar.

    Maliyet: O(V + E) zaman, O(V) alan

    g = {1: [2, 3], 2: [4], 3: [4], 4: []}
    def dfs(u, seen, order):
        seen.add(u)
        order.append(u)
        for v in g[u]:
            if v not in seen:
                dfs(v, seen, order)
        return order
    print(dfs(1, set(), []))
    def dfs_iter(src):   # no depth limit
        seen, order, stack = set(), [], [src]
        while stack:
            u = stack.pop()
            if u in seen:
                continue
            seen.add(u)
            order.append(u)
            stack.extend(reversed(g[u]))
        return order
    print(dfs_iter(1))

    Çıktı

    [1, 2, 4, 3]
    [1, 2, 4, 3]

    Komşuları ters sırayla push etmek, stack'in onları özyinelemeli sırayla ziyaret etmesini sağlar.

  • bisect ile ikili arama

    Sıralı bir liste: ekleme konumu, ilk/son geçiş, bir aralıktaki sayı.

    Maliyet: Arama başına O(log n)

    from bisect import bisect_left, bisect_right
    from bisect import insort
    a = [1, 2, 4, 4, 4, 7]
    print(bisect_left(a, 4), bisect_right(a, 4))
    print(bisect_right(a, 4) - bisect_left(a, 4))
    i = bisect_left(a, 5)
    print(i < len(a) and a[i] == 5)  # found?
    insort(a, 5)                # O(n) insert
    print(a)

    Çıktı

    2 5
    3
    False
    [1, 2, 4, 4, 4, 5, 7]

    bisect_left: a[i] ≥ x olan ilk indeks; bisect_right: a[i] > x olan ilk indeks. key= argümanı 3.10 ister.

    Ders
    İkili arama · Arama
  • Prefix sum

    Tek bir dizi üzerinde çok sayıda aralık toplamı ya da toplamı k olan subarray'ler.

    Maliyet: O(n) kurulum, sorgu başına O(1)

    from itertools import accumulate
    a = [2, 4, 1, 3]
    pre = [0, *accumulate(a)]  # sum(a[:i])
    print(pre, pre[3] - pre[1])  # sum(a[1:3])
    def count_k(nums, k):  # sums equal to k
        seen = {0: 1}
        total = count = 0
        for x in nums:
            total += x
            count += seen.get(total - k, 0)
            seen[total] = seen.get(total, 0) + 1
        return count
    print(count_k([1, 2, 1, -1, 2], 3))

    Çıktı

    [0, 2, 6, 7, 10] 5
    3

    pre[j] - pre[i]'yi özel durum olmadan a[i:j]'nin toplamı yapan, baştaki 0'dır.

    Ders
    Prefix sum · Diziler
  • Monoton stack

    Sonraki büyük / küçük eleman, span'ler, en büyük dikdörtgen.

    Maliyet: O(n) zaman, O(n) alan

    def next_greater(a):
        ans = [-1] * len(a)
        stack = []   # indices, values falling
        for i, x in enumerate(a):
            while stack and a[stack[-1]] < x:
                ans[stack.pop()] = x
            stack.append(i)
        return ans
    print(next_greater([2, 1, 2, 4, 3]))

    Çıktı

    [4, 2, 4, -1, -1]

    Her indeks bir kez push, en fazla bir kez pop edilir: içteki while'a rağmen O(n).

    Ders
    Monoton stack · Stack ve kuyruklar
  • Heap ile top-k

    n öğenin en büyük, en küçük, en yakın ya da en sık k tanesi.

    Maliyet: O(n log k) zaman, O(k) alan

    import heapq
    def top_k(nums, k):
        h = []            # min-heap, <= k
        for x in nums:
            heapq.heappush(h, x)
            if len(h) > k:
                heapq.heappop(h)
        return sorted(h, reverse=True)
    print(top_k([5, 1, 9, 3, 7, 2], 3))
    print(heapq.nlargest(3, [5, 1, 9, 3, 7, 2]))

    Çıktı

    [9, 7, 5]
    [9, 7, 5]

    En BÜYÜK k taneyi tutmak için bir MIN-heap'ten at: tepesi, tutulan k tanenin en zayıfıdır.

    Ders
    Top-k elemanlar · Heap'ler
  • Union-find

    Yalnız birleşen bağlı bileşenler; yönsüz bir grafta döngü tespiti.

    Maliyet: İşlem başına ≈ O(1), O(n) alan

    parent = list(range(5))
    size = [1] * 5
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # halve
            x = parent[x]
        return x
    def union(a, b):
        ra, rb = find(a), find(b)
        if ra == rb:
            return False       # already joined
        if size[ra] < size[rb]:
            ra, rb = rb, ra
        parent[rb] = ra
        size[ra] += size[rb]
        return True
    print(union(0, 1), union(1, 2), union(0, 2))
    print(len({find(x) for x in range(5)}))

    Çıktı

    True True False
    3

    find bilerek iteratif: özyinelemeli bir sürüm uzun bir zincirde özyineleme sınırına takılır.

    Ders
    Disjoint set temelleri · Union-find
  • Memoization'lı DPPython 3.9+

    Örtüşen alt problemler: recurrence'ı yaz, sonra cache'le.

    Maliyet: O(durum × seçenek) zaman, O(durum) alan

    from functools import cache
    coins = (1, 2, 5)
    @cache
    def fewest(amount):
        if amount == 0:
            return 0
        best = float("inf")
        for c in coins:
            if c <= amount:
                best = min(best,
                           fewest(amount - c) + 1)
        return best
    print(fewest(11), fewest(3))

    Çıktı

    3 2

    Derinlik, tutarın kendisi: birkaç bini geçince aşağıdan yukarıya çevir (bkz. Özyineleme sınırları).

    Ders
    Memoization · Özyineleme

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