1.1 Mục tiêu khoá học

Sau 14 tuần, sinh viên sẽ có khả năng:

• Giải 80% bài Easy và 50% bài Medium trên LeetCode trong vòng 30 phút.
• Vượt qua bài kiểm tra Codility 60–70 điểm trong các đợt phỏng vấn entry/mid-level.
• Phân tích độ phức tạp thời gian và bộ nhớ của một thuật toán bất kỳ.
• Nhận diện 15–20 pattern thuật toán phổ biến và áp dụng vào bài mới.
• Trình bày lời giải mạch lạc trong môi trường mock interview 45–60 phút.

1.2 Triết lý: Pattern trước Problem

Đa số người mới mắc lỗi là cày bài lẻ tẻ — giải xong bài này, gặp bài tương tự vẫn không nhận ra. Khoá học áp dụng ba nguyên tắc khoa học học tập:

1. Pattern trước Problem. Mỗi tuần học 1–2 pattern, mỗi pattern luyện 4–6 bài đại diện. Bài thứ 7 trở đi nên là bài mới hoàn toàn để kiểm tra khả năng nhận pattern.
2. Phân tích trước khi code. Bắt buộc viết complexity dự kiến và pseudo-code trước khi gõ dòng đầu tiên. Đây là kỹ năng phỏng vấn thực sự được chấm điểm.
3. Spaced retrieval. Mỗi bài làm xong phải code lại từ đầu sau 1 tuần và sau 3 tuần. Đây là cách duy nhất để pattern chìm vào trí nhớ dài hạn.

1.3 Thiết lập môi trường thực hành

Tài khoản online (bắt buộc)

• LeetCode (leetcode.com) — kho bài chính, có giải tự động.
• Codility (app.codility.com/programmers/lessons) — bài học miễn phí từ Lesson 1–17.
• NeetCode 150 (neetcode.io) — danh sách bài đã sắp xếp theo pattern, có video.

Môi trường code cục bộ

• Python 3.10 trở lên.
• VS Code với extension Python và LeetCode.
• Tạo repo Git riêng với cấu trúc week01/two-sum.py để theo dõi tiến độ.

2.1 Vì sao chọn Python?

Khoá học mặc định dùng Python. Bốn lý do:

1. Ít boilerplate. Một bài có thể giải trong 15–25 dòng thay vì 40–60 dòng Java/C++. Tiết kiệm thời gian phỏng vấn.
2. Cấu trúc dữ liệu mạnh sẵn có. dict, set, list, tuple đều hiệu năng tốt và cú pháp gọn.
3. Hỗ trợ tốt trên LeetCode/Codility. Hầu hết bài đều chấp nhận Python với time limit hào phóng hơn (thường ×3 so với C++).
4. Phổ biến trong ngành. ML, data, backend đều dùng Python. Kỹ năng chuyển trực tiếp sang công việc.

2.2 Bốn cấu trúc dữ liệu nội tại

2.3 List — Operations và độ phức tạp

2.4 Dict & Set — Hashing trong thực tế

# Đếm tần suất ký tự — O(n)
freq = {}
for ch in s:
    freq[ch] = freq.get(ch, 0) + 1

# Cách viết Pythonic hơn
from collections import Counter
freq = Counter(s)

# Set: kiểm tra trùng — O(1)
seen = set()
for x in nums:
    if x in seen:        # O(1) trung bình
        return True
    seen.add(x)
return False

2.5 String — Bất biến (immutable) và slicing

String trong Python là immutable. Mỗi thao tác ghép tạo ra string mới:

# BẪY: O(n²) vì mỗi += copy toàn bộ string cũ
result = ""
for word in words:
    result += word

# ĐÚNG: O(n) tổng
result = "".join(words)

Slicing và đảo chuỗi

s = "leetcode"
s[0:4]      # "leet"
s[-3:]      # "ode"  (3 ký tự cuối)
s[::-1]     # "edocteel" (đảo ngược)
s[::2]      # "lecd" (mỗi 2 ký tự)

2.6 Idioms quan trọng

List comprehension

squares = [x*x for x in range(10)]
evens   = [x for x in nums if x % 2 == 0]
matrix  = [[0]*n for _ in range(m)]   # ma trận m×n

# BẪY: KHÔNG dùng [[0]*n] * m — tất cả hàng là cùng 1 reference

Unpacking và enumerate / zip

a, b = b, a                          # swap không cần biến tạm
for i, x in enumerate(nums):         # truy cập index + giá trị
    ...
for k, v in d.items():               # duyệt dict
    ...
for x, y in zip(arr1, arr2):         # ghép cặp 2 mảng
    ...

Multi-assignment trong logic

prev, curr = curr, prev + curr       # Fibonacci 1 dòng

2.7 Built-in functions thiết yếu

2.8 Module collections — ba bảo bối

defaultdict

from collections import defaultdict
graph = defaultdict(list)            # giá trị mặc định: list rỗng
graph[u].append(v)                   # không cần check key tồn tại

Counter

from collections import Counter
c = Counter("leetcode")              # {'e':3, 'l':1, 't':1, 'c':1, 'o':1, 'd':1}
c.most_common(2)                     # [('e', 3), ('l', 1)]

deque (double-ended queue)

from collections import deque
q = deque([1, 2, 3])
q.appendleft(0)                      # O(1)
q.popleft()                          # O(1) — ngược với list.pop(0) là O(n)

Knowledge Check — Phần 2

3.1 Vì sao quan tâm complexity?

Một bài LeetCode điển hình có time limit ~1 giây. Máy chạy được khoảng 10⁸ thao tác đơn giản/giây. Đối chiếu với input size:

3.2 Định nghĩa Big-O

Ý nghĩa thực tế

Big-O đo tốc độ tăng, không đo thời gian thực. Hai thuật toán cùng O(n) có thể khác nhau 10 lần về thời gian thực — nhưng cùng tăng tuyến tính theo n.

Quy tắc đơn giản hoá

• Bỏ hằng số: \(O(2n)\) = \(O(n)\); \(O(\frac{n}{2})\) = \(O(n)\).
• Bỏ bậc thấp: \(O(n^2 + n)\) = \(O(n^2)\).
• Hai vòng lặp tách rời: \(O(n) + O(m) = O(n + m)\).
• Hai vòng lặp lồng: \(O(n) \times O(m) = O(nm)\).

3.3 Các bậc complexity phổ biến

Khoảng cách giữa O(n) và O(n²) khi n = 10⁵ là 100,000 lần. Đó là khác biệt giữa "chạy 1 giây" và "chạy 1 ngày".

3.4 Đọc complexity từ code

Quy trình 3 bước:

1. Xác định vòng lặp ngoài cùng chạy bao nhiêu lần.
2. Xác định công việc bên trong mỗi lần lặp tốn bao nhiêu.
3. Nhân lại, đơn giản hoá theo quy tắc Big-O.

# Ví dụ
def has_pair(nums, target):
    for i in range(len(nums)):           # vòng ngoài: n lần
        for j in range(i+1, len(nums)):  # vòng trong: trung bình n/2 lần
            if nums[i] + nums[j] == target:
                return True
    return False
# Tổng: n × n/2 = n²/2  →  O(n²)

3.5 Worked Example: Linear scan

def max_value(nums):
    m = float('-inf')
    for x in nums:        # n lần
        if x > m:         # O(1)
            m = x         # O(1)
    return m

Phân tích:

• Vòng lặp chạy đúng n lần.
• Mỗi lần làm O(1) việc.
• Tổng: \(n \cdot O(1) = O(n)\).

Space: chỉ dùng biến m — O(1).

3.6 Worked Example: Vòng lặp lồng nhau

def count_inversions(nums):
    count = 0
    for i in range(len(nums)):           # n lần
        for j in range(i+1, len(nums)):  # (n-1) + (n-2) + ... + 0
            if nums[i] > nums[j]:
                count += 1
    return count

Phân tích:

Tổng số lần thao tác bên trong:

Bỏ hằng số ½ → O(n²). Space: O(1).

3.7 Worked Example: Đệ quy

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

Phân tích: Mỗi lần gọi fib(n) sinh ra 2 lời gọi nhỏ hơn. Cây gọi đệ quy có chiều cao ~n và phân nhánh 2 → tổng số nút ~\(2^n\).

Space: O(n) cho call stack tại bất kỳ thời điểm nào.

3.8 Space Complexity

Phỏng vấn ngày càng quan tâm bộ nhớ, không chỉ thời gian. Hai loại space cần đếm:

1. Auxiliary space (bộ nhớ phụ trợ)

Bộ nhớ thuật toán dùng thêm ngoài input. Đây là cái phỏng vấn thường hỏi.

2. Total space (tổng bộ nhớ)

Bao gồm cả input. Ít quan tâm hơn vì input là "miễn phí".

# Auxiliary O(n)
def double_array(nums):
    return [x*2 for x in nums]   # tạo list mới size n

# Auxiliary O(1)
def double_inplace(nums):
    for i in range(len(nums)):   # sửa trực tiếp
        nums[i] *= 2

3.9 Đọc constraints để đoán complexity yêu cầu

Đây là kỹ năng quan trọng nhất của tuần này. Mở một bài LeetCode bất kỳ, mục "Constraints" cho biết:

Constraints:
  1 <= nums.length <= 10^5
  -10^9 <= nums[i] <= 10^9

Khi thấy n ≤ 10⁵, lập tức biết:

• O(n²) sẽ TLE (Time Limit Exceeded): 10¹⁰ thao tác >> 10⁸/giây.
• Cần đạt O(n log n) hoặc O(n).

Khi thấy n ≤ 10⁹, biết:

• Không được đụng tới mảng size n. Có thể là binary search trên answer space, hoặc công thức toán.

Knowledge Check — Phần 3

4.1 Bài 1: Two Sum (LeetCode #1)

Đề: Cho mảng nums và số target. Tìm hai chỉ số i, j sao cho nums[i] + nums[j] == target. Giả sử có đúng một đáp án.

Constraints: 2 ≤ n ≤ 10⁴.

Approach 1 — Brute Force

def twoSum(nums, target):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

Time O(n²), space O(1). Với n = 10⁴ thì ~5×10⁷ thao tác — chạy được nhưng rất sát giới hạn.

4.2 Two Sum — Tối ưu với Hash Map

Quan sát: với mỗi nums[i], ta cần tìm complement = target - nums[i] trong phần còn lại. Tìm trong list là O(n), nhưng tìm trong set/dict là O(1).

def twoSum(nums, target):
    seen = {}                       # value → index
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:      # O(1)
            return [seen[complement], i]
        seen[x] = i
    return []

Time O(n), space O(n).

4.3 Bài 2: Valid Anagram (LeetCode #242)

Đề: Cho hai string s và t. Trả về True nếu t là một anagram (đảo chữ) của s.

Approach 1 — Sort

def isAnagram(s, t):
    return sorted(s) == sorted(t)
# Time: O(n log n), Space: O(n)

Approach 2 — Counter (tốt hơn)

from collections import Counter
def isAnagram(s, t):
    return Counter(s) == Counter(t)
# Time: O(n), Space: O(k)  với k = số ký tự khác nhau

Approach 3 — Mảng đếm thủ công (chỉ với chữ thường a-z)

def isAnagram(s, t):
    if len(s) != len(t): return False
    cnt = [0] * 26
    for ch in s: cnt[ord(ch) - ord('a')] += 1
    for ch in t: cnt[ord(ch) - ord('a')] -= 1
    return all(c == 0 for c in cnt)
# Time: O(n), Space: O(1)  vì 26 là hằng số

4.4 Bài 3: Best Time to Buy and Sell Stock (LeetCode #121)

Đề: Mảng prices[i] = giá cổ phiếu ngày i. Mua 1 ngày, bán 1 ngày sau đó. Tính lợi nhuận tối đa (≥ 0).

Constraints: 1 ≤ n ≤ 10⁵ → cần O(n).

Brute force — TLE

# O(n²) — sẽ vượt time limit
for i in range(n):
    for j in range(i+1, n):
        profit = max(profit, prices[j] - prices[i])

Tối ưu — One pass O(n)

def maxProfit(prices):
    min_so_far = float('inf')
    best = 0
    for p in prices:
        min_so_far = min(min_so_far, p)
        best = max(best, p - min_so_far)
    return best

Tổng kết Tuần 1

Đã học

• Bốn cấu trúc dữ liệu Python nội tại và độ phức tạp của các thao tác.
• Module collections: defaultdict, Counter, deque.
• Định nghĩa Big-O và quy tắc đơn giản hoá.
• Cách đọc complexity từ code (vòng lặp, đệ quy).
• Đọc constraints để đoán bậc complexity yêu cầu.
• Pattern đầu tiên: "Đổi space lấy time" qua hashing.

Bài về nhà (8 bài)

1. LeetCode #1 — Two Sum (đã chữa, code lại không nhìn lời giải)
2. LeetCode #242 — Valid Anagram (cả 3 approach)
3. LeetCode #121 — Best Time to Buy and Sell Stock
4. LeetCode #217 — Contains Duplicate
5. LeetCode #136 — Single Number
6. LeetCode #169 — Majority Element
7. LeetCode #283 — Move Zeroes
8. LeetCode #14 — Longest Common Prefix

Mỗi bài: nộp solution.py + tests.py (3 test tự nghĩ) + analysis.md (complexity và lý do chọn approach).