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 İşlem Zaman 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;
dequekullan.- Big-O
- Dizi (dinamik)
- Ders
- Dizi temelleri · Diziler
dict
Bir hash map. Anahtarlar hashable olmalı; dolaşma ekleme sırasını izler.
dict: işlem maliyetleri İşlem Zaman 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;getvesetdefaultfı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 İşlem Zaman add, remove, x in s O(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ş setset().- 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 İşlem Zaman append, appendleft O(1) pop, popleft O(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.- Big-O
- Kuyruk / deque
- 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 İşlem Zaman heapify(a) O(n) heappush, heappop O(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.- Big-O
- İkili heap
- 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 İşlem Zaman 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 İşlem Zaman d[k] (yoksa oluşturur) O(1) avg geri kalan her şey as 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']} [] 3groups["zzz"]'yi yalnız okumak bile onu ekledi. Üyeliğiinile 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 İşlem Zaman move_to_end(k) O(1) popitem(last=False) O(1) geri kalan her şey as 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] 18Filtre
if'i döngüden sonra gelir;a if c else bseç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.
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:aartı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.
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.jointek 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;indexValueError 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
İ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}zipkı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.pairwiseikinci 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)] 120n! 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
3iki kez görünüyor. Grupladığın anahtarla sırala.
Ö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.cacheaynı ş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.infbir 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
roundyarımları çifte yuvarlar ve 2.675 aslında 2.67499…'dur./her zaman float döndürür.
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üzdenn & (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)vea.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
- Pratik
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
- Pratik
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.- Ders
- Genişlik öncelikli arama · Graflar
- Pratik
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.
- Ders
- Derinlik öncelikli arama · Graflar
- Pratik
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
- Pratik
- Tam sayı karekökKolay
- İlk ve son konumOrta
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 olmadana[i:j]'nin toplamı yapan, baştaki 0'dır.- Ders
- Prefix sum · Diziler
- Pratik
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
- Pratik
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
- Pratik
- En zayıf k ekipKolay
- k. en büyük değerOrta
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
findbilerek iteratif: özyinelemeli bir sürüm uzun bir zincirde özyineleme sınırına takılır.- Ders
- Disjoint set temelleri · Union-find
- Pratik
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
- Pratik
bytepatterns.com/cheatsheets/python — oradaki her satır animasyonlu bir derse bağlı.