Top 8 câu hỏi về thuật toán mà bạn cần phải biết

1. Thuật toán là gì?

Tuy cơ bản nhưng nếu bạn tình cờ được hỏi câu hỏi này, điều quan trọng là bạn phải trả lời một cách tự tin và đơn giản. Thuật toán là một chuỗi các bước tính toán sử dụng một đầu vào hoặc nhiều đầu vào và chuyển nó thành đầu ra. Có một số định dạng mà một thuật toán có thể được viết bằng tiếng Anh đơn giản hoặc dưới dạng mã giả.

Khi bạn đã đưa ra một câu trả lời ngắn gọn như thế này, nếu bạn muốn đi sâu hơn, bạn có thể làm như vậy bằng cách sử dụng một ví dụ.

2. Quicksort là gì?

Câu hỏi này nhằm kiểm tra khả năng áp dụng thuật toán của bạn ít nhất là ở mức rất cơ bản . Thuật toán Quicksort sắp xếp các truy vấn hoặc danh sách một cách nhanh chóng. Nó sử dụng những gì được gọi là kỹ thuật “phân chia và chinh phục”, trao đổi phân vùng, chia danh sách các mục thành ba phần khác nhau:

• Một phần tử tổng hợp được chọn từ mảng
• Các phần tử nhỏ hơn phần tử pivot được đặt ở bên trái của pivot để tạo thành một mảng con bên trái
• Các phần tử lớn hơn phần tử pivot được đặt ở bên phải của pivot để tạo thành một mảng con bên phải

Trong các mảng con, một phần tử trục được chọn và các giá trị còn lại được sắp xếp ở bên trái hoặc bên phải của trục. Quá trình được lặp lại cho đến khi chỉ còn lại một phần tử duy nhất trong các mảng con.

Phức tạp về thời gian:

• Trường hợp tốt nhất: O (nlogn) Điều này xảy ra khi giá trị phần tử xoay gần ở giữa
• Trường hợp tồi tệ nhất: O (n2) Điều này xảy ra khi giá trị phần tử tổng hợp là giá trị lớn nhất hoặc nhỏ nhất
• Trường hợp Trung bình: O (nlogn)

3. Chức năng của phần tử Pivot là gì?

Đây là một phần đi sâu khác vào những điều cơ bản của thuật toán. Bạn có thể trả lời bằng cách giải thích rằng phần tử xoay vòng là phần tử được chọn từ mảng hoặc ma trận đang được làm việc để đóng vai trò là phần tử đầu tiên được thuật toán chọn để thực hiện các phép tính.

Có nhiều cách để chọn một phần tử xoay. Đối với mảng, các trục có thể là phần tử cuối cùng hoặc đầu tiên, được chọn từ phần giữa hoặc thậm chí được chọn ngẫu nhiên. Tùy thuộc vào thuật toán, cách chọn trục xoay có thể mang lại kết quả tốt hơn.

4. Độ phức tạp thời gian của một thuật toán có nghĩa là gì?

Đây là một yếu tố cơ bản khác của thuật toán, vì vậy câu trả lời của bạn nên bắt đầu bằng một định nghĩa ngắn gọn. Yếu tố độ phức tạp thời gian của một thuật toán đề cập đến số lần lặp lại cần thiết để nó được chạy đến khi hoàn thành dựa trên kích thước đầu vào.

5. Giải thích các ký hiệu khác nhau được sử dụng khi nói đến độ phức tạp về thời gian.

Khi trả lời câu hỏi này và bất kỳ phần tiếp theo nào, bạn đang chứng minh kiến ​​thức của mình về cách hoạt động của các thuật toán, cũng như các cách khác nhau mà bạn có thể thay đổi chúng để đạt được kết quả mong muốn.

Sử dụng ký hiệu giúp dự đoán hiệu quả của thuật toán. Các ký hiệu bạn sử dụng cho sự phức tạp về thời gian bao gồm:

• Big Omega: Điều này biểu thị sự lặp lại "nhiều hơn hoặc giống như". Đó là giới hạn dưới chặt chẽ của sự tăng trưởng thời gian chạy của thuật toán. Đây sẽ là trường hợp phức tạp nhất về thời gian.
• Big-O: Điều này có nghĩa là số lần lặp lại “ít hơn hoặc giống như”. Đó là giới hạn trên chặt chẽ của sự tăng trưởng thời gian chạy của thuật toán. Đây sẽ là trường hợp xấu nhất về thời gian phức tạp.
• Big Theta: Điều này có nghĩa là các lần lặp lại "giống như". Nó vừa là giới hạn trên chặt chẽ vừa là giới hạn dưới chặt chẽ về sự tăng trưởng thời gian chạy của thuật toán.
• Little-O: Điều này có nghĩa là số lần lặp lại "ít hơn". Nó là một giới hạn trên không chặt chẽ về mặt tiệm cận.
• Little Omega: Điều này biểu thị sự lặp lại "nhiều hơn". Đó là giới hạn dưới không chặt chẽ về mặt tiệm cận.

6. Tìm kiếm nhị phân hoạt động như thế nào?

Tìm kiếm nhị phân được sử dụng để tìm một phần tử trong một mảng được sắp xếp. Mục ở giữa mảng được nhìn đầu tiên. Nếu phần tử cần tìm khớp với mục ở giữa thì quá trình tìm kiếm đã hoàn tất. Ngược lại, nếu phần tử đích lớn hơn phần tử giữa thì tìm kiếm được lặp lại ở nửa trên của mảng (tất cả các giá trị lớn hơn sau phần giữa). Nếu nó thấp hơn phần tử ở giữa thì việc tìm kiếm được thực hiện trên nửa dưới của mảng (tất cả các giá trị nhỏ hơn).

Phức tạp về thời gian:

• Trường hợp tốt nhất: O (1) Điều này xảy ra nếu giá trị khớp với mục ở giữa để bắt đầu.
• Trường hợp xấu nhất: O (logn) Xảy ra nếu giá trị nằm ở một trong các bước kết thúc hoặc hoàn toàn không có trong mảng.
• Trường hợp trung bình: O (logn)

7. Sắp xếp theo đống có nghĩa là gì?

Sắp xếp theo đống liên quan đến việc so sánh các mục bằng thuật toán sắp xếp. Đầu vào được phân chia giữa vùng được sắp xếp và vùng chưa được sắp xếp. Những gì được chuyển sang khu vực được sắp xếp phụ thuộc vào việc làm việc trên đống tối đa hay đống tối thiểu. Một đống tối đa có phần tử có giá trị lớn nhất ở gốc trong khi một đống tối thiểu có giá trị nhỏ nhất ở phần tử gốc. Khi sử dụng sắp xếp theo đống trên một đống tối đa, vùng không được sắp xếp sẽ thu hẹp lại khi mục lớn nhất được chuyển sang vùng được sắp xếp. Đối với min-heap, mục nhỏ nhất được chuyển sang vùng đã sắp xếp.

Trong max-heap, giá trị của nút cha luôn lớn hơn giá trị con của chúng. Để sắp xếp các phần tử của một đống tối đa bằng cách sử dụng sắp xếp đống, phải làm theo các bước sau:

• Thay thế phần tử cuối cùng của heap bằng nút gốc
• Xóa phần tử cuối cùng mới được đặt khỏi đống
• Chuyển đổi đống nhị phân hiện tại trở lại thành một đống tối đa
• Lặp lại quy trình cho đến khi không còn phần tử nào nữa

Phức tạp về thời gian:

• Trường hợp tốt nhất: O (nlogn)
• Trường hợp tệ nhất: O (nlogn)
• Trường hợp Trung bình: O (nlogn)

8. Danh sách bỏ qua được sử dụng để làm gì?

Danh sách bỏ qua được sử dụng cho quá trình cấu trúc dữ liệu. Nó dựa trên danh sách được liên kết và sử dụng xác suất để xây dựng các lớp liên kết mới trên danh sách được liên kết ban đầu. Có thể liên tưởng đến việc nhìn vào một chuỗi các tuyến xe buýt. Có xe buýt dừng ở mọi điểm dừng nhưng cũng có xe buýt chỉ dừng lại ở tốc độ cao. Xe buýt tốc hành có ít điểm dừng hơn so với xe buýt thông thường. Tạo các lớp mới trong danh sách bỏ qua có thể được coi như các tuyến đường tốc hành. Có thể truy cập các nút thường xuyên nhất một cách hiệu quả hơn có thể làm cho các tác vụ khác như chèn hoặc xóa các nút dễ dàng và nhanh hơn nhiều so với một số thuật toán khác.