lthieu's notes

12-Practice-Big-Tech-2

11 min read

Navigation

← 11-Practice-Big-Tech-1 | → 01-Two-Pointers-Sliding-Window Giai đoạn: Big Tech Foundation | Loại: Mock Interview

Buổi 12 — Mock Interview: Big Tech Final

1. Mock Interview Format

Định dạng phỏng vấn 45 phút

Đây là buổi cuối cùng của giai đoạn Big Tech Foundation. Buổi này mô phỏng chính xác điều kiện phỏng vấn onsite tại các công ty Big Tech (Google, Meta, Amazon, Apple, Microsoft).

Cấu trúc 45 phút chuẩn:

Thời gianHoạt động
0–2 phútGiới thiệu (trong mock: skip, bắt đầu ngay)
2–5 phútĐọc đề, clarifying questions
5–10 phútNêu brute force + approach tối ưu
10–38 phútCode + giải thích từng bước
38–43 phútTest cases + edge cases
43–45 phútPhân tích Big-O, thảo luận trade-offs

Cách tự đánh giá sau mock:

Tiêu chíThang điểm
Hiểu đề đúng, không cần nhắc0–2
Nêu brute force trước0–1
Tối ưu approach trước khi code0–2
Code sạch, đọc được0–2
Giải thích khi code (think out loud)0–2
Test edge cases0–1
Big-O đúng0–2
Tổng0–12
  • 10–12: Strong Hire
  • 7–9: Hire
  • 4–6: No Hire (cần luyện thêm)
  • < 4: Strong No Hire

2. Mock Set A (Easier)

Problem A1: Longest Substring Without Repeating Characters (LeetCode #3)

Difficulty: Medium Topic: Sliding Window + HashMap

Đề bài: Cho chuỗi s, tìm độ dài của substring dài nhất không chứa ký tự lặp.

Ví dụ:

Input:  s = "abcabcbb"  → Output: 3  // "abc"
Input:  s = "bbbbb"     → Output: 1  // "b"
Input:  s = "pwwkew"    → Output: 3  // "wke"

Clarifying questions cần hỏi:

  • Input có thể là chuỗi rỗng không? → Trả về 0
  • Có chứa ký tự Unicode không? → Dùng Map thay vì array[128]
  • “Repeating” nghĩa là cùng ký tự, không phải cùng vị trí?

Approach:

  • Sliding window với 2 pointers left, right
  • Map lưu {character → last seen index}
  • Khi gặp ký tự đã trong window: di chuyển left đến vị trí sau lần xuất hiện gần nhất
function lengthOfLongestSubstring(s: string): number {
  // Map: character -> most recent index seen
  const charIndex = new Map<string, number>();
  let maxLen = 0;
  let left = 0;
 
  for (let right = 0; right < s.length; right++) {
    const char = s[right];
 
    // If char is in window (its last index >= left), shrink window
    if (charIndex.has(char) && charIndex.get(char)! >= left) {
      left = charIndex.get(char)! + 1;
    }
 
    // Update last seen index for this character
    charIndex.set(char, right);
 
    // Update max length
    maxLen = Math.max(maxLen, right - left + 1);
  }
 
  return maxLen;
}
 
// Test cases
console.log(lengthOfLongestSubstring("abcabcbb")); // 3
console.log(lengthOfLongestSubstring("bbbbb"));    // 1
console.log(lengthOfLongestSubstring("pwwkew"));   // 3
console.log(lengthOfLongestSubstring(""));         // 0 (edge case)
console.log(lengthOfLongestSubstring("au"));       // 2
console.log(lengthOfLongestSubstring("dvdf"));     // 3 ("vdf") — tricky!

Key Insight — "dvdf" Tricky Case

Khi right = 3 (char = ‘f’), map có ‘d’ tại index 0. Nhưng left = 2 (đã di chuyển qua ‘d’). Condition charIndex.get(char)! >= left → 0 >= 2 là false → không shrink. Đây là lý do dùng >= left chứ không phải chỉ has.

Complexity: Time O(N) | Space O(min(N, Σ)) — Σ là kích thước alphabet

Problem A2: Product of Array Except Self (LeetCode #238)

Difficulty: Medium Topic: Array + Prefix/Suffix Products

Đề bài: Cho mảng nums, trả về mảng output sao cho output[i] bằng tích của tất cả các phần tử trong nums ngoại trừ nums[i]. Không được dùng phép chia. Yêu cầu O(N) time, O(1) extra space (ngoài output array).

Ví dụ:

Input:  nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]
// output[0] = 2*3*4 = 24
// output[1] = 1*3*4 = 12
// output[2] = 1*2*4 = 8
// output[3] = 1*2*3 = 6

Tư duy:

  • output[i] = (tích tất cả bên trái i) × (tích tất cả bên phải i)
  • Pass 1: Điền output[i] = prefix product (tích từ đầu đến i-1)
  • Pass 2: Nhân thêm suffix product (tích từ i+1 đến cuối) từ phải qua trái
function productExceptSelf(nums: number[]): number[] {
  const n = nums.length;
  const output = new Array(n).fill(1);
 
  // Pass 1: output[i] = product of all elements to the LEFT of i
  let leftProduct = 1;
  for (let i = 0; i < n; i++) {
    output[i] = leftProduct;
    leftProduct *= nums[i];
  }
 
  // Pass 2: multiply output[i] by product of all elements to the RIGHT of i
  let rightProduct = 1;
  for (let i = n - 1; i >= 0; i--) {
    output[i] *= rightProduct;
    rightProduct *= nums[i];
  }
 
  return output;
}
 
// Test cases
console.log(productExceptSelf([1, 2, 3, 4]));    // [24, 12, 8, 6]
console.log(productExceptSelf([-1, 1, 0, -3, 3])); // [0, 0, 9, 0, 0]
 
// Walkthrough for [1,2,3,4]:
// After pass 1: output = [1, 1, 2, 6]
//   i=0: output[0]=1, leftProduct=1
//   i=1: output[1]=1, leftProduct=2
//   i=2: output[2]=2, leftProduct=6
//   i=3: output[3]=6, leftProduct=24
// After pass 2: output = [24, 12, 8, 6]
//   i=3: output[3]=6*1=6,  rightProduct=4
//   i=2: output[2]=2*4=8,  rightProduct=12
//   i=1: output[1]=1*12=12, rightProduct=24
//   i=0: output[0]=1*24=24, rightProduct=24

Complexity: Time O(N) | Space O(1) extra (output array doesn’t count)

3. Mock Set B (Harder)

Problem B1: Trapping Rain Water (LeetCode #42)

Difficulty: Hard Topic: Two Pointers / Stack / DP

Đề bài: Cho mảng height biểu diễn độ cao của các cột. Tính lượng nước mưa có thể giữ lại được.

Ví dụ:

Input:  height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Input:  height = [4,2,0,3,2,5]
Output: 9

Visualization:

           #
   #   #   ##  #
   #   # # ## ##
 # #   ######## #
_____________________
 0 1 0 2 1 0 1 3 2 1 2 1
       ↑       ↑
    Water trapped between walls

Solution 1: Two Pointer Approach (Optimal — O(1) Space)

Tư duy:

  • Lượng nước tại vị trí i = min(maxLeft[i], maxRight[i]) - height[i]
  • Dùng 2 pointers từ 2 đầu, di chuyển pointer có height nhỏ hơn vào giữa
  • Key insight: Nếu leftMax < rightMax, thì water tại left chỉ phụ thuộc vào leftMax (rightMax đã đủ cao để giữ nước)
function trap(height: number[]): number {
  let left = 0;
  let right = height.length - 1;
  let leftMax = 0;
  let rightMax = 0;
  let water = 0;
 
  while (left < right) {
    if (height[left] < height[right]) {
      // Left side is the bottleneck
      if (height[left] >= leftMax) {
        leftMax = height[left]; // Update left max wall
      } else {
        water += leftMax - height[left]; // Fill with water
      }
      left++;
    } else {
      // Right side is the bottleneck
      if (height[right] >= rightMax) {
        rightMax = height[right]; // Update right max wall
      } else {
        water += rightMax - height[right]; // Fill with water
      }
      right--;
    }
  }
 
  return water;
}

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

Solution 2: Stack Approach (Intuitive — Think Horizontally)

Tư duy:

  • Thay vì tính nước theo chiều dọc (từng cột), tính theo chiều ngang (từng layer)
  • Dùng Stack (monotonic decreasing) lưu indices
  • Khi gặp cột cao hơn đỉnh stack → tìm thấy “bức tường phải” → tính nước bị giữ
function trapStack(height: number[]): number {
  const stack: number[] = []; // stores indices, monotonic decreasing height
  let water = 0;
 
  for (let i = 0; i < height.length; i++) {
    // While current bar is higher than stack top — water can be trapped
    while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
      const bottom = stack.pop()!;          // The "floor" of the trapped water
 
      if (stack.length === 0) break;         // No left wall
 
      const leftWall = stack[stack.length - 1]; // Left boundary
      const rightWall = i;                       // Right boundary (current)
 
      const width = rightWall - leftWall - 1;
      const boundedHeight = Math.min(height[leftWall], height[rightWall]) - height[bottom];
 
      water += width * boundedHeight;
    }
 
    stack.push(i);
  }
 
  return water;
}
 
// Test both approaches
console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1])); // 6
console.log(trap([4,2,0,3,2,5]));               // 9
console.log(trapStack([0,1,0,2,1,0,1,3,2,1,2,1])); // 6
console.log(trapStack([4,2,0,3,2,5]));              // 9
console.log(trap([]));     // 0 (edge case)
console.log(trap([1]));    // 0 (edge case: single element)
console.log(trap([1,2]));  // 0 (edge case: two elements, no valley)

Khi nào dùng cách nào?

  • Two Pointer: Khi cần O(1) space. Khó hiểu hơn nhưng tối ưu nhất.
  • Stack: Trực quan hơn, dễ giải thích trong phỏng vấn. O(N) space.
  • Trong phỏng vấn: giải thích cả hai, code Two Pointer (sẽ impress interviewer hơn).

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

4. Post-Interview Analysis Template

Sau mỗi mock interview, điền vào template này để track progress:

## Mock Session — [DATE]
 
**Bài làm:** [Tên bài toán]
**Thời gian:** [X] / 45 phút
 
### What went well
-
-
 
### What went wrong
-
-
 
### Where I got stuck
- Bị kẹt tại: [mô tả]
- Thời gian bị kẹt: [X] phút
- Cách thoát: [tự tìm ra / cần gợi ý / xem solution]
 
### Code quality
- [ ] Code chạy được lần đầu?
- [ ] Đặt tên biến rõ ràng?
- [ ] Có edge cases không?
- [ ] Big-O đúng không?
 
### Pattern nhận diện
- Nhận ra pattern ngay? [ ] Yes [ ] No
- Pattern: [tên pattern]
 
### Score: [X] / 12
### Next action: [Ôn lại topic gì?]

5. Big Tech Foundation — Final Checklist

Đây là danh sách toàn bộ kỹ năng cần nắm vững trước khi chuyển sang FAANG Mastery.

Data Structures

  • Array: Two pointers, prefix sums, sliding window (basic)
  • HashMap / HashSet: Frequency count, grouping, de-duplication
  • Stack: Monotonic stack, valid parentheses, next greater element
  • Queue / Deque: BFS traversal, sliding window maximum
  • Linked List: Reverse, detect cycle, find middle, merge sorted lists
  • Binary Tree: Traversals (pre/in/post/level), height, diameter
  • BST: Insert, search, validate, in-order = sorted
  • Heap / Priority Queue: Top-K, K-th largest, merge K sorted lists
  • Graph (adjacency list): Build from edges, understand directed vs undirected

Algorithms

  • BFS: Shortest path (unweighted), level-order traversal
  • DFS: Tree traversal, island counting, path finding
  • Binary Search: On sorted array, on answer space
  • Backtracking: Permutations, subsets, N-Queens
  • Greedy: Activity selection, interval scheduling
  • Dynamic Programming (1D): Fibonacci, climbing stairs, house robber
  • Dynamic Programming (2D): Unique paths, longest common subsequence
  • Sorting: Understand merge sort, quick sort, when each is used

Problem Patterns

  • Two Sum / K Sum — HashMap
  • Sliding Window (fixed and variable size)
  • Fast & Slow Pointers — cycle detection
  • Merge Intervals — sorting + scanning
  • Top K Elements — heap
  • BFS for shortest path
  • DFS/Backtracking for combinations/permutations
  • DP — recognize optimal substructure

Soft Skills (phỏng vấn)

  • Think out loud — nói ra suy nghĩ khi code
  • Brute force trước, tối ưu sau
  • Hỏi clarifying questions trước khi code
  • Test với: empty input, single element, all-same elements, max size

6. Readiness Assessment

Bạn đã sẵn sàng cho FAANG Mastery chưa?

Làm bài test này: Tự chọn 5 bài random từ LeetCode tags: Array, String, LinkedList, Tree, Graph. Làm trong điều kiện thi (không gợi ý, có timer).

Rubric đánh giá:

Kết quảÝ nghĩa
5/5 bài, mỗi bài < 25 phútSẵn sàng 100% — tiến ngay
4/5 bài trong giờSẵn sàng — tiến nhưng ôn lại bài sai
3/5 bài trong giờÔn lại 2–3 topic yếu trước
< 3/5 bài trong giờCần thêm 1–2 tuần practice ở Foundation level

Câu hỏi tự kiểm tra:

  • Mình có thể code Two Sum trong 5 phút không?
  • Mình có thể giải thích tại sao BFS cho shortest path trong unweighted graph không?
  • Mình biết khi nào dùng DFS vs BFS không?
  • Mình có thể nhận ra pattern Sliding Window từ đề bài không?
  • Mình có thể implement Binary Search đúng (không off-by-one) không?

Nếu trả lời Yes tất cả → Bạn đã sẵn sàng.

7. Bridge to FAANG Phase

Chúc mừng! Bạn đã hoàn thành Big Tech Foundation!

Nhìn lại những gì đã học:

  • 10 data structures và algorithms cốt lõi
  • ~50+ LeetCode problems từ Easy đến Medium
  • Kỹ năng nhận diện pattern
  • Kỹ năng phỏng vấn cơ bản

FAANG Mastery sẽ đưa bạn lên level tiếp theo:

Giai đoạn FoundationGiai đoạn FAANG
Two Sum (HashMap)Two Pointers + Sliding Window nâng cao
Basic BFS/DFSGraph algorithms (Dijkstra, Topological Sort)
Simple DP (1D)DP nâng cao (Intervals, Trees, Games)
Basic Tree traversalAdvanced Tree (Segment Tree, Trie)
Sorting basicsCustom comparators, advanced sorting

5 patterns đầu tiên của FAANG Mastery:

  1. Two Pointers & Sliding Window ← bắt đầu ngay từ 01-Two-Pointers-Sliding-Window
  2. Bit Manipulation
  3. Advanced Graph (Union Find, Dijkstra)
  4. Advanced DP (Interval, Tree DP)
  5. Trie

Lời khuyên quan trọng nhất

Đừng rush sang FAANG Mastery nếu Foundation chưa vững. Một nền tảng chắc quan trọng hơn nhiều bài khó. Revisit file này bất cứ lúc nào cảm thấy “bị trôi”.

Tiếp theo: 01-Two-Pointers-Sliding-Window — Two Pointers & Sliding Window (FAANG Level)

Graph View

Backlinks