Pular para o conteúdo

Cheat sheet de Python para entrevistas

O Python que o entrevistador espera: custo das estruturas, ordenação, strings, itertools, armadilhas e dez templates, com a saída real de cada trecho.

Atualizado em 54 trechos, todos executados10 templatesPronta para imprimir — use a impressão do seu navegador

Cada trecho desta página foi executado exatamente como está impresso, e a saída abaixo dele é o que o Python imprimiu. Escrito para Python 3.9 ou superior; as poucas linhas que exigem uma versão mais nova avisam. Os custos são os do CPython: pior caso, a menos que marcado como avg (médio) ou amortized (amortizado).

Estruturas de dados e seus custos

Os built-ins e os tipos de collections com que uma resposta é construída. Cada card leva à linha da cheat sheet de Big-O da estrutura por trás dele.

  • list

    Um array dinâmico: rápido no fim, lento no início.

    list: custo das operações
    OperaçãoTempo
    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] (copia)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

    Saída

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

    Tirar do início dentro de um loop custa O(n²) no total — use um deque.

    Aula
    O básico de arrays · Arrays
  • dict

    Um hash map. As chaves precisam ser hashable; a iteração segue a ordem de inserção.

    dict: custo das operações
    OperaçãoTempo
    d[k], d[k] = v, del d[k]O(1) avgO(n) worst
    k in d, d.get(k, default)O(1) avg
    percorrer chaves / itensO(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

    Saída

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

    d[k] com uma chave ausente lança KeyError; get e setdefault não.

    Aula
    O básico de tabelas hash · Tabelas hash
  • set

    “Já vi isso?” em O(1). Sem ordem, sem duplicatas.

    set: custo das operações
    OperaçãoTempo
    add, remove, x in sO(1) avg
    a | b, a & b, a - b (tamanhos 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))

    Saída

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

    Imprima um conjunto passando por sorted — a ordem dele não faz parte da linguagem. {} é um dict vazio; um conjunto vazio é set().

    Aula
    O básico de tabelas hash · Tabelas hash
  • deque

    from collections import deque

    A fila: O(1) nas duas pontas. A estrutura da BFS.

    deque: custo das operações
    OperaçãoTempo
    append, appendleftO(1)
    pop, popleftO(1)
    q[i] no meioO(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)

    Saída

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

    maxlen descarta pela outra ponta: uma janela de tamanho fixo de graça.

    Aula
    O básico de filas · Pilhas e filas
  • heapq

    import heapq

    Um MIN-heap binário sobre uma lista comum. Para um max-heap, insira os valores negativos.

    heapq: custo das operações
    OperaçãoTempo
    heapify(a)O(n)
    heappush, heappopO(log n)
    a[0] (ver o mínimo)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])

    Saída

    0 1
    [1, 3]
    8

    Insira tuplas (priority, count, item) para que um empate nunca compare dois itens.

    Aula
    O básico de heaps · Heaps
  • Counter

    from collections import Counter

    Um dict de contagens: frequências, anagramas, “top k mais comuns”.

    Counter: custo das operações
    OperaçãoTempo
    Counter(iterable)O(n)
    c[x] (0 se ausente)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"))

    Saída

    Counter({'a': 3, 'n': 2, 'b': 1})
    3 0
    [('a', 3), ('n', 2)]
    True
    Aula
    Contagem de frequência · Tabelas hash
  • defaultdict

    from collections import defaultdict

    Um dict que cria o valor ausente na primeira leitura — agrupamento em uma linha.

    defaultdict: custo das operações
    OperaçãoTempo
    d[k] (cria se ausente)O(1) avg
    todo o restoas 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))

    Saída

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

    Só de ler groups["zzz"], a chave foi inserida. Teste a presença com in.

    Aula
    Group Anagrams · Tabelas hash
  • OrderedDict

    from collections import OrderedDict

    Um dict com reordenação em O(1): o cache LRU em poucas linhas.

    OrderedDict: custo das operações
    OperaçãoTempo
    move_to_end(k)O(1)
    popitem(last=False)O(1)
    todo o restoas 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()))

    Saída

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

    Um dict comum também mantém a ordem de inserção (3.7+), mas não tem move_to_end.

    Aula
    Cache LRU · Low-level design

Fatiamento e comprehensions

a[start:stop:step] nunca lança erro com um limite fora do intervalo e sempre cria uma lista nova — O(k) de tempo e memória para k itens. Uma comprehension é o loop idiomático que cria uma lista, um dict ou um set; uma expressão geradora (generator expression) não cria nada.

  • Fatias

    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

    Saída

    [1, 2, 3] [4, 5] [0, 1]
    [0, 2, 4] [5, 4, 3, 2, 1, 0]
    [] []
  • Uma fatia é uma cópia

    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)

    Saída

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

    A cópia é rasa: listas aninhadas são compartilhadas (veja Armadilhas comuns).

  • Comprehensions de lista, dict e set

    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

    Saída

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

    O filtro if vai depois do loop; a escolha a if c else b vai antes dele.

  • Grids: montar, achatar, transpor

    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)])

    Saída

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

    Loops aninhados são lidos da esquerda para a direita, o externo primeiro — a ordem em que você os escreveria.

AulasO básico de arraysInversão in-place

Ordenação

Timsort: O(n log n) no pior caso, O(n) em dados que já estão ordenados, e ESTÁVEL — chaves iguais mantêm a ordem da entrada, e é isso que faz ordenações em várias passadas funcionarem. sorted() aceita qualquer iterável e retorna uma lista nova; list.sort() ordena in-place e retorna None.

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

    Saída

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

    a = a.sort() é o bug clássico: agora a é None.

  • key= e reverse=

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

    Saída

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

    A chave é calculada uma vez por item, não uma vez por comparação.

  • Várias chaves, direções mistas

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

    Saída

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

    Troque o sinal de um número para inverter a direção dele dentro de uma chave em tupla; strings não têm sinal — ordene duas vezes no lugar disso.

  • Estabilidade: ordene duas vezes, a chave secundária primeiro

    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)

    Saída

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

    Empates mantêm a ordem da entrada, então a segunda passada preserva a ordem da primeira dentro de cada número.

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

    Saída

    9534330

    Para uma ordem que nenhuma chave consegue expressar (“largest number”). Negativo significa a primeiro, positivo b primeiro, 0 iguais.

AulasO básico de ordenaçãoQual ordenação usar?

Strings

Strings são imutáveis: toda “mudança” cria uma nova. Monte a saída como uma lista de pedaços e faça join uma vez só; transforme a string em lista quando precisar editá-la in-place.

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

    Saída

    abc a-b-c
    1,2,3

    += em um loop pode ser O(n²): o CPython às vezes estende in-place, mas nada garante isso. join é uma única passada O(n).

  • f-stringsPython 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=}")

    Saída

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

    {x=} imprime a expressão e o valor dela — útil para depurar quando você executa o código no quadro.

  • Os métodos que o entrevistador espera

    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)

    Saída

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

    split() sem argumento divide em sequências de espaços em branco e descarta pedaços vazios. find retorna -1; index lança ValueError.

  • Caracteres como números; editar uma string

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

    Saída

    97 c
    [2, 1, 1]
    immutable
    bat

AulasO básico de stringsInverter as palavras

Ferramentas de iteração

Percorra valores, não índices. enumerate quando você também precisa do índice, zip para percorrer várias sequências juntas e itertools para a combinatória que você escreveria como recursão. As funções do itertools são preguiçosas (lazy): envolva-as em list() para ver o resultado.

  • enumerate e 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)))

    Saída

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

    zip para em silêncio na entrada mais curta. zip(..., strict=True) lança erro no lugar disso, mas só a partir da 3.10.

  • Transpor e pares vizinhos

    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:])])

    Saída

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

    itertools.pairwise faz a segunda linha a partir da 3.10; zip(a, a[1:]) funciona em qualquer versão.

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

    Saída

    [('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! permutações e C(n, k) combinações: tudo bem para n ≤ 10, nunca para n = 30.

  • accumulate: somas, máximos e produtos acumuladosPython 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)))

    Saída

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

    initial=0 dá o array de somas de prefixos com o zero inicial.

  • groupby: sequências de chaves iguais

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

    Saída

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

    Ele agrupa só itens ADJACENTES: 3 aparece duas vezes porque a lista foi ordenada por nome, não por tamanho. Ordene pela mesma chave usada para agrupar.

AulasPermutações vs. combinaçõesSubconjuntos

Limites de recursão e memoização

O CPython não otimiza chamadas de cauda e interrompe uma recursão em cerca de mil frames com um RecursionError. Uma DFS sobre um caminho de 10⁵ nós, ou uma DP memoizada com 10⁴ de profundidade, precisa de uma pilha explícita ou de uma tabela bottom-up — não de um limite maior.

  • O limite, atingido

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

    Saída

    500
    RecursionError

    O padrão é 1000 frames no CPython; o número exato é detalhe de implementação, então não o imprima numa resposta.

  • sys.setrecursionlimit — com cuidado

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

    Saída

    2000

    Ele aumenta o contador do Python, não a pilha de C por baixo dele. Na máquina Windows em que esta cheat sheet foi executada, a mesma função com 3.000 de profundidade derrubou o processo com um estouro de pilha (stack overflow) — sem RecursionError para capturar. Diga isso e ofereça a versão iterativa.

  • 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

    Saída

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

    81 chamadas distintas em vez de cerca de 8 × 10¹⁶. @functools.cache é a mesma coisa, com nome mais curto, a partir da 3.9.

  • Argumentos em cache precisam ser hashable

    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

    Saída

    list: unhashable
    3

    Converta listas em tuplas (ou índices) antes que elas cheguem a uma função com cache.

AulasO básico de recursãoA pilha de chamadasSua própria pilha de chamadasChamadas de cauda e loops

Pegadinhas com inteiros e floats

// e % do Python arredondam em direção a menos infinito, não em direção a zero como em C, Java e JavaScript. Inteiros nunca dão overflow, e floats são doubles IEEE — compare-os com uma tolerância.

  • // e % com negativos

    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

    Saída

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

    -7 // 2 é -4 (piso); int(-7 / 2) é -3 (trunca, passando por um float — errado para números grandes). As formas idiomáticas de teto (ceil) não saem dos inteiros.

  • Inteiros nunca dão overflow

    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

    Saída

    1267650600228229401496703205376
    False
    582344008
    136318165

    Quando um problema diz “retorne o resultado módulo 10⁹+7”, reduza ao longo do caminho mesmo assim: aritmética com inteiros grandes não é O(1).

  • math.inf como sentinela

    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)

    Saída

    3 True
    True
    nan False

    math.inf é um float: retorne -1 (ou um int) quando a resposta precisar ser inteira.

  • Igualdade de floats e arredondamento

    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)

    Saída

    False 0.30000000000000004
    True
    2 4 2.67
    45 1.0

    round arredonda metades para o par, e 2.675 na verdade é 2.67499…. / sempre retorna um float.

AulasAritmética modularExponenciação rápida

Truques com bits

Inteiros do Python não têm largura fixa, então ~x é -x - 1 e não existe overflow com que contar. Quando um problema supõe inteiros de 32 bits, aplique você mesmo a máscara 0xFFFFFFFF.

  • Os truques essenciais

    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

    Saída

    0b10110 0 11 88
    0b10100
    2
    3

    x.bit_count() conta os bits ligados (set bits) a partir da 3.10; bin(x).count("1") funciona em qualquer versão.

  • Potências de dois e máscaras de bits

    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

    Saída

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

    No Python, & tem precedência maior que == — o oposto de C e Java —, então n & (n - 1) == 0 funciona. Use parênteses mesmo assim: quem lê pode estar pensando em C.

  • XOR e todos os subconjuntos

    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)

    Saída

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

    x ^ x = 0 cancela cada par. As máscaras 0 … 2ⁿ−1 são os 2ⁿ subconjuntos.

  • Números negativos e visões de 32 bits

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

    Saída

    -6 -3
    0b11111111111111111111111111111011
    3 8

    -5 >> 1 é -3: o deslocamento à direita arredonda para baixo, como //.

AulasBinário e operações bit a bitMáscaras e potência de doisTruques com XORBitmask como conjunto

Armadilhas comuns

Os bugs que o entrevistador de Python está procurando. Cada um imprime algo surpreendente; a correção está nas linhas logo abaixo.

  • Argumentos padrão mutáveis

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

    Saída

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

    O padrão é avaliado uma vez, quando o def roda. Use None e crie a lista dentro da função.

  • Closures com late binding

    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])

    Saída

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

    Uma closure lê a variável quando é CHAMADA. Fixe o valor atual como argumento padrão.

  • 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

    Saída

    True False
    [1, 2, 3] True
    True

    is pergunta “é o mesmo objeto?”. Pode parecer certo com ints pequenos e strings curtas só porque o CPython os mantém em cache — nunca compare valores com ele.

  • Cópias rasas e [[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)

    Saída

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

    Monte grids com uma comprehension. a[:], list(a) e a.copy() copiam só a lista externa.

  • A ordem do dict é garantida; a do set, não

    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"}))

    Saída

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

    A ordem de inserção faz parte da linguagem a partir da 3.7. Atualizar uma chave existente mantém o lugar dela; remover e inserir outra vez a leva para o fim.

  • Alterar um dict enquanto você o percorre

    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)

    Saída

    RuntimeError
    {}

    Uma lista não lança erro — ela pula itens em silêncio. Percorra uma cópia ou crie uma coleção nova.

Os 10 templates de entrevista

Os esqueletos sobre os quais a maioria das respostas é construída, em Python idiomático — cada um com sua aula e um problema para praticar. A cheat sheet de padrões de entrevista tem os sinais que dizem qual deles o problema pede.

  • Dois ponteiros

    Um array ordenado e um par, uma partição ou um palíndromo decidido pelas duas pontas.

    Custo: O(n) de tempo, O(1) de espaço

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

    Saída

    (0, 4)
    Aula
    Dois ponteiros · Arrays
  • Janela deslizante

    A resposta é um trecho contíguo, e mover uma das pontas atualiza o estado de forma barata.

    Custo: O(n) de tempo, O(k) de espaço

    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"))

    Saída

    3
    Aula
    Janela deslizante · Arrays
  • BFS com deque

    Menos passos em um grafo ou grid sem pesos; nível por nível.

    Custo: O(V + E) de tempo, O(V) de espaço

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

    Saída

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

    list.pop(0) deixaria isto em O(V²). Marque um nó quando ele entra na fila, não quando sai.

    Aula
    Busca em largura · Grafos
  • DFS, recursiva e iterativa

    Alcançar tudo o que está conectado: flood fill, ilhas, verificação de ciclos, caminhos.

    Custo: O(V + E) de tempo, O(V) de espaço

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

    Saída

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

    Empilhar os vizinhos em ordem inversa faz a pilha visitá-los na mesma ordem da versão recursiva.

    Aula
    Busca em profundidade · Grafos
  • Busca binária com bisect

    Uma lista ordenada: posição de inserção, primeira/última ocorrência, contagem em um intervalo.

    Custo: O(log n) por busca

    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)

    Saída

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

    bisect_left: primeiro índice com a[i] ≥ x; bisect_right: primeiro com a[i] > x. O argumento key= exige a 3.10.

    Aula
    Busca binária · Busca
  • Somas de prefixos

    Muitas somas de intervalo sobre um array, ou subarrays que somam k.

    Custo: O(n) para montar, O(1) por consulta

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

    Saída

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

    O 0 inicial é o que faz pre[j] - pre[i] ser a soma de a[i:j] sem caso especial.

    Aula
    Somas de prefixos · Arrays
  • Pilha monotônica

    Próximo elemento maior / menor, spans, o maior retângulo.

    Custo: O(n) de tempo, O(n) de espaço

    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]))

    Saída

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

    Cada índice é empilhado uma vez e desempilhado no máximo uma vez: O(n) apesar do while interno.

    Aula
    Pilha monotônica · Pilhas e filas
  • Top-k com heap

    Os k maiores, menores, mais próximos ou mais frequentes de n itens.

    Custo: O(n log k) de tempo, O(k) de espaço

    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]))

    Saída

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

    Para manter os k MAIORES, remova de um MIN-heap: o topo dele é o mais fraco dos k mantidos.

    Aula
    Top-k elementos · Heaps
  • Union-find

    Componentes conexos que só se fundem; detecção de ciclo em um grafo não direcionado.

    Custo: ≈ O(1) por operação, O(n) de espaço

    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)}))

    Saída

    True True False
    3

    find é iterativo de propósito: um recursivo bate no limite de recursão em uma cadeia longa.

  • DP com memoizaçãoPython 3.9+

    Subproblemas sobrepostos: escreva a recorrência e depois coloque um cache nela.

    Custo: O(estados × escolhas) de tempo, O(estados) de espaço

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

    Saída

    3 2

    A profundidade é o próprio valor: passando de alguns milhares, converta para bottom-up (veja Limites de recursão).

    Aula
    Memoização · Recursão

bytepatterns.com/cheatsheets/python — lá, cada linha leva a uma aula animada.