Bản gốc: Nội dung chínhTự ôn tập phỏng vấn về lập trình [Coding Interview University]
- English
Tác giả gốc: John Washam
Đóng góp cho bản dịch tiếng Việt:
- Lê Tiến Tài - @letientai299
- Võ Tường Thọ - @thovo
- Lê Tấn Đăng Khoa - @dksdc
- Trương Đức Duy - @dauruy
- Lương Đăng Hải - @jarvisluong
- Hiền Vương - @duchienvuong
Ghi chú riêng cho việc duy trì và cập nhật bản dịch tiếng Việt:
Bản dịch này nhằm mục đích khuyến khích các bạn trẻ yêu thích công nghệ nhưng chưa vững tiếng Anh dễ tiếp cận, và tìm được hướng nghiên cứu. Để đi xa hơn trong ngành công nghệ thông tin [CNTT], sớm hay muộn, bạn cũng cần phải trau dồi vốn tiếng Anh của mình. Vì vậy, các thuật ngữ chuyên ngành, mình xin được giữ nguyên gốc. Ví dụ như:
stack,heap,queue,...Mình cố gắng dịch thoát nghĩa, sao cho các bạn với ít kiến thức công nghệ thông tin nhất cũng có thể hiểu được. Trong quá trình dịch khó có thể trách khỏi sai sót, xin được lượng thứ.
Mọi ý kiến, đóng góp về bản dịch, vui lòng tạo một issue mới hoặc bạn có thể chỉnh sửa và tạo Pull Request, đồng thời cc trực tiếp các dịch giả để kiểm tra.
Ban đầu, đây chỉ là một danh sách to-do [danh sách các việc cần làm] ngắn về các chủ đề phải ôn tập của tôi, để trở thành một kỹ sư phần mềm. Nhưng rôi nó lớn dần nên như ngày nay. Sau khi đi hết con đường này, tôi đã được tuyển vào vị trí Software Development Engineer ở Amazon! Bạn có lẽ không cần phải học nhiều như tôi đã học. Nhưng dù sao, mọi thứ bạn cần ở đây.
Những chủ đề này sẽ chuẩn bị cho bạn nền tảng kiến thức vững vàng cho bất kỳ công ty phần mềm nào, bao gồm cả những gã khổng lồ như: Amazon, Facebook, Google hay Microsoft.
Chúc may mắn!
Giới thiệu
Đây là kế hoạch học tập trong nhiều tháng của tôi, để từ một nhà phát triển web [tự học, không có bằng cấp về Khoa Học Máy Tính - KHMT] trở thành một kỹ sư phần mềm ở Google.
Danh sách dài này được trích và mở rộng từ Ghi chú huấn luyện của Google, vậy nên đây là những gì bạn cần biết. Một vài mục tôi thêm vào ở cuối danh sách có thể xuất hiện trong cuộc phỏng vấn hoặc hữu ích cho việc giải quyết các bài toán về lập trình. Nhiều mục đến từ bài viết Lấy được việc ở Google [Get that job at Google]" của Steve Yegge.
Tôi lược bớt những gì bạn cần từ lời khuyên của Yegge. Tôi cũng chỉnh sửa lại các yêu cầu dựa trên thông tin tôi có được từ bạn bè ở Google. Danh sách này được thiết kế cho Kỹ sư phần mềm hoặc những ai chuyển từ phát triển web hoặc phần mềm sang kỹ nghệ phần mềm [khi mà kiến thức về Khoa Học Máy Tính là bắt buộc]. Nếu bạn có nhiều kinh nghiệm và muốn khẳng định nhiều năm trong đó bạn làm việc như một kỹ sư phần mềm, hãy sẵn sàng cho một buổi phỏng vấn khó hơn. Xem thêm ở đây.
Nếu bạn có kinh nghiệm trong phát triển web hoặc ứng dụng, hãy chú ý rằng Google xem việc xây dựng phần mềm khác với web và ứng dụng thông thường. Họ yêu cầu kiến thức về Khoa Học Máy Tính.
Thêm vào đó, nếu bạn muốn trở thành một kỹ sư hệ thống [System Engineer], hãy học thêm từ danh sách bổ sung [mạng máy tính, bảo mật,...]
Mục lục
- Giới thiệu?
- Vì sao tôi cần tài liệu này?
- Sử dụng tài liệu này như thế nào?
- Đừng nghĩ rằng bạn không đủ thông minh
- Về nguồn video
- Quy trình phỏng vấn & các bước chuẩn bị tổng quát
- Chọn ngôn ngữ lập trình cho cuộc phỏng vấn
- Danh mục sách
- Trước khi bắt đầu
- Những phần không được đề cập
- Kiến thức tiên quyết
- Kế hoạch hằng ngày
- Độ phức tạp của thuật toán / Big-O / Phân tích tiệm cận
- Cấu trúc dữ liệu
- Arrays
- Linked Lists
- Stack
- Queue
- Hash table
- Kiến thức bổ sung
- Tìm kiếm nhị phân
- Toán tử trên bit
- Cây
- Cây - Ghi chú và kiến thức nền
- Cây tìm kiếm nhị phân
- Heap / Priority Queue / Binary Heap
- Cây tìm kiếm cân bằng [một chủ đề chung, không đi sâu vào chi tiết]
- Duyệt cây: preorder, inorder, postorder, BFS, DFS
- Sắp xếp
- Sắp xếp chọn [Selection Sort]
- Sắp xếp chèn [Insertion Sort]
- Sắp xếp chọn vun đống [Heapsort]
- Sắp xếp nhanh [Quicksort]
- Sắp xếp trộn [Merge Sort]
- Đồ thị
- có hướng
- vô hướng
- ma trận kề
- danh sách kề
- duyệt đồ thị: BFS, DFS
- Kiến thức bổ
sung
- Đệ quy
- Quy hoạch động
- Lập trình hướng đối tượng
- Mẫu thiết kế
- Tổ hợp và Xác Suất
- NP, NP-Complete và thuật toán xấp xỉ gần đúng
- Bộ nhớ cache
- Tiến trình và tiểu trình
- Các công trình nghiên cứu
- Kiểm thử phần mềm
- Lập lịch
- Cài đặt các hàm hệ thống
- Tìm kiếm và xử lý chuỗi
- Tries
- Cách biểu diễn số thực
- Unicode
- Endianness
- Mạng máy tính
- Thiết kế hệ thống, Khả năng mở rộng, Xử lý dữ liệu [Nếu bạn có hơn 4 năm kinh nghiệm]
- Tống kết
- Thực hành các câu hỏi về lập trình
- Giải bài tập lập trình
- Khi bạn tiến gần đến kỳ phỏng vấn
- Lý lịch [Resume] của bạn
- Hãy nghĩ đến những thứ bạn sẽ được hỏi
- Chuẩn bị câu hỏi dành cho phỏng vấn viên
- Khi bạn được nhận việc
---------------- Những mục dưới đây là tuỳ chọn ----------------
- Sách bổ sung
- Học thêm
- Trình biên dịch
- Emacs và vi[m]
- Các công cụ chạy trên dòng lệnh của Unix
- Lý thuyết thông tin
- Parity & Hamming Code
- Entropy
- Mã hóa
- Thuật toán nén
- Bảo mật
- Trình dọn rác
- Lập trình song song
- Messaging, Serialization, and Queueing Systems
- A*
- Fast Fourier Transform
- Bloom Filter
- HyperLogLog
- Locality-Sensitive Hashing
- van Emde Boas Trees
- Augmented Data Structures
- N-ary [K-ary, M-ary] trees
- Balanced search trees
- AVL trees
- Splay trees
- Red/black trees
- 2-3 search trees
- 2-3-4 Trees [aka 2-4 trees]
- N-ary [K-ary, M-ary] trees
- B-Trees
- k-D Trees
- Skip lists
- Network Flows
- Math for Fast Processing
- Treap
- Linear Programming
- Geometry, Convex hull
- Discrete math
- Machine Learning
- Go
- Đọc thêm về một số đề tài
- Các chuỗi Video
- Các khóa học khoa học máy tính
Vì sao tôi cần tài liệu này?
Tôi đang chuẩn bị tham gia phỏng vấn ở Google. Tôi từng làm web, xây dựng các dịch vụ và lập các công ty khởi nghiệp từ năm 1997. Tôi có bằng Kinh Tế, nhưng không có bằng Khoa Học Máy Tính. Tôi thấy sự nghiệp của mình khá thành công, nhưng như thế chưa đủ. Tôi muốn làm việc ở Google, được tham gia xử lý một hệ thống lớn; thực sự hiểu rõ về máy tính, sự hiệu quả của các thuật toán và cấu trúc dữ liệu, các ngôn ngữ lập trình cấp thấp, và chúng hoạt động cùng nhau như thế nào. Và nếu bạn không biết về cái nào trong số đó, Google sẽ không tuyển bạn.
Khi tôi bắt đầu dự án này, tôi không phân biệt được stack và heap, không biết về Big-O, không có khái niệm gì về cây [tree] hay việc duyệt đồ thị [graph traversal]. Và nếu buộc phải viết code cho một thuật toán sắp xếp, tôi đảm bảo rằng nó sẽ không chạy tốt.
Tất cả các cấu trúc dữ
liệu tôi từng sử dụng đều được cài đặt sẵn trong ngôn ngữ lập trình và tôi không nhất thiết phải biết chúng làm việc như thế nào. Tôi chưa từng phải tự quản lý vùng nhớ, trừ khi một tiến trình đang chạy ném lỗi "hết bộ nhớ" [out of memory], và sau đó tôi phải tìm một cách giải quyết khác. Tồi từng sử dụng mảng nhiều chiều vài lần trong đời, và hàng ngàn mảng kết hợp [associate arrays]. Nhưng thực sự tôi chưa từng tự mình xây dựng một cấu trúc dữ liệu nào.
Nhưng, sau khi trải qua dự án này, tôi rất tự tin rằng mình sẽ được tuyển. Đây là một dự án dài hơi, sẽ tốn của tôi hàng tháng. Nếu bạn đã quen với nhiều nội dung trong này, bạn sẽ mất ít thời gian hơn.
Sử dụng tài liệu này như thế nào?
Phần này được viết lại khá nhiều để thuận tiện cho các bạn tiếp cận. Dựa theo bản gốc, tác giả có vẻ như cũng đang cố hướng dẫn cho người mới dùng git.
Bạn có thể bỏ qua mục này nếu đã có kiến thức về Git, Github và Github Flavored Markdown
Nếu bạn chưa biết về git thì vui lòng tham khảo các bài hướng dẫn sau để nắm cách sử dụng:
- Tiếng Anh: git - the simple guide
- Tiếng Việt: Sổ tay git cho người mới bắt đầu [Việt hóa từ nội dung với link trên]
Tiếp theo, bạn cần biết cách gắp [fork] một repo trên github:
- Tiếng Anh Fork a repo
- Tiếng Việt: Cách gắp [fork] một repo trên github [Việt hoá từ nội dung với link trên]
Ok, bây giờ bạn có thể bắt đầu:
- Fork repo này.
- Clone bản fork của bạn về máy tính cá nhân.
git clone //github.com//coding-interview-university - Chạy các dòng lệnh sau
- Tạo một branch mới để đánh dấu tiến độ của bạn:
- Check các phần đã hoàn thành bằng cách thêm
xvào giữa cặp ngoặc vuông [[ ]], như thế này:[x]. - Chạy
git add .để bắt đầu lưu lại các thay đổi. - Chạy
git commit -m "commit message". Thaycommit messagevới ghi chú của bạn cho sự thay đổi đó. - Đồng bộ thay đổi với bản fork trên Github của bạn bằng
git push origin main.
Đừng nghĩ rằng bạn không đủ thông minh
- Các kỹ sư của Google là những người xuất sắc, nhưng nhiều người vẫn cho rằng họ không đủ thông minh, mặc dù họ đang làm việc tại Google.
- Bí mật của của Thiên Tài Lập Trình [The myth of the Genius Programmer] - video
- ulie Pagano: Đi một mình rất nguy hiểm - Cuộc chiến với con quái vật vô hình trong công nghệ
- Hãy tin bạn có thể thay đổi
Về nguồn video
Một vài video chỉ xem được khi bạn tham gia vào các lớp học online trên Coursera, EdX, hay Lynda.com. Các lớp đó được gọi là MOOC. Đôi khi các lớp chưa mở, và bạn phải đợi một vài tháng đến khi chúng được mở lại, do đó bạn không thể truy cập vào video được. Lynda.com thì không miễn phí.
Tôi sẽ rất cảm kích sự hỗ trợ của các bạn trong việc thêm các nguồn video miễn phí và luôn sẵn có, ví dụ như Youtube, để hỗ trợ nguồn video từ các khóa học online.
Tôi cũng rất thích xem các bài giảng của các trường đại học.
Quy trình phỏng vấn & các bước chuẩn bị tổng quát
- ABC: Always Be Coding
- 4 bước đến Google dù không có bằng cấp
- Whiteboarding [Giải toán lập trình trên bảng trắng]
- Google nghĩ thế nào về Tuyển dụng, Quản lý và Văn hóa
- Whiteboarding hiệu quả trong khi phỏng vấn kỹ năng lập trình
- Cracking The Coding Interview Set 1:
- Gayle L McDowell - Cracking The Coding Interview [video]
- Cracking the Coding Interview with Author Gayle Laakmann McDowell [video]
- Làm thế nào để lấy được công việc ở Big 4:
- Làm sao để lấy được công việc ở Big 4 - Amazon, Facebook, Google & Microsoft [video]
- Thất bại trong cuộc phỏng vấn với Google
Chọn ngôn ngữ lập trình cho cuộc phỏng vấn
Bạn có thể chọn ngôn ngữ mà bạn quen thuộc để thực hiện phần viết mã trong lúc phỏng vấn, nhưng với Google, những ngôn ngữ sau đây là thích hợp nhất:
- C++
- Java
- Python
Bạn cũng có thể sử dụng các ngôn ngữ sau đây, nhưng hãy tìm hiểu thêm trước. Chúng có thể có bất lợi:
- JavaScript
- Ruby
Dù sao, bạn cũng cần phải rất quen thuộc với ngôn ngữ lập trình của mình.
Xem thêm về các sự lựa chọn:
- //www.byte-by-byte.com/choose-the-right-language-for-your-coding-interview/
- //blog.codingforinterviews.com/best-programming-language-jobs/
- //www.quora.com/What-is-the-best-language-to-program-in-for-an-in-person-Google-interview
Xem tài liệu về các ngôn ngữ ở đây
Bạn sẽ thấy vài tài liệu về C, C++ và Python bên dưới, vì tôi đang học chúng. Ngoài ra còn có một vài đầu sách nữa, xem ở cuối.
Danh mục sách
Đây là danh sách rút gọn từ những gì mà tôi đọc, để tiết kiệm thời gian cho bạn. [xem bên dưới].
Chuẩn bị phỏng vấn
- Programming Interviews Exposed: Coding Your Way Through the Interview, 4nd Edition
- Có câu trả lời bằng C++ và Java
- Được khuyến khích bởi các khóa hướng dẫn của Google.
- Đây là một phần luyện tập tốt trước khi bắt đầu với quyển Cracking the Coding Interview
- Không quá khó, phần lớn các bài toán có lẽ dễ hơn nhiều so với những gì bạn thường thấy trong một buổi phỏng vấn [dựa theo những gì tôi đọc được]
- Cracking the Coding Interview, 6th Edition
- Trả lời bằng Java
- Được khuyến nghị trên Google Careers site
- Nếu bạn thấy mọi người trích dẫn "The Google Resume", đó là một cuốn sách được thay thế bởi "Cracking the Coding Interview".
Nếu bạn có nhiều thời gian hơn nữa:
- Elements of Programming Interviews
- Code trên C++, rất tốt nếu bạn muốn sử dụng C++ làm ngôn ngữ chính cho cuộc phỏng vấn.
- Một quyển sách hay về giải quyết vấn đề nói chung.
Kiến trúc máy tính
Nếu không có nhiều thời gian:
- Write Great Code: Volume 1: Understanding the Machine
- Quyển này được xuất bản năm 2004, phần nào đã lỗi thời, nhưng nó vẫn là một tài liệu tuyệt vời để tìm hiểu về máy tính một cách ngắn gọn. - Tác giả phát minh ra HLA [High Level Assembly], vậy nên hãy hãy chú ý một chút về các ví dụ và định nghĩa trong sách. Tuy không được sử dụng rộng rãi, nhưng đó là một ví dụ hiện đại về hợp ngữ.
- Những chương này rất đáng đọc để xây dựng cho bạn một nền tảng tốt [giữ nguyên gốc tiếng Anh]:
- Chapter 2 - Numeric Representation
- Chapter 3 - Binary Arithmetic and Bit Operations
- Chapter 4 - Floating-Point Representation
- Chapter 5 - Character Representation
- Chapter 6 - Memory Organization and Access
- Chapter 7 - Composite Data Types and Memory Objects
- Chapter 9 - CPU Architecture
- Chapter 10 - Instruction Set Architecture
- Chapter 11 - Memory Architecture and Organization
Nếu bạn có nhiều thời gian [tôi đã muốn đọc quyển này]:
- Computer
Architecture, Fifth Edition: A Quantitative Approach
- Dành cho người có điều kiện hơn, sách được cập nhật gần hơn [2011], đồng thời đòi hỏi nhiều thời gian hơn để thấm.
Từng ngôn ngữ riêng biệt
Bạn phải chọn một ngôn ngữ cho cuộc phỏng vấn [xem ở trên]. Đây là các khuyến nghị của tôi. Tôi không có tài liệu cho tất cả các ngôn ngữ lập trình, vậy nên, đóng góp từ bạn luôn được chào đón. Nếu bạn muốn đọc xuyên suốt một trong những quyển sách này, bạn nên có kiến thức về cấu trúc dữ liệu và giải thuật. Bạn cũng nên luyện tập giải toán lập trình.
Bạn có thể bỏ qua bài giảng video trong project này, trừ khi bạn muốn tự đánh giá lại kiến thức của mình.
Đây là tài liệu ngôn ngữ lập trình bổ sung.
C++
Tôi chưa đọc 2 cuốn này, nhưng chúng được đánh giá cao, và được viết bởi Sedgewick. Giáo sư Sedgewick rất xuất sắc.
- Algorithms in C++, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching
- Algorithms in C++ Part 5: Graph Algorithms
Nếu bạn có đề xuất nào tốt hơn cho C++, hãy cho tôi biết. Tôi đang tìm một tài liệu súc tích.
Java
- Algorithms [Sedgewick and Wayne]
- Video và mục lục của sách [và Sedgewick!]:
- Algorithms I
- Algorithms II
- Video và mục lục của sách [và Sedgewick!]:
hoặc:
- Data Structures and Algorithms in Java
- Bởi Goodrich, Tamassia, Goldwasser
- Được sử dụng làm tài liệu tham khảo cho khóa Dẫn nhập vào khoa học máy tính của UC Berkeley - Hãy xem mục sách của tôi bên dưới cho phiên bản Python. Cuốn sách này cũng bao phủ các chủ đề đó.
Python
- Data Structures and Algorithms in Python
- Bởi Goodrich, Tamassia, Goldwasser
- Tôi thích cuốn này. Nó bao phủ mọi thứ cần thiết và hơn thế nữa.
- Pythonic code [code theo đúng phong cách Python]
- Báo cáo đọc sách mới toanh của tôi: //googleyasheck.com/book-report-data-structures-and-algorithms-in-python/
Sách tùy chọn
Một vài người đề xuất mấy quyển này, nhưng tôi nghĩ chúng là quá nặng, trừ khi bạn có nhiều kinh nghiệm với kỹ nghệ phần mềm và đang mong đợi một cuộc phỏng vấn khó hơn nhiều:
Algorithm Design Manual [Skiena]
- Như một tài liệu ôn tập và hỗ trợ nhận dạng vấn đề.
- Danh mục thuật toán thật sự vượt xa độ khó của một cuộc phỏng vấn.
- Cuốn sách có 2 phần:
- Giáo trình về cấu trúc dữ liệu và giải thuật:
- Ưu:
- Là một bài tổng quát tốt tương đương với các giáo trình khác.
- Nhiều câu chuyện thú vị từ kinh nghiệm của tác giả trong việc giải quyết các vấn đề thực tế và trong giới học thuật.
- Code mẫu bằng C.
- Nhược:
- Cô đặc và có thể khó hiểu ngang với CLRS, và trong một số chủ đề, CLRS có thể là một tài liệu tốt hơn để tham khảo.
- Các chương 7, 8, 9 có thể rất vất vả để theo được, vì một vài phần không được giải thích rõ, hoặc là yêu cầu nhiều não hơn những gì tôi có.
- Đừng hiểu lầm: Tôi thích Skiena, cách dạy học và phong các của ông ấy, nhưng tôi có lẽ không đủ khả năng để tốt nghiệp ở Stony Brook [nơi Skiena giảng dạy].
- Ưu:
- Danh mục thuật toán:
- Đây là phần chính yếu mà bạn mua được từ quyển sách.
- Sắp đến được phần này rồi. Tôi sẽ cập nhật một khi tôi xong với nó.
- Giáo trình về cấu trúc dữ liệu và giải thuật:
- Trích dẫn từ Yegge: "Hơn hẳn những quyến sách khác, cuốn này giúp tôi hiểu rõ các bài toán về Graph phổ biến một cách đáng kinh ngạc và quan trọng như thế nào - chúng nên là một phần trong các công cụ của bất kỳ lập trình viên nào. Quyển sách đồng thời cũng bao phủ các cấu trúc dữ liệu cơ bản, các thuật toán sắp xếp. Đó là một điểm cộng. Nhưng phần quý giá thật sự nằm ở nửa sau, chính là bách khoa toàn thư ngắn gọn về hàng triệu bài toán hữu dụng và vô số cách để giải quyết chúng, trình bày sơ lược. Mỗi trang đều có một hình minh họa, giúp người đọc dễ ghi nhớ hơn. Đó là một cách tốt đề định dạng và phân loại các bài toán".
- Có thể thuê quyển sách này trên Kindle
- Half.com là một trang hữu dụng để tìm sách với giá tốt.
- Câu trả lời cho các bài tập trong sách:
- Solutions
- Solutions
- Danh mục lỗi của sách
Introduction to Algorithms - Chú ý: Đọc cuốn này chỉ có một ít giá trị. Đây là một tổng hợp xuất sắc về giải thuật và cấu trúc dữ liệu, nhưng nó không dạy cho bạn cách viết code xuất sắc. Để làm một lập trình viên giỏi, bạn đồng thời phải có khả năng phát triển một giải pháp một cách hiệu quả nữa.
- Trích lời Yegge: "Nhưng nếu bạn muốn đến với buổi phỏng vấn một cách có chuẩn bị, vậy hãy hoãn đơn xin ứng tuyển lại cho đến khi bạn hoàn tất quyển sách này"
- Half.com là một trang hữu dụng để tìm sách với giá tốt.
- Đôi được gọi là CLR, hoặc là CLRS [trích chữ cái đầu trong tên của các tác giả], vì Stein [một trong 4 tác giả, S trong CLRS] nhập cuộc trễ
Programming Pearls
- Vài chương đầu trình bày những giải pháp thông minh để giải quyết các vấn đề lập trình [một số đã rất cũ, từ thời người ta còn sử dụng băng từ]. Nhưng, đó chỉ là phần mở đầu. đây là một quyển sách về thiết kế và cấu trúc phần mềm, giống như Code Complete, nhưng ngắn hơn nhiều.
"Algorithms and Programming: Problems and Solutions" by Shen
- Sách tạm được, nhưng sau khi làm việc với các bài toán trong vài trang, tôi thấy nhức đầu với ngôn ngữ Pascal, do-while loop, mảng bắt đầu với số 1 [thay vì 0 như Java, C, C++, ...], và một vài thông tin không rõ ràng.
- Lẽ ra nên dành thời gian để giải toán từ các quyển sách khác hoặc làm toán lập trình online.
Trước khi bắt đầu
Danh sách này ngày càng dài theo năm tháng và tôi phải thừa nhận là nó ngoài tầm kiểm soát.
Sau đây là 1 vài lỗi tôi đã mắc phải, hy vọng rằng có thể mang lại cho bạn một chút kinh nghiệm.
1. Bạn sẽ không nhớ được tất cả
Tôi đã xem hàng giờ video và viết rất nhiều ghi chú, và chỉ sau vài tháng không còn nhớ chút gì. Tôi đã bỏ ra 3 ngày đọc lại các ghi chú và làm thẻ ghi nhớ để có thể đọc dễ dàng hơn.
Hãy đọc để tránh phạm phải sai lầm tương tự:
Retaining Computer Science Knowledge
2. Sử dụng thẻ ghi nhớ
Để giải quyết vấn đề, tôi đã viết 1 trang web nhỏ về thẻ ghi nhớ để thêm các thẻ mới với 2 dạng chính: kiến thức chung và code. Mỗi loại có định dạng riêng.
Tôi đã làm một trang mobile-first [lấy mobile là trọng tâm phát triển trang web] để có thể xem trên điện thoại và máy tính bảng, ở bất cứ đâu.
Tự tạo cho mình hoàn toàn miễn phí:
- Repo của trang thẻ ghi nhớ
- Cơ sở dữ liệu thẻ ghi nhớ của tôi: Lưu ý là tôi có đi hơi xa và các thẻ ghi nhớ có thể bao gồm cả hợp ngữ [ngôn ngữ máy] và Python cho đến cả máy học [machine learning] và thống kê. Như thế là quá nhiều cho các yêu cầu từ Google.
Ghi chú dành cho các thẻ ghi nhớ: Lần đầu tiên bạn nhận ra bạn biết câu trả lời, đừng đánh dấu là đã biết.Bạn phải xem thẻ tương tự và đưa ra câu trả lời chính xác vài lần trước khi bạn thực sự khẳng định đã nắm được vấn đề. Lặp đi lặp lại việc này sẽ giúp kiến thức được khắc sâu vào não bạn.
Có thể thay thế thẻ ghi nhớ với Anki, đây là ứng dụng mà bạn sẽ thấy tôi khuyến khích sử dụng rất nhiều lần. Nó sử dụng một hệ thống lặp để giúp bạn có thể ghi nhớ được kiến thức.
Đây là ứng dụng cực kì thân thiện với người dùng, có mặt trên tất cả các hệ điều hành, và có hệ thống lưu trữ đồng bộ đám mây. Tốn khoản 25$ cho iOS nhưng miễn phí trên các hệ điều hành khác.
Cơ sở dữ liệu thẻ ghi nhớ của tôi tuân theo chuẩn định dạng của Anki: //ankiweb.net/shared/info/25173560 [cảm ơn @xiewenya]
3. Xem đi xem lại và xem lại nữa
Tôi giữ một danh sách xem nhanh các mã của ASCII, OSI stack, định nghĩa về Big-O, và nhiều hơn nữa. Tôi đọc bất cứ khi nào rảnh rỗi.
Khi gặp vấn đề trong lúc code, nghỉ ngơi chừng nửa giờ và đọc lại các thẻ ghi nhớ.
4. Tập trung
Có rất nhiều thứ lấy đi sự tập trung của ta, việc này tốn rất nhiều thời gian. Tập trung và toàn tâm toàn ý rất khó.
Những phần không được đề cập
Danh sách lớn này bắt đầu như một bản To-do lược trích từ Huấn luyện phỏng vấn cho Google. Có vài công nghệ đang thịnh hành nhưng không được đề cập đến, ví dụ:
- SQL
- Javascript
- HTML, CSS, và các công nghệ thiết kế giao diện người dùng ["front-end"].
Kế hoạch hàng ngày
Một vài môn học chỉ mất một ngày, vài môn khác có thể mất nhiều ngày. Có vài môn chỉ có thể học thôi chứ không cài đặt được gì.
Mỗi ngày tôi sẽ chọn một trong các thứ liệt kê bên dưới, xem video bải giảng về nó, và viết mã trên:
- C - luyện tập sử dụng
structvà các hàm nhận cácstructđó cùng với các tham số khác. - C++ - không sử dụng các kiểu dữ liệu, cấu trúc sẵn có.
- C++ - sử dụng các kiểu, cấu trúc sẵn có, ví dụ như
std::listcho danh sách liên kết. - Python - sử dụng kiểu, cấu trúc sẵn có [để luyện tập Python].
- Viết test [thuật ngữ dành cho các đoạn mã chuyên để kiểm tra phần mềm, ở đây tác giả có lẽ muốn đề cập đến unit test] để chắc rằng tôi làm đúng. Đôi khi có thể chỉ là vài hàm
assert[]đơn giản. - Bạn có thể thực hành với Java hoặc ngôn ngữ khác. Đây chỉ là sự lựa chọn của tôi.
Bạn không cần luyện tất cả các ngôn ngữ đó. Chỉ cần một ngôn ngữ cho cuộc phỏng vấn là đủ.
Tại sao lại viết mã với tất cả các ngôn ngữ đó?
- Luyện tập, luyện tập, luyện tập, cho đến khi tôi phát bệnh với việc đó, và có thể giải các bài toán mà không gặp trục trặc gì [một vài bài toán có thể có nhiều trường hợp đặc biệt, hãy lưu lại các lần sai lầm đề ghi nhớ]
- Tôi muốn làm việc với các sức ép căn bản nhất [xin cấp phát/ giải phóng vùng nhớ, không sử dụng trợ giúp từ bộ dọn rác trong các ngôn ngữ câp cao, ngọai trừ Python]
- Học cách vận dụng kiểu dữ liệu sẵn có, nhờ đó, tôi có kinh nghiệm nhiều hơn và biết cách dùng chúng trong thực tế [sẽ không bao giờ bỏ thời gian ra tự thiết kế danh sách liên kết của riêng mình nữa].
Tôi có lẽ không đủ thời gian để thử hết tất cả các bước trên với từng chủ đề, nhưng tôi sẽ cố.
Bạn có thể xem code của tôi ở các trang sau:
- C
- C++
- Python
Bạn không cần phải ghi nhớ cặn kẽ từ giải thuật.
Hãy viết code trên bảng đen hoặc trên giấy. Đừng sử dụng máy tính. Chạy thử trên giấy với vài bộ dữ liệu mẫu, sau đó chạy thử thuật toán của bạn trên một máy tính.
Kiến thức tiên quyết
Học C
- C có ở khắp nơi. Bạn sẽ thấy các ví dụ trong sách, bài giảng, video, bất kỳ đâu mà bạn học.
- C Programming Language, Vol 2
- Sách ngắn, nhưng nó sẽ cho bạn một nền tảng tốt về C, và nếu bạn luyện tập nhiều hơn, bạn sẽ nhanh chóng thành thạo nó. Hiểu về C giúp bạn hiểu cách các chương trình và bộ nhớ hoạt động.
- Lời giải cho các câu hỏi
Máy tính thực thi một chương trình như thế nào?
- CPU thực thi chương trình thế nào [How does CPU execute program] - video
- Tập lệnh mã máy [Machine Code Instructions] - video
Độ phức tạp của thuật toán / Big-O / Phân tích tiệm cận
Link được giữ nguyên theo bản tiếng Anh
Harvard CS50 - Asymptotic Notation [video]
Big O Notations [general quick tutorial] [video]
Big O Notation [and Omega and Theta] - best mathematical explanation [video]
Skiena:
- video
- slides
A Gentle Introduction to Algorithm Complexity Analysis
Orders of Growth [video]
Asymptotics [video]
UC Berkeley Big O [video]
UC Berkeley Big Omega [video]
Amortized Analysis [video]
Illustrating "Big O" [video]
TopCoder [includes recurrence relations and master theorem]:
- Computational Complexity: Section 1
- Computational Complexity: Section 2
Cheat sheet
Nếu một vài bài học quá chuyên sâu về toán, bạn có thể nhảy cóc tới các bài toán riêng lẻ để có kiến thức toàn diện hơn.
Cấu trúc dữ liệu
Arrays
- Cấp phát mảng vector tự động tùy biến kích cỡ.
- Miêu tả, tên
gốc được giữ nguyên kèm với bản dịch sang tiếng Việt:
- Arrays - Mảng [video]
- UCBerkley CS61B - Linear and Multi-Dim Arrays - Mảng tuyến tính và mảng đa chiều[video]
- Dynamic Arrays - Mảng tùy biến [video]
- Jagged Arrays - Mảng trong mảng [video]
- Cấp phát vector [Mảng có thể thay đổi với khả năng tự điều chỉnh kích cỡ]:
- Tập sử dụng mảng và con trỏ, dùng phép toán con trỏ để nhảy tới một chỉ mục [index] thay vì sử dụng chỉ mục.
- Tạo
mảng mới với vùng nhớ được cấp phát sẵn
- Có thể triển khai mảng số nguyên một cách nhanh chóng, nhưng không sử dụng các tính năng sẵn có
- Bắt đầu với 16, hoặc số lớn hơn, với cấp số nhân của 2 - 16, 32, 64, 128
- size[] - Số lượng của các thành phần trong mảng
- capacity[] - Số lượng tối đa các phần tử mà mảng có thể lưu trữ
- is_empty[] - Kiểm tra mảng rỗng
- at[index] - Trả về phần tử ở vị trí chỉ mục [index], hoặc lỗi nếu rơi ra ngoài chỉ mục
- push[item] Thêm vào một phần tử mới
- insert[index, item] - Thêm một phần tử mới tại vị trí của chỉ mục, điều chỉnh lại chỉ mục và đưa các phần tử còn lại dịch chuyển theo
- prepend[item] - Thêm tại vị trí chỉ mục 0, hay đầu tiên
- pop[] - trả về phần tử cuối cùng
- delete[index] - Xóa phần tử tại chỉ mục, dịch chuyển lại các phần tử trong mảng
- remove[item] - Tìm theo giá trị của phần tử và xóa chỉ mục đang lưu trữ cho phần tử này [áp dụng với việc nhiều phần tử có cùng giá trị]
- find[item] - Tìm theo giá trị của phần tử và trả về chỉ mục đầu tiên tìm được, -1 nếu không tìm thấy
- resize[new_capacity] // private function
- Khi tới giới hạn của mảng, tăng gấp đôi giá trị độ dài mảng để thay đổi kích thước
- Khi xóa 1 thành phần, nếu kích thước hiện tại chỉ bằng 1/4 kích thước được cấp phát, thay đổi thành 1/2
- Thời gian thực thi
- O[1] để thêm/xóa tại vị trí cuối [tính luôn cả cấp phát lại để có thêm không gian lưu trữ], đánh chỉ mục, hay cập nhật
- O[n] để thêm/xóa tại bất cứ đâu
- Không gian
- Liên tục trong bộ nhớ, giúp cải thiện hiệu suất
- Không gian cần thiết = [Kích cỡ của mảng, thường >= n]* kích thước của 1 phần tử, cho dù là 2n, vẫn xem như O[n]
Linked Lists
- Miêu tả:
- Singly Linked Lists - Danh sách liên kết [video]
- CS 61B - Linked Lists - Danh sách liên kết [video]
- C Code [video] - Không cần xem toàn bộ video, chỉ phần cấu trúc Node và cấp phát vùng nhớ.
- Danh sách liên kết so sánh với Mảng:
- Core Linked Lists Vs Arrays - Danh sách liên kết Vs Mảng [video]
- In The Real World Linked Lists Vs Arrays - Trong thực tế, Danh sách liên kết Vs Mảng [video]
- Why you should avoid linked lists - Tại sao bạn nên tránh danh sách liên kết[video]
- Ghi chú: Bạn cần kiến thức về
con trỏ trỏ về con trỏ: [Khi bạn chuyển một con trỏ vào trong 1 thân hàm khiến thay đổi địa chỉ mà con trỏ trỏ về] Trang này giúp bạn có cái nhìn khái quát về con trỏ trỏ tới con trỏ. Tôi không khuyến khích đọc lướt qua danh sách này. Đề tài này rất khó đọc và nắm bắt.
- Pointers to Pointers - Con trỏ trỏ tới con trỏ - [ ] Cài đặt [Tôi đã thực hiện với con trỏ đuôi và không dùng con trỏ đuôi]:
- size[] - Trả về số lượng các phần tử trong danh sách
- empty[] - Giá trị luận lý logic, true nếu rỗng
- value_at[index] - Trả về phần tử tại vị trí thứ n [danh sách bắt đầu từ 0]
- push_front[value] - Thêm phần tử mới vào đầu danh sách
- pop_front[] - Xóa phần tử đầu tiên và trả về giá trị này
- push_back[value] - Thêm phần tử tại cuối danh sách
- pop_back[] - Xóa phần tử cuối và trả về giá trị
- front[] - Lấy giá trị của phần tử đầu tiền
- back[] - Lấy giá trị của phần tử cuối cùng
- insert[index, value] - Thêm phần tử mới tại vị trí chỉ mục, phần tử hiện tại sẽ trỏ về phần tử mới tại vị trí chỉ mục này [A->B->C, thêm N tại vị trí B, A->D->B->C, A hiện giờ sẽ trỏ tới D, chỉ mục 1 sẽ trỏ tới D thay vì B]
- erase[index] - Xóa node tại vị trí chỉ mục
- value_n_from_end[n] - Trả về danh sách từ vị trí thứ n đến cuối danh sách
- reverse[] - đảo ngược danh sách
- remove_value[value] - Xóa dữ liệu đầu tiên được tìm thấy khớp với giá trị được cho
-
Doubly-linked List
- Description - Miêu tả danh sách liên kết đôi [video]
- Không cần phải cài đặt
- Miêu tả:
Stack
- Stacks [video] - [ ] Sẽ không cài đặt. Cài đặt với mảng là điều hiển nhiên.
Queue
- Queue [video]
- Circular buffer/FIFO
- Cài đặt sử dụng danh sách liên kết, áp dụng con trỏ đuôi:
- enqueue[value] - Thêm giá trị ở đuôi
- dequeue[] - Trả về giá trị của dữ liệu được thêm vào xa nhất [thông thường là dữ liệu đầu tiên trong danh sách]
- empty[]
- Sử dụng mảng cố định kích thước:
- enqueue[value] - Thêm giá trị vào cuối mảng
- dequeue[] - Trả về giá trị của dữ liệu được thêm vào xa nhất
- empty[]
- full[]
- Chi phí:
- Không cài đặt đúng việc sử dụng danh sách liên kết khi enqueue tại đầu và dequeue tại đuôi sẽ có chi phí là O[n] bởi vì bạn cần con trỏ next tới giá trị cuối cùng, khiến việc phải chạy qua toàn danh sách mỗi lần dequeue
- enqueue: O[1] [Không đáng kể, danh sách liên kết và mảng [probing]]
- dequeue: O[1] [danh sách liên kết và mảng]
- empty: O[1] [danh sách liên kết và mảng]
Hash table
- Video:
- Hashing with Chaining [video]
- Table Doubling, Karp-Rabin [video]
- Open Addressing, Cryptographic Hashing [video]
- PyCon 2010: The Mighty Dictionary [video]
- [Advanced] Randomization: Universal & Perfect Hashing [video]
- [Advanced] Perfect hashing [video]
- Các khóa học online:
- Core Hash Tables - Cơ bản về bảng băm [video]
- Data Structures - Cấu trúc dữ liệu [video]
- Phone Book Problem - Vấn đề sổ điện thoại [video]
- Phân phối bảng băm:
- Instant Uploads And Storage Optimization In Dropbox - Tải nhanh và tối ưu lưu trữ trong Dropbox [video]
- Distributed Hash Tables - Phân phối bảng băm[video]
- Cài đặt với mảng sử dụng thăm dò tuyến tính:
- hash[k, m] - m là kích thước của bảng băm
- add[key, value] - nếu khóa đã tồn tại, cập nhật giá trị
- exists[key]
- get[key]
- remove[key]
- Video:
Kiến thức ngoài
Tìm kiếm nhị phân
- Tìm kiếm nhị phân [Binary Search] - video
- Tìm kiếm nhị phân - Khan Academy [Binary Search] - video
- giải thích chi tiết
- Cài đặt:
- Tìm kiếm nhị phân [trên mảng số nguyên đã sắp xếp]
- Tìm kiếm nhị phân sử dụng đệ quy
Toán tử trên bit
- Bits cheat sheet - bạn nên thuộc lòng nhiều lũy thừa của 2 [từ 2^1 đến 2^16 và 2^32]
- Hãy chuẩn bị một nền tảng tốt về các biến đổi bit với các toán tử: &, |, ^, ~, >>,