Danh sách này vừa là hướng dẫn nhanh vừa là tài liệu tham khảo để nghiên cứu sâu hơn về các chủ đề này. Về cơ bản, nó là một bản tóm tắt về khóa học khoa học máy tính mà bạn chưa bao giờ học hoặc đã quên, vì vậy không có cách nào nó có thể bao quát mọi thứ một cách sâu sắc
Đóng góp
Vui lòng xem Repo Tech Interview Cheat Sheet
Khái niệm cơ bản về cấu trúc dữ liệu
Mảng
Sự định nghĩa
- Lưu trữ các phần tử dữ liệu dựa trên chỉ mục tuần tự, phổ biến nhất dựa trên 0
- Dựa trên các bộ dữ liệu từ lý thuyết tập hợp
- Chúng là một trong những cấu trúc dữ liệu lâu đời nhất, được sử dụng phổ biến nhất
Những gì bạn cần biết
- Tối ưu cho việc lập chỉ mục;
- Mảng tuyến tính, hoặc mảng một chiều, là cơ bản nhất
- Có kích thước tĩnh, nghĩa là chúng được khai báo với kích thước cố định
- Mảng động giống như mảng một chiều, nhưng có không gian dành riêng cho các phần tử bổ sung
- Nếu một mảng động đầy, nó sẽ sao chép nội dung của nó sang một mảng lớn hơn
- Mảng đa chiều Các mảng lồng nhau cho phép nhiều chiều, chẳng hạn như một mảng các mảng cung cấp biểu diễn không gian 2 chiều thông qua tọa độ x, y
Thời gian phức tạp
- lập chỉ mục. Mảng tuyến tính. O[1], Mảng động. Ô[1]
- Tìm kiếm. Mảng tuyến tính. O[n], Mảng động. Trên]
- Tìm kiếm được tối ưu hóa. Mảng tuyến tính. O[log n], Mảng động. O[logn]
- Chèn. Mảng tuyến tính. n/a Mảng động. Trên]
Danh sách liên kết
Sự định nghĩa
- Lưu trữ dữ liệu với các nút trỏ đến các nút khác
- Các nút, ở mức cơ bản nhất, nó có một mốc thời gian và một tham chiếu [một nút khác]
- Một danh sách được liên kết xâu chuỗi các nút lại với nhau bằng cách trỏ tham chiếu của một nút tới một nút khác
Những gì bạn cần biết
- Được thiết kế để tối ưu hóa việc chèn và xóa, chậm lập chỉ mục và tìm kiếm
- Danh sách liên kết kép có các nút cũng tham chiếu đến nút trước đó
- Danh sách liên kết vòng là danh sách liên kết đơn có đuôi, nút cuối cùng, tham chiếu đến đầu, nút đầu tiên
- Ngăn xếp, thường được triển khai với danh sách liên kết nhưng cũng có thể được tạo từ mảng
- Ngăn xếp là cấu trúc dữ liệu vào sau, ra trước [LIFO]
- Được tạo bằng danh sách liên kết bằng cách lấy phần đầu là nơi duy nhất để chèn và xóa
- Hàng đợi cũng có thể được thực hiện với một danh sách được liên kết hoặc một mảng
- Hàng đợi là cấu trúc dữ liệu nhập trước, xuất trước [FIFO]
- Được tạo bằng một danh sách liên kết kép chỉ loại bỏ phần đầu và thêm vào phần đuôi
Thời gian phức tạp
- lập chỉ mục. Danh sách liên kết. Trên]
- Tìm kiếm. Danh sách liên kết. Trên]
- Tìm kiếm được tối ưu hóa. Danh sách liên kết. Trên]
- Chèn. Danh sách liên kết. Ô[1]
Bảng băm hoặc Bản đồ băm
Sự định nghĩa
- Lưu trữ dữ liệu với các cặp giá trị chính
- Các hàm băm chấp nhận một khóa và chỉ trả về một đầu ra duy nhất cho khóa cụ thể đó
- Điều này được gọi là băm, là khái niệm mà đầu vào và đầu ra có sự tương ứng một-một với thông tin bản đồ
- Các hàm băm trả về một địa chỉ duy nhất trong bộ nhớ cho dữ liệu đó
Những gì bạn cần biết
- Được thiết kế để tối ưu hóa tìm kiếm, chèn và xóa
- Xung đột băm là khi một hàm băm trả về cùng một đầu ra cho hai đầu vào riêng biệt
- Tất cả các hàm băm đều có vấn đề này
- Điều này thường được hỗ trợ bằng cách có các bảng băm rất lớn
- Băm rất quan trọng đối với mảng kết hợp và lập chỉ mục cơ sở dữ liệu
Thời gian phức tạp
- lập chỉ mục. Bảng băm. Ô[1]
- Tìm kiếm. Bảng băm. Ô[1]
- Chèn. Bảng băm. Ô[1]
Cây nhị phân
Sự định nghĩa
- Là một cấu trúc dữ liệu dạng cây trong đó mỗi nút có tối đa hai nút con
- Có một nút con trái và phải
Những gì bạn cần biết
- Được thiết kế để tối ưu hóa tìm kiếm và sắp xếp
- Cây suy biến là cây không cân bằng, nếu hoàn toàn một phía thì về cơ bản là một danh sách liên kết
- Chúng tương đối đơn giản để thực hiện hơn các cấu trúc dữ liệu khác
- Được sử dụng để tạo cây tìm kiếm nhị phân
- Cây nhị phân sử dụng các khóa có thể so sánh để chỉ định hướng của một đứa trẻ
- Nút con bên trái có khóa nhỏ hơn nút cha của nó
- Con phải có khóa lớn hơn nút cha
- Không thể có nút trùng lặp
- Do những điều trên, nó có nhiều khả năng được sử dụng làm cấu trúc dữ liệu hơn là cây nhị phân
Thời gian phức tạp
- lập chỉ mục. Cây tìm kiếm nhị phân. O[logn]
- Tìm kiếm. Cây tìm kiếm nhị phân. O[log n]
- Chèn. Cây tìm kiếm nhị phân. O[logn]
Khái niệm cơ bản về tìm kiếm
Tìm kiếm đầu tiên theo chiều rộng
Sự định nghĩa
- Một thuật toán tìm kiếm một cây [hoặc đồ thị] bằng cách tìm kiếm các cấp của cây trước tiên, bắt đầu từ gốc
- Nó tìm thấy mọi nút trên cùng một cấp độ, thường di chuyển từ trái sang phải
- Trong khi thực hiện việc này, nó theo dõi các nút con của các nút ở cấp độ hiện tại
- Khi kiểm tra xong một cấp độ, nó sẽ di chuyển đến nút ngoài cùng bên trái ở cấp độ tiếp theo
- Hầu hết nút dưới cùng bên phải được đánh giá cuối cùng [nút sâu nhất và xa nhất bên phải cấp độ của nó]
Những gì bạn cần biết
- Tối ưu để tìm kiếm một cái cây rộng hơn là sâu
- Sử dụng hàng đợi để lưu trữ thông tin về cây khi nó đi ngang qua cây
- Bởi vì nó sử dụng hàng đợi nên nó tốn nhiều bộ nhớ hơn so với tìm kiếm theo chiều sâu
- Hàng đợi sử dụng nhiều bộ nhớ hơn vì nó cần lưu trữ con trỏ
Thời gian phức tạp
- Tìm kiếm. Tìm kiếm đầu tiên theo chiều rộng. O[V + E]
- E là số cạnh
- V là số đỉnh
Độ sâu tìm kiếm đầu tiên
Sự định nghĩa
- Thuật toán tìm kiếm cây [hoặc đồ thị] bằng cách tìm kiếm độ sâu của cây trước, bắt đầu từ gốc
- Nó băng qua trái xuống một cái cây cho đến khi nó không thể đi xa hơn
- Khi nó đi đến cuối nhánh, nó sẽ quay ngược trở lại để thử con bên phải của các nút trên nhánh đó và nếu có thể, trái từ con bên phải
- Khi kiểm tra xong một nhánh, nó di chuyển đến nút bên phải của gốc rồi cố gắng đi sang trái trên tất cả các nhánh con của nó cho đến khi chạm đến đáy
- Hầu hết các nút bên phải được đánh giá cuối cùng [nút bên phải của tất cả các tổ tiên của nó]
Những gì bạn cần biết
- Tối ưu để tìm kiếm một cây sâu hơn chiều rộng
- Sử dụng ngăn xếp để đẩy các nút lên
- Vì ngăn xếp là LIFO nên nó không cần theo dõi các con trỏ nút và do đó ít tốn bộ nhớ hơn so với tìm kiếm theo chiều rộng đầu tiên
- Khi nó không thể đi xa hơn về bên trái, nó bắt đầu đánh giá ngăn xếp
Thời gian phức tạp
- Tìm kiếm. Độ sâu tìm kiếm đầu tiên. Ô[. E. +. V. ]
- E là số cạnh
- V là số đỉnh
Chiều rộng tìm kiếm đầu tiên Vs. Độ sâu tìm kiếm đầu tiên
- Câu trả lời đơn giản cho câu hỏi này là nó phụ thuộc vào kích thước và hình dạng của cây
- Đối với cây rộng, nông, hãy sử dụng Tìm kiếm theo chiều rộng
- Đối với những cây sâu, hẹp, hãy sử dụng Tìm kiếm theo chiều sâu
Sắc thái
- Vì BFS sử dụng hàng đợi để lưu trữ thông tin về các nút và phần tử con của nó nên nó có thể sử dụng nhiều bộ nhớ hơn mức có sẵn trên máy tính của bạn. [Nhưng có lẽ bạn sẽ không phải lo lắng về điều này. ]
- Nếu sử dụng DFS trên cây rất sâu, bạn có thể tìm kiếm sâu một cách không cần thiết. Xem xkcd để biết thêm thông tin
- Tìm kiếm theo chiều rộng có xu hướng là một thuật toán lặp
- Tìm kiếm theo chiều sâu có xu hướng là một thuật toán đệ quy
Khái niệm cơ bản về sắp xếp hiệu quả
Hợp nhất Sắp xếp
Sự định nghĩa
- Thuật toán sắp xếp dựa trên so sánh
- Chia toàn bộ tập dữ liệu thành các nhóm tối đa hai
- So sánh từng số một tại một thời điểm, di chuyển số nhỏ nhất sang trái của cặp
- Sau khi tất cả các cặp được sắp xếp, nó sẽ so sánh hầu hết các phần tử bên trái của hai cặp ngoài cùng bên trái để tạo ra một nhóm bốn được sắp xếp với các số nhỏ nhất ở bên trái và các số lớn nhất ở bên phải
- Quá trình này được lặp lại cho đến khi chỉ còn một tập hợp
Những gì bạn cần biết
- Đây là một trong những thuật toán sắp xếp cơ bản nhất
- Biết rằng nó chia tất cả dữ liệu thành các tập hợp nhỏ nhất có thể rồi so sánh chúng
Thời gian phức tạp
- Sắp xếp trường hợp tốt nhất. Hợp nhất Sắp xếp. Trên]
- Sắp xếp trường hợp trung bình. Hợp nhất Sắp xếp. O[n log n]
- Sắp xếp trường hợp xấu nhất. Hợp nhất Sắp xếp. O[n log n]
Sắp xếp nhanh chóng
Sự định nghĩa
- Thuật toán sắp xếp dựa trên so sánh
- Chia đôi toàn bộ tập dữ liệu bằng cách chọn phần tử ở giữa và đặt tất cả các phần tử nhỏ hơn ở bên trái của phần tử và các phần tử lớn hơn ở bên phải
- Nó lặp lại quá trình này ở phía bên trái cho đến khi nó chỉ so sánh hai phần tử mà tại đó phía bên trái được sắp xếp
- Khi bên trái sắp xếp xong, nó thực hiện thao tác tương tự ở bên phải
- Kiến trúc máy tính ủng hộ quá trình sắp xếp nhanh
Những gì bạn cần biết
- Mặc dù nó có cùng Big O như [hoặc tệ hơn trong một số trường hợp] nhiều thuật toán sắp xếp khác, nhưng trong thực tế, nó thường nhanh hơn nhiều thuật toán sắp xếp khác, chẳng hạn như sắp xếp hợp nhất
- Biết rằng nó giảm một nửa tập dữ liệu bằng trung bình cộng liên tục cho đến khi sắp xếp hết thông tin
Thời gian phức tạp
- Sắp xếp trường hợp tốt nhất. Hợp nhất Sắp xếp. Trên]
- Sắp xếp trường hợp trung bình. Hợp nhất Sắp xếp. O[n log n]
- Sắp xếp trường hợp xấu nhất. Hợp nhất Sắp xếp. O[n^2]
Sắp xếp bong bóng
Sự định nghĩa
- Thuật toán sắp xếp dựa trên so sánh
- Nó lặp từ trái sang phải so sánh mọi câu ghép, di chuyển phần tử nhỏ hơn sang trái
- Nó lặp lại quá trình này cho đến khi nó không còn di chuyển phần tử sang trái nữa
Những gì bạn cần biết
- Mặc dù rất đơn giản để thực hiện, nhưng đây là phương pháp kém hiệu quả nhất trong ba phương pháp sắp xếp này
- Biết rằng nó di chuyển một khoảng trống sang bên phải so sánh hai phần tử cùng một lúc và di chuyển phần tử nhỏ hơn sang trái
Thời gian phức tạp
- Sắp xếp trường hợp tốt nhất. Hợp nhất Sắp xếp. Trên]
- Sắp xếp trường hợp trung bình. Hợp nhất Sắp xếp. O[n^2]
- Sắp xếp trường hợp xấu nhất. Hợp nhất Sắp xếp. O[n^2]
Hợp nhất Sắp xếp Vs. Sắp xếp nhanh chóng
- Quicksort có khả năng nhanh hơn trong thực tế
- Hợp nhất Sắp xếp chia tập hợp thành các nhóm nhỏ nhất có thể ngay lập tức sau đó tái cấu trúc tăng dần khi nó sắp xếp các nhóm
- Quicksort liên tục chia tập hợp cho giá trị trung bình, cho đến khi tập hợp được sắp xếp đệ quy
Các loại thuật toán cơ bản
thuật toán đệ quy
Sự định nghĩa
- Một thuật toán gọi chính nó trong định nghĩa của nó
- Trường hợp đệ quy một câu lệnh có điều kiện được sử dụng để kích hoạt đệ quy
- Trường hợp cơ sở một câu lệnh có điều kiện được sử dụng để ngắt đệ quy
Những gì bạn cần biết
- Mức ngăn xếp quá sâu và tràn ngăn xếp
- Nếu bạn đã nhìn thấy một trong hai điều này từ một thuật toán đệ quy, thì bạn đã nhầm lẫn
- Điều đó có nghĩa là trường hợp cơ sở của bạn không bao giờ được kích hoạt vì nó bị lỗi hoặc sự cố lớn đến mức bạn đã hết bộ nhớ được phân bổ
- Biết liệu bạn có đạt được trường hợp cơ bản hay không là điều không thể thiếu để sử dụng đệ quy một cách chính xác
- Thường được sử dụng trong Tìm kiếm theo chiều sâu
thuật toán lặp
Sự định nghĩa
- Một thuật toán được gọi lặp đi lặp lại nhưng trong một số lần hữu hạn, mỗi lần là một lần lặp
- Thường được sử dụng để di chuyển tăng dần qua một tập dữ liệu
Những gì bạn cần biết
- Nói chung, bạn sẽ thấy phép lặp dưới dạng các vòng lặp, câu lệnh for, while và until
- Hãy nghĩ về phép lặp như di chuyển từng cái một qua một tập hợp
- Thường được sử dụng để di chuyển qua một mảng
đệ quy Vs. lặp lại
- Sự khác biệt giữa đệ quy và phép lặp có thể gây nhầm lẫn khi phân biệt vì cả hai đều có thể được sử dụng để thực hiện cái kia. Nhưng biết rằng,
- Đệ quy thường biểu cảm hơn và dễ thực hiện hơn
- Lặp lại sử dụng ít bộ nhớ hơn
- Các ngôn ngữ chức năng có xu hướng sử dụng đệ quy. [tôi. e. Haskell]
- Các ngôn ngữ mệnh lệnh có xu hướng sử dụng phép lặp. [tôi. e. hồng ngọc]
- Hãy xem bài đăng Stack Overflow này để biết thêm thông tin
Mã giả di chuyển qua một mảng [đây là lý do tại sao phép lặp được sử dụng cho việc này]
Recursion | Iteration
----------------------------------|----------------------------------
recursive method [array, n] | iterative method [array]
if array[n] is not nil | for n from 0 to size of array
print array[n] | print[array[n]]
recursive method[array, n+1] |
else |
exit loop |
thuật toán tham lam
Sự định nghĩa
- Một thuật toán, trong khi thực hiện, chỉ chọn thông tin đáp ứng một tiêu chí nhất định
- Năm thành phần chung, lấy từ Wikipedia
- Một tập hợp ứng cử viên, từ đó một giải pháp được tạo ra
- Chức năng lựa chọn, chọn ứng cử viên tốt nhất để thêm vào giải pháp
- Một chức năng khả thi, được sử dụng để xác định xem một ứng cử viên có thể được sử dụng để đóng góp cho giải pháp hay không
- Một hàm mục tiêu, gán một giá trị cho một giải pháp hoặc một giải pháp một phần
- Một chức năng giải pháp, sẽ cho biết khi nào chúng tôi đã phát hiện ra một giải pháp hoàn chỉnh
Những gì bạn cần biết
- Được sử dụng để tìm giải pháp phù hợp, mặc dù không tối ưu, cho một vấn đề nhất định
- Thường được sử dụng trên các tập hợp dữ liệu mà chỉ một tỷ lệ nhỏ thông tin được đánh giá đáp ứng kết quả mong muốn
- Thường thì thuật toán tham lam có thể giúp giảm Big O của thuật toán
Mã giả của một thuật toán tham lam để tìm sự khác biệt lớn nhất của hai số bất kỳ trong một mảng
greedy algorithm [array]
var largest difference = 0
var new difference = find next difference [array[n], array[n+1]]
largest difference = new difference if new difference is > largest difference
repeat above two steps until all differences have been found
return largest difference
Thuật toán này không bao giờ cần so sánh tất cả sự khác biệt với nhau, tiết kiệm toàn bộ quá trình lặp lại