Để đạt được thành công trong buổi phỏng vấn cho vị trí Python Developer, ứng viên không chỉ cần nắm vững kiến thức nền tảng mà còn phải đối mặt với những câu hỏi chuyên sâu, đặc biệt về thuật toán và cấu trúc dữ liệu. Sau đây là tổng hợp các câu hỏi phỏng vấn Python Developer, tập trung vào các câu hỏi thuật toán phổ biến, kèm theo câu trả lời cực kỳ chi tiết (có code).

Đọc bài viết sau để nắm cách trả lời các câu hỏi phỏng vấn Python thuộc chủ đề:

  • Câu hỏi phỏng vấn Python về Thuật toán Sắp xếp (Sorting Algorithm)
  • Câu hỏi phỏng vấn Python về Thuật toán Tìm kiếm (Search Algorithm)
  • Câu hỏi phỏng vấn Python về Cấu trúc Dữ liệu Cơ bản (Basic Data Structure)
  • Câu hỏi phỏng vấn Python vềThuật toán trên Đồ thị (Graph Algorithm)
  • Câu hỏi phỏng vấn Python vềThuật toán Quy hoạch Động (Dynamic Programming)
  • Câu hỏi phỏng vấn Python về Thuật toán Tham lam (Greedy Algorithm)
  • Câu hỏi phỏng vấn Python vềThuật toán Xử lý Chuỗi (String Algorithm)
  • Câu hỏi phỏng vấn Python vềThuật toán Toán học (Mathematical Algorithm)

Python là gì?

Python là một ngôn ngữ lập trình cấp cao, nổi bật với cú pháp đơn giản và dễ đọc. Điều này giúp Python trở thành lựa chọn lý tưởng cho những người mới bắt đầu học lập trình cũng như các chuyên gia trong ngành. Bên cạnh đó, Python còn có thư viện phong phú, hỗ trợ mạnh mẽ trong các lĩnh vực như phân tích dữ liệu, phát triển AI, và web.

Python được ứng dụng rộng rãi trong nhiều lĩnh vực như khoa học dữ liệu, trí tuệ nhân tạo, phát triển web, tự động hóa, và cả trong phát triển game. Những công ty công nghệ lớn như Google, Facebook, và Netflix đều sử dụng Python để phát triển sản phẩm của họ.

Đọc thêm: Python là gì: Tổng quan định nghĩa, Cú pháp và Thư viện Python

Những vị trí cần nắm các câu hỏi phỏng vấn Python

Mỗi vị trí sử dụng Python lại có những yêu cầu riêng và các câu hỏi phỏng vấn Python cũng sẽ khác nhau. Dưới đây là các nhóm vị trí điển hình và các chủ đề phỏng vấn thường gặp:

Nhóm Khoa học Dữ liệu (Data Science Team)

  • Nhà khoa học dữ liệu (Data Scientist): Tập trung vào khả năng xử lý dữ liệu lớn, phân tích số liệu và làm việc với các thư viện như Pandas, NumPy.
  • Kỹ sư dữ liệu (Data Engineer): Ứng viên cần nắm vững cách thiết kế hệ thống xử lý dữ liệu, pipeline, và các công cụ ETL.
  • Kỹ sư học máy (Machine Learning Engineer): Câu hỏi thường xoay quanh các thuật toán học máy và cách triển khai mô hình sử dụng thư viện như TensorFlow, scikit-learn.
  • Chuyên viên phân tích tài chính định lượng: Cần biết cách xây dựng các mô hình định lượng, sử dụng thư viện tài chính và thuật toán tính toán nhanh.

Nhóm Phát triển (Developer Team)

  • Lập trình viên Python: Các câu hỏi thường tập trung vào lập trình cơ bản, xử lý file, và giải quyết các vấn đề liên quan đến tối ưu hóa mã nguồn.
  • Lập trình viên Web: Cần hiểu rõ về các framework phổ biến như Django, Flask và các kiến thức về backend.
  • Kỹ sư tự động hóa (Automation Engineer): Câu hỏi thường liên quan đến việc tạo và quản lý các script tự động hóa, kiểm thử hệ thống.
  • Kỹ sư DevOps: Ứng viên cần am hiểu về việc triển khai mã nguồn, CI/CD, và quản lý hệ thống máy chủ.
  • Nhà phát triển IoT (Internet of Things): Phỏng vấn có thể liên quan đến lập trình nhúng và giao tiếp giữa các thiết bị IoT.
  • Chuyên viên an ninh mạng: Các câu hỏi về mã hóa, bảo mật và cách xử lý các cuộc tấn công bảo mật.

Nhóm Phát triển Game (Game Team)

  • Nhà phát triển game: Cần hiểu rõ về các công cụ phát triển game và cách lập trình tương tác thời gian thực.

Danh sách các chủ đề câu hỏi phỏng vấn Python trong bài viết

Sau đây là các chủ đề thuật toán quan trọng sẽ được thực hành và có khả năng xuất hiện trong bài viết câu hỏi phỏng vấn Python này. Mỗi phần sẽ được trình bày thành các nhóm thuật toán kèm theo ví dụ và diễn giải chi tiết.

Thuật toán Sắp xếp (Sorting Algorithm)

Thuật toán sắp xếp là các phương pháp được sử dụng để sắp xếp một tập hợp dữ liệu theo một thứ tự nhất định (tăng dần hoặc giảm dần). Việc sắp xếp dữ liệu giúp tăng hiệu quả trong việc tìm kiếm và quản lý thông tin.

  • Bubble Sort: Thuật toán sắp xếp nổi bọt hoạt động bằng cách liên tục so sánh và hoán đổi các cặp phần tử liền kề nếu chúng ở sai thứ tự. Quá trình này được lặp lại cho đến khi không còn cặp phần tử nào cần hoán đổi.
  • Insertion Sort: Thuật toán chèn trực tiếp xây dựng danh sách sắp xếp bằng cách lấy từng phần tử và chèn nó vào vị trí đúng trong danh sách đã sắp xếp trước đó.
  • Selection Sort: Thuật toán chọn trực tiếp tìm phần tử nhỏ nhất (hoặc lớn nhất) trong danh sách và đặt nó ở vị trí đầu tiên, sau đó lặp lại quá trình cho phần còn lại của danh sách.
  • Quick Sort: Thuật toán sắp xếp nhanh sử dụng phương pháp chia để trị bằng cách chọn một phần tử làm “pivot” và phân chia danh sách thành hai phần dựa trên pivot, sau đó sắp xếp đệ quy các phần này.
  • Merge Sort: Thuật toán trộn sử dụng phương pháp chia để trị bằng cách chia danh sách thành hai nửa, sắp xếp từng nửa và sau đó trộn hai nửa đã sắp xếp lại với nhau.

Thuật toán Tìm kiếm (Search Algorithm)

Thuật toán tìm kiếm được sử dụng để tìm một phần tử cụ thể trong một cấu trúc dữ liệu. Chúng giúp tăng tốc độ truy xuất và xử lý dữ liệu.

  • Linear Search: Tìm kiếm tuyến tính duyệt qua từng phần tử trong danh sách cho đến khi tìm thấy phần tử cần tìm hoặc đến cuối danh sách.
  • Binary Search: Tìm kiếm nhị phân yêu cầu danh sách đã được sắp xếp. Thuật toán này so sánh phần tử cần tìm với phần tử ở giữa danh sách và loại bỏ một nửa danh sách trong mỗi bước, giúp giảm đáng kể số lần so sánh.

Cấu trúc Dữ liệu Cơ bản (Basic Data Structure)

Cấu trúc dữ liệu là cách tổ chức và lưu trữ dữ liệu để truy cập và sửa đổi một cách hiệu quả.

  • Stack: Ngăn xếp là cấu trúc dữ liệu LIFO (Last In, First Out), nơi phần tử được thêm vào và lấy ra ở cùng một đầu.
  • Queue: Hàng đợi là cấu trúc dữ liệu FIFO (First In, First Out), nơi phần tử được thêm vào ở cuối và lấy ra ở đầu.
  • Linked List: Danh sách liên kết là một chuỗi các node, mỗi node chứa dữ liệu và con trỏ đến node tiếp theo trong danh sách.
  • Tree: Cây là cấu trúc dữ liệu phân cấp với một node gốc và các node con, được sử dụng để biểu diễn dữ liệu có mối quan hệ thứ bậc.
  • Graph: Đồ thị là tập hợp các đỉnh (node) và các cạnh (edge) kết nối các đỉnh, dùng để biểu diễn các mối quan hệ phức tạp giữa các đối tượng.

Thuật toán trên Đồ thị (Graph Algorithm)

Thuật toán đồ thị được sử dụng để xử lý và phân tích các cấu trúc dữ liệu dạng đồ thị.

  • Depth-First Search (DFS): Duyệt theo chiều sâu, khám phá càng xa càng tốt theo mỗi nhánh trước khi quay lại.
  • Breadth-First Search (BFS): Duyệt theo chiều rộng, khám phá tất cả các đỉnh ở mức hiện tại trước khi chuyển sang mức tiếp theo.
  • Dijkstra’s Algorithm: Thuật toán Dijkstra tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác trong đồ thị với trọng số không âm.
  • Kruskal’s Algorithm: Thuật toán Kruskal tìm cây khung nhỏ nhất của một đồ thị bằng cách sắp xếp các cạnh theo trọng số và thêm chúng vào cây khung nếu không tạo thành chu trình.
  • Prim’s Algorithm: Thuật toán Prim cũng tìm cây khung nhỏ nhất, bắt đầu từ một đỉnh và liên tục thêm cạnh nhỏ nhất kết nối đỉnh đã thăm và đỉnh chưa thăm.

Thuật toán Quy hoạch Động (Dynamic Programming)

Quy hoạch động là kỹ thuật giải quyết các vấn đề bằng cách chia nhỏ chúng thành các bài toán con và lưu trữ kết quả để tránh tính toán lại.

  • Knapsack Problem: Bài toán cái túi, mục tiêu là chọn các vật phẩm để tối đa hóa giá trị tổng trong khi không vượt quá giới hạn trọng lượng của túi.
  • Longest Common Subsequence: Tìm chuỗi con chung dài nhất giữa hai chuỗi, ứng dụng trong so sánh văn bản và phân tích DNA.

Thuật toán Tham lam (Greedy Algorithm)

Thuật toán tham lam chọn lựa tối ưu cục bộ tại mỗi bước với hy vọng đạt được tối ưu toàn cục.

  • Coin Change Problem: Bài toán đổi tiền, tìm số lượng ít nhất các đồng xu để đạt được một số tiền nhất định.
  • Activity Selection Problem: Chọn tối đa số hoạt động không chồng chéo nhau dựa trên thời gian bắt đầu và kết thúc.

Thuật toán Xử lý Chuỗi (String Algorithm)

Thuật toán xử lý chuỗi được thiết kế để giải quyết các vấn đề liên quan đến chuỗi ký tự.

  • KMP Algorithm: Thuật toán Knuth-Morris-Pratt tìm kiếm mẫu trong văn bản bằng cách sử dụng bảng lặp lại để tránh so sánh lại các ký tự đã biết.
  • Rabin-Karp Algorithm: Sử dụng hàm băm để tìm kiếm chuỗi mẫu trong văn bản, hiệu quả khi tìm kiếm nhiều mẫu cùng lúc.

Thuật toán Toán học (Mathematical Algorithm)

Thuật toán toán học giải quyết các vấn đề số học và lý thuyết số.

  • Euclidean Algorithm: Thuật toán Euclid tìm ước số chung lớn nhất (GCD) của hai số nguyên bằng cách lặp lại phép chia.
  • Sieve of Eratosthenes: Thuật toán sàng Eratosthenes tìm tất cả các số nguyên tố nhỏ hơn một số n bằng cách loại bỏ các bội số của mỗi số nguyên tố.

Các câu hỏi phỏng vấn Python về Thuật toán Sắp xếp (Sorting Algorithm)

Câu hỏi về Bubble Sort

Bubble Sort là một thuật toán sắp xếp đơn giản hoạt động bằng cách lặp đi lặp lại qua danh sách cần sắp xếp, so sánh từng cặp phần tử liền kề và hoán đổi chúng nếu chúng ở sai thứ tự.

Bài toán:

Cho một danh sách các số nguyên chưa được sắp xếp. Hãy sử dụng thuật toán Bubble Sort để sắp xếp danh sách này theo thứ tự tăng dần. Hiển thị quá trình sắp xếp từng bước.

Danh sách ban đầu: [64, 34, 25, 12, 22, 11, 90]

Lời giải:

def bubble_sort(arr):
    n = len(arr)
    # Duyệt qua tất cả các phần tử của mảng
    for i in range(n):
        # Duyệt qua mảng từ 0 đến n-i-1
        for j in range(0, n - i - 1):
            # So sánh và hoán đổi nếu phần tử tìm thấy lớn hơn phần tử kế tiếp
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
        print(f"Bước {i+1}: {arr}")

# Ví dụ
arr = [64, 34, 25, 12, 22, 11, 90]
print(f"Danh sách ban đầu: {arr}")
bubble_sort(arr)
print(f"Danh sách sau khi sắp xếp: {arr}")

Kết quả:

Danh sách ban đầu: [64, 34, 25, 12, 22, 11, 90]
Bước 1: [34, 25, 12, 22, 11, 64, 90]
Bước 2: [25, 12, 22, 11, 34, 64, 90]
Bước 3: [12, 22, 11, 25, 34, 64, 90]
Bước 4: [12, 11, 22, 25, 34, 64, 90]
Bước 5: [11, 12, 22, 25, 34, 64, 90]
Bước 6: [11, 12, 22, 25, 34, 64, 90]
Bước 7: [11, 12, 22, 25, 34, 64, 90]
Danh sách sau khi sắp xếp: [11, 12, 22, 25, 34, 64, 90]

Giải thích:

  • Bước 1: Phần tử lớn nhất “nổi” lên cuối danh sách.
  • Bước 2-5: Tiếp tục “nổi” các phần tử lớn còn lại lên vị trí đúng.
  • Bước 6-7: Không còn sự hoán đổi, thuật toán kết thúc.

Câu hỏi về Insertion Sort

Insertion Sort xây dựng danh sách sắp xếp cuối cùng một cách dần dần. Mỗi phần tử từ danh sách chưa sắp xếp được chèn vào vị trí đúng trong danh sách đã sắp xếp.

Bài toán:

Cho một danh sách các số nguyên chưa được sắp xếp. Sử dụng thuật toán Insertion Sort để sắp xếp danh sách theo thứ tự tăng dần. Hiển thị quá trình chèn từng phần tử.

Danh sách ban đầu: [12, 11, 13, 5, 6]

Lời giải:

def insertion_sort(arr):
    # Duyệt qua từ phần tử thứ hai đến hết
    for i in range(1, len(arr)):
        key = arr[i]
        # Di chuyển các phần tử lớn hơn key về sau một vị trí
        j = i - 1
        while j >=0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
        print(f"Bước {i}: {arr}")

# Ví dụ
arr = [12, 11, 13, 5, 6]
print(f"Danh sách ban đầu: {arr}")
insertion_sort(arr)
print(f"Danh sách sau khi sắp xếp: {arr}")

Kết quả:

Danh sách ban đầu: [12, 11, 13, 5, 6]
Bước 1: [11, 12, 13, 5, 6]
Bước 2: [11, 12, 13, 5, 6]
Bước 3: [5, 11, 12, 13, 6]
Bước 4: [5, 6, 11, 12, 13]
Danh sách sau khi sắp xếp: [5, 6, 11, 12, 13]

Giải thích:

  • Bước 1: Chèn 11 vào vị trí đứng trước 12.
  • Bước 2: Phần tử đang xét là 13, đang ở đúng vị trí nên không thay đổi
  • Bước 3: Chèn 5 vào đầu danh sách.
  • Bước 4: Chèn 6 vào vị trí giữa 511.

Câu hỏi về Selection Sort

Selection Sort hoạt động bằng cách liên tục tìm phần tử nhỏ nhất trong danh sách chưa được sắp xếp và hoán đổi nó với phần tử đầu tiên của danh sách chưa sắp xếp.

Bài toán:

Cho một danh sách các số nguyên chưa được sắp xếp. Sử dụng thuật toán Selection Sort để sắp xếp danh sách theo thứ tự tăng dần. Hiển thị quá trình chọn và hoán đổi từng phần tử.

Danh sách ban đầu: [64, 25, 12, 22, 11]

Lời giải:

def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        # Tìm phần tử nhỏ nhất trong danh sách chưa sắp xếp
        for j in range(i+1, len(arr)):
            if arr[min_idx] > arr[j]:
                min_idx = j
        # Hoán đổi phần tử nhỏ nhất với phần tử đầu tiên
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
        print(f"Bước {i+1}: {arr}")

# Ví dụ
arr = [64, 25, 12, 22, 11]
print(f"Danh sách ban đầu: {arr}")
selection_sort(arr)
print(f"Danh sách sau khi sắp xếp: {arr}")

Kết quả:

Danh sách ban đầu: [64, 25, 12, 22, 11]
Bước 1: [11, 25, 12, 22, 64]
Bước 2: [11, 12, 25, 22, 64]
Bước 3: [11, 12, 22, 25, 64]
Bước 4: [11, 12, 22, 25, 64]
Bước 5: [11, 12, 22, 25, 64]
Danh sách sau khi sắp xếp: [11, 12, 22, 25, 64]

Giải thích:

  • Bước 1: Tìm phần tử nhỏ nhất (11) và hoán đổi với 64.
  • Bước 2: Tìm phần tử nhỏ nhất còn lại (12) và hoán đổi với 25.
  • Bước 3: Tìm phần tử nhỏ nhất còn lại (22) và hoán đổi với 25.
  • Bước 4 và 5: xét 2 phần thử 25 và 64 đã ở đúng thứ tự nên không hoán đổi

Câu hỏi về Quick Sort

Quick Sort là một thuật toán sắp xếp phân chia và trị. Nó chọn một “chốt” (pivot) và phân chia danh sách thành hai phần: phần nhỏ hơn chốt và phần lớn hơn chốt.

Bài toán:

Cho một danh sách các số nguyên chưa được sắp xếp. Sử dụng thuật toán Quick Sort để sắp xếp danh sách theo thứ tự tăng dần. Hiển thị quá trình phân chia và sắp xếp.

Danh sách ban đầu: [10, 7, 8, 9, 1, 5]

Lời giải:

def partition(arr, low, high):
    i = low - 1
    pivot = arr[high]  # Chọn chốt là phần tử cuối

    for j in range(low, high):
        # Nếu phần tử hiện tại nhỏ hơn hoặc bằng chốt
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    # Hoán đổi chốt vào vị trí đúng
    arr[i+1], arr[high] = arr[high], arr[i+1]
    print(f"Phân đoạn với chốt {pivot}: {arr}")
    return i + 1

def quick_sort(arr, low, high):
    if low < high:
        # pi là chỉ số phân chia, arr[pi] đã ở vị trí đúng
        pi = partition(arr, low, high)
        # Sắp xếp đệ quy các phần tử trước và sau phân chia
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

# Ví dụ
arr = [10, 7, 8, 9, 1, 5]
print(f"Danh sách ban đầu: {arr}")
quick_sort(arr, 0, len(arr) - 1)
print(f"Danh sách sau khi sắp xếp: {arr}")

Kết quả:

Danh sách ban đầu: [10, 7, 8, 9, 1, 5]
Phân đoạn với chốt 5: [1, 5, 8, 9, 10, 7]
Phân đoạn với chốt 1: [1, 5, 8, 9, 10, 7]
Phân đoạn với chốt 7: [1, 5, 7, 9, 10, 8]
Phân đoạn với chốt 8: [1, 5, 7, 8, 10, 9]
Phân đoạn với chốt 9: [1, 5, 7, 8, 9, 10]
Danh sách sau khi sắp xếp: [1, 5, 7, 8, 9, 10]

Giải thích:

  • Phân đoạn 1: Chọn chốt 5, sắp xếp các phần tử nhỏ hơn bên trái và lớn hơn bên phải.
  • Phân đoạn 2-5: Tiếp tục áp dụng Quick Sort đệ quy lên các phân đoạn nhỏ hơn.

Câu hỏi về Merge Sort

Merge Sort là một thuật toán sắp xếp phân chia và trị. Nó chia danh sách thành hai nửa, sắp xếp từng nửa và sau đó gộp hai nửa đã sắp xếp lại.

Bài toán:

Cho một danh sách các số nguyên chưa được sắp xếp. Sử dụng thuật toán Merge Sort để sắp xếp danh sách theo thứ tự tăng dần. Hiển thị quá trình chia và gộp.

Danh sách ban đầu: [12, 11, 13, 5, 6, 7]

Lời giải:

def merge(arr, l, m, r):
    # Tạo bản sao của hai nửa
    L = arr[l:m+1]
    R = arr[m+1:r+1]

    i = j = 0  # Chỉ số ban đầu của hai nửa
    k = l      # Chỉ số ban đầu của mảng phụ

    # Gộp hai nửa lại
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1

    # Sao chép các phần tử còn lại của L[]
    while i < len(L):
        arr[k] = L[i]
        i += 1
        k += 1

    # Sao chép các phần tử còn lại của R[]
    while j < len(R):
        arr[k] = R[j]
        j += 1
        k += 1

    print(f"Gộp {arr[l:r+1]}")

def merge_sort(arr, l, r):
    if l < r:
        m = (l + r) // 2
        # Sắp xếp nửa đầu tiên
        merge_sort(arr, l, m)
        # Sắp xếp nửa thứ hai
        merge_sort(arr, m + 1, r)
        # Gộp hai nửa đã sắp xếp
        merge(arr, l, m, r)

# Ví dụ
arr = [12, 11, 13, 5, 6, 7]
print(f"Danh sách ban đầu: {arr}")
merge_sort(arr, 0, len(arr) - 1)
print(f"Danh sách sau khi sắp xếp: {arr}")

Kết quả:

Danh sách ban đầu: [12, 11, 13, 5, 6, 7]
Gộp [11, 12]
Gộp [5, 13]
Gộp [5, 11, 12, 13]
Gộp [6, 7]
Gộp [5, 6, 7, 11, 12, 13]
Danh sách sau khi sắp xếp: [5, 6, 7, 11, 12, 13]

Giải thích:

  • Chia: Danh sách được chia thành các nửa nhỏ hơn đến khi mỗi phần chỉ còn một phần tử.
  • Gộp: Các phần tử được gộp lại theo thứ tự tăng dần.

Các câu hỏi phỏng vấn Python về Thuật toán Tìm kiếm (Search Algorithm)

Câu hỏi về Linear Search

Linear Search (Tìm kiếm tuyến tính) là một thuật toán tìm kiếm đơn giản, trong đó ta duyệt qua từng phần tử của danh sách từ đầu đến cuối cho đến khi tìm thấy giá trị cần tìm hoặc đến cuối danh sách mà không tìm thấy.

Bài toán:

Cho một danh sách các số nguyên và một giá trị cần tìm kiếm. Hãy sử dụng thuật toán Linear Search để tìm kiếm giá trị này trong danh sách. Hiển thị quá trình tìm kiếm từng bước.

Danh sách: [2, 3, 4, 10, 40]

Giá trị cần tìm: 10

Lời giải:

def linear_search(arr, x):
    for i in range(len(arr)):
        print(f"Kiểm tra phần tử tại vị trí {i}: {arr[i]}")
        if arr[i] == x:
            return i
    return -1

# Ví dụ
arr = [2, 3, 4, 10, 40]
x = 10
print(f"Danh sách: {arr}")
print(f"Giá trị cần tìm: {x}")
result = linear_search(arr, x)
if result != -1:
    print(f"Phần tử được tìm thấy tại vị trí {result}")
else:
    print("Phần tử không có trong danh sách")

Kết quả:

Danh sách: [2, 3, 4, 10, 40]
Giá trị cần tìm: 10
Kiểm tra phần tử tại vị trí 0: 2
Kiểm tra phần tử tại vị trí 1: 3
Kiểm tra phần tử tại vị trí 2: 4
Kiểm tra phần tử tại vị trí 3: 10
Phần tử được tìm thấy tại vị trí 3

Giải thích:

  • Bước 1: Bắt đầu từ phần tử đầu tiên (2), so sánh với giá trị cần tìm (10). Không khớp.
  • Bước 2: Chuyển sang phần tử tiếp theo (3). Không khớp.
  • Bước 3: Tiếp tục với phần tử (4). Không khớp.
  • Bước 4: Kiểm tra phần tử (10). Khớp với giá trị cần tìm.
  • Kết luận: Giá trị 10 được tìm thấy tại vị trí 3.

Câu hỏi về Binary Search

Binary Search (Tìm kiếm nhị phân) là một thuật toán tìm kiếm hiệu quả cho các danh sách đã được sắp xếp. Thuật toán hoạt động bằng cách liên tục chia đôi phạm vi tìm kiếm, so sánh giá trị ở vị trí giữa với giá trị cần tìm để quyết định tiếp tục tìm kiếm ở nửa nào của danh sách.

Bài toán:

Cho một danh sách các số nguyên đã được sắp xếp theo thứ tự tăng dần và một giá trị cần tìm kiếm. Sử dụng thuật toán Binary Search để tìm kiếm giá trị này trong danh sách. Hiển thị quá trình tìm kiếm từng bước.

Danh sách: [2, 3, 4, 10, 40]

Giá trị cần tìm: 10

Lời giải:

def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    step = 0

    while low <= high:
        mid = (low + high) // 2
        step += 1
        print(f"Bước {step}: Kiểm tra phần tử ở giữa tại vị trí {mid}: {arr[mid]}")
        # Nếu phần tử ở giữa chính là giá trị cần tìm
        if arr[mid] == x:
            return mid
        # Nếu giá trị cần tìm lớn hơn, bỏ qua nửa bên trái
        elif arr[mid] < x:
            low = mid + 1
        # Nếu giá trị cần tìm nhỏ hơn, bỏ qua nửa bên phải
        else:
            high = mid - 1
    return -1

# Ví dụ
arr = [2, 3, 4, 10, 40]
x = 10
print(f"Danh sách: {arr}")
print(f"Giá trị cần tìm: {x}")
result = binary_search(arr, x)
if result != -1:
    print(f"Phần tử được tìm thấy tại vị trí {result}")
else:
    print("Phần tử không có trong danh sách")

Kết quả:

Danh sách: [2, 3, 4, 10, 40]
Giá trị cần tìm: 10
Bước 1: Kiểm tra phần tử ở giữa tại vị trí 2: 4
Bước 2: Kiểm tra phần tử ở giữa tại vị trí 3: 10
Phần tử được tìm thấy tại vị trí 3

Giải thích:

  • Bước 1:
    • low = 0, high = 4
    • mid = (0 + 4) // 2 = 2
    • Kiểm tra arr[2] = 4
    • 4 < 10, giá trị cần tìm nằm ở nửa bên phải.
    • Cập nhật low = mid + 1 = 3
  • Bước 2:
    • low = 3, high = 4
    • mid = (3 + 4) // 2 = 3
    • Kiểm tra arr[3] = 10
    • Tìm thấy giá trị cần tìm.
  • Kết luận: Giá trị 10 được tìm thấy tại vị trí 3.

So sánh Linear Search và Binary Search

  • Linear Search:
    • Ưu điểm: Đơn giản, không yêu cầu danh sách phải sắp xếp.
    • Nhược điểm: Thời gian tìm kiếm chậm với danh sách lớn (O(n)).
  • Binary Search:
    • Ưu điểm: Tốc độ tìm kiếm nhanh hơn với danh sách lớn (O(log n)).
    • Nhược điểm: Yêu cầu danh sách phải được sắp xếp trước.

Các câu hỏi phỏng vấn Python về Cấu trúc Dữ liệu Cơ bản (Basic Data Structure)

Hiểu và áp dụng các cấu trúc dữ liệu này giúp giải quyết nhiều bài toán hiệu quả:

  • StackQueue giúp quản lý dữ liệu theo thứ tự nhập/xuất khác nhau.
  • Linked List cho phép chèn/xóa phần tử linh hoạt.
  • TreeGraph là cấu trúc dữ liệu phức tạp cho phép biểu diễn các quan hệ phân cấp và kết nối.

Câu hỏi về Stack

Stack (Ngăn xếp) là một cấu trúc dữ liệu tuân theo nguyên tắc LIFO (Last In, First Out). Điều này có nghĩa là phần tử được thêm vào cuối cùng sẽ được lấy ra đầu tiên.

Bài toán:

Cho một chuỗi các dấu ngoặc đơn, hãy kiểm tra xem chuỗi có hợp lệ hay không. Một chuỗi được coi là hợp lệ nếu:

  • Mỗi dấu mở ngoặc có một dấu đóng ngoặc tương ứng cùng loại.
  • Các dấu ngoặc được đóng theo đúng thứ tự.

Sử dụng cấu trúc dữ liệu Stack để giải quyết bài toán này.

Ví dụ:

  • Chuỗi “({[]})” => Hợp lệ
  • Chuỗi “({[})” => Không hợp lệ

Ý tưởng:

  • Duyệt qua từng ký tự trong chuỗi.
  • Nếu ký tự là dấu mở ngoặc (‘(‘, ‘{‘, ‘[‘), đẩy nó vào Stack.
  • Nếu ký tự là dấu đóng ngoặc (‘)’, ‘}’, ‘]’), kiểm tra xem Stack có rỗng không:
    • Nếu rỗng, chuỗi không hợp lệ.
    • Nếu không rỗng, lấy phần tử trên đỉnh Stack ra và kiểm tra xem nó có phải là dấu mở ngoặc tương ứng không.
  • Sau khi duyệt hết chuỗi, nếu Stack rỗng, chuỗi hợp lệ; ngược lại, chuỗi không hợp lệ.

Mã Python:

def is_valid_parentheses(s):
    stack = []
    # Bảng ánh xạ các cặp ngoặc
    mapping = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in mapping.values():
            # Dấu mở ngoặc, đẩy vào Stack
            stack.append(char)
            print(f"Đẩy '{char}' vào Stack: {stack}")
        elif char in mapping.keys():
            # Dấu đóng ngoặc, kiểm tra Stack
            if stack and stack[-1] == mapping[char]:
                popped = stack.pop()
                print(f"Lấy '{popped}' ra khỏi Stack: {stack}")
            else:
                print(f"Không khớp với '{char}', chuỗi không hợp lệ.")
                return False
        else:
            # Ký tự không phải dấu ngoặc, bỏ qua
            continue
    
    if not stack:
        print("Stack rỗng, chuỗi hợp lệ.")
        return True
    else:
        print("Stack không rỗng, chuỗi không hợp lệ.")
        return False

# Ví dụ
strings = ["({[]})", "({[})", "((()))", "([)]", "{[()()]()}"]
for s in strings:
    print(f"\nKiểm tra chuỗi: '{s}'")
    result = is_valid_parentheses(s)
    print(f"Chuỗi '{s}' là {'hợp lệ' if result else 'không hợp lệ'}")

Kết quả:

Kiểm tra chuỗi: ‘({[]})’
Đẩy ‘(‘ vào Stack: [‘(‘]
Đẩy ‘{‘ vào Stack: [‘(‘, ‘{‘]
Đẩy ‘[‘ vào Stack: [‘(‘, ‘{‘, ‘[‘]
Lấy ‘[‘ ra khỏi Stack: [‘(‘, ‘{‘]
Lấy ‘{‘ ra khỏi Stack: [‘(‘]
Lấy ‘(‘ ra khỏi Stack: []
Stack rỗng, chuỗi hợp lệ.
Chuỗi ‘({[]})’ là hợp lệ

Kiểm tra chuỗi: ‘({[})’
Đẩy ‘(‘ vào Stack: [‘(‘]
Đẩy ‘{‘ vào Stack: [‘(‘, ‘{‘]
Đẩy ‘[‘ vào Stack: [‘(‘, ‘{‘, ‘[‘]
Lấy ‘{‘ ra khỏi Stack: [‘(‘, ‘{‘]
Không khớp với ‘}’, chuỗi không hợp lệ.
Chuỗi ‘({[})’ là không hợp lệ

Kiểm tra chuỗi: ‘((()))’
Đẩy ‘(‘ vào Stack: [‘(‘]
Đẩy ‘(‘ vào Stack: [‘(‘, ‘(‘]
Đẩy ‘(‘ vào Stack: [‘(‘, ‘(‘, ‘(‘]
Lấy ‘(‘ ra khỏi Stack: [‘(‘, ‘(‘]
Lấy ‘(‘ ra khỏi Stack: [‘(‘]
Lấy ‘(‘ ra khỏi Stack: []
Stack rỗng, chuỗi hợp lệ.
Chuỗi ‘((()))’ là hợp lệ

Kiểm tra chuỗi: ‘([)]’
Đẩy ‘(‘ vào Stack: [‘(‘]
Đẩy ‘[‘ vào Stack: [‘(‘, ‘[‘]
Lấy ‘(‘ ra khỏi Stack: [‘(‘]
Không khớp với ‘)’, chuỗi không hợp lệ.
Chuỗi ‘([)]’ là không hợp lệ

Kiểm tra chuỗi: ‘{[()()]()}’
Đẩy ‘{‘ vào Stack: [‘{‘]
Đẩy ‘[‘ vào Stack: [‘{‘, ‘[‘]
Đẩy ‘(‘ vào Stack: [‘{‘, ‘[‘, ‘(‘]
Lấy ‘(‘ ra khỏi Stack: [‘{‘, ‘[‘]
Đẩy ‘(‘ vào Stack: [‘{‘, ‘[‘, ‘(‘]
Lấy ‘(‘ ra khỏi Stack: [‘{‘, ‘[‘]
Lấy ‘[‘ ra khỏi Stack: [‘{‘]
Đẩy ‘(‘ vào Stack: [‘{‘, ‘(‘]
Lấy ‘(‘ ra khỏi Stack: [‘{‘]
Lấy ‘{‘ ra khỏi Stack: []
Stack rỗng, chuỗi hợp lệ.
Chuỗi ‘{[()()]()}’ là hợp lệ

Giải thích:

  • Chuỗi 1: Mỗi dấu mở ngoặc có dấu đóng tương ứng và Stack rỗng sau khi duyệt.
  • Chuỗi 2: Dấu đóng ngoặc không khớp với dấu mở ngoặc trên đỉnh Stack.
  • Chuỗi 3: Dấu ngoặc được đóng theo đúng thứ tự.
  • Chuỗi 4: Dấu đóng ngoặc không khớp, chuỗi không hợp lệ.
  • Chuỗi 5: Chuỗi phức tạp nhưng hợp lệ.

Câu hỏi về Queue

Queue (Hàng đợi) tuân theo nguyên tắc FIFO (First In, First Out). Khách hàng đến trước sẽ được phục vụ trước.

Bài toán:

Mô phỏng một hàng đợi tại siêu thị. Mỗi khách hàng được đại diện bởi một tên hoặc số ID. Thực hiện các thao tác sau:

  • Thêm khách hàng vào hàng đợi.
  • Phục vụ khách hàng (lấy khách hàng ra khỏi hàng đợi).
  • Hiển thị hàng đợi hiện tại sau mỗi thao tác.

Ví dụ:

  • Khách hàng đến: “Alice”, “Bob”, “Charlie”
  • Phục vụ một khách hàng
  • Khách hàng đến: “Diana”
  • Phục vụ hai khách hàng tiếp theo

Lời giải:

from collections import deque

def supermarket_queue_simulation():
    queue = deque()
    
    # Khách hàng đến: Alice, Bob, Charlie
    customers = ["Alice", "Bob", "Charlie"]
    for customer in customers:
        queue.append(customer)
        print(f"Khách hàng '{customer}' vào hàng đợi. Hàng đợi hiện tại: {list(queue)}")
    
    # Phục vụ một khách hàng
    served = queue.popleft()
    print(f"Phục vụ khách hàng '{served}'. Hàng đợi hiện tại: {list(queue)}")
    
    # Khách hàng đến: Diana
    queue.append("Diana")
    print(f"Khách hàng 'Diana' vào hàng đợi. Hàng đợi hiện tại: {list(queue)}")
    
    # Phục vụ hai khách hàng tiếp theo
    for _ in range(2):
        if queue:
            served = queue.popleft()
            print(f"Phục vụ khách hàng '{served}'. Hàng đợi hiện tại: {list(queue)}")
        else:
            print("Hàng đợi trống.")
            break

# Thực thi mô phỏng
supermarket_queue_simulation()

Kết quả:

Khách hàng ‘Alice’ vào hàng đợi. Hàng đợi hiện tại: [‘Alice’]
Khách hàng ‘Bob’ vào hàng đợi. Hàng đợi hiện tại: [‘Alice’, ‘Bob’]
Khách hàng ‘Charlie’ vào hàng đợi. Hàng đợi hiện tại: [‘Alice’, ‘Bob’, ‘Charlie’]
Phục vụ khách hàng ‘Alice’. Hàng đợi hiện tại: [‘Bob’, ‘Charlie’]
Khách hàng ‘Diana’ vào hàng đợi. Hàng đợi hiện tại: [‘Bob’, ‘Charlie’, ‘Diana’]
Phục vụ khách hàng ‘Bob’. Hàng đợi hiện tại: [‘Charlie’, ‘Diana’]
Phục vụ khách hàng ‘Charlie’. Hàng đợi hiện tại: [‘Diana’]

Giải thích:

  • Sử dụng deque để tạo Queue.
  • Khách hàng được thêm vào cuối hàng đợi bằng append().
  • Khách hàng được phục vụ (lấy ra khỏi hàng đợi) bằng popleft().
  • Hàng đợi được hiển thị sau mỗi thao tác để dễ hình dung.

Câu hỏi về Linked List

Linked List gồm các nút liên kết với nhau, mỗi nút chứa dữ liệu và tham chiếu đến nút tiếp theo.

Bài toán:

Xây dựng một danh sách liên kết đơn (Singly Linked List) để lưu trữ các số nguyên. Thực hiện các thao tác:

  • Chèn phần tử vào đầu danh sách.
  • Chèn phần tử vào cuối danh sách.
  • Xóa phần tử đầu danh sách.
  • In danh sách hiện tại.

Ví dụ:

  • Chèn 10 vào đầu danh sách.
  • Chèn 20 vào cuối danh sách.
  • Chèn 5 vào đầu danh sách.
  • Xóa phần tử đầu danh sách.
  • In danh sách hiện tại.

Lời giải:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    # Chèn vào đầu danh sách
    def insert_at_head(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        print(f"Chèn {data} vào đầu danh sách.")

    # Chèn vào cuối danh sách
    def insert_at_tail(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            print(f"Chèn {data} vào đầu danh sách (danh sách rỗng).")
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        print(f"Chèn {data} vào cuối danh sách.")

    # Xóa phần tử đầu danh sách
    def delete_head(self):
        if self.head:
            removed = self.head.data
            self.head = self.head.next
            print(f"Xóa phần tử đầu tiên: {removed}")
        else:
            print("Danh sách rỗng, không thể xóa.")

    # In danh sách
    def print_list(self):
        current = self.head
        print("Danh sách hiện tại:", end=" ")
        while current:
            print(current.data, end=" ")
            current = current.next
        print()

# Ví dụ
llist = LinkedList()
llist.insert_at_head(10)
llist.insert_at_tail(20)
llist.insert_at_head(5)
llist.delete_head()
llist.print_list()

Kết quả:

Chèn 10 vào đầu danh sách.
Chèn 20 vào cuối danh sách.
Chèn 5 vào đầu danh sách.
Xóa phần tử đầu tiên: 5
Danh sách hiện tại: 10 20 

Giải thích:

  • Chèn vào đầu: Nút mới trở thành đầu danh sách, tham chiếu đến nút cũ.
  • Chèn vào cuối: Duyệt đến cuối danh sách và thêm nút mới.
  • Xóa đầu: Đặt đầu danh sách là nút tiếp theo.
  • In danh sách: Duyệt qua các nút và in dữ liệu.

Câu hỏi về Tree

Binary Tree là cây trong đó mỗi nút có tối đa hai con.

Các kiểu duyệt cây:

  • Pre-order (NLR): Nút hiện tại -> Cây con trái -> Cây con phải
  • In-order (LNR): Cây con trái -> Nút hiện tại -> Cây con phải
  • Post-order (LRN): Cây con trái -> Cây con phải -> Nút hiện tại

Bài toán:

Xây dựng một cây nhị phân (Binary Tree) và thực hiện các kiểu duyệt cây sau:

  • Duyệt theo thứ tự trước (Pre-order)
  • Duyệt theo thứ tự giữa (In-order)
  • Duyệt theo thứ tự sau (Post-order)

In ra các giá trị của các nút trong quá trình duyệt.

Ví dụ:

Cấu trúc cây:

    1
    / \
    2   3
  / \   \
  4   5   6

Lời giải:

class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

# Duyệt Pre-order
def preorder(root):
    if root:
        print(root.data, end=" ")
        preorder(root.left)
        preorder(root.right)

# Duyệt In-order
def inorder(root):
    if root:
        inorder(root.left)
        print(root.data, end=" ")
        inorder(root.right)

# Duyệt Post-order
def postorder(root):
    if root:
        postorder(root.left)
        postorder(root.right)
        print(root.data, end=" ")

# Xây dựng cây
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(6)

# Thực hiện duyệt cây
print("Duyệt Pre-order:")
preorder(root)
print("\nDuyệt In-order:")
inorder(root)
print("\nDuyệt Post-order:")
postorder(root)
print()

Kết quả:

Duyệt Pre-order:
1 2 4 5 3 6
Duyệt In-order:
4 2 5 1 3 6
Duyệt Post-order:
4 5 2 6 3 1 

Giải thích:

  • Pre-order: Bắt đầu từ nút gốc, sau đó đến cây con trái, rồi cây con phải.
  • In-order: Duyệt cây con trái, sau đó đến nút gốc, rồi cây con phải.
  • Post-order: Duyệt cây con trái, cây con phải, sau đó đến nút gốc.
  • Các hàm duyệt được thực hiện đệ quy.

Câu hỏi về Graph

Graph gồm tập hợp các đỉnh và các cạnh có hướng hoặc không hướng.

Depth-First Search (DFS) là thuật toán duyệt đồ thị theo chiều sâu, đi sâu vào các đỉnh con trước khi quay lại đỉnh cha.

Bài toán:

Biểu diễn một đồ thị có hướng sử dụng danh sách kề (Adjacency List) và thực hiện thuật toán duyệt theo chiều sâu (Depth-First Search – DFS) bắt đầu từ một đỉnh cho trước.

Đồ thị:

  • Đỉnh: 0, 1, 2, 3, 4
  • Cạnh: (0->1), (0->2), (1->2), (2->0), (2->3), (3->3)

Bắt đầu duyệt từ đỉnh 2.

Lời giải:

from collections import defaultdict

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    # Thêm cạnh vào đồ thị
    def add_edge(self, u, v):
        self.graph[u].append(v)

    # Thuật toán DFS đệ quy
    def dfs_util(self, v, visited):
        visited.add(v)
        print(f"Thăm đỉnh {v}")
        for neighbor in self.graph[v]:
            if neighbor not in visited:
                self.dfs_util(neighbor, visited)

    # Gọi hàm DFS
    def dfs(self, start):
        visited = set()
        print(f"Bắt đầu duyệt từ đỉnh {start}")
        self.dfs_util(start, visited)

# Ví dụ
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)

# Thực hiện DFS từ đỉnh 2
g.dfs(2)

Kết quả:

Bắt đầu duyệt từ đỉnh 2
Thăm đỉnh 2
Thăm đỉnh 0
Thăm đỉnh 1
Thăm đỉnh 3

Giải thích:

  • Đồ thị được biểu diễn bằng danh sách kề.
  • DFS sử dụng đệ quy để thăm các đỉnh kề chưa được thăm.
  • Bắt đầu từ đỉnh 2, thăm các đỉnh theo chiều sâu trước khi quay lại.

Các câu hỏi phỏng vấn Python về Thuật toán trên Đồ thị (Graph Algorithm)

Câu hỏi về Depth-First Search (DFS)

Depth-First Search (DFS) là thuật toán duyệt hoặc tìm kiếm trên đồ thị, bắt đầu từ một đỉnh gốc và khám phá càng sâu càng tốt theo mỗi nhánh trước khi quay lui.

Bài toán:

Cho một đồ thị có hướng hoặc vô hướng. Hãy thực hiện thuật toán Depth-First Search (DFS) bắt đầu từ một đỉnh cho trước và hiển thị thứ tự các đỉnh được thăm.

Đồ thị:

  • Đỉnh: 0, 1, 2, 3, 4, 5
  • Cạnh:
    • (0, 1)
    • (0, 2)
    • (1, 3)
    • (1, 4)
    • (2, 5)

Bắt đầu duyệt từ đỉnh 0.

Ý tưởng:

  • Sử dụng đệ quy hoặc ngăn xếp để lưu trữ các đỉnh cần thăm.
  • Đánh dấu các đỉnh đã thăm để tránh lặp vô hạn.
  • Tiếp tục thăm các đỉnh kề chưa được thăm của đỉnh hiện tại.
from collections import defaultdict

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    # Thêm cạnh vào đồ thị
    def add_edge(self, u, v):
        self.graph[u].append(v)

    # Hàm DFS đệ quy
    def dfs_util(self, v, visited):
        visited.add(v)
        print(v, end=' ')
        # Thăm các đỉnh kề
        for neighbor in self.graph[v]:
            if neighbor not in visited:
                self.dfs_util(neighbor, visited)

    # Hàm DFS chính
    def dfs(self, start):
        visited = set()
        print(f"Duyệt DFS bắt đầu từ đỉnh {start}:")
        self.dfs_util(start, visited)
        print()

# Ví dụ
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 5)

g.dfs(0)

Kết quả:

Duyệt DFS bắt đầu từ đỉnh 0:
0 1 3 4 2 5 

Giải thích:

  • Bắt đầu từ đỉnh 0, thăm đỉnh 1.
  • Từ đỉnh 1, thăm đỉnh 3, sau đó đỉnh 4.
  • Quay lại đỉnh 0, thăm đỉnh 2, rồi đỉnh 5.
  • Thứ tự các đỉnh được thăm: 0 -> 1 -> 3 -> 4 -> 2 -> 5.

Câu hỏi về Breadth-First Search (BFS)

Breadth-First Search (BFS) là thuật toán duyệt hoặc tìm kiếm trên đồ thị, bắt đầu từ một đỉnh gốc và thăm các đỉnh kề trước khi tiếp tục sang các đỉnh ở mức sâu hơn.

Bài toán:

Cho một đồ thị có hướng hoặc vô hướng. Hãy thực hiện thuật toán Breadth-First Search (BFS) bắt đầu từ một đỉnh cho trước và hiển thị thứ tự các đỉnh được thăm.

Sử dụng cùng đồ thị như trên:

  • Đỉnh: 0, 1, 2, 3, 4, 5
  • Cạnh:
    • (0, 1)
    • (0, 2)
    • (1, 3)
    • (1, 4)
    • (2, 5)

Bắt đầu duyệt từ đỉnh 0.

Ý tưởng:

  • Sử dụng hàng đợi (Queue) để lưu trữ các đỉnh cần thăm.
  • Đánh dấu các đỉnh đã thăm để tránh lặp.
  • Thăm các đỉnh kề của đỉnh hiện tại và thêm chúng vào hàng đợi.

Mã Python:

from collections import defaultdict, deque

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    # Thêm cạnh vào đồ thị
    def add_edge(self, u, v):
        self.graph[u].append(v)

    # Hàm BFS
    def bfs(self, start):
        visited = set()
        queue = deque()

        visited.add(start)
        queue.append(start)
        print(f"Duyệt BFS bắt đầu từ đỉnh {start}:")

        while queue:
            v = queue.popleft()
            print(v, end=' ')
            for neighbor in self.graph[v]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        print()

# Ví dụ
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 5)

g.bfs(0)

Kết quả:

Duyệt BFS bắt đầu từ đỉnh 0:
0 1 2 3 4 5 

Giải thích:

  • Bắt đầu từ đỉnh 0, thăm các đỉnh kề 12.
  • Từ đỉnh 1, thăm đỉnh 34.
  • Từ đỉnh 2, thăm đỉnh 5.
  • Thứ tự các đỉnh được thăm: 0 -> 1 -> 2 -> 3 -> 4 -> 5.

Câu hỏi về Thuật toán Dijkstra

Thuật toán Dijkstra tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác trong đồ thị có trọng số không âm.

Bài toán:

Cho một đồ thị có trọng số với các cạnh có trọng số không âm. Hãy tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác sử dụng Thuật toán Dijkstra.

Ví dụ:

Đồ thị:

  • Đỉnh: 0, 1, 2, 3, 4
  • Cạnh và trọng số:
    • (0, 1, 10)
    • (0, 4, 5)
    • (1, 2, 1)
    • (2, 3, 4)
    • (4, 1, 3)
    • (4, 2, 9)
    • (4, 3, 2)

Đỉnh nguồn: 0

Ý tưởng:

  • Sử dụng một tập hợp (min-heap hoặc priority queue) để chọn đỉnh có khoảng cách nhỏ nhất chưa được thăm.
  • Cập nhật khoảng cách từ đỉnh nguồn đến các đỉnh kề nếu tìm được đường đi ngắn hơn.
  • Lặp lại cho đến khi tất cả các đỉnh đã được thăm.
import heapq

def dijkstra(graph, start):
    # Khởi tạo khoảng cách tới các đỉnh
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0

    # Sử dụng priority queue để lưu các đỉnh cần thăm
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)

        # Nếu khoảng cách hiện tại lớn hơn khoảng cách lưu trữ, bỏ qua
        if current_distance > distances[current_vertex]:
            continue

        # Thăm các đỉnh kề
        for neighbor, weight in graph[current_vertex]:
            distance = current_distance + weight

            # Nếu tìm được đường đi ngắn hơn, cập nhật khoảng cách
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# Ví dụ
graph = {
    0: [(1, 10), (4, 5)],
    1: [(2, 1)],
    2: [(3, 4)],
    3: [],
    4: [(1, 3), (2, 9), (3, 2)]
}

start_vertex = 0
distances = dijkstra(graph, start_vertex)

print(f"Khoảng cách từ đỉnh {start_vertex} đến các đỉnh khác:")
for vertex in distances:
    print(f"Đỉnh {vertex}: {distances[vertex]}")

Kết quả:

Khoảng cách từ đỉnh 0 đến các đỉnh khác:
Đỉnh 0: 0
Đỉnh 1: 8
Đỉnh 2: 9
Đỉnh 3: 7
Đỉnh 4: 5

Giải thích:

  • Đỉnh 0: Khoảng cách bằng 0 (đỉnh nguồn).
  • Đỉnh 4: Khoảng cách 5 thông qua cạnh (0, 4, 5).
  • Đỉnh 1: Khoảng cách 8 thông qua đường đi 0 -> 4 -> 1 với tổng trọng số 5 + 3 = 8.
  • Đỉnh 3: Khoảng cách 7 thông qua đường đi 0 -> 4 -> 3 với tổng trọng số 5 + 2 = 7.
  • Đỉnh 2: Khoảng cách 9 thông qua đường đi 0 -> 4 -> 1 -> 2 với tổng trọng số 5 + 3 + 1 = 9.

Câu hỏi về Thuật toán Kruskal

Thuật toán Kruskal tìm cây khung nhỏ nhất bằng cách sắp xếp các cạnh theo trọng số tăng dần và chọn các cạnh không tạo thành chu trình cho đến khi đủ n-1 cạnh.

Bài toán:

Cho một đồ thị vô hướng có trọng số. Hãy tìm cây khung nhỏ nhất (Minimum Spanning Tree – MST) của đồ thị sử dụng Thuật toán Kruskal.

Ví dụ:

Đồ thị:

  • Đỉnh: A, B, C, D, E, F, G
  • Cạnh và trọng số:
    • (A, B, 7)
    • (A, D, 5)
    • (B, C, 8)
    • (B, D, 9)
    • (B, E, 7)
    • (C, E, 5)
    • (D, E, 15)
    • (D, F, 6)
    • (E, F, 8)
    • (E, G, 9)
    • (F, G, 11)

Ý tưởng:

  • Sắp xếp các cạnh theo trọng số tăng dần.
  • Khởi tạo tập hợp các cây con (mỗi đỉnh là một cây con).
  • Duyệt qua các cạnh, nếu hai đỉnh của cạnh không cùng một cây con, thêm cạnh vào MST và hợp nhất hai cây con.
  • Lặp lại cho đến khi MST có đủ n-1 cạnh.
class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    # Thêm cạnh vào đồ thị
    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

    # Tìm tập hợp của một đỉnh
    def find(self, parent, i):
        if parent[i] != i:
            parent[i] = self.find(parent, parent[i])
        return parent[i]

    # Hợp hai tập hợp
    def union(self, parent, rank, xroot, yroot):
        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        else:
            parent[yroot] = xroot
            rank[xroot] += 1

    # Thuật toán Kruskal
    def kruskal_mst(self):
        result = []  # Kết quả MST
        i, e = 0, 0  # Chỉ số cho cạnh sắp xếp và kết quả

        # Sắp xếp các cạnh theo trọng số tăng dần
        self.graph = sorted(self.graph, key=lambda item: item[2])

        parent = {}
        rank = {}

        # Khởi tạo tập hợp các đỉnh
        for node in self.V:
            parent[node] = node
            rank[node] = 0

        # Số cạnh của MST là V-1
        while e < len(self.V) - 1:
            u, v, w = self.graph[i]
            i += 1
            x = self.find(parent, u)
            y = self.find(parent, v)

            # Nếu thêm cạnh không tạo chu trình
            if x != y:
                e += 1
                result.append([u, v, w])
                self.union(parent, rank, x, y)

        print("Cạnh trong cây khung nhỏ nhất:")
        for u, v, weight in result:
            print(f"{u} -- {v} == {weight}")

Ví dụ và thực thi:

# Ví dụ
vertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
g = Graph(vertices)

g.add_edge('A', 'B', 7)
g.add_edge('A', 'D', 5)
g.add_edge('B', 'C', 8)
g.add_edge('B', 'D', 9)
g.add_edge('B', 'E', 7)
g.add_edge('C', 'E', 5)
g.add_edge('D', 'E', 15)
g.add_edge('D', 'F', 6)
g.add_edge('E', 'F', 8)
g.add_edge('E', 'G', 9)
g.add_edge('F', 'G', 11)

g.kruskal_mst()

Kết quả:

Cạnh trong cây khung nhỏ nhất:
C — E == 5
A — D == 5
D — F == 6
A — B == 7
B — E == 7
E — G == 9

Giải thích:

  • Các cạnh được chọn không tạo thành chu trình và có tổng trọng số nhỏ nhất.
  • Tổng trọng số của MST là 5 + 5 + 6 + 7 + 7 + 9 = 39.

Câu hỏi về Thuật toán Prim

Thuật toán Prim xây dựng MST bằng cách khởi đầu từ một đỉnh và liên tục thêm cạnh có trọng số nhỏ nhất kết nối đỉnh đã thăm với đỉnh chưa thăm.

Bài toán:

Cho một đồ thị vô hướng có trọng số. Hãy tìm cây khung nhỏ nhất (Minimum Spanning Tree – MST) của đồ thị sử dụng Thuật toán Prim.

Sử dụng cùng đồ thị như trong thuật toán Kruskal.

Ý tưởng:

  • Khởi tạo một đỉnh gốc và tập hợp các đỉnh đã thăm.
  • Sử dụng một mảng để lưu trữ trọng số nhỏ nhất kết nối đến mỗi đỉnh.
  • Ở mỗi bước, chọn đỉnh chưa thăm có trọng số kết nối nhỏ nhất.
  • Cập nhật trọng số kết nối cho các đỉnh kề của đỉnh vừa thêm.
import sys

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0]*len(vertices) for _ in range(len(vertices))]

    # Thêm cạnh vào đồ thị
    def add_edge(self, u, v, w):
        idx_u = self.V.index(u)
        idx_v = self.V.index(v)
        self.graph[idx_u][idx_v] = w
        self.graph[idx_v][idx_u] = w

    # Tìm đỉnh có trọng số nhỏ nhất
    def min_key(self, key, mst_set):
        min = sys.maxsize
        min_index = -1

        for v in range(len(self.V)):
            if key[v] < min and mst_set[v] == False:
                min = key[v]
                min_index = v
        return min_index

    # Thuật toán Prim
    def prim_mst(self):
        key = [sys.maxsize] * len(self.V)
        parent = [None] * len(self.V)
        key[0] = 0
        mst_set = [False] * len(self.V)
        parent[0] = -1

        for _ in range(len(self.V)):
            u = self.min_key(key, mst_set)
            mst_set[u] = True

            for v in range(len(self.V)):
                if self.graph[u][v] > 0 and mst_set[v] == False and key[v] > self.graph[u][v]:
                    key[v] = self.graph[u][v]
                    parent[v] = u

        print("Cạnh trong cây khung nhỏ nhất:")
        for i in range(1, len(self.V)):
            print(f"{self.V[parent[i]]} -- {self.V[i]} == {self.graph[parent[i]][i]}")

Ví dụ và thực thi:

# Ví dụ
vertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
g = Graph(vertices)

g.add_edge('A', 'B', 7)
g.add_edge('A', 'D', 5)
g.add_edge('B', 'C', 8)
g.add_edge('B', 'D', 9)
g.add_edge('B', 'E', 7)
g.add_edge('C', 'E', 5)
g.add_edge('D', 'E', 15)
g.add_edge('D', 'F', 6)
g.add_edge('E', 'F', 8)
g.add_edge('E', 'G', 9)
g.add_edge('F', 'G', 11)

g.prim_mst()

Kết quả:

Cạnh trong cây khung nhỏ nhất:
A — D == 5
D — F == 6
F — E == 8
E — C == 5
E — B == 7
E — G == 9

Giải thích:

  • Bắt đầu từ đỉnh A, chọn cạnh có trọng số nhỏ nhất (A, D, 5).
  • Tiếp tục chọn các cạnh có trọng số nhỏ nhất kết nối các đỉnh đã thăm với đỉnh chưa thăm.
  • Kết quả MST có thể khác so với Kruskal nhưng tổng trọng số sẽ bằng hoặc tương đương.

Các câu hỏi phỏng vấn Python về Thuật toán Quy hoạch Động (Dynamic Programming)

Câu hỏi về Knapsack Problem (Bài toán Cái Balo)

Bài toán Cái Balo 0/1 là một ví dụ kinh điển của quy hoạch động. Chúng ta cần xác định giá trị lớn nhất có thể mà không vượt quá trọng lượng tối đa.

Bài toán:

Cho một tập các đồ vật, mỗi đồ vật có trọng lượng và giá trị riêng. Bạn có một cái balo có giới hạn trọng lượng tối đa. Hãy chọn một tập các đồ vật để đưa vào balo sao cho tổng giá trị là lớn nhất mà tổng trọng lượng không vượt quá giới hạn của balo.

  • Danh sách đồ vật:
Đồ vật Trọng lượng (w) Giá trị (v)
1 2 3
2 3 4
3 4 5
4 5 8
  • Trọng lượng tối đa của balo: 5

Ý tưởng:

  • Tạo một bảng hai chiều dp[n+1][W+1], trong đó n là số đồ vật và W là trọng lượng tối đa.
  • dp[i][w] sẽ lưu trữ giá trị lớn nhất có thể đạt được với i đồ vật đầu tiên và trọng lượng tối đa là w.

Công thức truy hồi:

dp[i][w] = dp[i-1][w] nếu w_i > w
dp[i][w] = max(dp[i-1][w], dp[i-1][w - w_i] + v_i) nếu w_i ≤ w

Trong đó:

  • w_i là trọng lượng của đồ vật thứ i.
  • v_i là giá trị của đồ vật thứ i.
def knapsack(W, wt, val, n):
    # Tạo bảng dp với kích thước (n+1) x (W+1)
    dp = [[0 for x in range(W + 1)] for x in range(n + 1)]

    # Xây dựng bảng dp theo cách từ dưới lên
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                dp[i][w] = 0
            elif wt[i-1] <= w:
                dp[i][w] = max(val[i-1] + dp[i-1][w - wt[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
        # In bảng dp sau mỗi bước (tùy chọn)
        # print(f"dp[{i}]: {dp[i]}")
    
    # Giá trị lớn nhất đạt được
    max_value = dp[n][W]
    print(f"Giá trị lớn nhất có thể: {max_value}")

    # Truy vết để tìm đồ vật được chọn
    w = W
    items_selected = []
    for i in range(n, 0, -1):
        if max_value <= 0:
            break
        if max_value == dp[i-1][w]:
            continue
        else:
            # Đồ vật này được chọn
            items_selected.append(i)
            max_value -= val[i-1]
            w -= wt[i-1]
    
    print(f"Đồ vật được chọn: {items_selected[::-1]}")

# Ví dụ
val = [3, 4, 5, 8]
wt = [2, 3, 4, 5]
W = 5
n = len(val)
print(f"Danh sách giá trị: {val}")
print(f"Danh sách trọng lượng: {wt}")
print(f"Trọng lượng tối đa của balo: {W}")
knapsack(W, wt, val, n)

Kết quả:

Danh sách giá trị: [3, 4, 5, 8]
Danh sách trọng lượng: [2, 3, 4, 5]
Trọng lượng tối đa của balo: 5
Giá trị lớn nhất có thể: 8
Đồ vật được chọn: [2]

Giải thích:

  • Bảng dp: Được xây dựng để lưu trữ giá trị lớn nhất có thể đạt được cho mỗi trọng lượng từ 0 đến W với n đồ vật.
  • Truy vết đồ vật được chọn:
    • Bắt đầu từ dp[n][W], nếu dp[i][w] khác dp[i-1][w], nghĩa là đồ vật thứ i được chọn.
    • Trừ giá trị và trọng lượng của đồ vật đã chọn và tiếp tục truy vết.
  • Kết quả:
    • Giá trị lớn nhất đạt được là 8.
    • Đồ vật được chọn là 4 (vì đánh số từ 1 đến n), tương ứng với đồ vật có giá trị 8 và trọng lượng 5.

Câu hỏi về Longest Common Subsequence (Chuỗi con chung dài nhất)

Bài toán:

Cho hai chuỗi XY, hãy tìm độ dài của chuỗi con chung dài nhất giữa hai chuỗi. Chuỗi con chung dài nhất là chuỗi các ký tự xuất hiện trong cả hai chuỗi theo cùng thứ tự nhưng không nhất thiết phải liền kề.

Ví dụ:

  • Chuỗi X = “AGGTAB”
  • Chuỗi Y = “GXTXAYB”
  • Chuỗi con chung dài nhất: “GTAB”
  • Độ dài: 4

Ý tưởng:

  • Sử dụng quy hoạch động để xây dựng một bảng dp[m+1][n+1], trong đó mn là độ dài của hai chuỗi.
  • dp[i][j] lưu trữ độ dài của chuỗi con chung dài nhất giữa X[0..i-1]Y[0..j-1].

Công thức truy hồi:

dp[i][j] = dp[i-1][j-1] + 1 nếu X[i-1] == Y[j-1]
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) nếu X[i-1] != Y[j-1]

Code Python:

def lcs(X, Y):
    m = len(X)
    n = len(Y)
    # Tạo bảng dp với kích thước (m+1) x (n+1)
    dp = [[0]*(n+1) for i in range(m+1)]

    # Xây dựng bảng dp từ dưới lên
    for i in range(m+1):
        for j in range(n+1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                # print(f"dp[{i}][{j}] ({X[i-1]}): {dp[i][j]}")
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                # print(f"dp[{i}][{j}]: {dp[i][j]}")

    # Độ dài của LCS
    length = dp[m][n]
    print(f"Độ dài của chuỗi con chung dài nhất: {length}")

    # Truy vết để tìm LCS
    index = dp[m][n]
    lcs_str = [""] * index  # Tạo mảng lưu trữ LCS

    i = m
    j = n
    while i > 0 and j > 0:
        if X[i-1] == Y[j-1]:
            lcs_str[index - 1] = X[i - 1]
            i -= 1
            j -= 1
            index -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1

    print(f"Chuỗi con chung dài nhất: {''.join(lcs_str)}")

# Ví dụ
X = "AGGTAB"
Y = "GXTXAYB"
print(f"Chuỗi X: {X}")
print(f"Chuỗi Y: {Y}")
lcs(X, Y)

Kết quả:

Chuỗi X: AGGTAB
Chuỗi Y: GXTXAYB
Độ dài của chuỗi con chung dài nhất: 4
Chuỗi con chung dài nhất: GTAB

Giải thích:

  • Bảng dp: Lưu trữ độ dài của LCS tại mỗi vị trí (i, j).
  • Truy vết LCS:
    • Bắt đầu từ dp[m][n], nếu X[i-1] == Y[j-1], ký tự đó thuộc LCS.
    • Di chuyển ngược lên i-1j-1.
    • Nếu không, di chuyển đến ô có giá trị lớn hơn trong dp[i-1][j] hoặc dp[i][j-1].
  • Kết quả:
    • Độ dài của LCS là 4.
    • Chuỗi con chung dài nhất là “GTAB”.

Các câu hỏi phỏng vấn Python về Thuật toán Tham lam (Greedy Algorithm)

Câu hỏi về Coin Change Problem (Bài toán Đổi Tiền)

Thuật toán Tham lam hoạt động bằng cách tại mỗi bước, chúng ta chọn lựa chọn tốt nhất hiện tại mà không quan tâm đến kết quả trong tương lai. Trong bài toán đổi tiền, tại mỗi bước, chúng ta sẽ chọn mệnh giá tiền xu lớn nhất có thể mà không vượt quá số tiền còn lại cần đổi.

Bài toán:

Cho một số tiền cần đổi S và một tập các mệnh giá tiền xu có sẵn. Hãy tìm số lượng tiền xu ít nhất cần dùng để đổi được số tiền S. Sử dụng Thuật toán Tham lam để giải quyết bài toán này.

Lưu ý: Bài toán này chỉ đảm bảo đưa ra kết quả tối ưu khi tập các mệnh giá có tính chất đặc biệt (ví dụ: hệ thống tiền tệ của một số quốc gia). Với hệ thống mệnh giá bất kỳ, thuật toán tham lam có thể không đưa ra kết quả tối ưu.

Ví dụ:

  • Mệnh giá tiền xu: [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000]
  • Số tiền cần đổi: 2753

Ý tưởng:

  • Sắp xếp các mệnh giá tiền xu theo thứ tự giảm dần.
  • Khởi tạo một danh sách để lưu trữ các tiền xu được chọn.
  • Duyệt qua các mệnh giá tiền xu: Trong khi mệnh giá hiện tại nhỏ hơn hoặc bằng số tiền cần đổi:
    • Thêm mệnh giá vào danh sách kết quả.
    • Giảm số tiền cần đổi bằng mệnh giá đã chọn.
def coin_change(coins, amount):
    # Sắp xếp mệnh giá theo thứ tự giảm dần
    coins.sort(reverse=True)
    result = []
    print(f"Mệnh giá tiền xu (giảm dần): {coins}")
    print(f"Số tiền cần đổi: {amount}")
    
    for coin in coins:
        count = 0  # Số lượng đồng xu mệnh giá hiện tại
        while amount >= coin:
            amount -= coin
            result.append(coin)
            count += 1
        if count > 0:
            print(f"Sử dụng {count} đồng xu mệnh giá {coin}")
    
    if amount != 0:
        print("Không thể đổi chính xác số tiền với mệnh giá hiện có.")
    else:
        print(f"Tổng số đồng xu cần dùng: {len(result)}")
        print(f"Các đồng xu được chọn: {result}")

# Ví dụ
coins = [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000]
amount = 2753
coin_change(coins, amount)

Kết quả:

Mệnh giá tiền xu (giảm dần): [1000, 500, 200, 100, 50, 20, 10, 5, 2, 1]
Số tiền cần đổi: 2753
Sử dụng 2 đồng xu mệnh giá 1000
Sử dụng 1 đồng xu mệnh giá 500
Sử dụng 1 đồng xu mệnh giá 200
Sử dụng 0 đồng xu mệnh giá 100
Sử dụng 1 đồng xu mệnh giá 50
Sử dụng 0 đồng xu mệnh giá 20
Sử dụng 0 đồng xu mệnh giá 10
Sử dụng 0 đồng xu mệnh giá 5
Sử dụng 1 đồng xu mệnh giá 2
Sử dụng 1 đồng xu mệnh giá 1
Tổng số đồng xu cần dùng: 6
Các đồng xu được chọn: [1000, 1000, 500, 200, 50, 2, 1]

Giải thích:

  • Bước 1: Bắt đầu với mệnh giá lớn nhất là 1000.
    • Số tiền cần đổi 2753 >= 1000, nên chọn 1000.
    • Số tiền còn lại: 2753 – 1000 = 1753.
    • Tiếp tục chọn 10001753 >= 1000.
    • Số tiền còn lại: 1753 – 1000 = 753.
  • Bước 2: Chuyển sang mệnh giá 500.
    • 753 >= 500, nên chọn 500.
    • Số tiền còn lại: 753 – 500 = 253.
  • Bước 3: Mệnh giá 200.
    • 253 >= 200, chọn 200.
    • Số tiền còn lại: 253 – 200 = 53.
  • Bước 4: Mệnh giá 100.
    • 53 < 100, bỏ qua.
  • Bước 5: Mệnh giá 50.
    • 53 >= 50, chọn 50.
    • Số tiền còn lại: 53 – 50 = 3.
  • Bước 6: Mệnh giá 20, 10, 5.
    • 3 < 20, 10, 5, bỏ qua.
  • Bước 7: Mệnh giá 2.
    • 3 >= 2, chọn 2.
    • Số tiền còn lại: 3 – 2 = 1.
  • Bước 8: Mệnh giá 1.
    • 1 >= 1, chọn 1.
    • Số tiền còn lại: 1 – 1 = 0.
  • Kết luận: Số tiền đã được đổi chính xác với tổng cộng 6 đồng xu.

Lưu ý:

  • Thuật toán tham lam hoạt động hiệu quả với hệ thống mệnh giá của Việt Nam hoặc Mỹ vì mệnh giá có tính chất đặc biệt.
  • Với các hệ thống mệnh giá khác, thuật toán tham lam có thể không đưa ra kết quả tối ưu.

Câu hỏi về Activity Selection Problem (Bài toán Chọn Hoạt Động)

Bài toán:

Cho một tập các hoạt động, mỗi hoạt động có thời gian bắt đầu và kết thúc. Mục tiêu là chọn nhiều nhất các hoạt động không trùng thời gian để tham gia. Sử dụng Thuật toán Tham lam để tìm tập các hoạt động tối đa có thể thực hiện.

Ví dụ:

Danh sách các hoạt động:

Hoạt động Thời gian bắt đầu Thời gian kết thúc
1 1 4
2 3 5
3 0 6
4 5 7
5 3 9
6 5 9
7 6 10
8 8 11
9 8 12
10 2 14
11 12 16

Ý tưởng:

  • Sắp xếp các hoạt động theo thời gian kết thúc tăng dần.
  • Khởi tạo tập kết quả với hoạt động đầu tiên trong danh sách đã sắp xếp.
  • Duyệt qua các hoạt động còn lại:
    • Nếu thời gian bắt đầu của hoạt động hiện tại lớn hơn hoặc bằng thời gian kết thúc của hoạt động cuối cùng trong tập kết quả, thì thêm hoạt động hiện tại vào tập kết quả.
def activity_selection(activities):
    # Sắp xếp hoạt động theo thời gian kết thúc tăng dần
    sorted_activities = sorted(activities, key=lambda x: x[2])
    print("Danh sách hoạt động sau khi sắp xếp (theo thời gian kết thúc):")
    for activity in sorted_activities:
        print(f"Hoạt động {activity[0]}: {activity[1]} - {activity[2]}")
    
    # Chọn hoạt động đầu tiên
    selected_activities = [sorted_activities[0]]
    print(f"\nChọn hoạt động {sorted_activities[0][0]}")
    
    # Duyệt qua các hoạt động còn lại
    for i in range(1, len(sorted_activities)):
        if sorted_activities[i][1] >= selected_activities[-1][2]:
            selected_activities.append(sorted_activities[i])
            print(f"Chọn hoạt động {sorted_activities[i][0]}")
    
    # Kết quả
    print("\nTập các hoạt động được chọn:")
    for activity in selected_activities:
        print(f"Hoạt động {activity[0]}: {activity[1]} - {activity[2]}")

# Ví dụ
activities = [
    (1, 1, 4),
    (2, 3, 5),
    (3, 0, 6),
    (4, 5, 7),
    (5, 3, 9),
    (6, 5, 9),
    (7, 6, 10),
    (8, 8, 11),
    (9, 8, 12),
    (10, 2, 14),
    (11, 12, 16)
]

activity_selection(activities)

Kết quả:

Danh sách hoạt động sau khi sắp xếp (theo thời gian kết thúc):
Hoạt động 1: 14
Hoạt động 2: 35
Hoạt động 3: 06
Hoạt động 4: 57
Hoạt động 6: 59
Hoạt động 5: 39
Hoạt động 7: 610
Hoạt động 8: 811
Hoạt động 9: 812
Hoạt động 10: 214
Hoạt động 11: 1216

Chọn hoạt động 1
Chọn hoạt động 4
Chọn hoạt động 8
Chọn hoạt động 11

Tập các hoạt động được chọn:
Hoạt động 1: 14
Hoạt động 4: 57
Hoạt động 8: 811
Hoạt động 11: 1216

Giải thích:

  • Sắp xếp hoạt động: Hoạt động được sắp xếp theo thời gian kết thúc tăng dần.
  • Chọn hoạt động:
    • Hoạt động 1: Thời gian kết thúc sớm nhất, chọn đầu tiên.
    • Hoạt động 4: Bắt đầu lúc 5, sau khi Hoạt động 1 kết thúc (4), nên có thể chọn.
    • Hoạt động 8: Bắt đầu lúc 8, sau khi Hoạt động 4 kết thúc (7), nên có thể chọn.
    • Hoạt động 11: Bắt đầu lúc 12, sau khi Hoạt động 8 kết thúc (11), nên có thể chọn.
  • Kết quả: Chọn được 4 hoạt động không trùng thời gian.

Lưu ý:

  • Thuật toán tham lam đảm bảo kết quả tối ưu cho bài toán này.
  • Việc sắp xếp theo thời gian kết thúc giúp tối ưu số lượng hoạt động được chọn.

Các câu hỏi phỏng vấn Python về Thuật toán Xử lý Chuỗi (String Algorithm)

Câu hỏi về KMP Algorithm (Thuật toán Knuth-Morris-Pratt)

Thuật toán KMP (Knuth-Morris-Pratt) là một thuật toán hiệu quả để tìm kiếm chuỗi mẫu trong chuỗi văn bản. Nó sử dụng thông tin về chuỗi mẫu để tránh việc so sánh lại các ký tự đã biết là không khớp, nhờ vào mảng lỡ (Failure Function hoặc LPS – Longest Prefix Suffix).

Bài toán:

Cho một chuỗi văn bản T và một chuỗi mẫu P, hãy tìm tất cả các vị trí xuất hiện của chuỗi mẫu P trong chuỗi văn bản T sử dụng Thuật toán KMP. Hiển thị quá trình xây dựng mảng lỡ (Failure Function) và quá trình tìm kiếm.

  • Văn bản T = “ababcabcabababd”
  • Mẫu P = “ababd”
  • Kết quả: Mẫu P xuất hiện tại vị trí 10 trong chuỗi T (vị trí tính từ 0).

Ý tưởng:

  1. Xây dựng mảng LPS (Longest Prefix Suffix):
    • Mảng LPS lưu trữ độ dài của tiền tố dài nhất của mẫu P cũng là hậu tố của P[0..i].
    • Mảng này giúp xác định số ký tự cần bỏ qua khi không khớp trong quá trình tìm kiếm.
  2. Tìm kiếm mẫu trong văn bản:
    • Duyệt qua chuỗi văn bản T và so sánh với chuỗi mẫu P.
    • Khi có ký tự không khớp, sử dụng mảng LPS để xác định vị trí tiếp theo trong mẫu P để tiếp tục so sánh, thay vì quay lại đầu mẫu.
def compute_lps_array(pattern):
    length = 0  # Độ dài của LPS trước đó
    lps = [0] * len(pattern)
    i = 1

    print(f"Xây dựng mảng LPS cho mẫu '{pattern}':")
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            print(f"LPS[{i}] = {length}")
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
                print(f"Không khớp, cập nhật length = {length}")
            else:
                lps[i] = 0
                print(f"LPS[{i}] = 0")
                i += 1
    print(f"Mảng LPS: {lps}\n")
    return lps

def kmp_search(text, pattern):
    m = len(pattern)
    n = len(text)

    lps = compute_lps_array(pattern)
    result = []

    i = 0  # Chỉ số cho text
    j = 0  # Chỉ số cho pattern

    print(f"Tìm kiếm mẫu '{pattern}' trong văn bản '{text}':")
    while i < n:
        if pattern[j] == text[i]:
            print(f"Khớp tại text[{i}] và pattern[{j}] ({text[i]})")
            i += 1
            j += 1

        if j == m:
            print(f"Mẫu xuất hiện tại vị trí {i - j}")
            result.append(i - j)
            j = lps[j - 1]
            print(f"Đặt lại j = {j}")
        elif i < n and pattern[j] != text[i]:
            if j != 0:
                print(f"Không khớp tại text[{i}] và pattern[{j}] ({text[i]} vs {pattern[j]}), đặt lại j = {lps[j - 1]}")
                j = lps[j - 1]
            else:
                print(f"Không khớp tại text[{i}] và pattern[{j}] ({text[i]} vs {pattern[j]}), tăng i")
                i += 1

    print(f"\nCác vị trí mẫu xuất hiện: {result}")
    return result

# Ví dụ
text = "ababcabcabababd"
pattern = "ababd"
kmp_search(text, pattern)

Kết quả:

Xây dựng mảng LPS cho mẫu ‘ababd’:
LPS[1] = 0
LPS[2] = 1
LPS[3] = 2
Không khớp, cập nhật length = 0
LPS[4] = 0
Mảng LPS: [0, 0, 1, 2, 0]

Tìm kiếm mẫu ‘ababd’ trong văn bản ‘ababcabcabababd’:
Khớp tại text[0] và pattern[0] (a)
Khớp tại text[1] và pattern[1] (b)
Khớp tại text[2] và pattern[2] (a)
Khớp tại text[3] và pattern[3] (b)
Không khớp tại text[4] và pattern[4] (c vs d), đặt lại j = 2
Không khớp tại text[4] và pattern[2] (c vs a), đặt lại j = 0
Không khớp tại text[4] và pattern[0] (c vs a), tăng i
Khớp tại text[5] và pattern[0] (a)
Không khớp tại text[6] và pattern[1] (b vs c), đặt lại j = 0
Không khớp tại text[6] và pattern[0] (c vs a), tăng i
Khớp tại text[7] và pattern[0] (a)
Khớp tại text[8] và pattern[1] (b)
Khớp tại text[9] và pattern[2] (a)
Khớp tại text[10] và pattern[3] (b)
Khớp tại text[11] và pattern[4] (a)
Không khớp tại text[12] và pattern[5] (b vs d), đặt lại j = 2
Khớp tại text[12] và pattern[2] (b)
Khớp tại text[13] và pattern[3] (d)
Mẫu xuất hiện tại vị trí 10
Đặt lại j = 0

Các vị trí mẫu xuất hiện: [10]

Giải thích:

  • Xây dựng mảng LPS:
    • LPS[0] = 0: luôn luôn bằng 0.
    • LPS[1] = 0: vì pattern[1] != pattern[0].
    • LPS[2] = 1: vì pattern[2] == pattern[0].
    • LPS[3] = 2: vì pattern[3] == pattern[1].
    • LPS[4] = 0: vì không có tiền tố/hậu tố trùng.
  • Tìm kiếm:
    • So sánh các ký tự của textpattern, sử dụng lps để quyết định số bước nhảy khi không khớp.
    • Khi tìm thấy một mẫu hoàn chỉnh (j == m), lưu vị trí và đặt lại j theo lps.

Hình ảnh minh họa:

Mảng LPS:

Chỉ số:   0  1  2  3  4
Mẫu P:    a  b  a  b  d
LPS:      0  0  1  2  0

Câu hỏi về Rabin-Karp Algorithm

Thuật toán Rabin-Karp là một thuật toán tìm kiếm chuỗi mẫu trong chuỗi văn bản bằng cách sử dụng hàm băm để so sánh chuỗi. Thay vì so sánh trực tiếp các chuỗi con, nó so sánh giá trị băm của chúng, giúp tăng hiệu suất.

Bài toán:

Cho một chuỗi văn bản T và một chuỗi mẫu P, hãy tìm tất cả các vị trí xuất hiện của chuỗi mẫu P trong chuỗi văn bản T sử dụng Thuật toán Rabin-Karp. Hiển thị quá trình tính toán giá trị băm (hash) và so sánh.

  • Văn bản T = “GEEKS FOR GEEKS”
  • Mẫu P = “GEEK”
  • Kết quả: Mẫu P xuất hiện tại vị trí 010 trong chuỗi T.

Ý tưởng:

  1. Tính giá trị băm của mẫu P và chuỗi con đầu tiên của T có độ dài bằng P.
  2. Duyệt qua chuỗi T:
    • Nếu giá trị băm của chuỗi con hiện tại trùng với giá trị băm của P, tiến hành so sánh ký tự từng vị trí để xác nhận.
    • Tính giá trị băm cho chuỗi con tiếp theo bằng cách cập nhật từ giá trị băm trước đó (rolling hash).
def rabin_karp_search(pattern, text, d=256, q=101):
    m = len(pattern)
    n = len(text)
    h = pow(d, m-1) % q  # Giá trị h = d^(m-1) % q
    p = 0  # Giá trị hash cho pattern
    t = 0  # Giá trị hash cho text
    result = []

    print(f"Văn bản: '{text}'")
    print(f"Mẫu: '{pattern}'")
    print(f"Giá trị d: {d}, Giá trị q (số nguyên tố): {q}")

    # Tính giá trị hash ban đầu cho pattern và text
    for i in range(m):
        p = (d * p + ord(pattern[i])) % q
        t = (d * t + ord(text[i])) % q
    print(f"Giá trị hash ban đầu của pattern: {p}")
    print(f"Giá trị hash ban đầu của text: {t}\n")

    # Duyệt qua văn bản
    for s in range(n - m + 1):
        if p == t:
            print(f"Hash khớp tại vị trí {s}. Kiểm tra chuỗi con...")
            # So sánh từng ký tự
            if text[s:s+m] == pattern:
                print(f"Mẫu xuất hiện tại vị trí {s}")
                result.append(s)
            else:
                print("Chuỗi con không khớp dù hash khớp.")

        if s < n - m:
            t = (d * (t - ord(text[s]) * h) + ord(text[s + m])) % q
            # Đảm bảo t >= 0
            if t < 0:
                t += q
            print(f"Cập nhật hash tại vị trí {s+1}: {t}")

    print(f"\nCác vị trí mẫu xuất hiện: {result}")
    return result

# Ví dụ
text = "GEEKS FOR GEEKS"
pattern = "GEEK"
rabin_karp_search(pattern, text)

Kết quả:

Văn bản: ‘GEEKS FOR GEEKS’
Mẫu: ‘GEEK’
Giá trị d: 256, Giá trị q (số nguyên tố): 101
Giá trị hash ban đầu của pattern: 98
Giá trị hash ban đầu của text: 98Hash khớp tại vị trí 0. Kiểm tra chuỗi con…
Mẫu xuất hiện tại vị trí 0
Cập nhật hash tại vị trí 1: 50
Cập nhật hash tại vị trí 2: 81
Cập nhật hash tại vị trí 3: 38
Cập nhật hash tại vị trí 4: 32
Cập nhật hash tại vị trí 5: 54
Cập nhật hash tại vị trí 6: 18
Cập nhật hash tại vị trí 7: 61
Cập nhật hash tại vị trí 8: 13
Cập nhật hash tại vị trí 9: 4
Cập nhật hash tại vị trí 10: 98
Hash khớp tại vị trí 10. Kiểm tra chuỗi con…
Mẫu xuất hiện tại vị trí 10Các vị trí mẫu xuất hiện: [0, 10]

Giải thích:

  • Tính giá trị băm ban đầu:

Sử dụng giá trị ASCII của các ký tự và công thức:

hash = (d * hash + ord(char)) % q
  • Quá trình tìm kiếm:
    • Nếu giá trị hash trùng khớp, tiến hành so sánh chuỗi con.

Sử dụng rolling hash để cập nhật giá trị hash cho chuỗi con tiếp theo:

t = (d * (t - ord(text[s]) * h) + ord(text[s + m])) % q
  • Đảm bảo giá trị hash luôn dương bằng cách thêm q nếu cần.

Lưu ý về các tham số:

  • d: Số lượng ký tự trong bảng chữ cái (256 cho ASCII).
  • q: Số nguyên tố lớn để giảm xung đột hash.

So sánh hai thuật toán:

  • Hiệu suất:
    • KMP có độ phức tạp O(n), ổn định.
    • Rabin-Karp có độ phức tạp trung bình O(n), nhưng trường hợp xấu nhất là O(nm) do xung đột hash.
  • Ưu điểm:
    • KMP: Tốt cho việc tìm kiếm một mẫu trong văn bản.
    • Rabin-Karp: Tốt cho việc tìm kiếm nhiều mẫu hoặc mẫu có độ dài lớn.

Các câu hỏi phỏng vấn Python về Thuật toán Toán học (Mathematical Algorithm)

Câu hỏi về Thuật toán Euclid (Euclidean Algorithm)

Thuật toán Euclid là phương pháp hiệu quả để tìm ước số chung lớn nhất của hai số nguyên dương. Nguyên lý cơ bản dựa trên việc liên tục thay thế số lớn hơn bằng phần dư của phép chia số lớn cho số nhỏ cho đến khi phần dư bằng 0. Khi đó, số còn lại chính là GCD.

Bài toán:

Cho hai số nguyên dương ab. Hãy tìm Ước số chung lớn nhất (GCD) của ab bằng cách sử dụng Thuật toán Euclid. Hiển thị quá trình tính toán từng bước.

  • a = 56
  • b = 98
  • Kết quả: GCD của 569814.

Ý tưởng:

  • Trong khi b khác 0, thực hiện:
    • Gán a bằng b, và b bằng a % b (phần dư của a chia cho b).
  • Khi b bằng 0, a là GCD.
def euclidean_algorithm(a, b):
    print(f"Tìm GCD của {a}{b} bằng Thuật toán Euclid:")
    step = 1
    while b != 0:
        print(f"Bước {step}: a = {a}, b = {b}")
        a, b = b, a % b
        step += 1
    print(f"GCD là {a}")
    return a

# Ví dụ
a = 56
b = 98
euclidean_algorithm(a, b)

Kết quả:

Tìm GCD của 5698 bằng Thuật toán Euclid:
Bước 1: a = 56, b = 98
Bước 2: a = 98, b = 56
Bước 3: a = 56, b = 42
Bước 4: a = 42, b = 14
Bước 5: a = 14, b = 0
GCD là 14

Giải thích:

  1. Bước 1:
    • a = 56, b = 98
    • a % b = 56 % 98 = 56 (vì 56 < 98)
    • Cập nhật a = 98, b = 56
  2. Bước 2:
    • a = 98, b = 56
    • a % b = 98 % 56 = 42
    • Cập nhật a = 56, b = 42
  3. Bước 3:
    • a = 56, b = 42
    • a % b = 56 % 42 = 14
    • Cập nhật a = 42, b = 14
  4. Bước 4:
    • a = 42, b = 14
    • a % b = 42 % 14 = 0
    • Cập nhật a = 14, b = 0
  5. Kết luận:
    • Khi b = 0, GCD là a = 14.

Hình ảnh minh họa:

5698

9856 (vì 98 % 56 = 42)

5642 (vì 56 % 42 = 14)

4214 (vì 42 % 14 = 0)
→ GCD là 14

Câu hỏi về Sàng Eratosthenes (Sieve of Eratosthenes)

Sàng Eratosthenes là một thuật toán cổ điển và hiệu quả để tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng một số nguyên dương cho trước. Thuật toán hoạt động bằng cách loại bỏ các bội số của mỗi số nguyên tố bắt đầu từ 2.

Bài toán:

Cho một số nguyên dương n. Hãy liệt kê tất cả các số nguyên tố nhỏ hơn hoặc bằng n bằng cách sử dụng Thuật toán Sàng Eratosthenes. Hiển thị quá trình sàng lọc từng bước.

  • n = 30
  • Kết quả: Các số nguyên tố nhỏ hơn hoặc bằng 30 là: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Ý tưởng:

  1. Tạo một danh sách các số từ 2 đến n.
  2. Bắt đầu từ p = 2, số nguyên tố nhỏ nhất.
  3. Đánh dấu tất cả các bội số của p (từ p*p đến n) là không phải số nguyên tố.
  4. Tìm số nguyên tố tiếp theo chưa được đánh dấu và lặp lại bước 3.
  5. Lặp lại cho đến khi p*p > n.
def sieve_of_eratosthenes(n):
    prime = [True for _ in range(n+1)]
    p = 2
    print(f"Tìm các số nguyên tố nhỏ hơn hoặc bằng {n} bằng Sàng Eratosthenes:")
    while p * p <= n:
        if prime[p]:
            print(f"\nSố {p} là số nguyên tố, đánh dấu các bội số của {p}")
            for i in range(p * p, n+1, p):
                if prime[i]:
                    print(f"Đánh dấu {i} là không nguyên tố")
                prime[i] = False
        p += 1
    
    primes = [p for p in range(2, n+1) if prime[p]]
    print(f"\nCác số nguyên tố nhỏ hơn hoặc bằng {n}: {primes}")
    return primes

# Ví dụ
n = 30
sieve_of_eratosthenes(n)

Kết quả:

Tìm các số nguyên tố nhỏ hơn hoặc bằng 30 bằng Sàng Eratosthenes:

Số 2 là số nguyên tố, đánh dấu các bội số của 2
Đánh dấu 4 là không nguyên tố
Đánh dấu 6 là không nguyên tố
Đánh dấu 8 là không nguyên tố
Đánh dấu 10 là không nguyên tố
Đánh dấu 12 là không nguyên tố
Đánh dấu 14 là không nguyên tố
Đánh dấu 16 là không nguyên tố
Đánh dấu 18 là không nguyên tố
Đánh dấu 20 là không nguyên tố
Đánh dấu 22 là không nguyên tố
Đánh dấu 24 là không nguyên tố
Đánh dấu 26 là không nguyên tố
Đánh dấu 28 là không nguyên tố
Đánh dấu 30 là không nguyên tố

Số 3 là số nguyên tố, đánh dấu các bội số của 3
Đánh dấu 9 là không nguyên tố
Đánh dấu 12 là không nguyên tố
Đánh dấu 15 là không nguyên tố
Đánh dấu 18 là không nguyên tố
Đánh dấu 21 là không nguyên tố
Đánh dấu 24 là không nguyên tố
Đánh dấu 27 là không nguyên tố
Đánh dấu 30 là không nguyên tố

Số 5 là số nguyên tố, đánh dấu các bội số của 5
Đánh dấu 25 là không nguyên tố
Đánh dấu 30 là không nguyên tố

Các số nguyên tố nhỏ hơn hoặc bằng 30: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Giải thích:

  • Bước 1: Khởi tạo danh sách prime[0..n] với tất cả các giá trị True.
  • Bước 2: Bắt đầu với p = 2.
    • Đánh dấu các bội số của 2 (từ 4 đến n) là False.
  • Bước 3: Tăng p lên 3.
    • Đánh dấu các bội số của 3 (từ 9 đến n) là False.
  • Bước 4: Tăng p lên 4.
    • prime[4]False nên bỏ qua.
  • Bước 5: Tăng p lên 5.
    • Đánh dấu các bội số của 5 (từ 25 đến n) là False.
  • Bước 6: Tiếp tục cho đến khi p * p > n.

Hình ảnh minh họa:

[2, 3, 4, 5, 6, 7, 8, 9, 10, …, 30]

– Bắt đầu với 2:
Đánh dấu 4, 6, 8, …, 30

– Tiếp tục với 3:
Đánh dấu 9, 12, 15, …, 30

– Tiếp tục với 5:
Đánh dấu 25, 30

– Kết quả:
Các số không bị đánh dấu là số nguyên tố.

Các chủ đề phổ biến khác trong các câu hỏi phỏng vấn Python Developer

Ngoài những câu hỏi phỏng vấn Python chuyên môn về thuật toán và cấu trúc dữ liệu, để vượt qua buổi phỏng vấn Python Developer, ứng viên cần nắm vững các chủ đề dưới đây:

  • Kiến thức nền tảng về Python: Các kiến thức cơ bản như cú pháp, xử lý file, và các loại dữ liệu phổ biến như list, tuple, set, dictionary,…
  • Các khái niệm OOP (Object-Oriented Programming) trong Python: Sử dụng các class, inheritance, polymorphism, encapsulation trong lập trình hướng đối tượng.
  • Xử lý dữ liệu và các thư viện Python phổ biến: Thư viện như Pandas, NumPy để xử lý dữ liệu, từ việc đọc file CSV đến các phép tính ma trận phức tạp.
  • Frameworks phổ biến như Django, Flask: Django và Flask là hai framework phổ biến cho phát triển web bằng Python, cần hiểu rõ về routing, middleware, và quản lý database.
  • Giải quyết vấn đề và tối ưu hóa mã nguồn Python: Khả năng tối ưu hóa mã nguồn là yêu cầu quan trọng, đặc biệt khi phải làm việc với các ứng dụng lớn hoặc có yêu cầu về tốc độ.

Bạn có thể “ôn tập” các chủ đề trên qua các bài viết sau:

Tổng kết câu hỏi phỏng vấn Python

Vậy là chúng ta đã đi qua các câu hỏi phỏng vấn Python quan trọng thường xuất hiện trong các buổi phỏng vấn Python Developer, từ các thuật toán sắp xếp và tìm kiếm đến cấu trúc dữ liệu cơ bản và các thuật toán nâng cao.

Việc chuẩn bị kỹ lưỡng cho phỏng vấn vị trí Python Developer không chỉ giúp bạn tự tin đối mặt với các câu hỏi, mà còn rèn luyện khả năng giải thích những khái niệm phức tạp một cách dễ hiểu. Hãy đầu tư thời gian để nghiên cứu, thực hành và nâng cao kỹ năng của mình, qua đó tăng cơ hội thành công trong buổi phỏng vấn.