Bài tập lập trình tổng hợp - Nâng cao
Trang này tổng hợp 100 bài tập lập trình Python nâng cao, dành cho bạn nào đã làm quen với các kiến thức cơ bản ở trang Bài tập lập trình tổng hợp - Cơ bản. Nội dung xoay quanh thuật toán sắp xếp/tìm kiếm, đệ quy & backtracking, quy hoạch động, cấu trúc dữ liệu, lập trình hướng đối tượng, lập trình hàm và các thư viện chuẩn hữu ích của Python.
Mỗi bài đều có phần đáp án gợi ý ở dưới, mặc định ẩn đi — bạn nên tự làm trước, sau đó bấm vào “Xem đáp án” để đối chiếu. Đáp án chỉ là một cách giải, không phải cách duy nhất và không phải lúc nào cũng tối ưu nhất.
Nhóm 1: Thuật toán sắp xếp nâng cao
Phần tiêu đề “Nhóm 1: Thuật toán sắp xếp nâng cao”1. Selection Sort
Cài đặt thuật toán sắp xếp chọn (selection sort) để sắp xếp tăng dần một list số.
Ví dụ:
Input: [64, 25, 12, 22, 11]Output: [11, 12, 22, 25, 64]Xem đáp án
def selection_sort(arr): n = len(arr) for i in range(n): # Tìm vị trí phần tử nhỏ nhất trong phần chưa sắp xếp min_idx = i for j in range(i + 1, n): if arr[j] < arr[min_idx]: min_idx = j arr[i], arr[min_idx] = arr[min_idx], arr[i] return arr
print(selection_sort([64, 25, 12, 22, 11]))2. Insertion Sort
Cài đặt thuật toán sắp xếp chèn (insertion sort) để sắp xếp tăng dần một list số.
Ví dụ:
Input: [12, 11, 13, 5, 6]Output: [5, 6, 11, 12, 13]Xem đáp án
def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 while j >= 0 and arr[j] > key: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key return arr
print(insertion_sort([12, 11, 13, 5, 6]))3. Merge Sort
Cài đặt thuật toán sắp xếp trộn (merge sort) theo kiểu chia để trị (divide and conquer).
Ví dụ:
Input: [38, 27, 43, 3, 9, 82, 10]Output: [3, 9, 10, 27, 38, 43, 82]Xem đáp án
def merge_sort(arr): if len(arr) <= 1: return arr
mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right): result = [] i = j = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result.extend(left[i:]) result.extend(right[j:]) return result
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))4. Quick Sort
Cài đặt thuật toán sắp xếp nhanh (quick sort) dùng phần tử cuối làm chốt (pivot).
Ví dụ:
Input: [10, 7, 8, 9, 1, 5]Output: [1, 5, 7, 8, 9, 10]Xem đáp án
def quick_sort(arr): if len(arr) <= 1: return arr
pivot = arr[-1] smaller = [x for x in arr[:-1] if x <= pivot] greater = [x for x in arr[:-1] if x > pivot]
return quick_sort(smaller) + [pivot] + quick_sort(greater)
print(quick_sort([10, 7, 8, 9, 1, 5]))5. Counting Sort
Cài đặt thuật toán sắp xếp đếm (counting sort), áp dụng cho list số nguyên không âm.
Ví dụ:
Input: [4, 2, 2, 8, 3, 3, 1]Output: [1, 2, 2, 3, 3, 4, 8]Xem đáp án
def counting_sort(arr): if not arr: return arr
max_val = max(arr) count = [0] * (max_val + 1)
for num in arr: count[num] += 1
result = [] for value, times in enumerate(count): result.extend([value] * times)
return result
print(counting_sort([4, 2, 2, 8, 3, 3, 1]))6. Sắp xếp theo nhiều tiêu chí
Cho một list các dictionary học sinh {"ten": ..., "diem": ..., "tuoi": ...}. Sắp xếp giảm dần theo điểm, nếu điểm bằng nhau thì sắp tăng dần theo tuổi.
Xem đáp án
students = [ {"name": "An", "score": 8, "age": 16}, {"name": "Binh", "score": 9, "age": 17}, {"name": "Chi", "score": 8, "age": 15},]
result = sorted(students, key=lambda student: (-student["score"], student["age"]))for student in result: print(student)Nhóm 2: Tìm kiếm nâng cao
Phần tiêu đề “Nhóm 2: Tìm kiếm nâng cao”7. Tìm kiếm nhị phân (Binary Search)
Cài đặt tìm kiếm nhị phân trên một list đã sắp xếp tăng dần, trả về index hoặc -1 nếu không tìm thấy.
Ví dụ:
Input: arr=[1, 3, 5, 7, 9, 11], target=7Output: 3Xem đáp án
def binary_search(arr, target): left, right = 0, len(arr) - 1
while left <= right: mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1
return -1
print(binary_search([1, 3, 5, 7, 9, 11], 7)) # 3print(binary_search([1, 3, 5, 7, 9, 11], 4)) # -18. Tìm kiếm nhị phân đệ quy
Viết lại bài toán tìm kiếm nhị phân bằng đệ quy thay vì vòng lặp.
Xem đáp án
def binary_search_recursive(arr, target, left=0, right=None): if right is None: right = len(arr) - 1
if left > right: return -1
mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: return binary_search_recursive(arr, target, mid + 1, right) else: return binary_search_recursive(arr, target, left, mid - 1)
print(binary_search_recursive([1, 3, 5, 7, 9, 11], 9)) # 49. Tìm kiếm trong list đã xoay (Rotated Sorted Array)
Cho một list đã sắp xếp tăng dần rồi bị xoay tại một điểm bất kỳ (ví dụ [4,5,6,7,0,1,2]). Tìm vị trí của target với độ phức tạp O(log n).
Ví dụ:
Input: arr=[4, 5, 6, 7, 0, 1, 2], target=0Output: 4Xem đáp án
def search_rotated(arr, target): left, right = 0, len(arr) - 1
while left <= right: mid = (left + right) // 2 if arr[mid] == target: return mid
# Nửa bên trái đang có thứ tự tăng dần if arr[left] <= arr[mid]: if arr[left] <= target < arr[mid]: right = mid - 1 else: left = mid + 1 else: # Nửa bên phải đang có thứ tự tăng dần if arr[mid] < target <= arr[right]: left = mid + 1 else: right = mid - 1
return -1
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0)) # 410. Tìm phần tử xuất hiện lẻ số lần (dùng XOR)
Cho một list mà mọi phần tử đều xuất hiện đúng 2 lần, trừ một phần tử xuất hiện đúng 1 lần. Tìm phần tử đó, dùng phép toán XOR (^), không dùng thêm bộ nhớ phụ.
Ví dụ:
Input: [4, 1, 2, 1, 2]Output: 4Xem đáp án
def find_single_number(arr): result = 0 for num in arr: # a ^ a = 0 và a ^ 0 = a, nên các cặp trùng nhau sẽ tự triệt tiêu result ^= num return result
print(find_single_number([4, 1, 2, 1, 2])) # 4Nhóm 3: Đệ quy & Backtracking
Phần tiêu đề “Nhóm 3: Đệ quy & Backtracking”11. Tháp Hà Nội (Tower of Hanoi)
Viết hàm đệ quy in ra các bước di chuyển để giải bài toán Tháp Hà Nội với n đĩa.
Ví dụ:
Input: n=2, source=A, destination=C, auxiliary=BOutput:Di chuyển đĩa 1 từ A sang BDi chuyển đĩa 2 từ A sang CDi chuyển đĩa 1 từ B sang CXem đáp án
def hanoi(n, source, destination, auxiliary): if n == 1: print(f"Di chuyển đĩa 1 từ {source} sang {destination}") return
hanoi(n - 1, source, auxiliary, destination) print(f"Di chuyển đĩa {n} từ {source} sang {destination}") hanoi(n - 1, auxiliary, destination, source)
hanoi(3, "A", "C", "B")12. Tổ hợp chập k (Combinations)
Viết hàm đệ quy combinations(arr, k) sinh ra tất cả tổ hợp chập k phần tử từ list arr (không dùng itertools).
Ví dụ:
Input: arr=[1, 2, 3, 4], k=2Output: [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]Xem đáp án
def combinations(arr, k, start=0, current=None): if current is None: current = []
if len(current) == k: print(current) return
for i in range(start, len(arr)): current.append(arr[i]) combinations(arr, k, i + 1, current) current.pop() # Quay lui (backtrack)
combinations([1, 2, 3, 4], 2)13. Hoán vị của list (Permutations)
Viết hàm đệ quy permutations(arr) sinh ra tất cả hoán vị của list arr (không dùng itertools).
Ví dụ:
Input: [1, 2, 3]Output: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]Xem đáp án
def permutations(arr, current=None): if current is None: current = []
if not arr: print(current) return
for i in range(len(arr)): remaining = arr[:i] + arr[i + 1:] permutations(remaining, current + [arr[i]])
permutations([1, 2, 3])14. Tập con (Subsets / Power Set)
Viết hàm đệ quy sinh ra tất cả tập con (kể cả tập rỗng) của một list.
Ví dụ:
Input: [1, 2, 3]Output: [], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]Xem đáp án
def subsets(arr, index=0, current=None): if current is None: current = []
if index == len(arr): print(current) return
# Không chọn phần tử arr[index] subsets(arr, index + 1, current) # Chọn phần tử arr[index] subsets(arr, index + 1, current + [arr[index]])
subsets([1, 2, 3])15. Bài toán N-Queens
Đếm số cách đặt n quân hậu trên bàn cờ n x n sao cho không có 2 quân nào ăn nhau, dùng backtracking.
Ví dụ:
Input: n=4Output: 2Xem đáp án
def solve_n_queens(n): def is_safe(queen_positions, row, col): for h in range(row): c = queen_positions[h] # Kiểm tra cùng cột hoặc cùng đường chéo if c == col or abs(c - col) == abs(h - row): return False return True
def backtrack(row, queen_positions): if row == n: return 1
ways = 0 for col in range(n): if is_safe(queen_positions, row, col): queen_positions.append(col) ways += backtrack(row + 1, queen_positions) queen_positions.pop() # Quay lui
return ways
return backtrack(0, [])
print(solve_n_queens(4)) # 2print(solve_n_queens(8)) # 9216. Đường đi trong lưới (Grid Paths)
Đếm số đường đi từ góc trên-trái đến góc dưới-phải của một lưới m x n, chỉ được di chuyển sang phải hoặc xuống dưới.
Ví dụ:
Input: m=3, n=3Output: 6Xem đáp án
def count_paths(m, n): if m == 1 or n == 1: return 1 return count_paths(m - 1, n) + count_paths(m, n - 1)
print(count_paths(3, 3)) # 617. Subset Sum
Cho một list số nguyên dương và một tổng đích target. Kiểm tra xem có tồn tại một tập con nào của list có tổng bằng target hay không, dùng đệ quy.
Ví dụ:
Input: arr=[3, 34, 4, 12, 5, 2], target=9Output: TrueXem đáp án
def subset_sum(arr, target, index=0): if target == 0: return True if index == len(arr) or target < 0: return False
# Không chọn arr[index] HOẶC có chọn arr[index] return subset_sum(arr, target, index + 1) or subset_sum(arr, target - arr[index], index + 1)
print(subset_sum([3, 34, 4, 12, 5, 2], 9)) # Trueprint(subset_sum([3, 34, 4, 12, 5, 2], 100)) # False18. Số Catalan bằng đệ quy
Số Catalan thứ n được tính bằng công thức đệ quy: C(0) = 1, C(n) = sum(C(i) * C(n-1-i)) với i từ 0 đến n-1. Viết hàm đệ quy tính số Catalan thứ n.
Ví dụ:
Input: n=4Output: 14Xem đáp án
def catalan(n): if n <= 1: return 1
result = 0 for i in range(n): result += catalan(i) * catalan(n - 1 - i)
return result
for i in range(6): print(catalan(i), end=" ") # 1 1 2 5 14 4219. Ghép ngoặc hợp lệ (Generate Parentheses)
Với n cặp ngoặc, sinh ra tất cả các chuỗi ngoặc () hợp lệ có thể tạo được, dùng backtracking.
Ví dụ:
Input: n=3Output: ['((()))', '(()())', '(())()', '()(())', '()()()']Xem đáp án
def generate_parentheses(n): result = []
def backtrack(current, opened, closed): if len(current) == 2 * n: result.append(current) return
if opened < n: backtrack(current + "(", opened + 1, closed) if closed < opened: backtrack(current + ")", opened, closed + 1)
backtrack("", 0, 0) return result
print(generate_parentheses(3))20. Chia list thành 2 phần có tổng gần bằng nhau
Dùng đệ quy để tìm cách chia một list số nguyên dương thành 2 phần sao cho hiệu tổng 2 phần là nhỏ nhất có thể.
Ví dụ:
Input: [1, 6, 11, 5]Output: 1Xem đáp án
def optimal_partition(arr): total = sum(arr) min_diff = [total] # dùng list để có thể thay đổi trong hàm lồng
def try_partition(index, sum_part1): if index == len(arr): diff = abs(total - 2 * sum_part1) min_diff[0] = min(min_diff[0], diff) return
try_partition(index + 1, sum_part1 + arr[index]) try_partition(index + 1, sum_part1)
try_partition(0, 0) return min_diff[0]
print(optimal_partition([1, 6, 11, 5])) # 1 (chia thành [1, 5, 6] và [11])Nhóm 4: Quy hoạch động (Dynamic Programming)
Phần tiêu đề “Nhóm 4: Quy hoạch động (Dynamic Programming)”21. Fibonacci với Memoization
Tối ưu hàm tính số Fibonacci thứ n bằng kỹ thuật ghi nhớ (memoization) để tránh tính lại nhiều lần.
Ví dụ:
Input: n=50Output: 12586269025Xem đáp án
def fib_memo(n, cache=None): if cache is None: cache = {}
if n <= 1: return n if n in cache: return cache[n]
cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache) return cache[n]
print(fib_memo(50)) # Chạy nhanh nhờ cache, không như đệ quy thường22. Fibonacci Bottom-up
Tính số Fibonacci thứ n bằng quy hoạch động kiểu bottom-up (dùng vòng lặp, không đệ quy).
Ví dụ:
Input: n=30Output: 832040Xem đáp án
def fib_bottom_up(n): if n <= 1: return n
dp = [0] * (n + 1) dp[1] = 1
for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
print(fib_bottom_up(30))23. Bài toán cái túi 0/1 (0/1 Knapsack)
Cho n món đồ, mỗi món có trọng lượng và giá trị, và một túi có sức chứa capacity. Tìm giá trị lớn nhất có thể mang được (mỗi món chỉ lấy 0 hoặc 1 lần).
Ví dụ:
Input: weights=[1, 3, 4, 5], values=[1, 4, 5, 7], capacity=7Output: 9Xem đáp án
def knapsack(weights, values, capacity): n = len(weights) dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1): for w in range(capacity + 1): if weights[i - 1] <= w: dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]) else: dp[i][w] = dp[i - 1][w]
return dp[n][capacity]
weights = [1, 3, 4, 5]values = [1, 4, 5, 7]print(knapsack(weights, values, 7)) # 924. Dãy con chung dài nhất (Longest Common Subsequence)
Tìm độ dài dãy con chung dài nhất giữa 2 chuỗi.
Ví dụ:
Input: s1="ABCBDAB", s2="BDCABA"Output: 4Xem đáp án
def lcs(s1, s2): m, n = len(s1), len(s2) dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1): for j in range(1, n + 1): if s1[i - 1] == s2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
print(lcs("ABCBDAB", "BDCABA")) # 425. Khoảng cách chỉnh sửa (Edit Distance)
Tính số phép biến đổi tối thiểu (thêm, xóa, sửa 1 ký tự) để biến chuỗi s1 thành chuỗi s2.
Ví dụ:
Input: s1="kitten", s2="sitting"Output: 3Xem đáp án
def edit_distance(s1, s2): m, n = len(s1), len(s2) dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1): dp[i][0] = i for j in range(n + 1): dp[0][j] = j
for i in range(1, m + 1): for j in range(1, n + 1): if s1[i - 1] == s2[j - 1]: dp[i][j] = dp[i - 1][j - 1] else: dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
return dp[m][n]
print(edit_distance("kitten", "sitting")) # 326. Đổi tiền tối ưu (Coin Change)
Cho một list mệnh giá tiền xu và một số tiền amount. Tìm số lượng xu tối thiểu để tạo thành amount (trả về -1 nếu không thể).
Ví dụ:
Input: coins=[1, 2, 5], amount=11Output: 3Xem đáp án
def coin_change(coins, amount): dp = [float("inf")] * (amount + 1) dp[0] = 0
for total in range(1, amount + 1): for coin in coins: if coin <= total: dp[total] = min(dp[total], dp[total - coin] + 1)
return dp[amount] if dp[amount] != float("inf") else -1
print(coin_change([1, 2, 5], 11)) # 3 (5 + 5 + 1)27. Dãy con tăng dài nhất (Longest Increasing Subsequence)
Tìm độ dài dãy con tăng dần dài nhất trong một list số.
Ví dụ:
Input: [10, 9, 2, 5, 3, 7, 101, 18]Output: 4Xem đáp án
def longest_increasing_subsequence(arr): if not arr: return 0
dp = [1] * len(arr)
for i in range(1, len(arr)): for j in range(i): if arr[j] < arr[i]: dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
print(longest_increasing_subsequence([10, 9, 2, 5, 3, 7, 101, 18])) # 428. Tổng dãy con lớn nhất (Kadane’s Algorithm)
Tìm tổng lớn nhất của một dãy con liên tiếp trong list số (có thể có số âm).
Ví dụ:
Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]Output: 6Xem đáp án
def max_subarray_sum(arr): max_sum = arr[0] current_sum = arr[0]
for num in arr[1:]: current_sum = max(num, current_sum + num) max_sum = max(max_sum, current_sum)
return max_sum
print(max_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4])) # 629. Leo cầu thang (Climbing Stairs)
Có n bậc cầu thang, mỗi bước bạn có thể leo 1 hoặc 2 bậc. Đếm số cách khác nhau để leo lên đến bậc thứ n.
Ví dụ:
Input: n=5Output: 8Xem đáp án
def climb_stairs(n): if n <= 2: return n
dp = [0] * (n + 1) dp[1], dp[2] = 1, 2
for i in range(3, n + 1): dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
print(climb_stairs(5)) # 830. Kẻ trộm nhà (House Robber)
Một tên trộm không thể trộm 2 nhà liền kề nhau. Cho list giá trị tiền ở mỗi nhà, tìm số tiền tối đa có thể trộm được.
Ví dụ:
Input: [2, 7, 9, 3, 1]Output: 12Xem đáp án
def house_robber(nums): if not nums: return 0 if len(nums) == 1: return nums[0]
dp = [0] * len(nums) dp[0] = nums[0] dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)): dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[-1]
print(house_robber([2, 7, 9, 3, 1])) # 12 (2 + 9 + 1)Nhóm 5: Cấu trúc dữ liệu
Phần tiêu đề “Nhóm 5: Cấu trúc dữ liệu”31. Stack (Ngăn xếp)
Cài đặt cấu trúc dữ liệu Stack bằng class, hỗ trợ push, pop, peek, is_empty.
Xem đáp án
class Stack: def __init__(self): self._items = []
def push(self, item): self._items.append(item)
def pop(self): return self._items.pop()
def peek(self): return self._items[-1]
def is_empty(self): return len(self._items) == 0
s = Stack()s.push(1)s.push(2)s.push(3)print(s.pop()) # 3print(s.peek()) # 2print(s.is_empty()) # False32. Kiểm tra ngoặc hợp lệ (dùng Stack)
Dùng Stack để kiểm tra một chuỗi ngoặc (gồm (), [], {}) có hợp lệ (đóng mở đúng thứ tự) hay không.
Ví dụ:
Input: "({[]})"Output: True
Input: "([)]"Output: FalseXem đáp án
def is_valid_parentheses(s): stack = [] bracket_pairs = {")": "(", "]": "[", "}": "{"}
for char in s: if char in "([{": stack.append(char) elif char in ")]}": if not stack or stack.pop() != bracket_pairs[char]: return False
return len(stack) == 0
print(is_valid_parentheses("({[]})")) # Trueprint(is_valid_parentheses("([)]")) # False33. Queue (Hàng đợi) bằng deque
Cài đặt cấu trúc dữ liệu Queue bằng collections.deque, hỗ trợ enqueue, dequeue.
Xem đáp án
from collections import deque
class Queue: def __init__(self): self._items = deque()
def enqueue(self, item): self._items.append(item)
def dequeue(self): return self._items.popleft()
def is_empty(self): return len(self._items) == 0
q = Queue()q.enqueue("A")q.enqueue("B")q.enqueue("C")print(q.dequeue()) # Aprint(q.dequeue()) # B34. Linked List đơn giản
Cài đặt Linked List (danh sách liên kết đơn) với các thao tác append và print_list.
Xem đáp án
class Node: def __init__(self, value): self.value = value self.next = None
class LinkedList: def __init__(self): self.head = None
def append(self, value): new_node = Node(value) if self.head is None: self.head = new_node return
current = self.head while current.next: current = current.next current.next = new_node
def print_list(self): current = self.head while current: print(current.value, end=" -> ") current = current.next print("None")
ll = LinkedList()ll.append(1)ll.append(2)ll.append(3)ll.print_list() # 1 -> 2 -> 3 -> None35. Đảo ngược Linked List
Viết hàm đảo ngược một Linked List (dùng lại class Node/LinkedList ở bài trước).
Xem đáp án
class Node: def __init__(self, value): self.value = value self.next = None
def reverse_linked_list(head): prev = None current = head
while current: next_node = current.next current.next = prev prev = current current = next_node
return prev
def print_list(head): current = head while current: print(current.value, end=" -> ") current = current.next print("None")
# Tạo list 1 -> 2 -> 3a, b, c = Node(1), Node(2), Node(3)a.next, b.next = b, c
new_head = reverse_linked_list(a)print_list(new_head) # 3 -> 2 -> 1 -> None36. Binary Tree - Duyệt cây
Cài đặt cây nhị phân đơn giản và viết 3 hàm duyệt: preorder, inorder, postorder.
Xem đáp án
class TreeNode: def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right
def preorder(node): if node: print(node.value, end=" ") preorder(node.left) preorder(node.right)
def inorder(node): if node: inorder(node.left) print(node.value, end=" ") inorder(node.right)
def postorder(node): if node: postorder(node.left) postorder(node.right) print(node.value, end=" ")
# 1# / \# 2 3root = TreeNode(1, TreeNode(2), TreeNode(3))
preorder(root) # 1 2 3print()inorder(root) # 2 1 3print()postorder(root) # 2 3 137. Tính chiều cao cây nhị phân
Viết hàm đệ quy tính chiều cao (số tầng) của một cây nhị phân.
Ví dụ: cây 1 có con trái 2 (con trái là 4) và con phải 3.
Output: 3Xem đáp án
class TreeNode: def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right
def height(node): if node is None: return 0 return 1 + max(height(node.left), height(node.right))
root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))print(height(root)) # 338. Kiểm tra cây đối xứng (Symmetric Tree)
Kiểm tra một cây nhị phân có đối xứng qua trục dọc hay không.
Ví dụ: cây gốc 1, con trái 2 (con trái 3, con phải 4), con phải 2 (con trái 4, con phải 3).
Output: TrueXem đáp án
class TreeNode: def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right
def is_mirror(t1, t2): if t1 is None and t2 is None: return True if t1 is None or t2 is None: return False return (t1.value == t2.value and is_mirror(t1.left, t2.right) and is_mirror(t1.right, t2.left))
def is_symmetric(root): if root is None: return True return is_mirror(root.left, root.right)
root = TreeNode(1, TreeNode(2, TreeNode(3), TreeNode(4)), TreeNode(2, TreeNode(4), TreeNode(3)))print(is_symmetric(root)) # True39. Duyệt cây theo tầng (Level Order / BFS)
Duyệt cây nhị phân theo từng tầng, in ra danh sách giá trị của mỗi tầng.
Ví dụ: cây gốc 3, con trái 9, con phải 20 (con trái 15, con phải 7).
Output: [[3], [9, 20], [15, 7]]Xem đáp án
from collections import deque
class TreeNode: def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right
def level_order(root): if root is None: return []
result = [] queue = deque([root])
while queue: count_items = len(queue) current_level = []
for _ in range(count_items): node = queue.popleft() current_level.append(node.value)
if node.left: queue.append(node.left) if node.right: queue.append(node.right)
result.append(current_level)
return result
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))print(level_order(root)) # [[3], [9, 20], [15, 7]]40. Binary Search Tree - Thêm và tìm kiếm
Cài đặt cây tìm kiếm nhị phân (BST) với thao tác insert và search.
Ví dụ:
Input: insert [50, 30, 70, 20, 40, 60, 80] rồi search(40)Output: True
Input: search(100)Output: FalseXem đáp án
class BSTNode: def __init__(self, value): self.value = value self.left = None self.right = None
def insert(root, value): if root is None: return BSTNode(value)
if value < root.value: root.left = insert(root.left, value) else: root.right = insert(root.right, value)
return root
def search(root, value): if root is None: return False if root.value == value: return True if value < root.value: return search(root.left, value) return search(root.right, value)
root = Nonefor num in [50, 30, 70, 20, 40, 60, 80]: root = insert(root, num)
print(search(root, 40)) # Trueprint(search(root, 100)) # FalseNhóm 6: Lập trình hướng đối tượng (OOP) nâng cao
Phần tiêu đề “Nhóm 6: Lập trình hướng đối tượng (OOP) nâng cao”41. Kế thừa (Inheritance)
Viết class Animal với phương thức speak(), sau đó viết class Dog và Cat kế thừa từ Animal và ghi đè (override) phương thức speak().
Xem đáp án
class Animal: def __init__(self, name): self.name = name
def speak(self): return f"{self.name} phát ra âm thanh"
class Dog(Animal): def speak(self): return f"{self.name} sủa: Gâu gâu!"
class Cat(Animal): def speak(self): return f"{self.name} kêu: Meo meo!"
animals = [Dog("Milu"), Cat("Mimi")]for a in animals: print(a.speak())42. Đa hình (Polymorphism)
Viết một hàm calculate_area(shape) nhận vào các đối tượng hình học khác nhau (Square, Circle) và gọi đúng phương thức area() tương ứng nhờ đa hình.
Xem đáp án
import math
class Square: def __init__(self, side): self.side = side
def area(self): return self.side ** 2
class Circle: def __init__(self, radius): self.radius = radius
def area(self): return math.pi * self.radius ** 2
def calculate_area(shape): return shape.area()
for shape in [Square(4), Circle(3)]: print(round(calculate_area(shape), 2))43. Encapsulation (property, getter/setter)
Viết class BankAccount với thuộc tính _balance được bảo vệ, dùng @property để đọc và @balance.setter để kiểm tra không cho set số dư âm.
Xem đáp án
class BankAccount: def __init__(self, initial_balance): self._balance = initial_balance
@property def balance(self): return self._balance
@balance.setter def balance(self, value): if value < 0: raise ValueError("Số dư không thể âm") self._balance = value
account = BankAccount(100)print(account.balance) # 100account.balance = 200print(account.balance) # 200
try: account.balance = -50except ValueError as e: print("Lỗi:", e)44. Static Method và Class Method
Viết class MathUtils có 1 @staticmethod tính bình phương và 1 @classmethod tạo đối tượng Point từ chuỗi "x,y".
Xem đáp án
class MathUtils: @staticmethod def square(x): return x ** 2
class Point: def __init__(self, x, y): self.x = x self.y = y
@classmethod def from_string(cls, text): x, y = text.split(",") return cls(int(x), int(y))
def __repr__(self): return f"Point({self.x}, {self.y})"
print(MathUtils.square(5)) # 25
d = Point.from_string("3,4")print(d) # Point(3, 4)45. __str__ và __repr__
Viết class Product với __str__ (hiển thị thân thiện cho người dùng) và __repr__ (hiển thị cho lập trình viên/debug).
Xem đáp án
class Product: def __init__(self, name, price): self.name = name self.price = price
def __str__(self): return f"{self.name}: {self.price:,}đ"
def __repr__(self): return f"Product(name={self.name!r}, price={self.price})"
product = Product("Laptop", 15000000)print(str(product)) # Laptop: 15,000,000đprint(repr(product)) # Product(name='Laptop', price=15000000)46. Nạp chồng toán tử (Operator Overloading)
Viết class Vector2D biểu diễn vector 2 chiều, nạp chồng toán tử +, - và ==.
Xem đáp án
class Vector2D: def __init__(self, x, y): self.x = x self.y = y
def __add__(self, other): return Vector2D(self.x + other.x, self.y + other.y)
def __sub__(self, other): return Vector2D(self.x - other.x, self.y - other.y)
def __eq__(self, other): return self.x == other.x and self.y == other.y
def __repr__(self): return f"Vector2D({self.x}, {self.y})"
v1 = Vector2D(1, 2)v2 = Vector2D(3, 4)print(v1 + v2) # Vector2D(4, 6)print(v1 - v2) # Vector2D(-2, -2)print(v1 == Vector2D(1, 2)) # True47. Abstract Base Class
Dùng module abc để tạo class trừu tượng Shape với phương thức trừu tượng perimeter(), ép các class con phải cài đặt phương thức này.
Xem đáp án
from abc import ABC, abstractmethod
class Shape(ABC): @abstractmethod def perimeter(self): pass
class Rectangle(Shape): def __init__(self, length, width): self.length = length self.width = width
def perimeter(self): return 2 * (self.length + self.width)
rect = Rectangle(4, 5)print(rect.perimeter()) # 18
try: shape = Shape() # Không thể khởi tạo class trừu tượngexcept TypeError as e: print("Lỗi:", e)48. Dataclass
Dùng @dataclass để viết class Employee gọn hơn, tự động có __init__, __repr__ và __eq__.
Xem đáp án
from dataclasses import dataclass
@dataclassclass Employee: name: str age: int luong: float = 0.0
nv1 = Employee("An", 25, 15000000)nv2 = Employee("An", 25, 15000000)
print(nv1) # Employee(name='An', age=25, luong=15000000)print(nv1 == nv2) # True (dataclass tự sinh __eq__)49. So sánh đối tượng (__eq__, __lt__) để sắp xếp
Viết class Student cài đặt __eq__ và __lt__ để có thể dùng trực tiếp sorted() theo điểm số.
Xem đáp án
class Student: def __init__(self, name, score): self.name = name self.score = score
def __eq__(self, other): return self.score == other.score
def __lt__(self, other): return self.score < other.score
def __repr__(self): return f"{self.name} ({self.score})"
student_list = [Student("An", 8), Student("Binh", 9), Student("Chi", 7)]print(sorted(student_list)) # [Chi (7), An (8), Binh (9)]50. Singleton Pattern
Cài đặt mẫu thiết kế Singleton đơn giản, đảm bảo một class chỉ có duy nhất 1 đối tượng được tạo ra.
Xem đáp án
class Singleton: _instance = None
def __new__(cls, *args, **kwargs): if cls._instance is None: cls._instance = super().__new__(cls) return cls._instance
def __init__(self): self.value = getattr(self, "value", 0)
a = Singleton()b = Singleton()a.value = 100
print(a is b) # True — cùng 1 đối tượngprint(b.value) # 100Nhóm 7: Closures, Decorators, Generators
Phần tiêu đề “Nhóm 7: Closures, Decorators, Generators”51. Closure - Bộ đếm
Viết một closure make_counter() trả về hàm count() mỗi lần gọi sẽ tăng và trả về một biến đếm được “nhớ” bên trong closure.
Xem đáp án
def make_counter(): count_value = 0
def count(): nonlocal count_value count_value += 1 return count_value
return count
counter = make_counter()print(counter()) # 1print(counter()) # 2print(counter()) # 352. Decorator đo thời gian chạy hàm
Viết decorator @do_thoi_gian in ra thời gian thực thi của hàm được trang trí.
Xem đáp án
import timefrom functools import wraps
def timer(func): @wraps(func) def wrapper(*args, **kwargs): start_time = time.time() result = func(*args, **kwargs) end_time = time.time() print(f"{func.__name__} chạy trong {end_time - start_time:.4f} giây") return result return wrapper
@timerdef calculate_sum(n): return sum(range(n))
print(calculate_sum(1_000_000))53. Decorator ghi log
Viết decorator @ghi_log in ra tên hàm cùng tham số truyền vào mỗi khi hàm được gọi.
Xem đáp án
from functools import wraps
def log_calls(func): @wraps(func) def wrapper(*args, **kwargs): print(f"Gọi hàm {func.__name__} với args={args}, kwargs={kwargs}") return func(*args, **kwargs) return wrapper
@log_callsdef add(a, b): return a + b
print(add(3, 5))54. Decorator tự động thử lại (Retry)
Viết decorator @retry(times) tự động gọi lại hàm tối đa times lần nếu hàm ném ra exception.
Xem đáp án
from functools import wraps
def retry(times=3): def decorator(func): @wraps(func) def wrapper(*args, **kwargs): for attempt in range(1, times + 1): try: return func(*args, **kwargs) except Exception as e: print(f"Lần thử {attempt} thất bại: {e}") raise Exception(f"Đã thử {times} lần nhưng vẫn thất bại") return wrapper return decorator
call_count = [0]
@retry(times=3)def unstable_function(): call_count[0] += 1 if call_count[0] < 3: raise ValueError("Lỗi giả lập") return "Thành công!"
print(unstable_function())55. Generator sinh dãy Fibonacci
Viết một generator function fibonacci_gen() sinh vô hạn các số Fibonacci, dùng yield.
Xem đáp án
def fibonacci_gen(): a, b = 0, 1 while True: yield a a, b = b, a + b
gen = fibonacci_gen()for _ in range(10): print(next(gen), end=" ") # 0 1 1 2 3 5 8 13 21 3456. Generator đọc dữ liệu lớn theo từng dòng
Viết generator read_file_lines(file_path) đọc file lớn từng dòng một, tránh load toàn bộ file vào bộ nhớ.
Xem đáp án
def read_file_lines(file_path): with open(file_path, "r", encoding="utf-8") as f: for line in f: yield line.strip()
with open("data.txt", "w", encoding="utf-8") as f: f.write("Dòng 1\nDòng 2\nDòng 3\n")
for line in read_file_lines("data.txt"): print(line)57. yield from
Viết generator chain_generators(gen1, gen2) dùng yield from để nối 2 generator lại thành 1 chuỗi giá trị liên tục.
Xem đáp án
def even_gen(n): for i in range(0, n, 2): yield i
def odd_gen(n): for i in range(1, n, 2): yield i
def chain_generators(gen1, gen2): yield from gen1 yield from gen2
for num in chain_generators(even_gen(6), odd_gen(6)): print(num, end=" ") # 0 2 4 1 3 558. Generator Expression vs List Comprehension
Viết cùng 1 phép tính bình phương các số từ 1 đến 1 triệu bằng cả list comprehension và generator expression, so sánh kích thước bộ nhớ bằng sys.getsizeof.
Xem đáp án
import sys
list_comp = [x ** 2 for x in range(1_000_000)]gen_exp = (x ** 2 for x in range(1_000_000))
print("List comprehension:", sys.getsizeof(list_comp), "bytes")print("Generator expression:", sys.getsizeof(gen_exp), "bytes")# Generator chỉ lưu "công thức sinh giá trị", không lưu toàn bộ dữ liệu59. Decorator cache kết quả (tự viết memoization)
Viết decorator @cache_ketqua tự lưu lại kết quả các lần gọi hàm trước đó, tránh tính toán lại (không dùng functools.lru_cache).
Xem đáp án
from functools import wraps
def cache_result(func): cache = {}
@wraps(func) def wrapper(*args): if args not in cache: cache[args] = func(*args) return cache[args]
return wrapper
@cache_resultdef fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2)
print(fib(35)) # Chạy nhanh nhờ cache60. Context Manager tự viết (class)
Viết một class context manager FileOpener (cài đặt __enter__ và __exit__) để dùng với cú pháp with.
Xem đáp án
class FileOpener: def __init__(self, file_path, mode): self.file_path = file_path self.mode = mode
def __enter__(self): self.file = open(self.file_path, self.mode, encoding="utf-8") return self.file
def __exit__(self, exc_type, exc_value, traceback): self.file.close() print("Đã tự động đóng file")
with FileOpener("data.txt", "w") as f: f.write("Xin chào từ context manager tự viết!")Nhóm 8: Lập trình hàm (Functional Programming)
Phần tiêu đề “Nhóm 8: Lập trình hàm (Functional Programming)”61. reduce tính tổng và tích
Dùng functools.reduce để tính tổng và tích các phần tử của một list số.
Xem đáp án
from functools import reduce
numbers = [1, 2, 3, 4, 5]
total = reduce(lambda a, b: a + b, numbers)product_value = reduce(lambda a, b: a * b, numbers)
print("Tổng:", total) # 15print("Tích:", product_value) # 12062. Kết hợp map và filter
Cho một list chuỗi số, dùng filter để loại các chuỗi không phải số, dùng map để chuyển các chuỗi còn lại thành int và nhân đôi giá trị.
Xem đáp án
data = ["10", "abc", "20", "xyz", "30"]
valid_numbers = filter(str.isdigit, data)result = list(map(lambda x: int(x) * 2, valid_numbers))
print(result) # [20, 40, 60]63. functools.partial
Dùng functools.partial để tạo ra một hàm mới từ hàm nhan(a, b) với a đã được cố định sẵn.
Xem đáp án
from functools import partial
def multiply(a, b): return a * b
double_value = partial(multiply, 2)triple_value = partial(multiply, 3)
print(double_value(5)) # 10print(triple_value(5)) # 1564. itertools.combinations
Dùng itertools.combinations để in ra tất cả tổ hợp chập 2 của một list.
Xem đáp án
from itertools import combinations
items = ["A", "B", "C", "D"]
for combo in combinations(items, 2): print(combo)65. itertools.permutations
Dùng itertools.permutations để in ra tất cả hoán vị của một list 3 phần tử.
Xem đáp án
from itertools import permutations
items = [1, 2, 3]
for current in permutations(items): print(current)66. itertools.groupby
Cho một list số đã sắp xếp, dùng itertools.groupby để nhóm các số theo tính chẵn/lẻ.
Xem đáp án
from itertools import groupby
numbers = [1, 3, 5, 2, 4, 6, 7, 9]numbers_sorted = sorted(numbers, key=lambda x: x % 2)
for key, groups in groupby(numbers_sorted, key=lambda x: "Chẵn" if x % 2 == 0 else "Lẻ"): print(key, ":", list(groups))67. sorted với key phức tạp
Cho một list các tuple (ten, tuoi). Sắp xếp theo độ dài tên tăng dần, nếu bằng nhau thì theo tuổi giảm dần.
Xem đáp án
people = [("An", 20), ("Binh", 25), ("Ba", 30), ("Chi", 22)]
result = sorted(people, key=lambda p: (len(p[0]), -p[1]))print(result)68. any và all nâng cao
Cho một list các list con điểm số, dùng any/all kết hợp generator expression để kiểm tra: (1) có học sinh nào toàn điểm 10 không, (2) tất cả học sinh có ít nhất 1 điểm trên 8 không.
Xem đáp án
student_scores = [ [8, 9, 7], [10, 10, 10], [6, 9, 5],]
has_student_all_10s = any(all(d == 10 for d in student) for student in student_scores)all_have_score_above_8 = all(any(d > 8 for d in student) for student in student_scores)
print(has_student_all_10s) # Trueprint(all_have_score_above_8) # FalseNhóm 9: Module chuẩn hữu ích
Phần tiêu đề “Nhóm 9: Module chuẩn hữu ích”69. collections.Counter - Ký tự phổ biến nhất
Dùng Counter để tìm ra 3 ký tự xuất hiện nhiều nhất trong một chuỗi.
Xem đáp án
from collections import Counter
s = "lap trinh python rat try_partition vi"count = Counter(s.replace(" ", ""))
print(count.most_common(3))70. collections.defaultdict - Nhóm dữ liệu
Cho một list các tuple (ten, mon_hoc). Dùng defaultdict để nhóm danh sách môn học theo từng người.
Xem đáp án
from collections import defaultdict
data = [("An", "Toán"), ("An", "Lý"), ("Binh", "Hóa"), ("An", "Anh"), ("Binh", "Toán")]
groups = defaultdict(list)for name, subject in data: groups[name].append(subject)
for name, subjects in groups.items(): print(name, ":", subjects)71. collections.namedtuple
Dùng namedtuple để tạo kiểu dữ liệu Point (có x, y) gọn nhẹ hơn class thông thường.
Xem đáp án
from collections import namedtuple
Point = namedtuple("Point", ["x", "y"])
p1 = Point(1, 2)p2 = Point(x=3, y=4)
print(p1) # Point(x=1, y=2)print(p1.x, p1.y) # 1 2print(p1 == Point(1, 2)) # True72. datetime - Tính số ngày giữa 2 mốc thời gian
Dùng module datetime để tính số ngày giữa 2 ngày cho trước.
Xem đáp án
from datetime import date
date1 = date(2024, 1, 1)date2 = date(2024, 12, 31)
day_count = (date2 - date1).daysprint(f"Số ngày giữa 2 mốc: {day_count}")73. re - Kiểm tra định dạng email
Dùng module re (regular expression) để kiểm tra một chuỗi có đúng định dạng email cơ bản hay không, có cho nhập lại nếu sai định dạng.
Xem đáp án
import re
pattern = r"^[\w.+-]+@[\w-]+\.[a-zA-Z]{2,}$"
while True: email = input("Nhập email: ") if re.match(pattern, email): print("Email hợp lệ!") break print("Email không hợp lệ, vui lòng nhập lại!")74. re - Trích xuất số điện thoại
Dùng re.findall để trích xuất tất cả số điện thoại (dạng 10 chữ số) xuất hiện trong một đoạn văn bản.
Xem đáp án
import re
text = "Liên hệ An qua 0901234567 hoặc Bình qua 0987654321 để biết thêm chi tiết."
phone_numbers = re.findall(r"\b0\d{9}\b", text)print(phone_numbers) # ['0901234567', '0987654321']75. json - Đọc và ghi dữ liệu JSON
Dùng module json để lưu một dictionary vào file .json, sau đó đọc lại và in ra.
Xem đáp án
import json
data = {"name": "An", "age": 20, "mon_yeu_thich": ["Toán", "Tin"]}
with open("data.json", "w", encoding="utf-8") as f: json.dump(data, f, ensure_ascii=False, indent=2)
with open("data.json", "r", encoding="utf-8") as f: loaded_data = json.load(f)
print(loaded_data)76. os / pathlib - Liệt kê file trong thư mục
Dùng pathlib để liệt kê tất cả các file có đuôi .txt trong thư mục hiện tại.
Xem đáp án
from pathlib import Path
directory = Path(".")txt_files = list(directory.glob("*.txt"))
for f in txt_files: print(f.name)77. random - Chọn ngẫu nhiên không trùng
Dùng random.sample để chọn ngẫu nhiên 5 số không trùng nhau từ 1 đến 45 (giống quay số trúng thưởng).
Xem đáp án
import random
winning_numbers = random.sample(range(1, 46), 5)print(sorted(winning_numbers))78. statistics - Thống kê cơ bản
Dùng module statistics để tính trung bình cộng, trung vị (median) và độ lệch chuẩn (standard deviation) của một list điểm số.
Xem đáp án
import statistics
score = [8, 7.5, 9, 6, 10, 8.5, 7]
print("Trung bình:", statistics.mean(score))print("Trung vị:", statistics.median(score))print("Độ lệch chuẩn:", round(statistics.stdev(score), 2))Nhóm 10: Xử lý ngoại lệ nâng cao
Phần tiêu đề “Nhóm 10: Xử lý ngoại lệ nâng cao”79. Phân cấp Exception tùy chỉnh
Tạo một hệ thống exception phân cấp cho việc rút tiền ngân hàng: AccountError (lớp cha), InsufficientBalanceError và InvalidAmountError (kế thừa từ lớp cha).
Xem đáp án
class AccountError(Exception): pass
class InsufficientBalanceError(AccountError): pass
class InvalidAmountError(AccountError): pass
def withdraw(balance, withdrawal_amount): if withdrawal_amount <= 0: raise InvalidAmountError("Số tiền rút phải lớn hơn 0") if withdrawal_amount > balance: raise InsufficientBalanceError("Số dư không đủ để rút") return balance - withdrawal_amount
for value in [-100, 5000, 100]: try: print(withdraw(1000, value)) except AccountError as e: print(f"Lỗi ({type(e).__name__}): {e}")80. Chained Exception (raise ... from ...)
Viết chương trình đọc số từ chuỗi, khi gặp lỗi định dạng thì ném ra một exception mới nhưng vẫn giữ lại nguyên nhân gốc bằng raise ... from ....
Xem đáp án
class InvalidDataError(Exception): pass
def process_data(text): try: return int(text) except ValueError as loi_goc: raise InvalidDataError(f"Không thể xử lý dữ liệu: {text!r}") from loi_goc
try: process_data("abc")except InvalidDataError as e: print("Lỗi:", e) print("Nguyên nhân gốc:", e.__cause__)81. Context Manager xử lý lỗi (__exit__ trả về True)
Viết context manager SuppressError cho phép bỏ qua một loại exception cụ thể xảy ra bên trong khối with.
Xem đáp án
class SuppressError: def __init__(self, *error_types): self.error_types = error_types
def __enter__(self): return self
def __exit__(self, exc_type, exc_value, traceback): if exc_type in self.error_types: print(f"Đã bỏ qua lỗi: {exc_value}") return True # True nghĩa là exception được "nuốt", chương trình chạy tiếp return False
with SuppressError(ZeroDivisionError): print(10 / 0)
print("Chương trình vẫn chạy tiếp bình thường")82. finally luôn được thực thi
Viết chương trình minh họa khối finally luôn chạy dù có exception hay không, hay dù có return sớm trong hàm.
Xem đáp án
def read_data(should_fail): try: if should_fail: raise ValueError("Dữ liệu lỗi") return "Đọc dữ liệu thành công" finally: print("Dọn dẹp tài nguyên (luôn chạy)")
print(read_data(False))
try: read_data(True)except ValueError as e: print("Bắt được lỗi:", e)83. Validate dữ liệu nhập với nhiều loại lỗi
Viết hàm input_age() yêu cầu người dùng nhập tuổi, bắt cả lỗi ValueError (không phải số) lẫn lỗi tuổi không hợp lệ (âm hoặc quá lớn), cho nhập lại đến khi hợp lệ.
Xem đáp án
class InvalidAgeError(Exception): pass
def input_age(): while True: try: age = int(input("Nhập tuổi của bạn: ")) if age < 0 or age > 150: raise InvalidAgeError("Tuổi phải trong khoảng 0-150") return age except ValueError: print("Vui lòng nhập một số nguyên hợp lệ!") except InvalidAgeError as e: print(f"Lỗi: {e}, vui lòng nhập lại!")
age = input_age()print("Tuổi hợp lệ:", age)Nhóm 11: Thuật toán số học & ma trận nâng cao
Phần tiêu đề “Nhóm 11: Thuật toán số học & ma trận nâng cao”84. Sàng Eratosthenes
Cài đặt thuật toán Sàng Eratosthenes để tìm tất cả số nguyên tố nhỏ hơn n, hiệu quả hơn nhiều so với kiểm tra từng số.
Ví dụ:
Input: n=20Output: [2, 3, 5, 7, 11, 13, 17, 19]Xem đáp án
def sieve_of_eratosthenes(n): is_prime = [True] * n is_prime[0:2] = [False, False] # 0 và 1 không phải số nguyên tố
for i in range(2, int(n ** 0.5) + 1): if is_prime[i]: for j in range(i * i, n, i): is_prime[j] = False
return [num for num, ok in enumerate(is_prime) if ok]
print(sieve_of_eratosthenes(50))85. Nhân 2 ma trận
Viết hàm nhân 2 ma trận (list 2 chiều) với nhau, không dùng thư viện ngoài.
Ví dụ:
Input: a=[[1,2],[3,4]], b=[[5,6],[7,8]]Output: [[19, 22], [43, 50]]Xem đáp án
def matrix_multiply(a, b): rows_a, cols_a = len(a), len(a[0]) cols_b = len(b[0])
result = [[0] * cols_b for _ in range(rows_a)]
for i in range(rows_a): for j in range(cols_b): for k in range(cols_a): result[i][j] += a[i][k] * b[k][j]
return result
a = [[1, 2], [3, 4]]b = [[5, 6], [7, 8]]print(matrix_multiply(a, b)) # [[19, 22], [43, 50]]86. Chuyển vị ma trận (Transpose)
Viết hàm chuyển vị một ma trận (đổi hàng thành cột), không dùng thư viện ngoài.
Ví dụ:
Input: [[1, 2, 3], [4, 5, 6]]Output: [[1, 4], [2, 5], [3, 6]]Xem đáp án
def transpose(matrix): rows = len(matrix) cols = len(matrix[0])
result = [[0] * rows for _ in range(cols)]
for i in range(rows): for j in range(cols): result[j][i] = matrix[i][j]
return result
matrix = [[1, 2, 3], [4, 5, 6]]print(transpose(matrix)) # [[1, 4], [2, 5], [3, 6]]87. Xoay ma trận vuông 90 độ
Viết hàm xoay một ma trận vuông 90 độ theo chiều kim đồng hồ, không dùng bộ nhớ phụ (in-place).
Ví dụ:
Input: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]Output: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]Xem đáp án
def rotate_90(matrix): n = len(matrix)
# Bước 1: chuyển vị ma trận for i in range(n): for j in range(i + 1, n): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# Bước 2: đảo ngược từng hàng for row in matrix: row.reverse()
return matrix
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]print(rotate_90(matrix)) # [[7, 4, 1], [8, 5, 2], [9, 6, 3]]88. Kiểm tra số chính phương không dùng sqrt
Kiểm tra một số nguyên dương có phải là số chính phương hay không, dùng thuật toán tìm kiếm nhị phân thay vì math.sqrt.
Ví dụ:
Input: 16Output: True
Input: 18Output: FalseXem đáp án
def is_perfect_square(n): if n < 0: return False
left, right = 0, n while left <= right: mid = (left + right) // 2 square = mid * mid
if square == n: return True elif square < n: left = mid + 1 else: right = mid - 1
return False
print(is_perfect_square(16)) # Trueprint(is_perfect_square(18)) # False89. Số nguyên tố Mersenne
Số Mersenne có dạng 2^p - 1. Viết chương trình kiểm tra với p là số nguyên tố, số Mersenne tương ứng có phải cũng là số nguyên tố hay không.
Xem đáp án
def is_prime(n): if n < 2: return False for i in range(2, int(n ** 0.5) + 1): if n % i == 0: return False return True
def check_mersenne(p): if not is_prime(p): return None # p phải là số nguyên tố
mersenne_number = 2 ** p - 1 return mersenne_number, is_prime(mersenne_number)
for p in [2, 3, 5, 7, 11]: print(f"p={p}: {check_mersenne(p)}")Nhóm 12: Đồ thị cơ bản (Graph)
Phần tiêu đề “Nhóm 12: Đồ thị cơ bản (Graph)”90. Duyệt đồ thị theo chiều rộng (BFS)
Cho một đồ thị biểu diễn bằng dictionary (adjacency list), duyệt đồ thị theo chiều rộng (BFS) bắt đầu từ 1 đỉnh.
Ví dụ:
Input: graph={"A":["B","C"],"B":["A","D","E"],"C":["A","F"],"D":["B"],"E":["B","F"],"F":["C","E"]}, start="A"Output: ['A', 'B', 'C', 'D', 'E', 'F']Xem đáp án
from collections import deque
def bfs(graph, start): visited = {start} queue = deque([start]) visit_order = []
while queue: vertex = queue.popleft() visit_order.append(vertex)
for neighbor in graph[vertex]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor)
return visit_order
graph = { "A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "F"], "D": ["B"], "E": ["B", "F"], "F": ["C", "E"],}
print(bfs(graph, "A"))91. Duyệt đồ thị theo chiều sâu (DFS) đệ quy
Với đồ thị ở bài trước, viết hàm duyệt theo chiều sâu (DFS) bằng đệ quy.
Ví dụ:
Input: graph (như bài 90), start="A"Output: ['A', 'B', 'D', 'E', 'F', 'C']Xem đáp án
def dfs(graph, vertex, visited=None): if visited is None: visited = set()
visited.add(vertex) visit_order = [vertex]
for neighbor in graph[vertex]: if neighbor not in visited: visit_order.extend(dfs(graph, neighbor, visited))
return visit_order
graph = { "A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "F"], "D": ["B"], "E": ["B", "F"], "F": ["C", "E"],}
print(dfs(graph, "A"))92. Kiểm tra đồ thị vô hướng có chu trình
Kiểm tra một đồ thị vô hướng (dạng adjacency list) có tồn tại chu trình (cycle) hay không, dùng DFS.
Ví dụ:
Input: {"A": ["B"], "B": ["A", "C"], "C": ["B", "A"]}Output: True
Input: {"A": ["B"], "B": ["A", "C"], "C": ["B"]}Output: FalseXem đáp án
def has_cycle(graph): visited = set()
def dfs(vertex, parent_vertex): visited.add(vertex) for neighbor in graph[vertex]: if neighbor not in visited: if dfs(neighbor, vertex): return True elif neighbor != parent_vertex: return True # Gặp lại đỉnh đã thăm mà không phải đỉnh cha -> có chu trình return False
for vertex in graph: if vertex not in visited: if dfs(vertex, None): return True
return False
graph_with_cycle = {"A": ["B"], "B": ["A", "C"], "C": ["B", "A"]}graph_without_cycle = {"A": ["B"], "B": ["A", "C"], "C": ["B"]}
print(has_cycle(graph_with_cycle)) # Trueprint(has_cycle(graph_without_cycle)) # False93. Đường đi ngắn nhất không trọng số (BFS)
Tìm đường đi ngắn nhất (số bước ít nhất) giữa 2 đỉnh trong đồ thị không trọng số, dùng BFS.
Ví dụ:
Input: graph={"A":["B","C"],"B":["A","D"],"C":["A","D"],"D":["B","C","E"],"E":["D"]}, start="A", end="E"Output: ['A', 'B', 'D', 'E']Xem đáp án
from collections import deque
def shortest_path(graph, start, end): queue = deque([[start]]) visited = {start}
while queue: path = queue.popleft() current_vertex = path[-1]
if current_vertex == end: return path
for neighbor in graph[current_vertex]: if neighbor not in visited: visited.add(neighbor) queue.append(path + [neighbor])
return None # Không có đường đi
graph = { "A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C", "E"], "E": ["D"],}
print(shortest_path(graph, "A", "E")) # ['A', 'B', 'D', 'E'] hoặc ['A', 'C', 'D', 'E']94. Đếm số thành phần liên thông (Connected Components)
Đếm số thành phần liên thông trong một đồ thị vô hướng có thể không liên thông hoàn toàn.
Ví dụ:
Input: {"A": ["B"], "B": ["A"], "C": ["D"], "D": ["C"], "E": []}Output: 3Xem đáp án
def count_connected_components(graph): visited = set()
def dfs(vertex): visited.add(vertex) for neighbor in graph[vertex]: if neighbor not in visited: dfs(neighbor)
component_count = 0 for vertex in graph: if vertex not in visited: dfs(vertex) component_count += 1
return component_count
graph = { "A": ["B"], "B": ["A"], "C": ["D"], "D": ["C"], "E": [],}
print(count_connected_components(graph)) # 395. Sắp xếp Topo (Topological Sort)
Với một đồ thị có hướng không có chu trình (DAG), sắp xếp các đỉnh theo thứ tự topo bằng thuật toán Kahn (dùng bậc vào - in-degree).
Ví dụ:
Input: {"ao": ["quan"], "quan": ["giay"], "vo": ["quan"], "giay": []}Output: ['ao', 'vo', 'quan', 'giay']Xem đáp án
from collections import deque
def topological_sort(graph): in_degree = {vertex: 0 for vertex in graph} for vertex in graph: for neighbor in graph[vertex]: in_degree[neighbor] += 1
queue = deque([vertex for vertex in graph if in_degree[vertex] == 0]) result = []
while queue: vertex = queue.popleft() result.append(vertex)
for neighbor in graph[vertex]: in_degree[neighbor] -= 1 if in_degree[neighbor] == 0: queue.append(neighbor)
return result
graph = { "ao": ["quan"], "quan": ["giay"], "vo": ["quan"], "giay": [],}
print(topological_sort(graph))Nhóm 13: Kiểm thử (Testing)
Phần tiêu đề “Nhóm 13: Kiểm thử (Testing)”96. Unit Test với unittest
Viết hàm cong(a, b) và một bộ test dùng module unittest để kiểm tra hàm hoạt động đúng.
Xem đáp án
import unittest
def add(a, b): return a + b
class TestAdd(unittest.TestCase): def test_positive(self): self.assertEqual(add(2, 3), 5)
def test_negative(self): self.assertEqual(add(-1, -1), -2)
def test_zero(self): self.assertEqual(add(0, 5), 5)
# Chạy test (trong file thực tế thường dùng: python -m unittest ten_file.py)runner = unittest.TextTestRunner()runner.run(unittest.TestLoader().loadTestsFromTestCase(TestAdd))97. Kiểm tra hàm bằng assert
Viết hàm is_palindrome(s) và dùng các câu lệnh assert để tự kiểm tra nhanh các trường hợp cơ bản.
Xem đáp án
def is_palindrome(s): s = s.lower().replace(" ", "") return s == s[::-1]
assert is_palindrome("level") == Trueassert is_palindrome("hello") == Falseassert is_palindrome("A man a plan a canal Panama") == Trueassert is_palindrome("") == True
print("Tất cả các assert đều đúng!")Nhóm 14: Lập trình đồng thời (Concurrency) cơ bản
Phần tiêu đề “Nhóm 14: Lập trình đồng thời (Concurrency) cơ bản”98. threading - Chạy song song đơn giản
Dùng module threading để chạy 2 tác vụ “song song” (thực chất là xen kẽ do GIL trong CPython), so sánh với chạy tuần tự.
Xem đáp án
import threadingimport time
def task(name, seconds): print(f"Bắt đầu {name}") time.sleep(seconds) print(f"Hoàn thành {name}")
start_time = time.time()
t1 = threading.Thread(target=task, args=("Task 1", 1))t2 = threading.Thread(target=task, args=("Task 2", 1))
t1.start()t2.start()
t1.join()t2.join()
print(f"Tổng thời gian: {time.time() - start_time:.2f} giây") # ~1 giây thay vì 299. multiprocessing - Tính tổng song song
Dùng module multiprocessing để chia một list số lớn thành nhiều phần, tính tổng từng phần song song trên nhiều tiến trình (process), rồi cộng kết quả lại.
Xem đáp án
from multiprocessing import Pool
def calculate_sum(sub_list): return sum(sub_list)
if __name__ == "__main__": numbers = list(range(1, 1_000_001)) num_parts = 4 chunk_size = len(numbers) // num_parts
parts = [ numbers[i:i + chunk_size] for i in range(0, len(numbers), chunk_size) ]
with Pool(processes=num_parts) as pool: part_results = pool.map(calculate_sum, parts)
print("Tổng cuối cùng:", sum(part_results))100. Mô phỏng nhiều tác vụ chờ với concurrent.futures
Dùng concurrent.futures.ThreadPoolExecutor để tải “giả lập” 5 trang web cùng lúc (mỗi trang mất 1 giây), thay vì tải tuần tự mất 5 giây.
Xem đáp án
import timefrom concurrent.futures import ThreadPoolExecutor
def download_page(page_name): time.sleep(1) # Giả lập thời gian chờ mạng return f"Đã tải xong {page_name}"
websites = [f"trang-{i}.com" for i in range(1, 6)]
start_time = time.time()
with ThreadPoolExecutor(max_workers=5) as executor: result = list(executor.map(download_page, websites))
for r in result: print(r)
print(f"Tổng thời gian: {time.time() - start_time:.2f} giây") # ~1 giây thay vì 5Bạn đã hoàn thành cả 100 bài cơ bản và 100 bài nâng cao? Quay lại trang Bài tập lập trình tổng hợp - Cơ bản để ôn lại, hoặc thử sức với các bài tập theo từng chủ đề riêng ở sidebar bên trái.