Computer Science
Lộ trình phát triển toàn diện Computer Science theo tiêu chuẩn quốc tế nilbuild/developer-roadmap
Hướng dẫn từng bước từ nền tảng đến chuyên sâu giúp bạn làm chủ Computer Science. Tích hợp tài liệu lý thuyết, bài viết thực chiến, video tham khảo và bài tập lập trình trực tiếp trên IDE.
Nền Tảng & Khái Niệm Cốt Lõi
Giai đoạn 1 tập trung hoàn thiện 38 chủ đề then chốt.
2-3-4 Search Trees
In practice: For every 2-4 tree, there are corresponding red–black trees with data elements in the same order. The insertion and deletion operations on 2-4 trees are also equivalent to color-flipping and rotations in red–black trees. This makes 2-4 trees an important tool for understanding the logic behind red–black trees, and this is why many introductory algorithm texts introduce 2-4 trees just before red–black trees, even though 2-4 trees are not often used in practice.
2-3 Search Trees
In practice: 2-3 trees have faster inserts at the expense of slower searches (since height is more compared to AVL trees). You would use 2-3 tree very rarely because its implementation involves different types of nodes. Instead, people use Red Black trees.
A* Algorithm
A\* is a graph traversal algorithm that is used to find the shortest path between two nodes in a graph. It is a modified version of Dijkstra's algorithm that uses heuristics to find the shortest path. It is used in pathfinding and graph traversal.
ACID
ACID are the four properties of any database system that help in making sure that we are able to perform the transactions in a reliable manner. It's an acronym which refers to the presence of four properties: atomicity, consistency, isolation and durability
Activity Diagrams
Activity diagrams are used to model the flow of control in a system. They are used in conjunction with use case diagrams to model the behavior of the system for each use case. They are also used to model the behavior of a single class.
Adjacency List
An adjacency list represents a graph by storing, for each vertex, a list of the vertices it connects to. This representation uses memory proportional to the number of edges, which makes it efficient for sparse graphs where most vertices are not directly connected to each other.
Adjacency Matrix
An adjacency matrix is a square matrix used to represent a finite graph. It is used to represent the connections between vertices in a graph. The matrix is filled with 0s and 1s, where a 1 represents a connection between two vertices and a 0 represents no connection.
Architectural Patterns
Architectural patterns are a high-level design pattern that focuses on the overall structure of the system. They are similar to design patterns, but they are more concerned with the structure of the system. They are used to solve problems that are common to many software systems.
Architectural Styles
Architectural patterns are the fundamental organization of a system, defining how the system is composed and how its components interact. Architectural patterns are identified by their name, like client-server, peer-to-peer, and layered.
Array
An array stores a fixed-size sequence of elements in contiguous memory, where each element is accessed directly by its index. This contiguous layout makes reading or writing any element an O(1) operation. Inserting or removing an element in the middle is slower, since it requires shifting the elements after it.
ASCII
ASCII is a character encoding standard for electronic communication. It was developed from telegraph code and uses 7 bits to represent 128 different characters. The first 32 characters are non-printable control characters used to control devices like printers and typewriters. The remaining 96 characters are printable and include the letters of the English alphabet, numbers, punctuation, and various symbols.
Asymptotic Notation
Asymptotic notation describes how the running time or memory usage of an algorithm grows as the size of its input increases, without tying the description to a specific machine or implementation detail. It focuses on the dominant term as input size approaches infinity, ignoring constants and lower-order terms. This makes it possible to compare algorithms independent of hardware or programming language.
AVL Trees
An AVL tree is a self-balancing binary search tree where the heights of the left and right subtrees of any node differ by at most one. When an insertion or deletion violates this balance, the tree performs rotations to restore it, guaranteeing O(log n) time for search, insert, and delete.
B-Trees
A B-tree is a self-balancing tree where each node can hold multiple keys and have multiple children, keeping the tree shallow even with a large number of elements. This makes B-trees well suited for storage systems like databases and file systems, where each node can be sized to match a disk block and minimize the number of disk reads needed to find data.
Balanced Search Trees
Balanced search trees are a type of data structure that allow for fast insertion, deletion, and lookup of data. They are a type of self-balancing binary search tree, which means that they are a binary tree that maintains the binary search tree property while also keeping the tree balanced. This means that the tree is always approximately balanced, which allows for fast insertion, deletion, and lookup of data.
Balanced Tree
A balanced tree keeps the height difference between subtrees small, typically bounded by a constant, so no path from root to leaf is much longer than another. This guarantees that operations like search, insert, and delete stay close to O(log n) regardless of insertion order. AVL trees and red-black trees are common implementations that enforce balance automatically.
BASE Model
BASE describes an alternative to the ACID model used by many distributed and NoSQL databases, standing for basically available, soft state, and eventually consistent. It favors availability and scalability over the strict consistency guarantees of ACID, accepting that data may be temporarily inconsistent across nodes before converging.
Basic Math Skills
Basic math skills for computer science cover the mathematical foundations that algorithm analysis and design rely on, including logic, probability, and combinatorics. These skills come up when estimating an algorithm's performance, reasoning about randomized algorithms, or counting the number of possible outcomes in a problem.
Bellman Ford's Algorithm
Bellman ford's algorithm is a graph algorithm that finds the shortest path from a source vertex to all other vertices in a graph. It is a dynamic programming algorithm that uses a bottom-up approach to find the shortest path. It is similar to Dijkstra's algorithm but it can handle negative weights. It is also similar to Floyd-Warshall's algorithm but it can handle negative weights and it is faster than Floyd-Warshall's algorithm.
Big Endian
Big endian is the most common type of endianness. In this type, the most significant byte is stored at the lowest memory address. This means that the most significant byte is stored first and the least significant byte is stored last.
Big O Notation
The Big O notation can be used to describe how the running time of an algorithm scales with the growth of the input size, ignoring implementation details such as programming language and computer speed. Specifically, it denotes the upper bound of the growth rate of a function that relates the running time of an algorithm to its input size. It can be used to compare algorithms and determine which one is better.
Big Omega Notation
Big Omega (Ω) notation describes a lower bound on an algorithm's growth rate, meaning the algorithm will take at least this much time or space in the best case. It is used to express the minimum amount of work an algorithm is guaranteed to do for a given input size.
Big Theta Notation
Big-Theta (Θ) notation describes a tight bound on an algorithm's growth rate, meaning the algorithm's running time grows at the same rate as the given function in both the best and worst case. It gives the most precise asymptotic description when an algorithm's upper and lower bounds match.
Binary Search Tree
A binary search tree (BST) is a binary tree where, for every node, all values in its left subtree are smaller and all values in its right subtree are larger. This ordering allows searching, insertion, and deletion in O(log n) time on average, since each comparison rules out half of the remaining nodes. Without balancing, a BST can degrade into a linked list in the worst case, which slows every operation to O(n).
Binary Search
Binary search is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.
Binary Tree
A binary tree is a tree where each node has at most two children, usually called the left and right child. This constraint makes it simple to reason about and forms the basis for more specialized structures like binary search trees and heaps. Binary trees can be traversed in different orders depending on when the current node is visited relative to its children.
Bitwise Operators
Bitwise operators are used to perform operations on individual bits of a number. They are used in cryptography, image processing, and other applications.
Boyer Moore Algorithm
Boyer Moore algorithm is a string searching algorithm that is used to find the index of a substring in a string. It is a very efficient algorithm that is used in many applications. It is used in text editors, compilers, and many other applications.
Breadth First Search
Breadth first search is a graph traversal algorithm that starts at the root node and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
Breadth First Search
Breadth first search for a graph is a way to traverse the graph. It starts at the root node and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
Brute Force Search
Brute force search is a simple algorithm that checks for a pattern in a string by comparing each character of the string with the first character of the pattern. If the first character matches, it then compares the next character of the string with the next character of the pattern and so on. If all the characters of the pattern match, then the pattern is found. If the first character does not match, then the algorithm compares the second character of the string with the first character of the pattern and so on.
Bubble Sort
Bubble sort repeatedly steps through a list, comparing adjacent elements and swapping them if they are in the wrong order, until no swaps are needed. Each pass moves the largest unsorted element into its correct position, like a bubble rising to the top. It runs in O(n²) time in the average and worst case, which makes it inefficient for large datasets but simple to understand and implement.
C++
C++ extends the C language with object-oriented features like classes, inheritance, and templates, while keeping low-level memory control. It compiles to native machine code and gives direct access to hardware resources, making it a common choice for game engines, operating systems, and performance-critical software. Manual memory management gives more control but also more room for bugs like leaks or dangling pointers.
C#
C# is an object-oriented language developed by Microsoft that runs on the .NET runtime. It combines a syntax similar to Java with features like properties, LINQ, and async/await for asynchronous programming. It is used heavily for Windows desktop apps, enterprise backends, and game development through Unity.
C
C is a general-purpose computer programming language. It was created in the 1970s by Dennis Ritchie, and remains very widely used and influential. By design, C's features cleanly reflect the capabilities of the targeted CPUs.
Caching
Caching is a way of storing data in a temporary storage to make future requests faster. It is one of the most important tools in the computer science toolbox.
CAP Theorem
CAP is an acronym for Consistency, Availability, and Partition Tolerance. According to the CAP theorem, any distributed system can only guarantee two of the three properties at any time. You can't guarantee all three properties at once.
Content Delivery Network (CDN)
A CDN is a network of servers that are distributed geographically. The servers are connected to each other and to the internet. The servers are used to deliver content to users. The content is delivered to the user from the server that is closest to the user. This is done to reduce latency and improve the performance of the content delivery.
Kỹ Năng Trọng Tâm & Thực Hành
Giai đoạn 2 tập trung hoàn thiện 38 chủ đề then chốt.
Character Encodings
A character encoding maps characters, like letters, digits, and symbols, to numeric values that a computer can store and process as bytes. Different encodings can represent different sets of characters and use different numbers of bytes per character, which is why text can display as garbled symbols when read with the wrong encoding.
Class Diagrams
Class Diagrams are used to model the static structure of a system. They are used to show the classes, their attributes, operations (or methods), and the relationships between objects.
Cloud Design Patterns
Cloud design patterns are reusable solutions for common problems that arise when building and operating applications on cloud infrastructure, such as handling transient failures, managing configuration across services, or scaling components independently. Patterns like circuit breaker, retry, and sidecar address the distributed and elastic nature of cloud environments.
Clustering
At a high level, a computer cluster is a group of two or more computers, or nodes, that run in parallel to achieve a common goal. This allows workloads consisting of a high number of individual, parallelizable tasks to be distributed among the nodes in the cluster. As a result, these tasks can leverage the combined memory and processing power of each computer to increase overall performance.
Co-NP
Co-NP stands for the complement of NP Class. It means if the answer to a problem in Co-NP is No, then there is proof that can be checked in polynomial time.
Combinatorics
Combinatorics is the branch of math concerned with counting, arranging, and combining objects according to given rules, covering concepts like permutations and combinations. It is used in algorithm analysis to count the number of possible states or configurations a problem can have, which often determines the feasibility of a brute-force approach.
Common Algorithms
Common algorithms are well-established, reusable procedures for solving recurring problems like sorting a list, searching for a value, or finding a path through a graph. Studying them builds intuition for algorithm design and gives a shared vocabulary for discussing performance trade-offs, since most real-world problems can be broken down into variations of these known patterns.
UML
UML is a standard way of visualizing a software system. It is a general-purpose, developmental, modeling language in the field of software engineering that is intended to provide a standard way to visualize the design of a system.
Complete Binary Tree
A complete binary tree fills every level from left to right, with all levels full except possibly the last, which is filled from the left. This shape allows the tree to be stored efficiently in an array, since a node's children can be found using simple index arithmetic instead of pointers. Binary heaps are usually implemented as complete binary trees for this reason.
Complexity Classes
In computer science, there exist some problems whose solutions are not yet found, the problems are divided into classes known as Complexity Classes. In complexity theory, a Complexity Class is a set of problems with related complexity. These classes help scientists to groups problems based on how much time and space they require to solve problems and verify the solutions. It is the branch of the theory of computation that deals with the resources required to solve a problem.
Concurrency in Multiple Cores
Concurrency or Parallelism is simultaneous execution of processes on a multiple cores per CPU or multiple CPUs (on a single motherboard). Concurrency is when Parallelism is achieved on a single core/CPU by using scheduling algorithms that divides the CPU's time (time-slice).
Constant
Constant time, written O(1), means an operation takes the same amount of time regardless of input size. Accessing an array element by index or reading a value from a hash table are typical examples, since neither depends on how much data the structure holds.
CPU Cache
A CPU cache is a hardware cache used by the central processing unit of a computer to reduce the average cost to access data from the main memory. A cache is a smaller, faster memory, located closer to a processor core, which stores copies of the data from frequently used main memory locations.
CPU Interrupts
CPU Interrupts are a way for the CPU to communicate with the rest of the computer. They are a way for the CPU to tell the rest of the computer that it needs to do something. For example, if the CPU is running a program and it needs to read from the keyboard, it will send an interrupt to the keyboard to tell it to send the data to the CPU. The CPU will then wait for the keyboard to send the data and then continue running the program.
Data Structures
A data structure is a way of organizing and storing data so it can be accessed and modified efficiently. Different structures, like arrays, linked lists, trees, and hash tables, trade off speed for different operations: some are fast to search, others are fast to insert into. Picking the right one for a problem often has a bigger effect on performance than optimizing the code around it.
Database Federation
Federation (or functional partitioning) splits up databases by function. The federation architecture makes several distinct physical databases appear as one logical database to end-users.
Databases
A database is a collection of useful data of one or more related organizations structured in a way to make data an asset to the organization. A database management system is a software designed to assist in maintaining and extracting large collections of data in a timely fashion.
DCL (Data Control Language)
DCL includes commands such as GRANT and REVOKE which mainly deal with the rights, permissions, and other controls of the database system.
DDL (Data Definition Language)
DDL or Data Definition Language actually consists of the SQL commands that can be used to define the database schema. It simply deals with descriptions of the database schema and is used to create and modify the structure of database objects in the database. DDL is a set of SQL commands used to create, modify, and delete database structures but not data. These commands are normally not used by a general user, who should be accessing the database via an application.
Dependency Injection
Dependency injection is a software design pattern that allows us to decouple the dependencies of a class from the class itself. This allows us to write more flexible and testable code.
Depth First Search
Depth first search is a graph traversal algorithm that starts at a root node and explores as far as possible along each branch before backtracking.
Depth First Search
Depth first search is a graph traversal algorithm that starts at a root node and explores as far as possible along each branch before backtracking.
Design Patterns
Design patterns are solutions to common problems in software design. They are formalized best practices that the programmer can use to solve common problems when designing an application or system.
Dijkstra's Algorithm
Dijkstra's algorithm is a greedy algorithm that finds the shortest path between two nodes in a graph. It is a very common algorithm used in computer science and is used in many applications such as GPS navigation, network routing, and finding the shortest path in a maze.
Dijkstra's Algorithm
Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. It repeatedly picks the closest unvisited vertex and updates the shortest known distances to its neighbors, using a priority queue to make this selection efficient. It does not work correctly if the graph contains negative edge weights.
Directed Graph
A directed graph is graph, i.e., a set of objects (called vertices or nodes) that are connected together, where all the edges are directed from one vertex to another. A directed graph is sometimes called a digraph or a directed network. In contrast, a graph where the edges are bidirectional is called an undirected graph.
DML (Data Manipulation Language)
The SQL commands that manipulate data in the database belong to DML, or Data Manipulation Language, and this includes most of the SQL statements. DCL is the component of the SQL statement that controls access to data and to the database. Basically, DCL statements are grouped with DML statements.
DNS
The Domain Name System (DNS) is the phonebook of the Internet. Humans access information online through domain names, like [nytimes.com](http://nytimes.com) or [espn.com](http://espn.com). Web browsers interact through Internet Protocol (IP) addresses. DNS translates domain names to IP addresses so browsers can load Internet resources.
DQL (Data Query Language)
DQL (Data Query Language) is the subset of SQL used to retrieve data from a database, primarily through the SELECT statement. It is used to read and filter existing data without modifying it.
Endianness
Endianness is the order in which bytes are stored in memory. The two most common types of endianness are big endian and little endian. Big endian stores the most significant byte first, while little endian stores the least significant byte first.
Entity Relationship Model
Entity relationship model is a high-level data model that describes the logical structure of a database. It is a graphical representation of entities and their relationships to each other, typically used in modeling the organization of data within databases or information systems.
Exponential
Exponential time, written O(2^n), means the work doubles with each additional unit of input size. Algorithms with exponential time complexity become impractical quickly as input grows, and they often show up in brute-force solutions to problems without known efficient algorithms.
Factorial
Factorial time, written O(n!), means the work grows by the factorial of the input size, making it impractical for anything but very small inputs. Algorithms that generate every possible permutation of a set, like a brute-force solution to the traveling salesman problem, run in factorial time.
Finding Hamiltonian Paths
Hamiltonian paths are paths that visit every node in a graph exactly once. They are named after the famous mathematician Hamilton. Hamiltonian paths are a special case of Hamiltonian cycles, which are cycles that visit every node in a graph exactly once.
Floating Point Numbers
Floating point numbers are numbers that have a decimal point in them. They are used to represent real numbers. For example, 3.14 is a floating point number. 3 is not a floating point number because it does not have a decimal point in it.
Ford Fulkerson Algorithm
Ford Fulkerson Algorithm is a greedy algorithm that is used to find the maximum flow in a flow network. It is also known as the Edmonds-Karp Algorithm.
Full Binary Tree
A full binary tree is a binary tree where every node has either zero or two children, never just one. This property is used in some algorithm proofs and data structures, like certain heap implementations, where a strict shape simplifies reasoning about node counts and depth.
Go
Go is a compiled, statically typed language created at Google to make concurrent, networked software simple to write and deploy. It has built-in support for concurrency through goroutines and channels, and it compiles to a single binary with no external runtime dependencies. Go is widely used for backend services, CLIs, and infrastructure tooling.
Kiến Trúc Nâng Cao & Tối Ưu
Giai đoạn 3 tập trung hoàn thiện 38 chủ đề then chốt.
GoF Design Patterns
Gang of Four (GoF) design patterns are a set of 23 design patterns that were first described in the book "Design Patterns: Elements of Reusable Object-Oriented Software" by Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. The book is commonly referred to as the "Gang of Four book".
Graph
Graphs in data structures are non-linear data structures made up of a finite number of nodes or vertices and the edges that connect them. Graphs in data structures are used to address real-world problems in which it represents the problem area as a network like telephone networks, circuit networks, and social networks.
GraphQL
GraphQL is a query language for APIs and a runtime for fulfilling those queries with your existing data. GraphQL provides a complete and understandable description of the data in your API, gives clients the power to ask for exactly what they need and nothing more, makes it easier to evolve APIs over time, and enables powerful developer tools.
gRPC
gRPC is a remote procedure call framework that lets a client call methods on a server as if they were local function calls, using Protocol Buffers for efficient binary serialization. It runs over HTTP/2, which enables features like multiplexed streaming, and is commonly used for fast communication between internal microservices.
Hash Table
A hash table stores key-value pairs and uses a hash function to compute an index into an underlying array where each value is stored. This gives average-case O(1) time for lookups, insertions, and deletions. Collisions, where two keys hash to the same index, are handled with techniques like chaining or open addressing.
Hashing/Encryption/Encoding
Hashing, encryption, and encoding are often confused but serve different purposes. Hashing produces a fixed-size, one-way output used to verify data integrity or store passwords securely, encryption transforms data reversibly so only someone with the right key can read it, and encoding transforms data into a different format for compatibility, with no security guarantee at all.
Hashing Algorithms
Hashing algorithms are used to generate a unique value for a given input. This value is called a hash. Hashing algorithms are used to verify the integrity of data, to store passwords, and to generate unique identifiers for data.
Heap Sort
Heap sort is a comparison based sorting algorithm. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for remaining element.
Heap
A heap is a tree-based structure that satisfies the heap property: in a max heap, every parent is greater than or equal to its children, and in a min heap, every parent is smaller than or equal to its children. This makes finding the maximum or minimum element an O(1) operation, while insertion and removal take O(log n). Heaps are commonly used to implement priority queues.
Horizontal vs Vertical Scaling
Horizontal scaling is the process of adding more machines to your system. This is also known as scaling out. Vertical scaling is the process of adding more power to a single machine. This is also known as scaling up.
How Computers Calculate?
Computers perform calculations by representing numbers in binary and manipulating them using logic gates built from transistors, which implement operations like addition through circuits called adders. Complex operations, like multiplication or floating point math, are built up from combinations of these basic binary operations at the hardware level.
How Computers Work?
Computers are everywhere. They are in our phones, our cars, our homes, and even in our pockets. But how do they actually work? How do they take in information, and how do they output information?
How CPU Executes Programs?
The CPU executes programs by repeatedly fetching instructions from memory, decoding them to understand the operation, and then executing those operations. This cycle, called the fetch-decode-execute cycle, continues for each instruction in the program, with the CPU using registers for temporary storage and a program counter to keep track of the next instruction. Modern CPUs use techniques like pipelining and caches to speed up this process, enabling them to execute complex programs efficiently.
HTTP?
HTTP is the `TCP/IP` based application layer communication protocol which standardizes how the client and server communicate with each other. It defines how the content is requested and transmitted across the internet.
Huffman Coding
Huffman coding is a lossless data compression algorithm. The idea is to assign variable-length codes to input characters, lengths of the assigned codes are based on the frequencies of corresponding characters. The most frequent character gets the smallest code and the least frequent character gets the largest code.
In-Order Traversal
In-order traversal is a tree traversal algorithm that visits the left subtree, the root, and then the right subtree. This is the most common way to traverse a binary search tree. It is also used to create a sorted list of nodes in a binary search tree.
Database Indexes
An index is a data structure that you build and assign on top of an existing table that basically looks through your table and tries to analyze and summarize so that it can create shortcuts.
Insertion Sort
Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time by comparisons. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.
Instructions and Programs
Instructions are the most basic commands a CPU can understand, directing it to perform specific actions like adding numbers or moving data. A program, on the other hand, is a collection of these instructions, organized in a sequence to accomplish a particular task. Think of instructions as individual words and a program as a complete sentence or story; the CPU executes these instructions one by one, following the program's logic, to achieve the desired outcome.
Java
Java is an object-oriented, statically typed language that compiles to bytecode and runs on the Java Virtual Machine (JVM), which lets the same compiled code run on any platform with a JVM installed. It manages memory automatically through garbage collection. Java is widely used in enterprise backend systems, Android development, and large-scale distributed applications.
N-ary (K-ary, M-ary) Trees
A k-ary (or m-ary) tree is a generalization of a binary tree where each node can have up to k children instead of just two. Increasing the branching factor reduces the tree's height for a given number of nodes, which is useful in structures like B-trees where minimizing height matters for disk access.
K-D Trees
K-D Trees are a data structure that allow for fast nearest neighbor search in high dimensional spaces. They are a generalization of binary search trees, and are used in a variety of applications, including computer vision and computational geometry.
Knapsack Problem
KnapSack Problem is a classic problem in computer science. It is a problem in which we are given a set of items, each with a weight and a value, and we need to determine which items to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
Knuth Morris Pratt
The Knuth-Morris-Pratt (KMP) algorithm searches for a pattern in text by preprocessing the pattern into a table that tracks the longest proper prefix that is also a suffix. This lets the algorithm skip re-checking characters it has already matched when a mismatch occurs, giving it O(n + m) time complexity.
Kruskal's algorithm
Kruskal's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted graph. It is a minimum spanning tree algorithm that takes a graph as input and finds the subset of the edges of that graph which form a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component).
LFU Cache
LFU Cache is a data structure that stores key-value pairs. It has a fixed size and when it is full, it removes the least frequently used key-value pair. It is a variation of the LRU Cache and is used in many applications such as caching web pages, caching database queries, and caching images.
Linear Search
Linear search is a very simple algorithm that is used to search for a value in an array. It sequentially checks each element of the array until a match is found or until all the elements have been searched.
Linear
Linear algorithms are algorithms that have a runtime that is directly proportional to the size of the input. This means that the runtime of the algorithm will increase linearly with the size of the input. For example, if the input size is 10, the runtime will be 10 times the runtime of the algorithm when the input size is 1. If the input size is 100, the runtime will be 100 times the runtime of the algorithm when the input size is 1.
Linked Lists
Arrays store elements in contiguous memory locations, resulting in easily calculable addresses for the elements stored and this allows faster access to an element at a specific index. Linked lists are less rigid in their storage structure and elements are usually not stored in contiguous locations, hence they need to be stored with additional tags giving a reference to the next element. This difference in the data storage scheme decides which data structure would be more suitable for a given situation.
Little Endian
Little Endian is a way of storing data in memory. It is the opposite of Big Endian. In Little Endian, the least significant byte is stored first. In Big Endian, the most significant byte is stored first.
Load Balancing
Load balancing is the process of distributing network or application traffic across a cluster of servers. Load balancing is used to improve responsiveness and reliability of applications, maximize throughput, minimize response time, and avoid overload of any single server.
Lock / Mutex / Semaphore
A lock or mutex ensures that only one thread can access a shared resource at a time, preventing race conditions when multiple threads read and write the same data. A semaphore is a more general version that allows a set number of threads to access a resource concurrently, using a counter instead of a simple locked or unlocked state.
Locking
Locks are used to prevent data from being modified by multiple processes at the same time. This is important because if two processes are modifying the same data at the same time, the data can become corrupted. Locks are used to prevent this from happening.
Logarithmic
Logarithmic time, written O(log n), means the work needed grows very slowly as input size increases, typically because the algorithm cuts the problem size in half (or by some fraction) at each step. Binary search is a classic example: doubling the input size only adds one more comparison.
Long Polling
Long polling is a technique used to implement server push functionality over HTTP. It is a method of opening a request on the server and keeping it open until an event occurs, at which point the server responds. This is in contrast to a regular HTTP request, where the server responds immediately with whatever data is available at the time.
Longest Path Problem
The Longest Path Problem asks for the longest simple path between two vertices in a graph, one that does not repeat any vertex. Unlike the shortest path problem, which has efficient algorithms, finding the longest path is NP-hard in general graphs, though it becomes solvable in polynomial time for special cases like directed acyclic graphs.
LRU Cache
LRU cache is a cache that evicts the least recently used item first. It is a very common cache algorithm. It is used in many places, such as in the browser cache, the database cache, and the cache of the operating system.
Maze Solving Problem
Maze solving problem is a classic problem in computer science. It is a problem where we have to find a path from a starting point to an end point in a maze. The maze is represented as a grid of cells. Each cell can be either a wall or a path. The path cells are connected to each other. The starting point and the end point are also given. The goal is to find a path from the starting point to the end point. The path can only be made up of path cells. The path cannot go through the wall cells.
Hệ Sinh Thái & Triển Khai Thực Tế
Giai đoạn 4 tập trung hoàn thiện 38 chủ đề then chốt.
Memory Management
Memory management is the process of allocating and deallocating memory. It is a very important part of any programming language.
Merge Sort
Merge sort is a divide and conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves. The `merge()` function is used for merging two halves. The `merge(arr, l, m, r)` is key process that assumes that `arr[l..m]` and `arr[m+1..r]` are sorted and merges the two sorted sub-arrays into one.
MFU Cache
MFU Cache is another cache algorithm. The difference is that instead of deleting the least frequently used entry, the MFU Cache deletes the most frequently used entry.
Networking
Networking is the process of connecting two or more computing devices together for the purpose of sharing data. In a data network, shared data may be as simple as a printer or as complex as a global financial transaction. If you have networking experience or want to be a reliability engineer or operations engineer, expect questions from these topics. Otherwise, this is just good to know.
Non-Tail Recursion
Non-tail recursion is a form of recursion where work remains to be done after the recursive call returns, such as combining the result with something else. Each call must keep its stack frame until the recursive call underneath it finishes, which means the call stack grows with each level of recursion and cannot be optimized away like tail recursion.
Normalization vs Denormalization
Normalization organizes a database schema to reduce data redundancy by splitting data into related tables, following a set of normal forms. Denormalization does the opposite, intentionally duplicating data across tables to reduce the number of joins needed for common queries, trading storage and update complexity for faster reads.
NP Complete
A problem is NP-complete if it is both NP and NP-hard. NP-complete problems are the hard problems in NP.
NP-Hard
An NP-hard problem is at least as hard as the hardest problem in NP and it is the class of the problems such that every problem in NP reduces to NP-hard.
NP
The NP in NP class stands for Non-deterministic Polynomial Time. It is the collection of decision problems that can be solved by a non-deterministic machine in polynomial time.
Null Object Pattern
Null object pattern is a design pattern that is used to represent a null value with an object. It is a way to avoid null reference exceptions by providing a default object that does nothing. It is a way to provide a default behavior in case data is not available.
OSI and TCP/IP Models
The OSI and TCP/IP model is used to help the developer to design their system for interoperability. The OSI model has 7 layers while the TCP/IP model has a more summarized form of the OSI model only consisting 4 layers. This is important if you're trying to design a system to communicate with other systems.
OWASP
OWASP or Open Web Application Security Project is an online community that produces freely-available articles, methodologies, documentation, tools, and technologies in the field of web application security.
P = NP
P = NP is one of the most famous open problems in computer science, asking whether every problem whose solution can be verified quickly can also be solved quickly. Most researchers believe P does not equal NP, but no one has proven it either way, and a proof in either direction would have major implications for cryptography and optimization.
P
P is the complexity class of decision problems that can be solved by a deterministic algorithm in polynomial time. Problems in P are generally considered efficiently solvable, forming the baseline against which harder complexity classes are compared.
PACELC Theorem
The PACELC Theorem is an extension of the CAP Theorem. One of the questions that CAP Theorem wasn’t able to answer was “what happens when there is no Partition, What Logical Combination then a Distributed System have?“. So to answer this, In addition to Consistency, Availability, and Partition Tolerance it also includes Latency as one of the desired properties of a Distributed System. The acronym PACELC stands for Partitioned, Availability, Consistency Else Latency, Consistency.
Pick a Language
You need to pick a programming language to learn computer science concepts. My personal recommendation would be to pick C++ or C. They allow you to deal with pointers and memory allocation/deallocation, so you feel the data structures and algorithms in your bones. In higher level languages like Python or Java, these are hidden from you. In day to day work, that's terrific, but when you're learning how these low-level data structures are built, it's great to feel close to the metal. Also, you will be able to find a lot of resources for the topics listed in this roadmap using C or C++.
Polynomial
Polynomial time means an algorithm's running time can be expressed as n raised to some fixed power, such as O(n²) or O(n³). Problems solvable in polynomial time are generally considered tractable in complexity theory, forming the basis of the complexity class P.
Post-Order Traversal
Post-order traversal is a type of tree traversal that visits the left subtree, then the right subtree, and finally the root node. This is the opposite of pre-order traversal, which visits the root node first, then the left subtree, and finally the right subtree.
Pre-Order Traversal
Pre-order traversal is a way to visit every node in a tree data structure. It follows a specific order: first, the current node is processed (or visited). Then, the left subtree of the current node is traversed using pre-order. Finally, the right subtree of the current node is traversed using pre-order. This "node-left-right" sequence ensures each node is visited exactly once.
Prim's Algorithm
Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. A minimum spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. A minimum spanning tree for a weighted undirected graph is also called a minimum weight spanning tree or minimum cost spanning tree.
Probability
Probability measures how likely an event is to occur, expressed as a number between 0 and 1. In computer science, it comes up in randomized algorithms, hashing collision analysis, and average-case complexity analysis, where the expected behavior of an algorithm depends on the distribution of its inputs.
Process Forking
Process forking is a way to create a new process from an existing process. The new process is a copy of the existing process. The new process is called a child process and the existing process is called a parent process.
Processes and Threads
Processes and threads are the basic building blocks of a computer program. They are the smallest units of execution in a program. A process is an instance of a program that is being executed. A thread is a sequence of instructions within a process that can be executed independently of other code.
Processes and Threads
Processes and threads are the basic building blocks of a computer program. They are the smallest units of execution in a program. A process is an instance of a program that is being executed. A thread is a sequence of instructions within a process that can be executed independently of other code.
Proxy
A proxy server is an intermediary piece of hardware/software sitting between the client and the backend server. It receives requests from clients and relays them to the origin servers. Typically, proxies are used to filter requests, log requests, or sometimes transform requests (by adding/removing headers, encrypting/decrypting, or compression).
Public Key Cryptography
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic algorithms based on mathematical problems termed one-way functions.
Python
Python is a well known programming language which is both a strongly typed and a dynamically typed language. Being an interpreted language, code is executed as soon as it is written and the Python syntax allows for writing code in functional, procedural or object-oriented programmatic ways.
Queue
A queue is a data structure that processes elements in the order they arrived, following a first-in, first-out (FIFO) rule. New elements are added at the back and removed from the front. Queues are used for task scheduling, handling requests in order, and breadth-first traversal of trees and graphs.
Queues
Messaging queues are a common way to decouple systems. They are used to decouple the producer of a message from the consumer of a message. This allows the producer to send a message and not have to wait for the consumer to process it. It also allows the consumer to process the message at their own pace.
Quick Sort
Quick Sort is a divide and conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.
Rabin-Karp's algorithm
Rabin-Karp algorithm is a string searching algorithm that uses hashing to find any one of a set of pattern strings in a text. For strings of average length `n`, it performs in `O(n+m)` time with `O(m)` space, where `m` is the length of the pattern. It is often used in bioinformatics to search for DNA patterns.
Red / Black Trees
A red-black tree is a self-balancing binary search tree where each node is colored red or black, and a set of coloring rules ensures the tree never becomes more than roughly twice as tall as the shortest possible balanced tree. It requires fewer rotations on average than an AVL tree, which makes it a common choice for implementing ordered maps and sets in standard libraries.
Registers and RAMs
**_Registers_** are the smallest data-holding elements built into the processor itself. Registers are the memory locations that are directly accessible by the processor. The registers hold the instruction or operands currently accessed by the CPU. Registers are the high-speed accessible storage elements. The processor accesses the registers within one CPU clock cycle. The processor can decode the instructions and perform operations on the register contents at more than one operation per CPU clock cycle. **_Memory_** is a hardware device that stores computer programs, instructions, and data. The memory that is internal to the processor is primary memory (RAM), and the memory that is external to the processor is secondary (**Hard Drive**).
Replication
Replication is a process that involves sharing information to ensure consistency between redundant resources such as multiple databases, to improve reliability, fault-tolerance, or accessibility.
REST
REST, or REpresentational State Transfer, is an architectural style for providing standards between computer systems on the web, making it easier for systems to communicate with each other.
Rabin-Karp's algorithm
Rabin-Karp algorithm is a string searching algorithm that uses hashing to find any one of a set of pattern strings in a text. For strings of average length `n`, it performs in `O(n+m)` time with `O(m)` space, where `m` is the length of the pattern. It is often used in bioinformatics to search for DNA patterns.
Rust
Java is an object-oriented, statically typed language that compiles to bytecode and runs on the Java Virtual Machine (JVM), which lets the same compiled code run on any platform with a JVM installed. It manages memory automatically through garbage collection. Java is widely used in enterprise backend systems, Android development, and large-scale distributed applications.
Scheduling Algorithms
Scheduling algorithms determine the order in which an operating system runs competing processes or threads on the available CPU cores. Different algorithms, like round robin, shortest job first, or priority scheduling, balance goals such as fairness, responsiveness, and overall throughput differently.
Chuyên Gia & Mở Rộng Hệ Thống
Giai đoạn 5 tập trung hoàn thiện 36 chủ đề then chốt.
Search Pattern in Text
Searching pattern in text is a very common task in computer science. It is used in many applications like spell checkers, text editors, and many more.
Security
Web security refers to the protective measures taken by the developers to protect the web applications from threats that could affect the business.
Selection Sort
Selection sort is a sorting algorithm that selects the smallest unsorted item in the list and swaps it with index 0, then finds the next smallest and places it into index 1 and so on.
Sequence Diagrams
A sequence diagram shows how objects interact with each other over time by depicting the order in which messages are sent between them. It is commonly used to visualize the flow of a specific scenario, like a user login process, across multiple components.
Sharding
Database sharding is a method of distributing data across multiple machines. It is a horizontal scaling technique, as opposed to vertical scaling, which is scaling by adding more power to a single machine. Sharding is a common way to scale a database.
Short Polling
In short polling, the client requests information from the server. The server processes the request. If data is available for the request, server responds to the request with the required information. However, if the server has no data available for the client, server returns an empty response. In both the situation, the connection will be closed after returning the response. Clients keep issuing new requests even after server sends the empty responses. This mechanism increases the network cost on the server.
Skip Lists
Skip lists are a data structure that allows you to perform operations on a sorted list in O(log n) time. Skip lists are a probabilistic data structure, which means that the probability of a certain operation taking a certain amount of time is a certain value. In the case of skip lists, the probability of an operation taking O(log n) time is 1.
Small O Notation
Small o notation describes an upper bound that is strictly greater than the actual growth rate, rather than a tight or achievable bound like Big O. It is used to express that one function grows strictly slower than another, useful in more formal algorithm analysis and proofs.
Small Omega
Small omega notation describes a lower bound that is strictly less than the actual growth rate, the counterpart to small o. It states that an algorithm's growth rate is strictly greater than a given function, used mainly in theoretical analysis rather than everyday complexity comparisons.
Sockets
A socket is an interface for network communication. It is a way for two programs to communicate with each other over a network. It is a way for a client to send a request to a server and for the server to send a response back to the client.
Solving n Queen Problem
N Queen Problem is a famous problem in Computer Science. It is a problem of placing n queens on an n x n chessboard such that no two queens attack each other. The problem is to find all possible solutions to the problem.
Spanning Tree
A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected..
SQL vs NoSQL databases
SQL databases store data in structured tables with fixed schemas and use SQL to query relationships between them, prioritizing consistency and complex querying. NoSQL databases store data in more flexible formats, like documents, key-value pairs, or graphs, and generally prioritize horizontal scalability and flexible schemas over strict consistency guarantees.
Server Sent Events
Server-Sent Events is a server push technology enabling a client to receive automatic updates from a server via an HTTP connection, and describes how servers can initiate data transmission towards clients once an initial client connection has been established.
Stack
Stack is a linear collection of items where items are inserted and removed in a particular order. Stack is also called a LIFO Data Structure because it follows the "Last In First Out" principle i.e. the item that is inserted in the last is the one that is taken out first.
State Machine Diagrams
State machine diagrams are used to show the different states an object can be in at a given time. The object can be in one and only one state at a given time. State machine diagrams are similar to activity diagrams, but they are more focused on the flow of an object's state rather than the flow of the object itself.
Stored Procedures
Stored Procedures are created to perform one or more DML operations on Database. It is nothing but the group of SQL statements that accepts some input in the form of parameters and performs some task and may or may not returns a value.
String Search and Manipulations
String search and manipulation is a very important topic in computer science. It is used in many different applications, such as searching or replacing a specific pattern, word or character in a string.
Substring Search
Substring search is the problem of finding a substring in a string. This is a very common problem in computer science, and there are many algorithms for solving it.
Suffix Arrays
Suffix arrays are a data structure that allows us to quickly find all the suffixes of a string in lexicographical order. This is useful for many problems, such as finding the longest common substring between two strings, or finding the number of distinct substrings of a string.
System Design
System design is the process of defining the architecture, modules, interfaces, and data for a system to satisfy specified requirements. It is a very broad topic, and there are many ways to approach it.
Tail Recursion
Tail recursion is a special kind of recursion where the recursive call is the very last thing in the function. It's a function that does not do anything at all after recursing.
OSI and TCP/IP Models
The OSI and TCP/IP model is used to help the developer to design their system for interoperability. The OSI model has 7 layers while the TCP/IP model has a more summarized form of the OSI model only consisting 4 layers. This is important if you're trying to design a system to communicate with other systems.
Knight's Tour Problem
Knight's Tour Problem is a problem where we have to find a path for a knight to visit all the cells of a chessboard without visiting any cell twice.
TLS / HTTPS
TLS (Transport Layer Security) is a cryptographic protocol that provides privacy and data integrity between two communicating applications. It is widely used to secure HTTP, although it can be used with any protocol. TLS is often used in combination with HTTPS, which is HTTP over TLS.
Transactions
In short, a database transaction is a sequence of multiple operations performed on a database, and all served as a single logical unit of work — taking place wholly or not at all. In other words, there's never a case where only half of the operations are performed and the results saved.
Travelling Salesman Problem
The Travelling Salesman Problem (TSP) is a classic problem in computer science. It is a problem that is NP-complete, which means that it is a problem that is hard to solve. It is also a problem that is used to test the efficiency of algorithms.
Tree
A tree is a hierarchical data structure made of nodes connected by edges, with one node designated as the root and every other node reachable from it through exactly one path. Each node can have child nodes, and nodes with no children are called leaves. Trees are used to represent hierarchical relationships and support efficient searching, insertion, and deletion when balanced.
Tries
Tries are a data structure that can be used to store strings. The idea is to store the characters of the string in a tree-like structure, where each node of the tree represents a single character. We can use this structure to store strings in a way that allows us to quickly search for strings with a common prefix.
Type Object Pattern
Type object pattern is a creational design pattern that allows us to create a new object of a type without exposing the object creation logic to the client. It is used when we need to create a new object of a type, but we don't know which type we need to create until runtime. It is like a factory pattern, but instead of returning a new object of a type, it returns a new object of a type that is already created.
Unbalanced Tree
An unbalanced tree has subtrees of very different heights, which can happen when data is inserted in a sorted or near-sorted order into a plain binary search tree. In the worst case, the tree degenerates into something resembling a linked list, and operations that should take O(log n) instead take O(n). Self-balancing tree variants exist specifically to prevent this.
Undirected Graph
An undirected graph is graph, i.e., a set of objects (called vertices or nodes) that are connected together, where all the edges are bidirectional. An undirected graph is sometimes called an undirected network. In contrast, a graph where the edges point in a direction is called a directed graph.
Unicode
Unicode is a standard for encoding characters. It is a superset of ASCII, which means that ASCII is a subset of Unicode. Unicode is a 16-bit encoding, which means that it can encode 2^16 = 65536 characters. This is a lot more than ASCII, which can only encode 128 characters.
Usecase Diagrams
A use case diagram shows the interactions between actors, such as users or external systems, and the use cases, or goals, they can achieve within a system. It gives a high-level view of what a system does from the perspective of the people or systems that use it, without describing implementation details.
Views
Views in SQL are kind of virtual tables. A view also has rows and columns as they are in a real table in the database. We can create a view by selecting fields from one or more tables present in the database. A View can either have all the rows of a table or specific rows based on certain condition.
Web Sockets
Web sockets are a bidirectional communication protocol between a client and a server. They are used for real-time applications like chat, multiplayer games, and live data updates. Web sockets are also used to establish a connection between a server and a client. This connection is then used to send data in both directions.