Python DSA Interview Cheatsheet — Syntax, Data Structures & Tricks

1
nums = [1, 2, 3, 4, 5]
2

3
# --- Truy cập & cắt lát (slicing) ---
4
nums[0]            # 1     — phần tử đầu
5
nums[-1]           # 5     — phần tử cuối, không cần len()
6
nums[1:4]          # [2,3,4]   — từ index 1 đến trước 4
7
nums[:3]           # [1,2,3]   — 3 phần tử đầu
8
nums[2:]           # [3,4,5]   — từ index 2 đến hết
9
nums[::-1]         # [5,4,3,2,1] — đảo ngược (tạo bản copy)
10
nums[::2]          # [1,3,5]   — lấy cách 1 phần tử (step=2)
11
nums[:]            # bản copy nông (shallow copy)
12

13
# --- Thêm / xóa ---
14
nums.append(6)     # thêm cuối — O(1)
15
nums.pop()         # lấy & xóa cuối — O(1)
16
nums.pop(0)        # lấy & xóa đầu — O(n), nên tránh
17
nums.insert(0, 0)  # chèn vào đầu — O(n)
18
nums.extend([7,8]) # nối nhiều phần tử
19
nums += [9]        # tương đương extend
20
del nums[1]        # xóa theo index
21
nums.remove(3)     # xóa theo GIÁ TRỊ (lần đầu gặp)
22

23
# --- Tra cứu ---
24
3 in nums          # True/False — O(n) với list
25
nums.index(3)      # vị trí đầu tiên của 3
26
nums.count(3)      # số lần xuất hiện

1
nums.sort()              # sắp xếp tại chỗ, O(n log n)
2
nums.sort(reverse=True)  # giảm dần
3
nums.reverse()           # đảo ngược tại chỗ
4
nums[::-1] = nums        # cũng đảo ngược (gán slice)

1
# enumerate — vừa lấy index vừa lấy giá trị
2
for i, val in enumerate(nums):
3
    print(i, val)
4
for i, val in enumerate(nums, start=1):   # đánh số từ 1
5
    print(i, val)
6

7
# zip — duyệt nhiều list song song
8
for a, b in zip(list1, list2):
9
    ...
10
for (r, c), name in zip(coords, names):   # kết hợp unpacking
11
    ...
12

13
# zip(*matrix) — "xoay" hàng thành cột (transpose)
14
rows = [[1, 2, 3], [4, 5, 6]]
15
cols = list(zip(*rows))    # [(1,4), (2,5), (3,6)]
16

17
# Unpacking
18
first, *middle, last = [1, 2, 3, 4, 5]  # first=1, middle=[2,3,4], last=5
19
a, b = b, a                              # hoán đổi không cần biến tạm
20
return lo, hi                            # trả nhiều giá trị (là tuple)

1
s = "Hello World"
2

3
# Slicing & truy cập — giống hệt list
4
s[0]              # 'H'
5
s[-1]             # 'd'
6
s[::-1]           # đảo ngược chuỗi
7

8
# Tách & ghép
9
"a,b,c".split(",")       # ['a', 'b', 'c']
10
"a b  c".split()         # ['a', 'b', 'c'] — tách theo mọi khoảng trắng
11
"".join(['a', 'b', 'c']) # 'abc' — cách nối chuỗi ĐÚNG
12
"-".join(['1', '2'])     # '1-2'
13

14
# Kiểm tra & tìm kiếm
15
s.startswith("He"), s.endswith("ld")
16
s.find("o")        # 4  — index đầu tiên, -1 nếu không có
17
s.count("o")       # 2
18
"abc".isalpha(), "123".isdigit(), "a1".isalnum()
19

20
# Biến đổi (trả chuỗi MỚI)
21
s.lower(), s.upper()
22
"  hi  ".strip()   # 'hi' — bỏ khoảng trắng hai đầu
23
s.replace("o", "0")
24

25
# Ký tự ↔ mã số (cực hữu ích cho bài về bảng chữ cái)
26
ord('a')           # 97
27
chr(97)            # 'a'
28
ord('c') - ord('a')   # 2 — index trong bảng 26 chữ

1
d = {"a": 1, "b": 2}
2

3
# Truy cập AN TOÀN — không gây lỗi nếu thiếu key
4
d.get("c")          # None — không lỗi
5
d.get("c", 0)       # 0    — trả giá trị mặc định
6
d.setdefault("c", []).append(1)  # nếu chưa có thì tạo rồi thao tác
7

8
# Pattern đếm tần suất (rất hay dùng)
9
freq = {}
10
for x in nums:
11
    freq[x] = freq.get(x, 0) + 1
12

13
# Duyệt
14
for key in d:                 # duyệt key
15
    ...
16
for key, val in d.items():    # duyệt cả cặp
17
    ...
18
d.keys(), d.values(), d.items()
19

20
# Thao tác khác
21
d.pop("a", None)    # xóa & trả về, không lỗi nếu thiếu
22
"a" in d            # check key tồn tại — O(1)
23
{**d1, **d2}        # gộp hai dict (d2 ghi đè trùng key)

1
from collections import defaultdict, Counter
2

3
# defaultdict — bỏ qua bước kiểm tra key
4
graph = defaultdict(list)     # mặc định []
5
graph[u].append(v)
6

7
groups = defaultdict(list)
8
for word in words:
9
    groups[tuple(sorted(word))].append(word)   # gom nhóm anagram
10

11
seen = defaultdict(int)       # mặc định 0
12
seen[x] += 1
13

14
# Counter — đếm trong 1 dòng
15
cnt = Counter("aabbbc")       # Counter({'b':3, 'a':2, 'c':1})
16
cnt = Counter(nums)
17
cnt.most_common(2)            # [('b', 3), ('a', 2)] — top 2
18
cnt['a']                      # 2, trả 0 nếu thiếu (không lỗi)
19
cnt['z'] += 1                 # tự khởi tạo
20
list(cnt.elements())          # bung ngược lại thành các phần tử
21

22
# Counter còn cộng/trừ được như multiset
23
Counter("aab") - Counter("a") # Counter({'a':1, 'b':1})

1
seen = set()
2
seen.add(x)
3
seen.discard(x)        # xóa, không lỗi nếu thiếu
4
x in seen              # O(1) trung bình — lý do chính để dùng set
5

6
# Phép toán tập hợp
7
a | b                  # hợp (union)
8
a & b                  # giao (intersection)
9
a - b                  # hiệu (difference)
10
a ^ b                  # khác nhau (symmetric difference)
11

12
# Lưu tọa độ đã thăm trong ma trận/đồ thị
13
visited = set()
14
visited.add((r, c))    # tuple hashable nên dùng làm phần tử set được

1
point = (x, y)                  # cặp tọa độ
2
visited.add((r, c))             # tuple làm phần tử set
3
dp[(i, mask)] = value           # tuple làm key DP state
4

5
# Sắp xếp theo nhiều tiêu chí: tuple so sánh theo thứ tự từ trái
6
pairs.sort(key=lambda p: (p[1], -p[0]))  # tăng theo p[1], rồi giảm theo p[0]

1
squares = [x * x for x in range(10)]
2
evens   = [x for x in nums if x % 2 == 0]
3
flat    = [x for row in matrix for x in row]     # làm phẳng ma trận
4

5
# Dict & set comprehension
6
idx = {v: i for i, v in enumerate(nums)}         # value -> index
7
uniq = {x % k for x in nums}
8

9
# Generator — không tạo list trung gian
10
total = sum(x * x for x in nums)
11
ok    = any(x < 0 for x in nums)                 # dừng ngay khi gặp True
12
allp  = all(x > 0 for x in nums)

1
7 // 2             # 3   — chia lấy phần nguyên (làm tròn xuống)
2
7 % 3              # 1   — số dư
3
divmod(7, 3)       # (2, 1) — thương và dư cùng lúc
4
2 ** 10            # 1024 — lũy thừa
5
abs(-5), min(a, b), max(a, b)
6

7
# Số nguyên Python KHÔNG bị tràn (overflow) — thoải mái với số lớn
8

9
# --- Thao tác bit (cho bitmask DP, subset) ---
10
a & b              # AND
11
a | b              # OR
12
a ^ b              # XOR — dùng tìm số xuất hiện lẻ lần
13
~a                 # NOT
14
a << 1             # dịch trái (= nhân 2)
15
a >> 1             # dịch phải (= chia 2)
16

17
x & 1              # kiểm tra bit cuối (1 = lẻ)
18
x & (x - 1)        # xóa bit 1 thấp nhất
19
bin(13)            # '0b1101'
20
bin(13).count('1') # 3 — đếm số bit 1
21
int('1101', 2)     # 13 — đổi chuỗi nhị phân sang số

1
# So sánh chuỗi (chaining) — Pythonic, dễ đọc
2
if 0 <= i < n:           # thay vì i >= 0 and i < n
3
    ...
4

5
# Biểu thức điều kiện (ternary)
6
val = a if cond else b
7

8
# Toán tử walrus := — gán và dùng luôn trong điều kiện
9
while (line := read_next()):
10
    process(line)
11
if (size := len(nums)) > 10:
12
    print(size)
13

14
# min/max với key
15
longest = max(words, key=len)
16
closest = min(points, key=lambda p: p[0]**2 + p[1]**2)

1
sorted(nums)                       # tăng dần, trả list mới
2
sorted(nums, reverse=True)         # giảm dần
3
nums.sort(key=lambda x: -x)        # tại chỗ, theo key
4

5
# Sắp xếp theo nhiều tiêu chí bằng tuple key
6
people.sort(key=lambda p: (p.age, p.name))      # tuổi tăng, rồi tên
7
nums.sort(key=lambda x: (-freq[x], x))          # freq giảm, giá trị tăng
8

9
# Sắp theo index thay vì theo giá trị
10
order = sorted(range(len(nums)), key=lambda i: nums[i])
11

12
# Comparator tùy chỉnh (kiểu cũ, khi tiêu chí không gói thành key được)
13
from functools import cmp_to_key
14
def cmp(a, b):
15
    return (a + b < b + a) - (a + b > b + a)   # trả -1/0/1
16
arr.sort(key=cmp_to_key(cmp))

1
import heapq
2

3
heap = []
4
heapq.heappush(heap, 3)
5
heapq.heappush(heap, 1)
6
smallest = heap[0]            # xem phần tử nhỏ nhất — O(1)
7
val = heapq.heappop(heap)     # lấy & xóa nhỏ nhất — O(log n)
8

9
heapq.heapify(nums)           # biến list thành heap tại chỗ — O(n)
10

11
# Max-heap: đảo dấu
12
heapq.heappush(heap, -x)
13
largest = -heapq.heappop(heap)
14

15
# Heap chứa tuple — so sánh theo phần tử đầu, rồi phần tử sau
16
heapq.heappush(heap, (dist, node))
17

18
# Top-k tiện lợi
19
heapq.nlargest(k, nums)
20
heapq.nsmallest(k, nums)
21
heapq.heappushpop(heap, x)    # push rồi pop trong 1 thao tác (giữ size k)

1
import bisect
2

3
a = [1, 3, 3, 5, 7]
4
bisect.bisect_left(a, 3)    # 1 — vị trí số 3 đầu tiên
5
bisect.bisect_right(a, 3)   # 3 — ngay sau số 3 cuối cùng
6
bisect.insort(a, 4)         # chèn 4 vào đúng chỗ, giữ sorted
7

8
# Kiểm tra phần tử có tồn tại không
9
i = bisect.bisect_left(a, x)
10
exists = i < len(a) and a[i] == x

1
from collections import deque
2

3
dq = deque([1, 2, 3])
4
dq.append(4)         # thêm cuối
5
dq.appendleft(0)     # thêm đầu — O(1) (list không làm được rẻ thế này)
6
dq.pop()             # xóa cuối
7
dq.popleft()         # xóa đầu — O(1)
8
dq = deque(maxlen=k) # tự động bỏ phần tử cũ khi vượt size k

1
import math
2
from itertools import combinations, permutations, product, accumulate
3

4
math.inf, -math.inf    # khởi tạo min/max trong DP, Dijkstra
5
math.gcd(12, 8)        # 4
6
math.lcm(4, 6)         # 12  (Python 3.9+)
7
math.comb(5, 2)        # 10 — C(n,k)
8
math.isqrt(17)         # 4  — căn bậc hai nguyên, không sai số float
9

10
# itertools — sinh tổ hợp cho brute force nhỏ / backtracking
11
list(combinations([1,2,3], 2))    # [(1,2),(1,3),(2,3)]
12
list(permutations([1,2,3], 2))    # các hoán vị độ dài 2
13
list(product([0,1], repeat=3))    # mọi chuỗi nhị phân dài 3
14
list(accumulate([1,2,3,4]))       # [1,3,6,10] — prefix sum sẵn

1
# Stack — LIFO
2
stack = []
3
stack.append(x)
4
top = stack.pop()
5
peek = stack[-1] if stack else None
6

7
# Queue — FIFO
8
from collections import deque
9
q = deque()
10
q.append(x)          # vào cuối
11
front = q.popleft()  # ra đầu — O(1)

1
class ListNode:
2
    def __init__(self, val=0, next=None):
3
        self.val = val
4
        self.next = next
5

6
def reverse(head):                  # đảo danh sách
7
    prev = None
8
    while head:
9
        head.next, prev, head = prev, head, head.next
10
    return prev
11

12
slow = fast = head                  # fast/slow: tìm giữa & bắt chu trình
13
while fast and fast.next:
14
    slow = slow.next
15
    fast = fast.next.next

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

5
def dfs(node):                      # DFS đệ quy (đây là preorder)
6
    if not node:
7
        return
8
    # xử lý node
9
    dfs(node.left)
10
    dfs(node.right)
11

12
from collections import deque
13
def level_order(root):              # BFS theo từng tầng
14
    if not root:
15
        return []
16
    res, q = [], deque([root])
17
    while q:
18
        level = []
19
        for _ in range(len(q)):     # cố định số node của tầng hiện tại
20
            node = q.popleft()
21
            level.append(node.val)
22
            if node.left:  q.append(node.left)
23
            if node.right: q.append(node.right)
24
        res.append(level)
25
    return res

1
from collections import defaultdict, deque
2

3
graph = defaultdict(list)
4
for u, v in edges:
5
    graph[u].append(v)
6
    graph[v].append(u)             # bỏ dòng này nếu đồ thị có hướng
7

8
def bfs(start):                     # đường đi ngắn nhất (không trọng số)
9
    visited = {start}
10
    q = deque([start])
11
    while q:
12
        u = q.popleft()
13
        for v in graph[u]:
14
            if v not in visited:
15
                visited.add(v)
16
                q.append(v)
17

18
def dfs(u, visited):                # duyệt sâu
19
    visited.add(u)
20
    for v in graph[u]:
21
        if v not in visited:
22
            dfs(v, visited)

1
class UnionFind:
2
    def __init__(self, n):
3
        self.parent = list(range(n))
4
        self.count = n              # số thành phần liên thông
5

6
    def find(self, x):
7
        while self.parent[x] != x:
8
            self.parent[x] = self.parent[self.parent[x]]  # nén đường (path compression)
9
            x = self.parent[x]
10
        return x
11

12
    def union(self, x, y):
13
        rx, ry = self.find(x), self.find(y)
14
        if rx == ry:
15
            return False            # đã cùng nhóm → có chu trình
16
        self.parent[rx] = ry
17
        self.count -= 1
18
        return True

1
class Trie:
2
    def __init__(self):
3
        self.root = {}
4

5
    def insert(self, word):
6
        node = self.root
7
        for ch in word:
8
            node = node.setdefault(ch, {})   # tạo nhánh nếu chưa có
9
        node['#'] = True                     # đánh dấu hết từ
10

11
    def search(self, word, prefix_only=False):
12
        node = self.root
13
        for ch in word:
14
            if ch not in node:
15
                return False
16
            node = node[ch]
17
        return prefix_only or '#' in node

1
# Next Greater Element — stack giảm dần, lưu index
2
res = [-1] * len(nums)
3
stack = []
4
for i, x in enumerate(nums):
5
    while stack and nums[stack[-1]] < x:
6
        res[stack.pop()] = x
7
    stack.append(i)
8

9
# Sliding Window Maximum — deque chứa index, giá trị giảm dần
10
from collections import deque
11
def max_window(nums, k):
12
    dq, res = deque(), []
13
    for i, x in enumerate(nums):
14
        while dq and nums[dq[-1]] <= x:
15
            dq.pop()
16
        dq.append(i)
17
        if dq[0] <= i - k:          # phần tử rời khỏi cửa sổ
18
            dq.popleft()
19
        if i >= k - 1:
20
            res.append(nums[dq[0]])
21
    return res

1
# Hai đầu dồn vào giữa — tìm cặp có tổng = target (mảng đã sắp)
2
lo, hi = 0, len(nums) - 1
3
while lo < hi:
4
    s = nums[lo] + nums[hi]
5
    if s == target:   return [lo, hi]
6
    elif s < target:  lo += 1
7
    else:             hi -= 1
8

9
# Cùng chiều — ghi đè tại chỗ (giữ phần tử thỏa điều kiện)
10
write = 0
11
for read in range(len(nums)):
12
    if keep(nums[read]):
13
        nums[write] = nums[read]
14
        write += 1

1
# Cửa sổ co giãn — chuỗi con dài nhất không lặp ký tự
2
seen, left, best = {}, 0, 0
3
for right, ch in enumerate(s):
4
    if ch in seen and seen[ch] >= left:
5
        left = seen[ch] + 1
6
    seen[ch] = right
7
    best = max(best, right - left + 1)

1
prefix = [0]
2
for x in nums:
3
    prefix.append(prefix[-1] + x)
4
# tổng nums[i..j] = prefix[j+1] - prefix[i]

1
# 1) Tìm chính xác target
2
lo, hi = 0, len(nums) - 1
3
while lo <= hi:
4
    mid = (lo + hi) // 2
5
    if nums[mid] == target: return mid
6
    elif nums[mid] < target: lo = mid + 1
7
    else: hi = mid - 1
8

9
# 2) Lower bound — index đầu tiên có nums[i] >= target
10
lo, hi = 0, len(nums)
11
while lo < hi:
12
    mid = (lo + hi) // 2
13
    if nums[mid] < target: lo = mid + 1
14
    else: hi = mid
15

16
# 3) Binary search trên ĐÁP ÁN — "nhỏ nhất thỏa điều kiện"
17
lo, hi = min_ans, max_ans
18
while lo < hi:
19
    mid = (lo + hi) // 2
20
    if feasible(mid): hi = mid
21
    else: lo = mid + 1
22
return lo

1
def backtrack(start, path):
2
    res.append(path[:])             # LƯU Ý: copy path, đừng lưu tham chiếu
3
    for i in range(start, len(nums)):
4
        path.append(nums[i])
5
        backtrack(i + 1, path)      # i+1: tổ hợp; i: cho lặp lại
6
        path.pop()                  # hoàn tác (undo)

1
from functools import lru_cache
2

3
@lru_cache(maxsize=None)
4
def dp(i, remaining):
5
    if remaining == 0: return 1
6
    if i == n or remaining < 0: return 0
7
    return dp(i + 1, remaining - coins[i]) + dp(i + 1, remaining)