Bí kíp giải quyết cấu trúc dữ liệu

1. Cấu trúc dữ liệu là gì?

Cấu trúc dữ liệu là cách lưu trữ, tổ chức dữ liệu có thứ tự, có hệ thống để dữ liệu có thể được sử dụng một cách hiệu quả. Cấu trúc dữ liệu được hình thành bởi:

Interface: Mỗi cấu trúc dữ liệu có một Interface. Interface biểu diễn một tập hợp các phép tính mà một cấu trúc dữ liệu hỗ trợ. Một Interface chỉ cung cấp danh sách các phép tính được hỗ trợ, các loại tham số mà chúng có thể chấp nhận và kiểu trả về của các phép tính này.

Implementation (có thể hiểu là sự triển khai): Cung cấp sự biểu diễn nội bộ của một cấu trúc dữ liệu. Implementation cũng cung cấp phần định nghĩa của giải thuật được sử dụng trong các phép tính của cấu trúc dữ liệu.

2. Đặc điểm của một cấu trúc dữ liệu

Chính xác: Sự triển khai của Cấu trúc dữ liệu nên triển khai Interface của nó một cách chính xác.

Độ phức tạp về thời gian (Time Complexity): Thời gian chạy hoặc thời gian thực thi của các phép tính của cấu trúc dữ liệu phải là nhỏ nhất có thể.

Độ phức tạp về bộ nhớ (Space Complexity): Sự sử dụng bộ nhớ của mỗi phép tính của cấu trúc dữ liệu nên là nhỏ nhất có thể.

3. Những cuốn sách kinh điển về cấu trúc dữ liệu

Data Structures and Algorithms Made Easy – Narasimha Karumanchi

Cuốn này giải thích các khái niệm cấu trúc dữ liệu xuyên suốt 21 chương với các chủ đề như: Recursion & Backtracking, Linked Lists, Stacks, Queues, Trees, Priority Queues, Heaps, String Algorithms, Algorithms Design Technique… Nó cũng đưa ra nhiều phương pháp tiếp cận khác nhau cho mỗi vấn đề, nhờ đó, độc giả dễ dàng hình dung và phân tích được các giải thuật tương ứng cho từng bài toán.

Data Structures and Algorithm in Java, 2nd Edition – Robert Lafore

Cuốn này giải thích các concept ở mức căn bản nhất cùng các gợi ý về solution cho mỗi project ở từng chương. Cuốn này đã từng được sử dụng làm giáo trình cho một khóa học “Cấu trúc dữ liệu và giải thuật”. Các topic ở những cuốn sách kiểu này thường không khác nhau nhiều, vẫn là các cấu trúc dữ liệu quen thuộc : Stack, queue, heaps, hashtable…

Introduction to Algorithm, 3rd edition – Thomas H.Cormen

Cuốn này bao quát một phạm vi khá rộng trong cấu trúc dữ liệu, bên cạnh đó, mỗi topic đều được viết rất sâu. Introduction to Algorithm phù hợp với tất cả đối tượng – từ sinh viên chưa tốt nghiệp cho đến chuyên gia…

Pseudocode cũng được sử dụng để trình bày các ý tưởng trong cuốn sách này. Các chủ đề thuộc giải thuật hiện đại như lý thuyết đồ thị, giải thuật đa luồng đều được đề cập rất chi tiết. Đây cũng là một bí kíp cần được tu luyện tử tế trước khi đi phỏng vấn.

Algorithm, 4th Edition – Robert Sedgewick, Kevin Wayne

Cuốn này được sử dụng rộng rãi tại các trường đại học trên toàn thế giới. Nó thống kê các thuật toán quan trọng đang được áp dụng rộng rãi cũng như đề cập một cách hết sức chi tiết tới các thuật toán và cấu trúc dữ liệu áp dụng cho công việc tìm kiếm, sắp xếp, xử lý đồ thị và xử lý xâu ký tự, Tác giả Robert Sedgewick và Kevin Wayne cũng duy trì một cổng thông tin điện tử cung cấp source code tương ứng. Trong tài liệu này, ngôn ngữ lập trình được sử dụng là Java.

Elements of Programming Interviews in Java: The Insiders’ Guide – Adnan Aziz, Tsung-Hsien Lee, Amit Prakash

The Elements of Programming Interviews hỗ trợ rất hiệu quả cho các buổi phỏng vấn. Tác giả cuốn này phát hành 2 bản, một bản cho ngôn ngữ C và một bản cho Java.

Các hướng dẫn trong quyển này bắt đầu với các giải thuật kiểu vét cạn, sau đó phân tích và đi đến những lựa chọn tối ưu hơn. Tất cả các vấn đề đều được phân loại dựa theo độ khó và các trường hợp liên quan trong thực tế, kèm theo đó là những gợi ý hữu ích, nhờ vậy bạn dễ dàng hiểu và áp dụng các giải thuật này trong công việc thường nhật. Cuốn sách này cũng mô phỏng được một phần những khó khăn bạn sẽ gặp phải trong các buổi phỏng vấn.

Tổng kết

Đây không phải là tài liệu mà mình nghiên cứu nhưng mình đã tình cờ được được nó trong lần tìm kiếm về chủ đề Cấu trúc dữ liệu và giải thuật. Hy vọng bài viết này có thể phần nào giúp được mọi người khi quan tâm đến chủ đề này.
Bài viết gốc: (https://techinsight.com.vn/bi-kip-giai-quyet-cau-truc-du-lieu/)