Skip to content

Latest commit

 

History

History
1918 lines (1578 loc) · 166 KB

README-vi.md

File metadata and controls

1918 lines (1578 loc) · 166 KB
Raw

Tự ôn tập phỏng vấn về lập trình (Coding Interview University)

Bản gốc:

Tác giả gốc: John Washam

Đóng góp cho bản dịch tiếng Việt:

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.

Viết code trên bảng - ảnh trích từ bộ phim Silicon Valley của HBO

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

---------------- Những mục dưới đây là tuỳ chọn ----------------

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ếp theo, bạn cần biết cách gắp (fork) một repo trên github:

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 https://github.com/<your-username>/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: 
    git checkout -b progress
  • Check các phần đã hoàn thành bằng cách thêm x và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" . Thay commit message vớ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

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

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:

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):

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.

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

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

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).
      • 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ó.
    • 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:
    • 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í:

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: https://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 struct và các hàm nhận các struct đó 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::list cho 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:

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

Độ 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

    • 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:
    • 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

  • 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

Kiến thức ngoài

Cây

Sắp xếp

Nếu bạn muốn biết thêm chi tiết trong chủ đề này, xem qua phần "Sắp xếp" trong Đọc thêm về một số đề tài

Đồ thị

Đồ thị có thể được sử dụng để miêu tả nhiều bài toán trong khoa học máy tính, vậy nên phần này cũng khá dài, tương đương với Cây và Sắp xếp.

Bạn sẽ biết thêm nhiều ứng dụng của đồ thị trong sách của Skiena (xem danh mục sách bên dưới) và các sách về phỏng vấn.

Kiến thức bổ sung

Thiết kế hệ thống, Khả năng mở rộng, Xử lý dữ liệu

Tổng kết

Phần này sẽ là các video ngắn đề bạn ôn tập lại hầu hết các khái niệm quan trọng.
Cũng tốt nếu như bạn muốn bồi dưỡng thường xuyên.
  • Các video ngắn 2-3 phút (23 video)
  • Các video ngắn 2-5 phút - Michael Sambol (38 video)

Thực hành các câu hỏi về lập trình

Bây giờ bạn đã biết tất cả các chủ đề về khoa học máy tính, đây là lúc để thực hành các câu hỏi về lập trình.

Thực hành trả lời các câu hỏi về lập trình không phải là ghi nhớ cách trả lời các vấn đề trong lập trình

Tại sao bạn cần thực hành trả lời các vấn đề lập trình:

  • Nhận diện vấn đề, lựa chọn cấu trúc dữ liệu và thuật toán phù hợp
  • Xác định các yêu cầu của vấn đề
  • Trình bày cách suy nghĩ của bạn như thể bạn đang trong buổi phỏng vấn
  • Lập trình trên bảng trắng hoặc trên giấy, không phải với máy tính
  • Đưa ra được tính toán độ phức tạp về thời gian và không gian thực thi của giải pháp của bạn
  • Kiểm tra giải pháp của bạn

Dưới đây là một bài viết tuyệt vời về phương thức luận, cách kết nối giải quyết vấn đề trong một bài phỏng vấn. Bạn có thể gặp các bài viết tương tự trong các sách hướng dẫn phỏng vấn nhưng tôi cho là bài này thật sự cực kì xuất sắc: Thiết kế thuật toán (Algorithm design canvas)

Các bước tôi xử lý cho các câu hỏi về lập trình trong phỏng vấn (My Process for Coding Interview (Book) Exercises)

Không có bảng trắng ở nhà? Cũng hợp lý chứ. Tôi có chút khác biệt và tôi có một cái bảng trắng rất to. Thay vì bảng trắng, bạn có thể chọn một tập sổ ký họa từ các cửa hàng nghệ thuật. Bạn có thể ngồi ở ghế salon và thực hành. Tôi gọi nó là "bảng trắng mềm mại". Tôi có bỏ vào cây bút để dễ ước lượng. Nếu bạn dùng bút mực, bạn sẽ mong chọn loại nào có thể tẩy được ấy, vì sớm muộn sẽ rối cả lên.

Bảng trắng mềm mại của tôi(my sofa whiteboard)

Phụ lục:

Đọc và làm các bài tập về lập trình (theo thứ tự sau):

Đọc qua Danh sách sách phía trên

Giải bài tập lập trình

Bạn nên để cho bộ não vận dụng các kiến thức đã học. Hãy thử sức với các bài toán lập trình hàng ngày, càng nhiều càng tốt.

Các trang giải toán lập trình:

Xem thêm:

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

Nghĩ sẵn 20 câu hỏi kỹ thuật bạn có thể gặp phải, cùng với danh sách bên dưới. Chuẩn bị 2 đến 3 câu trả lời cho mỗi câu hỏi. Hãy chuẩn bị cả câu chuyện (từ chính kinh nghiệm của bạn), chứ không chỉ một câu trả lời suông.

  • Tại sao bạn lại muốn ứng tuyển vị trí này?
  • Vấn đề khó chịu nhất bạn từng giải quyết là gì?
  • Thử thách lớn nhất bạn từng đối mặt?
  • Thiết kế (hệ thống) tốt nhất/tồi nhất bạn từng gặp?
  • Những ý tưởng để cải thiện các sản phẩm hiện giờ của Google.
  • Bạn sẽ làm việc như thế nào để đạt hiệu quả tốt nhất, trong trường hợp làm việc một mình và làm theo team?
  • Kỹ năng hay kinh nghiệm nào của bạn thích hợp cho công việc này, và tại sao?
  • Bạn thích điều gì nhất ở [công việc X/ dự án Y]?
  • Lỗi gấy ức chế nhất bạn từng gặp phải ở [công việc X/ dự án Y]?
  • Bạn học được những gì ở [công việc X/ dự án Y]?
  • Những gì bạn cho rằng mình đã có thể làm tốt hơn ở [công việc X/ dự án Y]?

Chuẩn bị câu hỏi dành cho phỏng vấn viên

Một vài câu hỏi của tôi (Tôi có thể đã tìm hiểu trước rồi, nhưng vẫn muốn được nghe ý kiến từ góc nhìn của người phỏng vấn):
  • Quy mô của team thế nào?
  • Quy trình phát triển của bạn? Waterfall/sprints/agile?
  • Áp lực deadline có phổ biến không? Liệu có sự linh hoạt nào không?
  • Các quyết định của team được xây dựng như thế nào?
  • Khoảng bao nhiêu cuộc họp hàng tuần?
  • Bạn có cho rằng môi trường làm việc giúp bạn tập trung hơn không?
  • Hiện tại bạn đang xây dựng những gì?
  • Bạn thích gì ở công việc này?
  • Sự cân bằng giữa công việc và cuộc sống của bạn có ổn không?

Khi bạn được nhận việc

Chúc mừng!

Hãy tiếp tục rèn luyện.

Bạn không bao giờ thực sự học xong!

*****************************************************************************************************
*****************************************************************************************************

Học các chủ đề này sẽ giúp bạn hiểu sâu hơn về Khoa học máy tính, và sẵn sàng hơn cho bất kỳ công ty nào.

*****************************************************************************************************
*****************************************************************************************************

Sách bổ sung

Học thêm

Tiêu đề của các video, các thuật ngữ cao cấp xin được giữ nguyên. Một số thuật ngữ có thể dịch được, nhưng người dịch không đủ vốn từ đề diễn đạt chúng một cách ngắn gọn như trong tiếng Anh, nên cũng xin phép cho qua.

--

Đọc thêm về một số đề tài

   Tôi thêm những phần này để củng cố các kiến thức đã được trình bày ở trên, nhưng không muốn đưa chúng vào danh sách trên, vì đã quá nhiều rồi. Cũng có hơi vượt mức cần thiết. Nhưng dù sao, bạn muốn trúng tuyển mà phải không?

Các chuỗi Video

Hãy ngồi xuống và thưởng thức. "Luyện kỹ năng với Netflix" :P

Các khóa học khoa học máy tính