Cụm bài Thực hành backend: 1. Yêu cầu và thiết kế dữ liệu · 2. API và chống overbooking · 3. Ôn tập phỏng vấn · 4. Đệ quy và sắp xếp · 5. Bài tập SQL · 6. SQL trên database E-Learning
Bài này ôn nhanh sắp xếp, tìm kiếm, rồi đi sâu vào đệ quy: độ phức tạp, memoization, khử đệ quy bằng stack. Đọc xong, bạn trả lời được các câu hỏi vặn ở phỏng vấn và làm được hai bài tập đi kèm. Nền tảng Big-O ở bài Thuật toán cơ bản; nên tự làm bài tập trước rồi mới mở lời giải.
Sơ đồ tóm tắt:
flowchart TD
R[Hàm đệ quy] --> T["Hệ thức T(n)"]
R --> S["Stack: O(độ sâu)"]
R --> Q{Bài toán con lặp?}
Q -->|có| M[Memoization]
Q -->|không| D{Độ sâu theo dữ liệu?}
D -->|có| L["Vòng lặp + ArrayDeque"]
D -->|không| K[Giữ đệ quy]
SO[Sắp xếp] --> P["int[]: Dual-Pivot Quicksort"]
SO --> TS["Object[]: TimSort ổn định"]
1. Ôn tập thuật toán
Ý chính: nhớ thứ tự các lớp độ phức tạp và bảng sắp xếp bên dưới; merge sort và heap sort luôn O(n log n), quick sort xấu nhất O(n²).
- Các lớp (tốt đến tệ): O(1) — O(log n) — O(n) — O(n log n) — O(n²) — O(2ⁿ) — O(n!).
- Có độ phức tạp thời gian và không gian, và ba trường hợp tốt nhất / trung bình / xấu nhất. Big-O thường nói về xấu nhất hoặc khấu hao (amortized — chi phí trung bình qua nhiều lần chạy).
- Ổn định (stable): các phần tử có khoá bằng nhau giữ nguyên thứ tự ban đầu.
| Thuật toán sắp xếp | Tốt nhất | Trung bình | Xấu nhất | Bộ nhớ thêm | Ổn định |
|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Có |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | Không |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Có |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Có |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) | Không |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | Không |
Bảng độ phức tạp tìm kiếm
| Tìm kiếm | Độ phức tạp | Điều kiện |
|---|---|---|
| Tuyến tính | O(n) | Không cần gì |
| Nhị phân | O(log n) | Dữ liệu đã sắp xếp, truy cập ngẫu nhiên O(1) |
Bảng băm (HashMap) |
O(1) trung bình | Xấu nhất O(log n) từ Java 8 (bucket chuyển thành cây) |
Cây cân bằng (TreeMap) |
O(log n) | Cần thứ tự / tìm theo khoảng |
| Duyệt đồ thị BFS/DFS | O(V + E) |
2. Đệ quy dưới góc nhìn senior
Ý chính: phỏng vấn hay hỏi ba điều: độ phức tạp, tối ưu khi bài toán con lặp lại, và tránh StackOverflowError.
2.1 Độ phức tạp của hàm đệ quy
Ý chính: viết hệ thức truy hồi T(n) (công thức thời gian theo chính nó với đầu vào nhỏ hơn) từ số lời gọi con và việc làm ở mỗi tầng, rồi khớp với một dạng quen thuộc.
| Hệ thức | Ví dụ | Thời gian | Độ sâu stack |
|---|---|---|---|
| T(n) = T(n − 1) + O(1) | tổng 1..n, powLinear, duyệt mảng bằng đệ quy |
O(n) | O(n) |
| T(n) = T(n / 2) + O(1) | lũy thừa nhanh, tìm kiếm nhị phân | O(log n) | O(log n) |
| T(n) = 2T(n / 2) + O(n) | merge sort | O(n log n) | O(log n) |
| T(n) = T(n − 1) + O(n) | reverseNaive (tạo chuỗi mới mỗi tầng), selection sort đệ quy |
O(n²) | O(n) |
| T(n) = T(n − 1) + T(n − 2) + O(1) | Fibonacci ngây thơ | O(φⁿ) ≈ O(1,618ⁿ) | O(n) |
Hai điều hay bị quên:
- Bộ nhớ của đệ quy gồm cả stack, nên
sum(n)tốn O(n) bộ nhớ dù không cấp phát gì. - Với chia để trị, cái quyết định là số nhánh × kích thước mỗi nhánh, không chỉ “có chia đôi”.
2.2 Memoization: khi các bài toán con lặp lại
Ý chính: bài toán con lặp lại thì nhớ kết quả (memoization), độ phức tạp sụp từ mũ xuống tuyến tính. Đó là gốc của quy hoạch động.
Fibonacci ngây thơ tính fib(28) hai lần, fib(27) ba lần, và cứ thế nhân lên (fib(30) tốn 2,7 triệu lời gọi). Giống làm bài mà không ghi nháp: câu nào cũng tính lại từ đầu.
| Cách viết | Thời gian | Bộ nhớ |
|---|---|---|
fibNaive |
O(2ⁿ) | O(n) stack |
fibMemo (top-down) |
O(n) | O(n) mảng + O(n) stack |
fibIter (bottom-up, hai biến) |
O(n) | O(1), không stack |
Code ba cách viết Fibonacci
// O(2^n): mỗi lời gọi tách thành hai, các bài toán con bị tính lại rất nhiều lần
static long fibNaive(int n) {
return n < 2 ? n : fibNaive(n - 1) + fibNaive(n - 2);
}
// Memoization (top-down): mỗi n chỉ tính một lần -> O(n) thời gian, O(n) bộ nhớ + O(n) stack
static long fibMemo(int n, long[] memo) {
if (n < 2) return n;
if (memo[n] != 0) return memo[n];
return memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
}
// Tabulation (bottom-up) rút gọn còn hai biến: O(n) thời gian, O(1) bộ nhớ, không dùng stack
static long fibIter(int n) {
long prev = 0, cur = 1;
for (int i = 0; i < n; i++) {
long next = prev + cur;
prev = cur;
cur = next;
}
return prev;
}
// fibNaive(30) = 832040 sau 2.692.537 lời gọi; fibMemo(90) = fibIter(90) = 2880067194370816120
2.3 Khử đệ quy bằng stack tường minh
Ý chính: khi độ sâu đệ quy phụ thuộc dữ liệu, đẩy “việc còn phải làm” vào một ArrayDeque trên heap và lặp đến khi rỗng. Java không tối ưu tail call, nên đây là cách chắc chắn.
Dữ liệu có độ sâu tuỳ ý (cây danh mục, comment lồng nhau, đồ thị phụ thuộc) có thể làm sập service: cây suy biến sâu 100.000 tầng làm bản đệ quy ném StackOverflowError, bản vòng lặp vẫn chạy.
Quy tắc chuyển đổi:
- Mỗi lời gọi đệ quy thành một lần
push; thân hàm thành phần xử lý saupop. - Cần kết quả hậu tố (tính con xong mới tính cha): đẩy thêm một đánh dấu “đã thăm con”, hoặc dùng hai stack.
- Với đồ thị: thêm tập
visited, nếu không dữ liệu có chu trình sẽ lặp vô tận dù đã khử đệ quy.
Code đếm cây danh mục: đệ quy và stack tường minh
record Category(String name, List<Category> children) {
Category(String name) { this(name, new ArrayList<>()); }
}
// Đệ quy: gọn, nhưng độ sâu stack = độ sâu của cây
static int countRecursive(Category c) {
int total = 1;
for (Category child : c.children()) total += countRecursive(child);
return total;
}
// Vòng lặp + stack tường minh: stack nằm trên heap, không bị giới hạn bởi -Xss
static int countIterative(Category root) {
Deque<Category> stack = new ArrayDeque<>();
stack.push(root);
int total = 0;
while (!stack.isEmpty()) {
Category c = stack.pop();
total++;
for (Category child : c.children()) stack.push(child);
}
return total;
}
// Cây suy biến thành một đường thẳng sâu 100.000 tầng:
// countIterative(root) -> 100001; countRecursive(root) -> StackOverflowError
Bài tập
Bài 1 — Đệ quy
Đề (diễn đạt lại): Dùng đệ quy để: (a) tính 2ⁿ, (b) tính xⁿ, (c) tính tổng 1 + 2 + … + n, (d) tính tổng các số chẵn trong một mảng số nguyên, (e) kiểm tra mảng có đối xứng không, (f) đảo ngược một chuỗi.
Công thức chung: điều kiện dừng + bước thu nhỏ bài toán về chính nó với đầu vào nhỏ hơn.
- (b) Lũy thừa nhanh O(log n) thay vì O(n); (c) thực tế dùng n(n+1)/2; (f) bản cộng chuỗi O(n²), bản hai con trỏ O(n).
- Đáp án mẫu trong slide gọi một hàm
pow2chưa được định nghĩa — mình viết đủ ở dưới.
Lời giải Bài 1: RecursionDrills
public final class RecursionDrills {
// (a) 2^n = 2 * 2^(n-1); dừng khi n = 0. Dùng phép dịch bit cũng được: 1L << n (n < 63)
static long powerOfTwo(int n) {
if (n < 0) throw new IllegalArgumentException("n must be >= 0");
return n == 0 ? 1 : 2 * powerOfTwo(n - 1);
}
// (b) Cách thẳng: x^n = x * x^(n-1) -> O(n) lời gọi, sâu n tầng
static long powLinear(long x, int n) {
return n == 0 ? 1 : x * powLinear(x, n - 1);
}
// (b) Cách tốt hơn: lũy thừa nhanh, x^n = (x^(n/2))^2 [* x nếu n lẻ] -> O(log n)
static long pow(long x, int n) {
if (n < 0) throw new IllegalArgumentException("n must be >= 0");
if (n == 0) return 1;
long half = pow(x, n / 2);
long sq = Math.multiplyExact(half, half); // ném ArithmeticException nếu tràn
return (n % 2 == 0) ? sq : Math.multiplyExact(sq, x);
}
// (c) S(n) = n + S(n-1); dừng khi n = 0. (Thực tế dùng công thức n(n+1)/2 — O(1))
static long sum(int n) {
return n <= 0 ? 0 : n + sum(n - 1);
}
// (d) Tổng số chẵn từ vị trí i đến cuối mảng
static long sumEven(int[] a, int i) {
if (i == a.length) return 0;
int self = (a[i] % 2 == 0) ? a[i] : 0; // a[i] % 2 == 0 đúng cả với số âm
return self + sumEven(a, i + 1);
}
// (e) Đối xứng nếu hai đầu bằng nhau và phần giữa cũng đối xứng
static boolean isSymmetric(int[] a, int left, int right) {
if (left >= right) return true;
return a[left] == a[right] && isSymmetric(a, left + 1, right - 1);
}
// (f) reverse(s) = reverse(s[1..]) + s[0] — dễ đọc nhưng O(n^2) vì tạo chuỗi mới mỗi tầng
static String reverseNaive(String s) {
return s.length() <= 1 ? s : reverseNaive(s.substring(1)) + s.charAt(0);
}
// (f) Phiên bản O(n): đảo trên mảng char bằng hai con trỏ
static String reverse(String s) {
char[] c = s.toCharArray();
swap(c, 0, c.length - 1);
return new String(c);
}
private static void swap(char[] c, int l, int r) {
if (l >= r) return;
char t = c[l]; c[l] = c[r]; c[r] = t;
swap(c, l + 1, r - 1);
}
public static void main(String[] args) {
System.out.println(powerOfTwo(10)); // 1024
System.out.println(pow(3, 13)); // 1594323
System.out.println(sum(100)); // 5050
System.out.println(sumEven(new int[]{1, 2, 3, 4, -6}, 0)); // 0
System.out.println(isSymmetric(new int[]{1, 2, 3, 2, 1}, 0, 4)); // true
System.out.println(reverse("backend")); // dnekcab
}
}
Những điều cần biết khi dùng đệ quy trong Java:
Thêm: tràn số long và chọn đệ quy hay vòng lặp
Bài 2 — Sắp xếp xen kẽ lớn nhất, nhỏ nhất
Đề (diễn đạt lại): Cho n số nguyên đôi một khác nhau (n ≤ 1000). In ra theo thứ tự: lớn nhất, nhỏ nhất, lớn nhì, nhỏ nhì, … Ví dụ [9, 7, 12, 8, 6, 5] → 12 5 9 6 8 7.
Hướng giải: sắp xếp tăng dần, rồi dùng hai con trỏ (two pointers) ở hai đầu, lần lượt lấy phải rồi trái cho đến khi gặp nhau. O(n log n) thời gian do sắp xếp, O(n) bộ nhớ.
Hai lỗi nhỏ trong đáp án gốc: gọi sort(a) mà không định nghĩa (phải là Arrays.sort(a)), và khi n chẵn thì không in xuống dòng cuối, làm dính kết quả các test liền nhau trên hệ thống chấm nhiều bộ test.
Lời giải Bài 2: MaxMinOrder
import java.io.*;
import java.util.*;
public class MaxMinOrder {
static int[] arrange(int[] input) {
int[] a = input.clone(); // không sửa mảng của người gọi
Arrays.sort(a);
int[] out = new int[a.length];
int lo = 0, hi = a.length - 1, k = 0;
while (lo <= hi) {
out[k++] = a[hi--];
if (lo <= hi) out[k++] = a[lo++];
}
return out;
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer st = new StreamTokenizer(in); // nhanh hơn Scanner khi input lớn
st.nextToken();
int n = (int) st.nval;
int[] a = new int[n];
for (int i = 0; i < n; i++) { st.nextToken(); a[i] = (int) st.nval; }
StringJoiner sj = new StringJoiner(" ");
for (int v : arrange(a)) sj.add(String.valueOf(v));
System.out.println(sj);
}
}
Ghi nhớ
- Viết được hệ thức truy hồi cho lũy thừa nhanh, merge sort, Fibonacci ngây thơ và suy ra thời gian, độ sâu stack.
- Giải thích được vì sao gọi
pow(x, n/2)hai lần làm mất lợi thế O(log n). - Biết khi nào dùng memoization, khi nào chuyển sang tabulation, và vì sao không memoize bằng
computeIfAbsent. - Chuyển được một hàm đệ quy duyệt cây sang vòng lặp với
ArrayDeque, kể cả khi có chu trình. - Giải thích được vì sao
Arrays.sortdùng thuật toán khác nhau choint[]vàObject[].
Câu hỏi phỏng vấn
Junior
Điều kiện dừng (base case) của đệ quy là gì? Thiếu hoặc sai thì chuyện gì xảy ra?
Là trường hợp nhỏ nhất hàm trả kết quả ngay, không gọi lại chính nó (ví dụ n == 0). Thiếu hoặc sai thì hàm gọi mãi tới khi ném StackOverflowError.
Mỗi bước đệ quy phải tiến gần hơn tới điều kiện dừng. Bước không làm bài toán nhỏ đi (ví dụ n âm với điều kiện n == 0) cũng gây lặp vô tận. Vì vậy nên kiểm tra đầu vào không hợp lệ ngay đầu hàm.
Thuật toán sắp xếp ổn định (stable) là gì, khi nào điều đó quan trọng?
Ổn định nghĩa là các phần tử có khoá bằng nhau giữ nguyên thứ tự tương đối ban đầu. Quan trọng khi sắp nhiều lượt theo nhiều tiêu chí.
Ví dụ: sắp đơn hàng theo thời gian, rồi sắp ổn định theo trạng thái, thì trong cùng trạng thái vẫn giữ thứ tự thời gian. Trong Java, List.sort và Arrays.sort(Object[]) dùng TimSort nên ổn định. Arrays.sort(int[]) dùng Dual-Pivot Quicksort không ổn định, nhưng hai số nguyên thuỷ bằng nhau không phân biệt được nên không sao.
Mid
Lũy thừa nhanh và Fibonacci ngây thơ có độ phức tạp bao nhiêu? Giải thích bằng hệ thức truy hồi.
Lũy thừa nhanh: T(n) = T(n/2) + O(1), nên O(log n) thời gian và stack. Fibonacci ngây thơ: T(n) = T(n−1) + T(n−2) + O(1), số lời gọi tăng theo mũ cỡ 1,618ⁿ, stack chỉ O(n).
pow(x, n)gọi đúng một lầnpow(x, n/2)rồi làm O(1) việc. Nếu viếtpow(x, n/2) * pow(x, n/2)(gọi hai lần) thì T(n) = 2T(n/2) + O(1) = O(n), mất hết lợi thế.fib(30)cần khoảng 2,7 triệu lời gọi.
Memoization và tabulation khác nhau thế nào?
Cả hai lưu kết quả bài toán con để không tính lại; memoization đi top-down bằng đệ quy, tabulation đi bottom-up bằng vòng lặp.
- Memoization: giữ hàm đệ quy, tra bộ nhớ đệm trước khi tính. Dễ viết từ công thức, chỉ tính trạng thái cần, nhưng tốn stack và có thể tràn stack.
- Tabulation: điền bảng từ trường hợp nhỏ lên. Không dùng stack, thường rút gọn được bộ nhớ, nhưng phải tự xác định thứ tự tính. Fibonacci rút gọn còn hai biến, O(1) bộ nhớ.
Vì sao Arrays.sort dùng thuật toán khác nhau cho int[] và Object[]?
Số nguyên thuỷ không cần ổn định nên dùng Dual-Pivot Quicksort cho nhanh; object cần ổn định nên dùng TimSort.
- Dual-Pivot Quicksort: nhanh trên thực tế, sắp tại chỗ, thân thiện cache.
- TimSort: các phần tử “bằng nhau” theo comparator vẫn là object khác nhau. TimSort ổn định, O(n log n) xấu nhất, gần O(n) với dữ liệu gần như có thứ tự, đổi lại tốn thêm O(n) bộ nhớ.
- Comparator vi phạm hợp đồng (không bắc cầu) có thể làm TimSort ném
IllegalArgumentException: Comparison method violates its general contract.
Senior
Một hàm đệ quy chạy đúng với test nhưng sập trên production với StackOverflowError. Bạn xử lý thế nào?
Chuyển sang vòng lặp với stack/queue tường minh (ArrayDeque), hoặc đổi thuật toán để độ sâu là O(log n). Tăng -Xss chỉ là chữa cháy.
Nguyên nhân thường là độ sâu đệ quy tỉ lệ với kích thước dữ liệu thật: danh sách dài, cây suy biến thành đường thẳng, dữ liệu vòng lặp không có điều kiện dừng. Java không tối ưu tail call nên không viết lại dạng đệ quy đuôi được. Kèm theo: test với dữ liệu kích thước production và phát hiện chu trình bằng tập visited.
Từ vựng tiếng Anh
| Term | Phát âm | Nghĩa | Ví dụ câu tiếng Anh dùng trong phỏng vấn |
|---|---|---|---|
| base case | /beɪs keɪs/ | điều kiện dừng của đệ quy | “Every recursive function needs a base case, or it never stops.” |
| stack overflow | /stæk ˈoʊvərfloʊ/ | tràn stack | “Deep recursion on a long list caused a stack overflow in production.” |
| tail call | /teɪl kɔːl/ | lời gọi đuôi | “The JVM doesn’t optimise tail calls, so I convert deep recursion into a loop.” |
| two pointers | /tuː ˈpɔɪntərz/ | kỹ thuật hai con trỏ | “After sorting, I walk two pointers inward from both ends.” |
| recurrence relation | /rɪˈkɜːr.əns rɪˈleɪ.ʃən/ | hệ thức truy hồi | “The recurrence T(n) = T(n/2) + O(1) gives logarithmic time.” |
| memoization | /ˌmem.ə.waɪˈzeɪ.ʃən/ | ghi nhớ kết quả bài toán con | “Memoization turns the exponential Fibonacci into a linear one.” |
| stable sort | /ˈsteɪ.bəl sɔːrt/ | sắp xếp ổn định | “TimSort is a stable sort, so equal elements keep their original order.” |
| divide and conquer | /dɪˈvaɪd ənd ˈkɑːŋ.kər/ | chia để trị | “Merge sort is a classic divide-and-conquer algorithm.” |
| call stack | /kɔːl stæk/ | ngăn xếp lời gọi | “Each recursive call adds a frame to the call stack.” |
Ghi chép dựa trên khoá Fundamentals of Backend (Ronin Engineer), viết lại theo cách hiểu của mình.