Câu hỏi phỏng vấn Thuật toán

Giới thiệu thuật toán

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

Cấu trúc dữ liệu và giải thuật là những khái niệm cốt lõi trong mọi buổi phỏng vấn dev, bất kể bạn là dev C, Java, Web hay Mobile. Dù là ở lĩnh vực nào trong công nghệ thông tin thì bạn cũng cần phải biết về giải thuật.

Một lập trình viên cần hiểu kỹ lưỡng về cả hai khái niệm là cấu trúc dữ liệu (mảng, danh sách liên kết, cây, ngăn xếp, hàng đợi,..) và các thuật toán như Tìm kiếm nhị phân, quy hoạch động,... Do đó, bài viết này chủ yếu tập trung vào thuật toán - giới thiệu về thuật toán, với 30 câu hỏi phỏng vấn về thuật toán.

Trước hết, câu hỏi đầu tiên và phổ biến nhất với hầu hết mọi người "Thuật toán là gì?". Câu trả lời đầy đủ có thể là: Thuật toán là một tập hợp hữu hạn các hướng dẫn được xác định rõ ràng, có thể thực hiện được bằng máy tính, thường để giải quyết một lớp vấn đề hoặc để thực hiện một phép tính.

Thuật toán thường được sử dụng để chỉ định cách tính toán, xử lý dữ liệu, suy luận tự động, ra quyết định tự động và các tác vụ khác cần được thực hiện. Thuật toán là một phương pháp hiệu quả, có thể được biểu diễn trong một khoảng không gian và thời gian hữu hạn, và bằng một ngôn ngữ hình thức được xác định rõ ràng để tính toán một hàm số. Bắt đầu từ trạng thái ban đầu và đầu vào ban đầu (input - có thể trống), khi được thực thi, sẽ tiến hành một hữu hạn các trạng thái kế tiếp được xác định rõ ràng, và cuối cùng là tạo ra đầu ra (output) và dừng ở trạng thái kết thúc. Sự chuyển đổi từ trạng thái này sang trạng thái khác không nhất thiết phải mang tính xác định, một số thuật toán được gọi là thuật toán ngẫu nhiên, kết hợp đầu vào ngẫu nhiên.

2. Lợi ích của thuật toán

• Gia tăng sự hiệu quả của một giải pháp đã tồn tại.
• Dễ dàng sử dụng để so sánh hiệu suất của các thuật toán khác nhau cho cùng một vấn đề bằng cách dùng các phương pháp như độ phức tạp thời gian, độ phức tạp không gian,...
• Thuật toán cung cấp một bản thiết kế với các mô tả chi tiết cốt lõi để giải quyết vấn đề.
• Giúp hiểu đúng về luồng hoạt động của chương trình.
• Các thuật toán đánh giá mức độ hoạt động của các phương pháp tiếp cận trong các tình huống khác nhau (Trường hợp tốt nhất, trường hợp xấu nhất, trường hợp trung bình).
• Một thuật toán cũng xác định tài nguyên nào (input/output) là cần thiết.
• Ta có thể định lượng và đánh giá độ phức tạp của vấn đề về thời gian và không gian bằng cách sử dụng thuật toán.
• Chi phí thiết kế sẽ giảm nếu dùng các thuật toán thích hợp.