Ngày 6 — DSA coding interview

Mục tiêu ngày 6

Sau ngày 6, bạn phải:

• Hiểu Big O đến mức tự tính được cho code lạ.
• Có pattern suy nghĩ khi gặp 1 bài DSA mới (không chỉ học thuộc lời giải).
• Giải tự tin 8–10 bài Easy trong LeetCode bằng C#.
• Trình bày out loud khi solve — đây là điểm interview quan trọng nhất.

1. Big O — phân tích độ phức tạp

1.1. Big O là gì?

1.2. Bảng so sánh trực quan

Cho n = 1000:

1.3. Cách tính Big O — quy tắc

Ví dụ tính Big O:

// Code 1
for (int i = 0; i < n; i++) {
    Console.WriteLine(i);
}
// → O(n) — vòng lặp chạy n lần

// Code 2
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        Console.WriteLine(i + j);
    }
}
// → O(n²) — 2 vòng lồng

// Code 3
for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        Console.WriteLine(i + j);
    }
}
// → Vẫn O(n²) — dù chỉ chạy n(n+1)/2 lần, bỏ hằng số ½

// Code 4
int i = n;
while (i > 0) {
    Console.WriteLine(i);
    i = i / 2;
}
// → O(log n) — i chia đôi mỗi lần

1.4. Time vs Space complexity

Time complexity: số phép tính theo input. Space complexity: bộ nhớ thêm dùng theo input (không tính input gốc).

public int Sum(int[] arr) {
    int sum = 0;            // O(1) space
    foreach (var x in arr) sum += x;
    return sum;
}
// Time: O(n), Space: O(1)

public int[] Double(int[] arr) {
    var result = new int[arr.Length];     // O(n) space
    for (int i = 0; i < arr.Length; i++) {
        result[i] = arr[i] * 2;
    }
    return result;
}
// Time: O(n), Space: O(n)

1.5. Cheat sheet — Big O của data structure C#

2. Framework 8 bước giải bài DSA

Framework:

1. UNDERSTAND   — đọc kỹ đề, vẽ ví dụ tay
2. CLARIFY      — hỏi interviewer giả định, edge case
3. BRUTE FORCE  — giải pháp đơn giản nhất, dù chậm
4. OPTIMIZE     — cải thiện complexity
5. DRY RUN      — chạy thử ví dụ bằng tay
6. CODE         — viết clean, có comment
7. COMPLEXITY   — phân tích Big O
8. EDGE CASES   — test mảng rỗng, 1 phần tử, duplicate...

Bây giờ áp dụng framework này cho từng bài.

3. Bài 1 — Two Sum (LC 1) — pattern HashMap

3.1. Step 1 — Understand

Đề: Cho int[] nums và int target. Tìm 2 chỉ số i, j sao cho nums[i] + nums[j] == target. Mỗi input có đúng 1 cặp.

Ví dụ: nums = [2, 7, 11, 15], target = 9 → output [0, 1] (vì nums[0] + nums[1] = 2 + 7 = 9).

3.2. Step 2 — Clarify (nói với interviewer)

• "Mảng có thể có số âm không?" → giả định: có.
• "Có thể dùng cùng index 2 lần không?" → không.
• "Số có thể trùng nhau không?" → có (vd [3, 3], target 6).
• "Có chắc chắn có solution không?" → đề bài nói có.
• "Output cần thứ tự index không?" → thường không, nhưng nên trả nhỏ trước.

3.3. Step 3 — Brute force

Suy nghĩ ban đầu: với mỗi cặp (i, j), check nums[i] + nums[j] == target. → 2 nested loop.

public int[] TwoSumBrute(int[] nums, int target) {
    for (int i = 0; i < nums.Length; i++) {
        for (int j = i + 1; j < nums.Length; j++) {
            if (nums[i] + nums[j] == target) {
                return new[] { i, j };
            }
        }
    }
    return Array.Empty<int>();
}

Complexity: O(n²) time, O(1) space.

"OK, đây là cách brute. Em sẽ tối ưu."

3.4. Step 4 — Optimize

Insight: với mỗi nums[i], ta cần tìm complement = target - nums[i] trong mảng. Tìm trong mảng = O(n) bằng linear, nhưng nếu lưu vào HashMap thì tìm O(1).

Ý tưởng: duyệt 1 lần. Mỗi số nums[i]:

1. Check xem complement = target - nums[i] đã trong map chưa.
2. Nếu có → đã tìm thấy cặp.
3. Nếu chưa → lưu nums[i] → i vào map, tiếp.

→ One-pass HashMap, O(n) time, O(n) space.

3.5. Step 5 — Dry run

nums = [2, 7, 11, 15], target = 9.

3.6. Step 6 — Code

public int[] TwoSum(int[] nums, int target) {
    var map = new Dictionary<int, int>();        // value → index
    for (int i = 0; i < nums.Length; i++) {
        int complement = target - nums[i];
        if (map.TryGetValue(complement, out int j)) {
            return new[] { j, i };               // j tìm thấy trước i
        }
        map[nums[i]] = i;                        // chưa thấy → lưu
    }
    return Array.Empty<int>();
}

3.7. Step 7 — Complexity

• Time: O(n) — duyệt mảng 1 lần. Mỗi thao tác HashMap (TryGetValue, set) là O(1) trung bình.
• Space: O(n) — map có thể chứa tới n entry trong worst case.

3.8. Step 8 — Edge cases

• Mảng rỗng → return empty. Đề bảo đảm có solution, nhưng code an toàn vẫn return empty.
• 1 phần tử → không có cặp → return empty.
• 2 phần tử trùng ([3, 3], target 6) → vòng đầu i=0, lưu 3 → 0. Vòng 2 i=1, complement=3, map có → return [0, 1]. ✅
• Số âm ([-3, 4, 3, 90], target 0) → tương tự. ✅
• Overflow: nếu nums có giá trị cực lớn, target - nums[i] có thể overflow int. Trong LeetCode, đề thường giới hạn → không cần lo, nhưng nói được điểm là plus.

3.9. Follow-up interviewer hay hỏi

4. Bài 2 — Valid Parentheses (LC 20) — pattern Stack

4.1. Understand + Clarify

Đề: Cho chuỗi s chỉ chứa ()[]{}. Kiểm tra parentheses hợp lệ — mở phải đóng đúng loại và đúng thứ tự.

Ví dụ:

• "()" → true.
• "()[]{}" → true.
• "(]" → false (sai loại).
• "([)]" → false (sai thứ tự).
• "" → true (empty hợp lệ).

Clarify: chuỗi có ký tự khác ()[]{} không? — Đề nói không.

4.2. Brute force

Suy nghĩ ban đầu: thay liên tục (), [], {} bằng rỗng cho đến khi không thay được. Nếu chuỗi rỗng cuối → hợp lệ.

public bool IsValidBrute(string s) {
    while (s.Contains("()") || s.Contains("[]") || s.Contains("{}")) {
        s = s.Replace("()", "").Replace("[]", "").Replace("{}", "");
    }
    return s.Length == 0;
}

Complexity: O(n²) hoặc tệ hơn vì mỗi replace là O(n).

4.3. Optimize — Stack

Insight: parentheses lồng nhau giống chồng đĩa — đóng phải khớp với mở gần nhất. Đó chính là Stack (LIFO).

Ý tưởng:

1. Duyệt từng ký tự.
2. Nếu là mở ((, [, {) → push vào stack.
3. Nếu là đóng (), ], }) → pop khỏi stack và check khớp.
4. Cuối: stack phải rỗng.

4.4. Dry run

s = "([])":

End: stack rỗng → ✅ valid.

s = "(]":

4.5. Code

public bool IsValid(string s) {
    var stack = new Stack<char>();
    var pairs = new Dictionary<char, char> {
        { ')', '(' },
        { ']', '[' },
        { '}', '{' }
    };
    
    foreach (var c in s) {
        if (pairs.ContainsValue(c)) {
            // ký tự mở → push
            stack.Push(c);
        }
        else if (pairs.TryGetValue(c, out char expectedOpen)) {
            // ký tự đóng → check
            if (stack.Count == 0 || stack.Pop() != expectedOpen) {
                return false;
            }
        }
    }
    
    return stack.Count == 0;        // còn ký tự mở chưa đóng?
}

4.6. Complexity

• Time: O(n) — duyệt chuỗi 1 lần, mỗi thao tác stack O(1).
• Space: O(n) — worst case "((((((" — toàn ký tự mở, stack chứa n.

4.7. Edge cases

• "" (rỗng) → loop không chạy, stack rỗng → return true. ✅
• ")" (chỉ đóng) → pop khi stack rỗng → return false. ✅
• "(" (chỉ mở) → loop push, end stack có 1 → return false. ✅
• "((((((" → toàn push, stack chứa hết → return false. ✅
• Hỗn hợp "({})[]" → đan xen vẫn OK miễn match đúng cặp.

4.8. Follow-up

5. Bài 3 — Reverse Linked List (LC 206) — pattern 3 con trỏ

5.1. Khái niệm Linked List

public class ListNode {
    public int Val;
    public ListNode? Next;
    public ListNode(int v = 0, ListNode? n = null) { Val = v; Next = n; }
}

Linked list = chuỗi node, mỗi node có giá trị + con trỏ Next. Hình dung:

head → [1|*] → [2|*] → [3|*] → [4|null]

5.2. Understand + Clarify

Đề: đảo ngược linked list. Trả head mới.

1 → 2 → 3 → 4 → null thành 4 → 3 → 2 → 1 → null.

5.3. Suy nghĩ

Insight: với mỗi node, đổi Next trỏ ngược về node trước. Cần track 3 thứ:

• prev — node trước (lúc đầu null vì head không có trước).
• curr — node hiện tại đang xử lý.
• next — lưu Next để không mất sau khi đổi.

5.4. Dry run

1 → 2 → 3 → null:

Bước 0: prev=null, curr=1
  next = 2
  curr.Next = prev (= null)
  → 1 → null
  prev = 1, curr = 2

Bước 1: prev=1, curr=2
  next = 3
  curr.Next = prev (= 1)
  → 2 → 1 → null
  prev = 2, curr = 3

Bước 2: prev=2, curr=3
  next = null
  curr.Next = prev (= 2)
  → 3 → 2 → 1 → null
  prev = 3, curr = null

Loop kết thúc (curr == null). Return prev = 3.

5.5. Code

public ListNode? Reverse(ListNode? head) {
    ListNode? prev = null;
    ListNode? curr = head;
    
    while (curr != null) {
        ListNode? next = curr.Next;     // 1. lưu next trước khi mất
        curr.Next = prev;                // 2. đảo ngược con trỏ
        prev = curr;                     // 3. dịch prev tiến
        curr = next;                     // 4. dịch curr tiến
    }
    
    return prev;        // prev cuối cùng = head mới
}

5.6. Complexity

• Time: O(n) — đi qua mỗi node 1 lần.
• Space: O(1) — chỉ dùng 3 biến.

5.7. Edge cases

• Empty list (head = null) → loop không chạy, return null. ✅
• 1 node → loop 1 lần, next = null, curr.Next = null (đã thế), prev = node, curr = null → return node. ✅
• 2 node → loop 2 lần đúng. ✅

5.8. Follow-up

1. "Đệ quy?" — Có:

public ListNode? ReverseRec(ListNode? head) {
    if (head == null || head.Next == null) return head;
    var rest = ReverseRec(head.Next);
    head.Next.Next = head;        // đảo
    head.Next = null;
    return rest;
}

Space O(n) do call stack. Iterative tốt hơn.

2. "Đảo k node một (LC 25)?" — kết hợp đảo + đếm.
3. "Đảo từ vị trí m đến n (LC 92)?" — find m và n, đảo trong đoạn.

6. Bài 4 — Binary Search (LC 704) — pattern Divide & Conquer

6.1. Khái niệm

6.2. Đề + suy nghĩ

Đề: mảng sorted nums, tìm target. Trả index hoặc -1.

Ý tưởng:

1. l = 0, r = length - 1.
2. mid = (l + r) / 2.
3. So sánh nums[mid] với target:
   • bằng → return mid.
   • bé hơn target → target ở nửa phải → l = mid + 1.
   • lớn hơn → nửa trái → r = mid - 1.
4. Loop tới l > r.

6.3. Dry run

nums = [-1, 0, 3, 5, 9, 12], target = 9:

target = 2:

l > r → return -1.

6.4. Code

public int Search(int[] nums, int target) {
    int l = 0, r = nums.Length - 1;
    
    while (l <= r) {
        int mid = l + (r - l) / 2;       // ⚠ tránh overflow (l+r)/2 với int lớn
        
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    
    return -1;
}

6.5. Bẫy nhỏ — overflow

6.6. Complexity

• Time: O(log n) — mỗi bước chia đôi.
• Space: O(1) iterative; O(log n) nếu đệ quy (call stack).

6.7. Edge cases

• Mảng rỗng → l = 0, r = -1, while không chạy → return -1. ✅
• Target nhỏ hơn min hoặc lớn hơn max → loop kết thúc với -1. ✅
• 1 phần tử bằng target → mid = 0, return 0. ✅
• 1 phần tử khác target → l > r → -1. ✅

6.8. Follow-up — pattern Binary Search nâng cao

7. Bài 5 — Maximum Subarray (LC 53) — pattern Kadane

7.1. Đề

Cho int[] nums, tìm contiguous subarray có tổng lớn nhất. Trả tổng đó.

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] → subarray [4, -1, 2, 1], tổng = 6.

7.2. Brute force

3 vòng lặp: i = start, j = end, sum trong đoạn → O(n³). Tối ưu thành O(n²) bằng cách tính sum tăng dần. Vẫn quá chậm với n lớn.

7.3. Insight — Kadane's algorithm

7.4. Dry run

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

Final: 6. ✅

7.5. Code

public int MaxSubArray(int[] nums) {
    int curr = nums[0];
    int best = nums[0];
    
    for (int i = 1; i < nums.Length; i++) {
        // Mở rộng hay bắt đầu mới?
        curr = Math.Max(nums[i], curr + nums[i]);
        // Cập nhật best
        best = Math.Max(best, curr);
    }
    
    return best;
}

7.6. Complexity

• Time: O(n) — 1 vòng.
• Space: O(1) — 2 biến.

7.7. Edge cases

• Mảng 1 phần tử → return luôn nó.
• Mảng toàn âm [-3, -1, -5] → best = -1 (max trong các phần tử). ✅
• Mảng toàn dương → best = tổng cả mảng.

8. Bài 6 — Valid Anagram (LC 242) — pattern frequency count

8.1. Đề

Cho 2 chuỗi s, t. Check t có phải anagram của s không (chứa cùng ký tự với cùng tần suất).

s = "anagram", t = "nagaram" → true.

8.2. Suy nghĩ

3 cách:

Cách 1 — Sort + compare:

return new string(s.OrderBy(c => c).ToArray()) ==
       new string(t.OrderBy(c => c).ToArray());

Time O(n log n), Space O(n).

Cách 2 — Count + map (Unicode):

var count = new Dictionary<char, int>();
foreach (var c in s) count[c] = count.GetValueOrDefault(c) + 1;
foreach (var c in t) {
    if (!count.ContainsKey(c) || --count[c] < 0) return false;
}
return true;

Time O(n), Space O(k).

Cách 3 — Count array (chỉ a-z):

if (s.Length != t.Length) return false;
var cnt = new int[26];
foreach (var c in s) cnt[c - 'a']++;
foreach (var c in t) {
    if (--cnt[c - 'a'] < 0) return false;
}
return true;

Time O(n), Space O(1) (alphabet cố định).

8.3. Optimize chọn cách 3

Insight 1: length phải bằng nhau → check trước, early return.

Insight 2: alphabet a-z có 26 → int[26] đủ, không cần Dictionary (cấp phát object đắt hơn).

Insight 3: chỉ cần 1 vòng tăng cho s và 1 vòng giảm cho t → nếu phần tử nào âm tức là t có ký tự s không có.

8.4. Dry run

s = "abc", t = "bca":

cnt = [0]*26
Sau loop s: cnt['a']=1, cnt['b']=1, cnt['c']=1 → [1,1,1,0,...]
Loop t:
  'b': --cnt['b'] → 0, OK.
  'c': --cnt['c'] → 0, OK.
  'a': --cnt['a'] → 0, OK.
End → return true.

s = "abc", t = "abd": length bằng, nhưng vòng t có 'd' chưa có trong s → cnt'd' = -1 < 0 → return false.

8.5. Complexity

• Time: O(n).
• Space: O(1) — array 26 cố định.

8.6. Edge case

• Length khác → false.
• Empty + empty → loop không chạy, return true.
• Có ký tự ngoài a-z → cách này crash. Phải hỏi clarify hoặc dùng Dictionary.

8.7. Follow-up

• "Unicode (tiếng Việt, emoji)?" → Dùng Dictionary thay int26.
• "Group Anagrams (LC 49)?" → key = chuỗi sorted, group bằng map.

9. Lộ trình LeetCode 1 tuần (sau ngày 6)

Mỗi ngày 2-3 bài Easy, áp dụng framework 8 bước. Đừng chỉ đọc — gõ + chạy trong LeetCode.

10. Câu hỏi tự test cuối ngày

Tham khảo thêm 38 bài DSA (ngắn hơn, kèm code): Ngân hàng câu hỏi DSA.

➡️ Ngày mai: Ngày 7 — Mock interview