Cải thiện các thuật toán và kỹ năng cấu trúc dữ liệu của bạn

Hình ảnh từ Primo Primer.

Một số tài nguyên trong bài viết này ban đầu xuất hiện trong một trong những bình luận của tôi về một bài đăng trên reddit đã trở nên khá phổ biến. Đây là chủ đề ban đầu, và bài viết mới của tôi ở bên dưới.

Nguyên tắc cơ bản

Điều đầu tiên bạn sẽ cần nếu bạn muốn cải thiện thuật toán và cấu trúc dữ liệu là một cơ sở vững chắc. Cơ sở này có thể được học theo một trong nhiều cách, thông qua chương trình khoa học máy tính tại trường đại học, một số bootcamp mã hóa tập trung một chút vào các chủ đề dưới đây hoặc bạn có thể tự học từ sách, video hoặc bài giảng trực tuyến. Vì vậy, bạn sẽ cần một sự hiểu biết cơ bản về các chủ đề sau để bắt đầu:

Cấu trúc dữ liệu

Tìm hiểu về mảng, danh sách được liên kết, cây nhị phân, bảng băm, biểu đồ, ngăn xếp, hàng đợi, đống và các cấu trúc dữ liệu cơ bản khác.

Toán & Logic

Bạn cần phải biết một số khái niệm toán học từ một số lĩnh vực khác nhau nếu bạn muốn vượt trội về thuật toán. Tìm hiểu về lý thuyết tập hợp, máy trạng thái hữu hạn, biểu thức chính quy, nhân ma trận, phép toán bit, giải phương trình tuyến tính, các khái niệm tổ hợp quan trọng như hoán vị, kết hợp, nguyên lý pigeonhole.

Kiến trúc máy tính

Tìm hiểu cách dữ liệu được biểu diễn trong máy tính, những điều cơ bản của thiết kế logic kỹ thuật số, đại số boolean, số học máy tính, biểu diễn dấu phẩy động, thiết kế bộ đệm. Hãy thử và tìm hiểu một chút về lập trình C và hội.

Tiến về phía trước Nguyên tắc cơ bản

Một khi bạn cảm thấy mình hiểu rõ về hầu hết các khái niệm được liệt kê ở trên, đã đến lúc bắt đầu đi sâu vào phần thuật toán. Dưới đây là danh sách các tài nguyên và những điều tôi đã làm để viết tốt hơn và hiểu các thuật toán quan trọng.

Các trang được lấy từ Hướng dẫn thiết kế thuật toán.

Big-O & Thời gian chạy

  • Tìm hiểu Big-O là gì và cách phân tích thời gian chạy của các thuật toán. Đây là một cuốn sách kinh điển về chủ đề (đây là chương về sự tăng trưởng của các chức năng).
  • Dưới đây là một danh sách tốt các khóa học trực tuyến dạy các thuật toán.

Tự thực hiện một số thuật toán

Bắt đầu bằng cách tự thực hiện một số thuật toán quan trọng và tìm hiểu về thời gian chạy của chúng. Một số ví dụ:

  • Tìm kiếm nhị phân
  • Thuật toán Euclid
  • Độ sâu và chiều rộng tìm kiếm đầu tiên
  • Con đường ngắn nhất của Dijkstra
  • Đi qua cây nhị phân
  • Sắp xếp chèn, Sáp nhập, Quicksort
  • Heap tối thiểu
  • Thêm ví dụ và danh sách.

Sách thuật toán

  • Đọc Hướng dẫn thiết kế thuật toán. Nó một cuốn sách tuyệt vời và nó yêu thích của tôi.
  • Giới thiệu về Thuật toán là một cuốn sách cổ điển bao gồm rất nhiều tài liệu.
  • Các yếu tố của các cuộc phỏng vấn lập trình chứa rất nhiều thách thức và giải pháp mã sẽ giúp bạn chuẩn bị cho các cuộc phỏng vấn.

Thử thách

  • Thực hành mã hóa các thuật toán đơn giản và nâng cao hơn trên các trang web như Coderbyte và HackerRank, cung cấp các giải thích và giải pháp để bạn có thể học hỏi từ các lập trình viên khác.
  • Vượt qua những thách thức trên trang web thuật toán python tương tác này.
  • 10 trang web thử thách mã hóa phổ biến nhất năm 2017.
  • 5 thử thách mã khó nhất cho người mới bắt đầu.

Giải thích thuật toán & Câu hỏi phỏng vấn

  • Đọc càng nhiều giải thích thuật toán và ví dụ mã càng tốt trên GeekforGeek. Dưới đây là một ví dụ về một bài viết tốt về các thuật toán đồ thị.
  • Nhìn vào một số câu hỏi phỏng vấn được đăng trên CareerCup và thử và hiểu cách người dùng khác giải quyết các câu hỏi. Giống như ví dụ này.
  • Ngoài các trang web thử thách mã hóa, hãy thử và giải quyết các câu hỏi phỏng vấn mã hóa phổ biến mà bạn tìm thấy trực tuyến, chẳng hạn như những câu hỏi trong danh sách này.

Lập trình năng động

Đây là một khái niệm rất quan trọng bạn sẽ cần phải hiểu nếu bạn muốn cải thiện thuật toán, đó là lý do tôi tách chủ đề này khỏi phần còn lại. Mô tả từ Wikipedia cho nó là (bashing là của tôi):

Một phương pháp để giải quyết một vấn đề phức tạp bằng cách chia nó thành một tập hợp các bài toán con đơn giản hơn, giải từng bài toán con đó một lần và lưu trữ các giải pháp của chúng. Lần sau, cùng một bài toán con xảy ra, thay vì tính toán lại giải pháp của nó, người ta chỉ cần tra cứu giải pháp đã được tính toán trước đó, nhờ đó tiết kiệm thời gian tính toán.

Tôi đã thấy lập trình động xuất hiện trong một vài cuộc phỏng vấn mã hóa mà tôi đã có. Tôi cũng đã thấy các vấn đề đòi hỏi một giải pháp lập trình động trên các trang web thách thức như LeetCode, Google Code Jam và một số thách thức trên Google Foo Bar yêu cầu một giải pháp DP.

Tôi khuyên bạn nên thử và giải quyết càng nhiều vấn đề trong danh sách này càng tốt. Ngoài ra còn có một hướng dẫn tốt về TopCoder có tiêu đề: Lập trình động - Từ Novice đến Advanced. Rất nhiều vấn đề DP có cấu trúc và mô hình giống nhau, vì vậy nếu bạn giải quyết 3 vấn đề DP mỗi ngày trong 2 tuần hoặc lâu hơn, sau một thời gian, bạn sẽ có thể phát hiện và giải quyết vấn đề DP không có vấn đề gì.

Tài nguyên nâng cao trong thuật toán (tùy chọn)

  • Bài giảng cấu trúc dữ liệu nâng cao của Erik Demaine
  • Thuật toán giới hạn dưới: Vui với chứng minh độ cứng của Erik Demaine
  • Cẩm nang lập trình viên cạnh tranh
  • Hướng dẫn về Hitchhiker về các cuộc thi lập trình
  • AlgoWiki: Một wiki dành riêng cho lập trình cạnh tranh
  • Các vấn đề và thuật toán Hình học tính toán (thú vị và vui vẻ, nhưng có thể trở nên khá khó khăn)
  • Danh sách các vấn đề hoàn thành NP
  • Sách cấu trúc dữ liệu mở: triển khai và phân tích cấu trúc dữ liệu cho các chuỗi, hàng đợi, hàng đợi ưu tiên, từ điển không có thứ tự, từ điển được đặt hàng và biểu đồ

Tôi hy vọng bạn thích danh sách tài nguyên này. Hãy thoải mái thực hành mã hóa trên Coderbyte và bình luận bên dưới với bất kỳ tài nguyên nào khác mà bạn cho là hữu ích.