Những cấu trúc dữ liệu và thuật toán tôi dùng trong thực chiến

Người ta thường nói rằng những câu hỏi thuật toán hay được hỏi trong phỏng vấn thực ra không được dùng ngoài thực tế,

tác giả đã tổng hợp những thứ mình thực sự thường xuyên dùng khi làm việc tại Skype/Uber v.v. kèm ví dụ, cùng các tài liệu nền tảng nên đọc

Đồ thị và duyệt đồ thị: Skype & Uber

Đồ thị có trọng số và đường đi ngắn nhất: SkyScanner

Sắp xếp: Skype

Bảng băm và hàm băm: ở mọi nơi

Ngăn xếp và hàng đợi: đôi khi

Mật mã học (Crypto), lý thuyết xác suất và suy đoán, lưới lục giác và chỉ mục phân cấp: Uber

• Về thuật toán và cấu trúc dữ liệu trong phỏng vấn

Biết các thuật toán nổi tiếng hay những cấu trúc dữ liệu đặc biệt không phải là điều quan trọng nhất.

Bạn cần hiểu thuật toán là gì, và phải có khả năng tự nghĩ ra những thuật toán đơn giản như thuật toán tham lam.

Cần biết các cấu trúc dữ liệu cơ bản như bảng băm, hàng đợi & ngăn xếp, nhưng không cần phải học thuộc những thuật toán đặc biệt như Dijkstra hay A*.

Phần lớn công việc tôi từng làm với các thuật toán vượt quá phạm vi sắp xếp chỉ dừng ở mức tra cứu rồi cố gắng hiểu chúng.

Các cấu trúc dữ liệu đặc biệt như cây Red-Black hay AVL cũng vậy.

Thực tế tôi chưa từng phải dùng những cấu trúc dữ liệu như vậy, và kể cả khi cần thì tôi cũng sẽ tìm lại để xem.

Ở Thung lũng Silicon, việc đặt câu hỏi về quy hoạch động hoặc các cấu trúc dữ liệu đặc biệt đang ngày càng trở nên phổ biến hơn.

Những câu hỏi như vậy có thể giúp tuyển được các kỹ sư xuất sắc, nhưng cũng khiến người ta bỏ lỡ những người làm công việc không hề cần kiến thức thuật toán nâng cao mà vẫn làm rất giỏi.

Điều thực sự cần thiết là nhận thức về những cấu trúc dữ liệu phổ biến nhất và khả năng dùng những thuật toán đơn giản nhất như một công cụ để giải quyết vấn đề.

Cấu trúc dữ liệu và thuật toán chỉ là một bộ công cụ.

Đó là những công cụ bạn cần dùng một cách tự tin khi phát triển phần mềm.

Nếu hiểu rõ các công cụ này, bạn sẽ trở nên quen thuộc hơn khi đọc những đoạn mã sử dụng chúng.

Ngoài ra, bạn cũng sẽ tự tin hơn khi triển khai các lời giải cho những vấn đề khó.

Để nắm được những điều cơ bản, tôi đề xuất các tài liệu sau. (liên kết ở phần bình luận)

• Data Structures Overview của GeekforGeeks (tập hợp bài viết trực tuyến)

• DataStructure Collection của HackerRank (học bằng cách giải bài tập)

• Grokking Algorithms: thuật toán được giải thích bằng hình ảnh để hiểu khái niệm (bản dịch)

• The Algorithm Design Manual và Algorithms: Fourth Edition quá khô khan và không thật sự phù hợp để dùng hằng ngày trong thực tế.

[xguru]

• Data Structures Overview của GeekforGeeks

https://geeksforgeeks.org/overview-of-data-structures-set-1-linear-dat…

• Bộ sưu tập DataStructure của HackerRank

https://www.hackerrank.com/domains/data-structures

• Grokking Algorithms: thuật toán giúp hiểu khái niệm bằng hình ảnh

Bản tiếng Anh: https://www.amazon.com/gp/product/1617292230/?tag=amzneu-20

Bản tiếng Hàn (Hanbit Media): https://www.hanbit.co.kr/store/books/look.php?p_code=B5896248244

The Algorithm Design Manual https://www.amazon.com/gp/product/1848000693?tag=amzneu-20

Algorithms: 4th Edition https://www.amazon.com/gp/product/032157351X/?tag=amzneu-20

• Thuật toán bản sửa đổi lần 4 (ebook) http://www.yes24.com/Product/Goods/71729526

[xguru]

Giai thoại ở phần đầu bài về việc Max Howell, nhà phát triển Homebrew, trượt phỏng vấn Google vì không thể viết cách đảo ngược cây nhị phân lên bảng là chuyện rất nổi tiếng.

Trớ trêu là 90% lập trình viên Google thực tế đang dùng Homebrew, vậy mà chính nhà phát triển của nó lại bị đánh trượt..

[lazinism]

90% đó là con số do một lập trình viên homebrew tự đưa ra, và hình như trong tweet đó cũng có một lập trình viên Google trả lời rằng tuyệt đối không phải là 90%.

Dù sao thì ở Google desktop dùng gUbuntu còn laptop là shell machine, nên cũng chẳng có mấy dịp để dùng đến.