Phỏng vấn 1: array, string và two pointers

Giới thiệu

Bạn luyện bài mảng chuỗi hay gặp nhất. Nói to suy nghĩ khi làm bài.

Kiến thức cần nhớ

Two pointers đối đầu

• Hai con trỏ đi từ hai đầu vào giữa.
• Hợp mảng đã sắp như tìm cặp tổng.
• Ví dụ đời thường: giống hai người đi từ hai đầu cầu.
• Gặp trùng thì bỏ qua để tránh đáp án lặp.

Two pointers đồng hướng

• Hai con trỏ cùng đi một chiều, một nhanh một chậm.
• Hợp dồn số 0 về cuối hoặc xóa tại chỗ.
• Ví dụ đời thường: giống hai người chạy cùng đường.
• Chỉ dùng bộ nhớ phụ hằng số.

Sliding window và chuỗi

• Sliding window là cửa sổ trượt trên mảng.
• Cửa cố định hợp đoạn dài k, cửa co giãn hợp ràng buộc.
• Ví dụ đời thường: giống khung nhìn trượt trên thước.
• Chuỗi hay gặp: đảo từ, đối xứng, tiền tố chung.

# hai con trỏ tìm cặp tổng
def cap_tong(a, k):
    t, p = 0, len(a) - 1  # hai đầu mảng
    while t < p:  # chưa gặp nhau
        s = a[t] + a[p]  # tổng hiện tại
        if s == k:  # trúng mục tiêu
            return (t, p)
        if s < k:  # tổng nhỏ, tăng trái
            t += 1
        else:  # tổng lớn, giảm phải
            p -= 1

Ví dụ

• Input [1, 2, 3, 4], k = 5 -> cặp (1, 3) vì 1 + 4 = 5.
• Input "hello" đảo từ đơn -> vẫn rõ từng từ.

💻 Bài tập

Luyện phỏng vấn: mỗi bài tự bấm giờ 25 phút, viết bằng ngôn ngữ bạn định dùng khi phỏng vấn. Nộp vào day-161/, mỗi bài 1 file có test.

Với mỗi bài, trước khi code, viết comment 3 dòng: ý tưởng, độ phức tạp thời gian, độ phức tạp bộ nhớ.

Bài 1: Hai con trỏ

1a: [-1,0,1,2,-1,-4] -> [[-1,-1,2], [-1,0,1]]
1b: "A man, a plan, a canal: Panama" -> true
1c: [0,1,0,3,12] -> [1,3,12,0,0]
1d: [1,8,6,2,5,4,8,3,7] -> 49

Bài 2: Cửa sổ trượt

2a: "abcabcbb" -> 3
2b: target=7, [2,3,1,2,4,3] -> 2
2c: s="cbaebabacd", p="abc" -> [0, 6]

Bài 3: Chuỗi và mô phỏng phỏng vấn (nâng cao)

1. Đảo thứ tự từ trong câu, bỏ khoảng trắng thừa: " the sky is blue " -> "blue is sky the".
2. Tiền tố chung dài nhất của mảng chuỗi.
3. Nhóm các từ là hoán vị của nhau.
4. Nhờ 1 người đóng vai người phỏng vấn cho 1 bài bất kỳ (hoặc tự ghi âm và nói to suy nghĩ). Ghi lại: thời gian, có hỏi làm rõ đề không, có tự kiểm tra biên không.

✅ Tiêu chí hoàn thành

• 10 bài có test gồm ca biên (rỗng, 1 phần tử, toàn trùng).
• Mỗi bài có comment độ phức tạp.
• Bảng thời gian thực tế mỗi bài so với 25 phút.
• Có ghi chú buổi phỏng vấn thử.

❓ Câu hỏi ôn tập

1. Two pointers đối đầu hợp mảng nào?
2. Đồng hướng dùng mấy chiều đi?
3. Cửa sổ co giãn dùng khi nào?
4. Think-aloud gồm mấy lượt?

🌕 Bạn đã hoàn thành ngày 161. Làm hết bài tập phía trên rồi sang ngày tiếp theo.