ldhnam
Công nghệ, kinh tế, và những suy nghĩ rời rạc.Technology, economics, and scattered thoughts.
← Ghi chú← Notes

Cấu trúc dữ liệu & Giải thuậtData Structures & Algorithms

24 ghi chú24 notes

⌕
  1. 01Nền tảng lập trình & PseudocodeProgramming Fundamentals & PseudocodeData structures và algorithms không phải là một ngôn ngữ lập trình. Chúng là cách tư duy về việc dữ liệu được bố trí trong memory ra sao và một chuỗi các bước biến đổi dữ liệu đó như thế nào — và cách tư duy này mang đi…Data structures and algorithms are not a programming language. They are a way of thinking about how data is laid out in memory and how a sequence of steps transforms it — and that thinking is portable. A binary search…7 Th8, 2026Aug 7, 2026
  2. 02Cấu trúc dữ liệu là gì?What Are Data Structures?Data structure là cách tổ chức và lưu trữ dữ liệu trong máy tính sao cho có thể sử dụng nó một cách hiệu quả. Định nghĩa đó chính xác nhưng khô khan. Có một cách nói hữu ích hơn: data structure là một thỏa thuận bạn ký…A data structure is a way of organizing and storing data in a computer so that it can be used efficiently. That definition is accurate but bloodless. A more useful way to say it: a data structure is a deal you make with…7 Th8, 2026Aug 7, 2026
  3. 03Độ phức tạp thuật toánAlgorithmic ComplexityAlgorithmic complexity là môn học về việc một thuật toán tốn bao nhiêu khi input của nó lớn dần — tốn bao nhiêu thời gian và bao nhiêu memory, biểu diễn dưới dạng hàm của kích thước input n. Đây là kỹ năng mang đi được…Algorithmic complexity is the study of what an algorithm costs as its input grows — how much time it takes and how much memory it consumes, expressed as a function of the input size n. It is the single most transferable…7 Th8, 2026Aug 7, 2026
  4. 04Mảng (Array)ArraysArray là cấu trúc dữ liệu đơn giản nhất, và cũng là quan trọng nhất. Nó là một khối bộ nhớ liên tục (contiguous) chứa một số phần tử cố định có kích thước bằng nhau. Chỉ riêng đặc tính đó — liên tục, kích thước bằng…An array is the simplest data structure there is, and also the most important one. It is a block of contiguous memory holding a fixed number of equally sized elements. That single property — contiguous, equally sized —…7 Th8, 2026Aug 7, 2026
  5. 05Danh sách liên kếtLinked ListsLinked list lưu một dãy dưới dạng chuỗi các node, mỗi node chứa một giá trị và một tham chiếu tới node kế tiếp. Khác với array, các node không cần nằm cạnh nhau trong bộ nhớ — chúng có thể nằm rải rác bất kỳ đâu trên…A linked list stores a sequence as a chain of nodes, each holding a value and a reference to the next node. Unlike an array, the nodes do not have to be adjacent in memory — they can be scattered anywhere on the heap…7 Th8, 2026Aug 7, 2026
  6. 06Stack & QueueStacks & QueuesStack và queue là hai cấu trúc được định nghĩa không phải bởi cách chúng lưu dữ liệu mà bởi những gì chúng từ chối cho bạn làm. Cả hai đều chứa một dãy; cả hai đều cho bạn đúng một chỗ để thêm và một chỗ để lấy ra…Stacks and queues are the two structures defined not by how they store data but by what they refuse to let you do. Both hold a sequence; both give you exactly one place to add and one place to remove; neither lets you…7 Th8, 2026Aug 7, 2026
  7. 07Hash TableHash TablesHash table là câu trả lời cho một câu hỏi rất cụ thể: array cho phép truy cập O(1) bằng index kiểu số nguyên — vậy làm sao để truy cập O(1) bằng một key bất kỳ? Câu trả lời là tính ra index từ chính key đó. Một hash…A hash table is the answer to a very specific question: an array gives me O(1) access by integer index — how do I get O(1) access by arbitrary key? The answer is to compute the index from the key. A hash function turns…7 Th8, 2026Aug 7, 2026
  8. 08Thuật toán sắp xếpSorting AlgorithmsSắp xếp là việc sắp lại một tập dữ liệu theo một thứ tự xác định dựa trên một toán tử so sánh. Định nghĩa đó nghe rất hẹp, và chủ đề này trông như một bảo tàng những món đồ cổ — chẳng ai đem bubble sort lên production…Sorting is rearranging a collection into a defined order according to a comparison operator. That definition sounds narrow, and the subject looks like a museum of historical curiosities — nobody ships bubble sort. Yet…7 Th8, 2026Aug 7, 2026
  9. 09Thuật toán tìm kiếmSearch AlgorithmsTìm kiếm là việc xác định một phần tử cụ thể, hoặc một nhóm phần tử, trong một tập dữ liệu. Roadmap nêu bốn thuật toán tìm kiếm chính: linear search, binary search, depth-first search, và breadth-first search. Hai cái…Searching is finding a specific item, or group of items, among a collection of data. The roadmap names four main search algorithms: linear search, binary search, depth-first search, and breadth-first search. The first…7 Th8, 2026Aug 7, 2026
  10. 10Cấu trúc dữ liệu câyTree Data StructuresMọi cấu trúc đã đi qua từ đầu tới giờ — array, linked list, stack, queue, hash table — đều là tuyến tính: các phần tử nằm thành một dãy, và "phần tử kế tiếp" chỉ có đúng một nghĩa. Tree là cấu trúc phi tuyến tính đầu…Every structure covered so far — arrays, linked lists, stacks, queues, hash tables — is linear: elements sit in a sequence, and "next" means exactly one thing. A tree is the first genuinely non-linear structure. Each…7 Th8, 2026Aug 7, 2026
  11. 11Cây cân bằng & cây nhiều nhánhBalanced & Multiway TreesNote trước kết thúc bằng một vấn đề. Binary search tree cho search, insert và delete O(log n) — nhưng chỉ khi height của nó còn gần log n, và không có gì trong thuật toán BST thuần bắt buộc điều đó. Nạp vào 1, 2, 3, 4…The previous note ended on a problem. A binary search tree gives O(log n) search, insert, and delete — but only while its height stays near log n, and nothing in the plain BST algorithm enforces that. Feed it 1, 2, 3…7 Th8, 2026Aug 7, 2026
  12. 12Heap & Priority QueueHeaps & Priority QueuesMảng đã sắp xếp trả lời "phần tử nhỏ nhất là gì?" trong O(1) nhưng tốn O(n) để insert. Một list thường insert trong O(1) nhưng tốn O(n) để tìm minimum. Balanced BST làm cả hai trong O(log n), nhưng bạn đang trả tiền cho…A sorted array answers "what is the smallest element?" in O(1) but costs O(n) to insert into. A plain list answers insertion in O(1) but costs O(n) to find the minimum. A balanced BST does both in O(log n), but you are…7 Th8, 2026Aug 7, 2026
  13. 13Cấu trúc dữ liệu đồ thịGraph Data StructuresGraph là một tập các vertex (node) cùng với một tập các edge, mỗi edge nối một cặp vertex. Định nghĩa này đơn giản đến mức gần như tầm thường, và đó chính là lý do graph quan trọng: hầu như mọi mối quan hệ bạn có thể kể…A graph is a set of vertices (nodes) together with a set of edges, where each edge connects a pair of vertices. That definition is almost insultingly simple, and that is exactly why graphs matter: almost every…7 Th8, 2026Aug 7, 2026
  14. 14Thuật toán đường đi ngắn nhấtShortest Path Algorithms"Đi từ A tới B rẻ nhất bằng cách nào?" là câu hỏi mà các thuật toán graph được thuê để trả lời nhiều nhất. Chỉ đường, định tuyến mạng (OSPF theo đúng nghĩa đen là Dijkstra chạy trên mọi router), phát hiện arbitrage tiền…"What is the cheapest way to get from A to B?" is the question that graph algorithms are most often hired to answer. Route planning, network routing protocols (OSPF is literally Dijkstra running on every router)…7 Th8, 2026Aug 7, 2026
  15. 15Cây khung nhỏ nhấtMinimum Spanning TreesBạn có một tập địa điểm và một tập kết nối khả dĩ giữa chúng, mỗi kết nối có một chi phí. Bạn muốn mọi địa điểm đều tới được nhau, và muốn trả càng ít tiền càng tốt. Đó là bài toán minimum spanning tree (MST), và nó là…You have a set of locations and a set of possible connections between them, each with a cost. You want every location reachable from every other, and you want to pay as little as possible. That is the minimum spanning…7 Th8, 2026Aug 7, 2026
  16. 16Disjoint Set (Union-Find)Disjoint Set (Union-Find)Đó là một interface rất nhỏ, và chính sự hạn hẹp đó là điểm mấu chốt. Union-find là câu trả lời cho câu hỏi "hai thứ này có kết nối với nhau không?" khi các kết nối liên tục xuất hiện và không bao giờ biến mất. Hầu hết…A disjoint-set structure — also called union-find or a merge-find set — tracks a partition of a set: a collection of elements split into non-overlapping groups, where every element belongs to exactly one group. It…7 Th8, 2026Aug 7, 2026
  17. 17Cấu trúc cây nâng caoAdvanced Tree StructuresCác loại tree đã học từ trước đến giờ đều xoay quanh thứ tự: binary search tree giữ key được sắp xếp để bạn tìm được một key trong O(log n), và balanced tree (AVL, red-black, B-tree — xem…The trees covered so far are all about ordering: a binary search tree keeps keys sorted so you can find one in O(log n), and a balanced tree (AVL, red-black, B-tree — see ./11-balanced-and-multiway-trees.md) keeps that…7 Th8, 2026Aug 7, 2026
  18. 18IndexingIndexingMọi cấu trúc trong roadmap này từ trước tới giờ đều được nghiên cứu trong memory: array là một khối liên tục, B-tree là một tập các node, hash table là một mảng bucket. Indexing là chuyện xảy ra khi bạn lấy đúng những…Every structure in this roadmap so far has been studied in memory: an array is a contiguous block, a B-tree is a set of nodes, a hash table is a bucket array. Indexing is what happens when you take those same structures…7 Th8, 2026Aug 7, 2026
  19. 19Đệ quy & Chia để trịRecursion & Divide and ConquerĐệ quy (recursion) là cách giải một bài toán bằng cách diễn đạt nó qua một phiên bản nhỏ hơn của chính bài toán đó. Một hàm đệ quy gọi lại chính nó trên input đã được thu nhỏ, và cứ tiếp tục như vậy cho tới khi input đủ…Recursion is a way of solving a problem by expressing it in terms of a smaller instance of the same problem. A recursive function calls itself on a reduced input, and keeps doing so until the input is small enough to…7 Th8, 2026Aug 7, 2026
  20. 20Brute Force, Greedy & Thuật toán ngẫu nhiênBrute Force, Greedy & Randomised AlgorithmsMọi thứ từ đầu roadmap tới đây đều xoay quanh cấu trúc — cách bố trí dữ liệu sao cho một thao tác cụ thể chạy nhanh. Chủ đề này là chủ đề đầu tiên về kỹ thuật: các chiến lược tổng quát để tấn công một bài toán bạn chưa…Everything up to this point in the roadmap has been about structures — how to lay data out so that a particular operation is fast. This topic is the first of the techniques: general strategies for attacking a problem…7 Th8, 2026Aug 7, 2026
  21. 21Backtracking (Quay lui)BacktrackingBacktracking là kỹ thuật dành cho những bài toán mà lời giải là một chuỗi các quyết định phải cùng lúc thỏa mãn một số ràng buộc. Bạn dựng lời giải từng quyết định một; khi nào lời giải dở dang không còn khả năng hoàn…Backtracking is the technique for problems where a solution is a sequence of decisions that must jointly satisfy some constraints. You build the solution one decision at a time; whenever the partial solution can no…7 Th8, 2026Aug 7, 2026
  22. 22Quy hoạch độngDynamic ProgrammingDynamic programming (DP — quy hoạch động) là thứ bạn thu được khi lấy một lời giải đệ quy đang tính đi tính lại cùng một subproblem và bắt nó dừng việc đó lại. Toàn bộ ý tưởng chỉ có vậy. Mọi thứ còn lại — bảng, thiết…Dynamic programming (DP) is what you get when you take a recursive solution that recomputes the same subproblems over and over, and make it stop doing that. That is the whole idea. Everything else — tables, state…7 Th8, 2026Aug 7, 2026
  23. 23Hai con trỏ & Cửa sổ trượtTwo Pointers & Sliding WindowCác pattern trong bài này đều chung một lập luận kinh tế: thay một vòng lặp lồng nhau bằng một cặp chỉ số mà mỗi cái chỉ tiến về phía trước. Vòng lặp lồng nhau trên mảng tốn O(n²) vì chỉ số bên trong phải chạy lại từ…The patterns in this note all share one economic argument: replace a nested loop with a pair of indices that each move only forward. A nested loop over an array does O(n²) work because the inner index restarts from…7 Th8, 2026Aug 7, 2026
  24. 24Nền tảng luyện tập & Chuẩn bị phỏng vấnPlatforms to Practice & Interview PreparationToàn bộ hai mươi ba topic trước là kiến thức bạn có thể thu nạp bằng cách đọc. Topic này thì không. Data structures và algorithms là một kỹ năng, mà kỹ năng thì chỉ có được bằng cách làm dở, nhận phản hồi, rồi làm lại —…Everything in the previous twenty-three topics is knowledge you can acquire by reading. This one is not. Data structures and algorithms are a skill, and skills are acquired by doing the thing badly, getting feedback…7 Th8, 2026Aug 7, 2026