lthieu's notes

11-Practice-Big-Tech-1

13 min read

Navigation

← 10-Heap | → 12-Practice-Big-Tech-2 Giai đoạn: Big Tech Foundation | Loại: Practice Round

Buổi 11 — Practice Round 1: Big Tech Foundation

1. Mục tiêu buổi Practice

Timed Practice — Simulate Real Interview Conditions

Buổi này không dạy kiến thức mới. Mục tiêu duy nhất: luyện tập có thời gian giới hạn, giống hệt điều kiện phỏng vấn thực tế.

  • Mỗi bài Warm-up: tối đa 15 phút
  • Mỗi bài Core: tối đa 30 phút
  • Không xem gợi ý trước khi hết thời gian
  • Sau khi hết giờ: xem solution, phân tích điểm khác biệt

Mindset: Trong phỏng vấn thực, bạn sẽ bị áp lực thời gian. Buổi này rèn luyện khả năng suy nghĩ rõ ràng dưới áp lực đó.

Quy trình cho mỗi bài:

  1. Đọc đề — 2 phút, đọc kỹ, hỏi clarifying questions (tự hỏi)
  2. Brute force — nêu ra ngay, dù chưa tối ưu
  3. Tối ưu — tìm pattern, nêu approach trước khi code
  4. Code — viết sạch, có comments
  5. Test — chạy qua 2–3 test cases bằng tay
  6. Analyze — Big-O time và space

2. Warm-up Problems (15 phút mỗi bài)

Warm-up 1: Two Sum (Array + HashMap)

Đề bài: Cho mảng nums và số target. Trả về indices của 2 phần tử có tổng bằng target. Giả sử có đúng 1 đáp án.

Ví dụ:

Input:  nums = [2, 7, 11, 15], target = 9
Output: [0, 1]  // nums[0] + nums[1] = 2 + 7 = 9

Tư duy:

  • Brute force: 2 vòng lặp lồng nhau — O(N²)
  • Tối ưu: Với mỗi số x, ta cần tìm target - x. Dùng HashMap lưu {value → index}, tra cứu O(1)
function twoSum(nums: number[], target: number): number[] {
  // Map: value -> index
  const seen = new Map<number, number>();
 
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
 
    if (seen.has(complement)) {
      // Found the pair
      return [seen.get(complement)!, i];
    }
 
    // Store current number for future lookups
    seen.set(nums[i], i);
  }
 
  // Problem guarantees exactly one solution, so this is unreachable
  return [];
}
 
// Test cases
console.log(twoSum([2, 7, 11, 15], 9));   // [0, 1]
console.log(twoSum([3, 2, 4], 6));         // [1, 2]
console.log(twoSum([3, 3], 6));            // [0, 1]

Complexity: Time O(N) | Space O(N)

Warm-up 2: Reverse Linked List

Đề bài: Đảo ngược một singly linked list.

Ví dụ:

Input:  1 -> 2 -> 3 -> 4 -> 5 -> null
Output: 5 -> 4 -> 3 -> 2 -> 1 -> null

Tư duy: Dùng 3 con trỏ: prev, curr, next. Từng bước đảo ngược arrow.

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val: number, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}
 
function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let curr: ListNode | null = head;
 
  while (curr !== null) {
    const nextTemp = curr.next; // Save next before overwriting
    curr.next = prev;           // Reverse the arrow
    prev = curr;                // Move prev forward
    curr = nextTemp;            // Move curr forward
  }
 
  // prev is now the new head
  return prev;
}
 
// Recursive version (bonus — good to know for interviews)
function reverseListRecursive(head: ListNode | null): ListNode | null {
  // Base case: empty or single node
  if (head === null || head.next === null) return head;
 
  const newHead = reverseListRecursive(head.next);
  head.next.next = head; // Node behind us points back to us
  head.next = null;      // We point to nothing (will be overwritten)
  return newHead;
}

Complexity: Time O(N) | Space O(1) iterative, O(N) recursive (call stack)

Warm-up 3: Valid Parentheses

Đề bài: Cho chuỗi s chứa các ký tự (, ), {, }, [, ]. Kiểm tra xem chuỗi có hợp lệ không (đóng mở đúng thứ tự và loại).

Ví dụ:

Input:  s = "()[]{}"  → Output: true
Input:  s = "([)]"    → Output: false
Input:  s = "{[]}"    → Output: true

Tư duy: Dùng Stack. Gặp mở ngoặc → push. Gặp đóng ngoặc → pop và kiểm tra khớp.

function isValid(s: string): boolean {
  const stack: string[] = [];
 
  // Map closing bracket -> expected opening bracket
  const matchMap = new Map<string, string>([
    [')', '('],
    ['}', '{'],
    [']', '['],
  ]);
 
  for (const char of s) {
    if (!matchMap.has(char)) {
      // It's an opening bracket — push to stack
      stack.push(char);
    } else {
      // It's a closing bracket — check top of stack
      const top = stack.pop();
      if (top !== matchMap.get(char)) {
        return false; // Mismatch
      }
    }
  }
 
  // Stack must be empty — all opened brackets were closed
  return stack.length === 0;
}
 
// Test cases
console.log(isValid("()"));      // true
console.log(isValid("()[]{}")); // true
console.log(isValid("(]"));     // false
console.log(isValid("([)]"));   // false
console.log(isValid("{[]}"));   // true
console.log(isValid(""));       // true (edge case: empty string)

Complexity: Time O(N) | Space O(N)

3. Core Problems (30 phút mỗi bài)

Core 1: LRU Cache (HashMap + Doubly Linked List)

Đề bài: Thiết kế cấu trúc dữ liệu LRU Cache với capacity k. Implement get(key) và put(key, value). Cả hai phải chạy O(1).

Tư duy:

  • Cần truy cập O(1) → HashMap
  • Cần biết thứ tự “recently used” và xóa phần tử cũ nhất O(1) → Doubly Linked List
  • Kết hợp: HashMap lưu key → node, DLL duy trì thứ tự (head = most recent, tail = least recent)
class DLinkedNode {
  key: number;
  value: number;
  prev: DLinkedNode | null = null;
  next: DLinkedNode | null = null;
 
  constructor(key: number = 0, value: number = 0) {
    this.key = key;
    this.value = value;
  }
}
 
class LRUCache {
  private capacity: number;
  private cache: Map<number, DLinkedNode>;
  // Sentinel nodes — simplify edge case handling
  private head: DLinkedNode; // dummy head (most recently used side)
  private tail: DLinkedNode; // dummy tail (least recently used side)
 
  constructor(capacity: number) {
    this.capacity = capacity;
    this.cache = new Map();
 
    // Initialize doubly linked list with two sentinel nodes
    this.head = new DLinkedNode();
    this.tail = new DLinkedNode();
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
 
  get(key: number): number {
    if (!this.cache.has(key)) return -1;
 
    const node = this.cache.get(key)!;
    // Move to front (most recently used)
    this.moveToFront(node);
    return node.value;
  }
 
  put(key: number, value: number): void {
    if (this.cache.has(key)) {
      // Update existing node
      const node = this.cache.get(key)!;
      node.value = value;
      this.moveToFront(node);
    } else {
      // Insert new node
      const newNode = new DLinkedNode(key, value);
      this.cache.set(key, newNode);
      this.addToFront(newNode);
 
      // Evict LRU if over capacity
      if (this.cache.size > this.capacity) {
        const lru = this.tail.prev!; // node just before tail sentinel
        this.removeNode(lru);
        this.cache.delete(lru.key);
      }
    }
  }
 
  private addToFront(node: DLinkedNode): void {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next!.prev = node;
    this.head.next = node;
  }
 
  private removeNode(node: DLinkedNode): void {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }
 
  private moveToFront(node: DLinkedNode): void {
    this.removeNode(node);
    this.addToFront(node);
  }
}
 
// Test
const lru = new LRUCache(2);
lru.put(1, 1);   // cache: {1=1}
lru.put(2, 2);   // cache: {1=1, 2=2}
console.log(lru.get(1));  // 1 — cache: {2=2, 1=1} (1 moved to front)
lru.put(3, 3);   // evicts key 2 — cache: {1=1, 3=3}
console.log(lru.get(2));  // -1 (not found)
lru.put(4, 4);   // evicts key 1 — cache: {3=3, 4=4}
console.log(lru.get(1));  // -1
console.log(lru.get(3));  // 3
console.log(lru.get(4));  // 4

Complexity: Time O(1) for both get and put | Space O(capacity)

Core 2: Binary Tree Level Order Traversal

Đề bài: Cho binary tree, trả về danh sách các levels từ trên xuống dưới, mỗi level là một mảng.

Ví dụ:

Input:
    3
   / \
  9  20
    /  \
   15   7

Output: [[3], [9, 20], [15, 7]]

Tư duy: BFS với Queue. Mỗi “round” của vòng lặp xử lý hết một level.

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}
 
function levelOrder(root: TreeNode | null): number[][] {
  if (root === null) return [];
 
  const result: number[][] = [];
  const queue: TreeNode[] = [root];
  let head = 0; // Index pointer (O(1) dequeue) — xem 03-Stack-and-Queue § Pitfall 2
 
  while (head < queue.length) {
    const levelSize = queue.length - head; // Snapshot: how many nodes are in this level
    const currentLevel: number[] = [];
 
    for (let i = 0; i < levelSize; i++) {
      const node = queue[head++];
      currentLevel.push(node.val);
 
      // Add children for next level
      if (node.left !== null) queue.push(node.left);
      if (node.right !== null) queue.push(node.right);
    }
 
    result.push(currentLevel);
  }
 
  return result;
}

Key Insight

Chìa khóa của BFS level-order là snapshot levelSize = queue.length trước vòng lặp inner. Điều này đảm bảo bạn chỉ xử lý các node của level hiện tại, không lẫn với level tiếp theo đã được push vào queue.

Complexity: Time O(N) | Space O(N) — queue holds at most one full level at a time (worst case: last level has N/2 nodes)

Core 3: Number of Islands

Đề bài: Cho lưới 2D gồm '1' (đất) và '0' (nước). Đếm số lượng đảo. Một đảo là tập hợp các ô '1' kết nối nhau theo 4 hướng.

Ví dụ:

Input:
  11110
  11010
  11000
  00000
Output: 1

Input:
  11000
  11000
  00100
  00011
Output: 3

Tư duy: DFS/BFS. Với mỗi ô '1' chưa thăm, đó là một đảo mới. DFS từ đó đánh dấu toàn bộ đảo.

function numIslands(grid: string[][]): number {
  if (grid.length === 0) return 0;
 
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;
 
  function dfs(r: number, c: number): void {
    // Boundary check or water or already visited
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== '1') {
      return;
    }
 
    // Mark as visited by overwriting with '0'
    // (Alternative: use a separate visited[][] boolean array)
    grid[r][c] = '0';
 
    // Explore all 4 directions
    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  }
 
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++;
        dfs(r, c); // Sink the entire island
      }
    }
  }
 
  return count;
}
 
// BFS variant (iterative — avoids stack overflow on very large inputs)
function numIslandsBFS(grid: string[][]): number {
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;
  const directions = [[1,0],[-1,0],[0,1],[0,-1]];
 
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++;
        const queue: [number, number][] = [[r, c]];
        grid[r][c] = '0';
        let head = 0; // Index pointer (O(1) dequeue)
 
        while (head < queue.length) {
          const [row, col] = queue[head++];
          for (const [dr, dc] of directions) {
            const nr = row + dr;
            const nc = col + dc;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === '1') {
              grid[nr][nc] = '0';
              queue.push([nr, nc]);
            }
          }
        }
      }
    }
  }
 
  return count;
}

Complexity: Time O(M×N) | Space O(M×N) worst case (DFS call stack or BFS queue)

4. Pattern Drill

Nhìn vào mô tả bài toán → xác định pattern cần dùng trong vòng 30 giây.

#Mô tả bài toánPattern cần dùng
1Tìm 2 số trong mảng có tổng bằng targetHashMap / Two Pointers (if sorted)
2Tìm subarray dài nhất không có ký tự lặpSliding Window
3Kiểm tra có cycle trong linked list khôngFast/Slow Pointers (Floyd’s)
4Trả về k phần tử lớn nhất trong mảngMin-Heap (size k)
5Serialize/deserialize binary treeBFS Level Order / DFS Pre-order
6Tìm đường ngắn nhất trong graph không trọng sốBFS
7Implement cache với O(1) get/put, evict LRUHashMap + Doubly Linked List
8Tìm tất cả các hoán vị của một mảngBacktracking
9Kiểm tra mở ngoặc đóng ngoặc hợp lệStack
10Tính số đảo trong lưới 2DDFS/BFS (Flood Fill)

Cách luyện tập

Che cột “Pattern” lại. Đọc mô tả → suy nghĩ 30 giây → reveal đáp án. Lặp lại cho đến khi nhận ra ngay lập tức.

5. Self-Timer Challenge

Mock 45-Minute Interview Session

Đây là bước quan trọng nhất của buổi học này.

Setup:

  1. Đặt timer 45 phút
  2. Mở IDE sạch (không có gợi ý, autocomplete cơ bản thôi)
  3. Chọn 1 bài trong danh sách dưới — chọn ngẫu nhiên
  4. Không xem solution cho đến khi hết giờ

Danh sách bài thi thử:

  • Merge Intervals — LeetCode #56
  • Clone Graph — LeetCode #133
  • Word Search — LeetCode #79
  • Coin Change — LeetCode #322
  • Validate BST — LeetCode #98

Trong 45 phút, thực hiện:

[ ] 0-2  phút: Đọc đề, hỏi clarifying questions (tự nói to ra)
[ ] 2-5  phút: Trình bày brute force approach
[ ] 5-10 phút: Tối ưu approach, phân tích Big-O
[ ] 10-40 phút: Code sạch, có comments
[ ] 40-45 phút: Test với các edge cases

Sau khi hết giờ:

  1. So sánh solution của mình với solution chuẩn
  2. Ghi chú: mình bị kẹt ở đâu? Tại sao?
  3. Refactor code theo chuẩn (clean code)

6. Common Mistakes Review

Mistake #1: Off-by-one errors trong Two Pointers

Hay quên kiểm tra left < right vs left <= right. Trong binary search: mid = left + Math.floor((right - left) / 2) (không dùng (left + right) / 2 — có thể overflow).

Mistake #2: Không xử lý null/empty input

Luôn check if (!head), if (!root), if (nums.length === 0) trước khi làm bất cứ điều gì. Big Tech interviewer sẽ hỏi “what if input is empty/null?”

Mistake #3: Modify array/list trong khi đang iterate

Không được xóa/thêm phần tử vào array trong lúc đang loop qua nó. Nếu cần, dùng separate result array hoặc iterate ngược.

Mistake #4: Quên reset visited state trong DFS/BFS

Trong Number of Islands, nếu không đánh dấu visited (bằng cách set '0' hoặc dùng Set), sẽ bị infinite loop hoặc đếm sai. Luôn mark visited ngay khi enqueue, không phải khi dequeue.

Mistake #5: Dùng array index thay vì Map cho character frequency

const freq = new Array(26).fill(0) chỉ hoạt động với lowercase English letters. Trong phỏng vấn thực tế, hỏi “input có Unicode không?” — nếu có, dùng Map<string, number>.

7. Progress Tracking

Đánh giá độ tự tin của mình sau khi ôn xong mỗi topic:

  • ⭐ = Biết khái niệm nhưng chưa code được
  • ⭐⭐ = Code được với gợi ý
  • ⭐⭐⭐ = Code được trong 30 phút không cần gợi ý
  • ⭐⭐⭐⭐ = Optimize được, biết edge cases
  • ⭐⭐⭐⭐⭐ = Giải thích và dạy lại được
#TopicStatusConfidence
1Array & Two Pointers[ ] Done⭐⭐⭐
2HashMap & HashSet[ ] Done⭐⭐⭐
3Stack & Queue[ ] Done⭐⭐⭐
4Linked List[ ] Done⭐⭐⭐
5Binary Tree & BST[ ] Done⭐⭐⭐
6BFS & DFS[ ] Done⭐⭐⭐
7Recursion & Backtracking[ ] Done⭐⭐⭐
8Dynamic Programming (Intro)[ ] Done⭐⭐⭐
9Sorting & Binary Search[ ] Done⭐⭐⭐
10Heap[ ] Done⭐⭐⭐

Tổng điểm tự đánh giá:

  • 40–50 điểm: Sẵn sàng tiến sang FAANG Mastery
  • 30–39 điểm: Ôn lại 2–3 topic yếu trước
  • Dưới 30: Ôn lại từ đầu, tập trung vào practice

Xem tiếp: 12-Practice-Big-Tech-2 — Mock Interview Final

Graph View

Backlinks