Dil

Mülakatlar için Python

Deyimler, koleksiyonlar, ListNode/TreeNode ve kod mülakatlarında çıkan tuzaklar. Python 3.10+; sitenin CI’si 3.12 çalıştırır.

Python 3.10 veya daha yenisini varsayar. Sitenin CI’si 3.12 çalıştırır.

match 3.10 ister. dict | other ve list[int] 3.9 ister. Walrus operatörü 3.8 ister. math.lcm 3.9, int.bit_count 3.10 ister.

Aşağıdaki her Python bloğu kendi başına çalışır.

İsimler ve unpacking

a, b = 1, 2
a, *rest = [1, 2, 3]
assert rest == [2, 3]
a, b = b, a
assert (a, b) == (2, 1)
x = y = z = 0
assert (x, y, z) == (0, 0, 0)

type(x) sınıfı döndürür. isinstance(x, (int, float)) ikisini de kabul eder. Gerçekten istediğin dönüşümler int("5"), float("1.5"), str(5), bool(0) ve list("ab"). bool(0) False.

Operatörler

assert 7 / 2 == 3.5
assert 7 // 2 == 3
assert -3 // 2 == -2          # floor, toward -infinity
assert -3 % 2 == 1            # remainder takes the sign of the divisor
assert 2 ** 10 == 1024
assert (1 < 3 < 5) is True
value = 1 if True else 2
assert value == 1

and, or ve not boolean operatörleridir. in üyelik, is kimlik operatörüdür. & | ^ ~ << >> bitwise. Problemlerde işe yarayan kimlikler için bit-manipülasyonu kalıbına bak.

x or default, 0, "" ve [] dahil her falsy x için default döner. Bu değerler gerçek veri olduğunda x if x is not None else default kullan.

name = "ada"
n = len(name)
assert (n := len(name)) > 2 and n == 3

if testinin içinde walrus’un çevresindeki parantez zorunludur.

Dizgiler

name, pi, bits = "ada", 3.14159, 10
text = f"{name!r:>6} {pi:.2f} {1024:,} {bits:08b} {bits=}"
assert text == " 'ada' 3.14 1,024 00001010 bits=10"

s = "ab,cd"
assert s[0] == "a" and s[-1] == "d"
assert s[1:4] == "b,c" and s[::-1] == "dc,ba"
assert s.split(",") == ["ab", "cd"]
assert " ".join(["ab", "cd"]) == "ab cd"
assert s.replace("ab", "xy") == "xy,cd"
assert s.startswith("ab") and s.endswith("cd")
assert s.find("z") == -1
assert "5".isdigit() and "a".isalpha()
assert ord("A") == 65 and chr(65) == "A"

s.index("z") alt dizgi yoksa ValueError fırlatır. s.find -1 döner. Argümansız s.split() boşlukta böler ve boş parçaları atar. s.strip, lstrip ve rstrip yalnızca uçları siler.

Biçim genişliği bir minimumdur. {10:08b} → 00001010. {1024:08b} → 10000000000, çünkü 1024 zaten 11 bit ister. !r tırnakları genişliğe sayar; ada için {name!r:>6} bir boşluk artı 'ada'.

Listeler

bad = [[0] * 2] * 2
bad[0][0] = 1
assert bad == [[1, 0], [1, 0]]

good = [[0] * 2 for _ in range(2)]
good[0][0] = 1
assert good == [[1, 0], [0, 0]]

nums = [3, 1, 2]
nums.append(4)
nums.extend([5])
assert nums == [3, 1, 2, 4, 5]
assert nums.pop() == 5
assert nums == [3, 1, 2, 4]
assert nums[1:3] == [1, 2]
assert sorted(nums) == [1, 2, 3, 4]
assert nums[::-1] == [4, 2, 1, 3]
shallow = nums[:]
shallow.append(9)
assert 9 not in nums

list.sort yerinde sıralar ve None döner. sorted yeni bir liste döner. nums.pop(0) ve nums.insert(0, x) O(n). İki uç da önemliyse collections.deque kullan.

copy.copy sığdır. copy.deepcopy iç içe kapları kopyalar.

Tuple ve kümeler

pair = (1, 2)
one = (1,)
assert one != (1)

items = {1, 2, 3}
empty = set()
items.add(4)
items.discard(9)
assert items == {1, 2, 3, 4}
a, b = {1, 2}, {2, 3}
assert (a | b, a & b, a - b, a ^ b) == ({1, 2, 3}, {2}, {1}, {1, 3})
assert {1} <= a
assert frozenset([1, 2]) == frozenset([2, 1])

{} bir dict’tir. Boş küme set(). remove eleman yoksa KeyError fırlatır. discard fırlatmaz.

Dict’ler

keys, values = ["a", "b"], [1, 2]
d = dict(zip(keys, values))
assert d.get("z", 0) == 0
d.setdefault("k", []).append(1)
assert d["k"] == [1]
left, right = {"a": 1}, {"b": 2}
assert left | right == {"a": 1, "b": 2}
assert {k: v for k, v in d.items() if k == "a"} == {"a": 1}

del d[key] anahtar yoksa KeyError fırlatır. d.pop(key, None) varsayılanı döner. Dict’i dolaşırken anahtar ekleme veya silme.

Comprehension’lar

assert [x * x for x in range(5) if x % 2 == 0] == [0, 4, 16]
matrix = [[1, 2], [3]]
assert [y for row in matrix for y in row] == [1, 2, 3]
squares = (x * x for x in range(3))
assert list(squares) == [0, 1, 4]

Parantezli biçim bir generator’dır. Her seferinde bir değer üretir; bir geçişten sonra tükenir.

Kontrol akışı

seen = []
for i, value in enumerate(["a", "b"], start=1):
    seen.append((i, value))
assert seen == [(1, "a"), (2, "b")]
assert list(zip([1, 2], ["a", "b", "c"])) == [(1, "a"), (2, "b")]

found = None
for value in [1, 3, 4]:
    if value % 2 == 0:
        found = value
        break
else:
    found = -1
assert found == 4

for/else yan tümcesi döngü break etmediyse çalışır.

def classify(cmd):
    match cmd:
        case "go" | "run":
            return "move"
        case [x, y]:
            return ("pair", x, y)
        case {"k": v}:
            return ("map", v)
        case int() if cmd > 5:
            return "big"
        case _:
            return "other"

assert classify("run") == "move"
assert classify([1, 2]) == ("pair", 1, 2)
assert classify({"k": 3}) == ("map", 3)
assert classify(6) == "big"
assert classify(1) == "other"

Fonksiyonlar

def append_bad(value, bucket=[]):
    bucket.append(value)
    return bucket

first = append_bad(1)
second = append_bad(2)
assert first is second and second == [1, 2]

def append_ok(value, bucket=None):
    if bucket is None:
        bucket = []
    bucket.append(value)
    return bucket

assert append_ok(1) == [1]
assert append_ok(2) == [2]

fns = [lambda: i for i in range(3)]
assert [fn() for fn in fns] == [2, 2, 2]
fns = [lambda i=i: i for i in range(3)]
assert [fn() for fn in fns] == [0, 1, 2]

def outer():
    count = 0

    def inner():
        nonlocal count
        count += 1
        return count

    return inner

tick = outer()
assert tick() == 1 and tick() == 2

Varsayılan argüman tanımda bir kez hesaplanır. Liste, dict veya küme varsayılanı her çağıranla paylaşılır. Döngü değişkenini kapatan bir closure, değer varsayılan olarak bağlanmadıkça değişkenin son değerini görür.

def f(a, b=2, /, c=3, *args, d, e=5, **kw):
    return (a, b, c, args, d, e, kw)

assert f(1, 2, 3, d=4) == (1, 2, 3, (), 4, 5, {})

/ öncesi isimler yalnızca konumsal. * veya *args sonrası isimler yalnızca anahtar kelime.

sum(nums, 10) bir başlangıç değeri ekler. Parametre anahtar kelime de kabul eder: sum(nums, start=10).

Decorator’lar

from functools import wraps

def bold(fn):
    @wraps(fn)
    def wrapper(*args, **kwargs):
        return f"<b>{fn(*args, **kwargs)}</b>"
    return wrapper

def italic(fn):
    @wraps(fn)
    def wrapper(*args, **kwargs):
        return f"<i>{fn(*args, **kwargs)}</i>"
    return wrapper

@bold
@italic
def greet(name):
    return f"Hello, {name}"

assert greet("World") == "<b><i>Hello, World</i></b>"
assert greet.__name__ == "greet"

@italic üstündeki @bold bold(italic(greet)) demektir. Çağrı önce bold, sonra italic, sonra fonksiyonu çalıştırır. @wraps orijinal adı wrapper’a kopyalar. Bu bir Python fonksiyon decorator’ıdır. Gang-of-Four decorator bir nesne sarmalayıcısıdır.

Iterator’lar

from itertools import groupby

def gen(n):
    yield from range(n)

assert list(gen(3)) == [0, 1, 2]

data = [1, 2, 1]
assert [k for k, _ in groupby(data)] == [1, 2, 1]
data = sorted(data)
groups = [(k, list(g)) for k, g in groupby(data)]
assert groups == [(1, [1, 1]), (2, [2])]

itertools.groupby yalnızca yan yana eşit anahtarları gruplar. Anahtarlar dağınıksa önce sırala.

itertools ayrıca chain, islice, product, permutations, combinations ve accumulate sunar.

Sınıflar, dataclass, istisnalar

class Animal:
    def __init__(self, name):
        self.name = name

    def speak(self):
        raise NotImplementedError

class Dog(Animal):
    def speak(self):
        return "woof"

assert Dog("a").speak() == "woof"

from dataclasses import dataclass, field

@dataclass(frozen=True, order=True)
class Point:
    x: int
    y: int = 0
    tags: list = field(default_factory=list)

assert Point(1) < Point(2)

field(default_factory=list) her örneğe kendi listesini verir. Çıplak tags: list = [] paylaşılır; frozen=True onu reddeder.

def parse(text):
    try:
        return int(text)
    except ValueError:
        return None

assert parse("3") == 3 and parse("x") is None

try üzerindeki else istisna yoksa çalışır. finally çıkışta çalışır. raise New() from err nedeni zincirler.

Dosyalar

from pathlib import Path

here = Path("notes.txt")
assert here.suffix == ".txt" and here.stem == "notes"

Metni encoding="utf-8" ile aç. Küçük işler için pathlib.Path.read_text ve write_text yeter. with bloğu dosyayı kapatır.

Mülakat koleksiyonları

from collections import Counter, defaultdict, deque
import heapq
import bisect

assert Counter("abca").most_common(1) == [("a", 2)]

graph = defaultdict(list)
graph["a"].append("b")
assert graph["missing"] == []

q = deque([1])
q.append(2)
assert q.popleft() == 1

heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
assert heapq.heappop(heap) == 1
heapq.heappush(heap, -5)
assert -heapq.heappop(heap) == 5

ordered = [1, 3, 3, 7]
assert bisect.bisect_left(ordered, 3) == 1
assert bisect.bisect_right(ordered, 3) == 3

heapq bir min-heap. Max-heap için negatifi it. bisect_left değerin oturabileceği ilk indeks. bisect_right eşitlerin hemen sonrası.

Matematik

import math

assert divmod(7, 3) == (2, 1)
assert pow(2, 10, 1000) == 24
assert math.gcd(12, 18) == 6
assert math.lcm(4, 6) == 12
assert math.isclose(0.1 + 0.2, 0.3)
assert round(1.5) == 2 and round(2.5) == 2  # ties go to the even integer
assert math.inf > 10**18

math.prod 3.8’den beri var. math.lcm olmayan sürümlerde LCM abs(a * b) // math.gcd(a, b).

Kimlik

assert 1 == 1
sentinel = object()
assert (sentinel is sentinel) is True

is kimliği karşılaştırır. None ve sentinel’ler için kullan. == değerleri karşılaştırır. CPython küçük int’leri intern eder; is orada eşitlik gibi görünüp büyük int’lerde bozulur. Değerleri == ile karşılaştır.

Async

import asyncio

async def fetch(n):
    return n

async def main():
    return await asyncio.gather(fetch(1), fetch(2))

assert asyncio.run(main()) == [1, 2]

async with ve async for, context manager ve döngünün async biçimleridir.

Tipler

from typing import TypeVar

T = TypeVar("T")

def first(xs: list[T]) -> T:
    return xs[0]

assert first([1, 2]) == 1

name: str | None = None
assert name is None

3.12 ve sonrasında aynı fonksiyon def first[T](xs: list[T]) -> T yazılabilir. Protocol, TypedDict, Literal ve Final typing içindedir.

Standart kütüphane isimleri

Algoritma problemlerinin dışında görünenler: json, re, random, datetime, logging, subprocess, argparse, csv, sqlite3, unittest ve pytest. Metin için re.search, re.findall, re.sub. JSON için json.loads / json.dumps. El yapımı yollar yerine pathlib.

Bağlı listeler

Bağlı liste şablonu bu düğüm artı reverse ve dummy-head birleştirmesidir.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

a = ListNode(1, ListNode(2, ListNode(3)))
assert to_list(reverse_list(a)) == [3, 2, 1]

while cur ile yürü. Dummy head, birleştirme döngüsünün ilk düğümü özel saymasını engeller. Boş liste None.

Ağaçlar

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

root = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4)))
assert max_depth(root) == 3

left ve right üzerinde özyineleme DFS şablonudur. Seviye sırası bir kuyruk; mevcut seviye için len(q) anlık görüntüsü.

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def level_order(root):
    if not root:
        return []
    res, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):
            n = q.popleft()
            level.append(n.val)
            if n.left:
                q.append(n.left)
            if n.right:
                q.append(n.right)
        res.append(level)
    return res

root = TreeNode(1, TreeNode(2), TreeNode(3))
assert level_order(root) == [[1], [2, 3]]

Graflar

Graf-DFS şablonu yönsüz kenarları defaultdict(list) olarak saklar. Izgara flood fill (r, c) hücrelerinin yığını (veya kuyruğu)dır.

from collections import defaultdict

def count_components(n, edges):
    adj = defaultdict(list)
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    visited = [False] * n
    count = 0

    def dfs(v):
        visited[v] = True
        for u in adj[v]:
            if not visited[u]:
                dfs(u)

    for v in range(n):
        if not visited[v]:
            dfs(v)
            count += 1
    return count

assert count_components(4, [(0, 1), (2, 3)]) == 2

def flood_fill(image, sr, sc, new_color):
    orig = image[sr][sc]
    if orig == new_color:
        return image
    rows, cols = len(image), len(image[0])
    stack = [(sr, sc)]
    while stack:
        r, c = stack.pop()
        if r < 0 or c < 0 or r >= rows or c >= cols or image[r][c] != orig:
            continue
        image[r][c] = new_color
        stack.extend([(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)])
    return image

assert flood_fill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2) == [
    [2, 2, 2],
    [2, 2, 0],
    [2, 0, 1],
]

orig == new_color aynı rengi sonsuz yeniden yazmayı kesen erken dönüştür.

Union-Find

Path compression artı rank’e göre birleştirme. union, iki düğümün farklı bileşenlerde olup olmadığını döner.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.components = n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        self.components -= 1
        return True

uf = UnionFind(4)
assert uf.union(0, 1) and uf.union(2, 3)
assert not uf.union(0, 1)
assert uf.components == 2

Trie

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_word = True

    def _walk(self, s):
        node = self.root
        for ch in s:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

    def search(self, word):
        node = self._walk(word)
        return bool(node and node.is_word)

    def startsWith(self, prefix):
        return self._walk(prefix) is not None

t = Trie()
t.insert("apple")
assert t.search("apple") and not t.search("app")
assert t.startsWith("app")

search is_word ister. startsWith yalnızca yürüyüşün hayatta kalmasını ister.