The Advanced Toolkit
The Engine of Instant Lookups
In an array, finding an element by its value is an O(n) operation. If you have a million users, finding one by their email address could take a million comparisons.
How can we do better? How can we achieve O(1), or constant-time, lookups?
A Hash Table is a data structure that maps keys to values for highly efficient lookups. It uses a hash function to compute an index into an array of buckets or slots.
Analogy: A library with a magical filing system. To find a book, you tell the librarian the title (the key). The librarian performs a magic spell (the hash function) on the title, which instantly tells them exactly which shelf and slot (the index) the book is on.
You have been using hash tables all along!
What happens if the hash function produces the same index for two different keys? This is called a collision.
A common solution is called Separate Chaining. Instead of storing the value directly in the array slot, we store a linked list of key-value pairs at that index. If a collision occurs, we just add the new pair to the linked list.
The time complexity depends on the quality of the hash function.
Hierarchical Data Structures
A tree is a non-linear data structure that consists of nodes in a parent-child relationship. It's used to represent hierarchical data.
Examples: A file system, an organization chart, the DOM.
A Binary Tree is a tree where each node has at most two children, referred to as the left and right child.
A Binary Search Tree is a special type of binary tree with a strict ordering property:
This ordering property is a superpower. It allows for incredibly fast operations by repeatedly discarding half the tree.
For a balanced BST (where the height is kept to a minimum):
This is why databases use tree-like structures (B-Trees) for their indexes!
class TreeNode {
public value: number;
public left: TreeNode | null = null;
public right: TreeNode | null = null;
constructor(value: number) {
this.value = value;
}
}
class BinarySearchTree {
public root: TreeNode | null = null;
insert(value: number) {
// ... logic to traverse and insert
}
find(value: number): TreeNode | null {
// ... logic to traverse and find
}
}
The Ultimate Network Structure
A graph is a collection of vertices (or nodes) and edges that connect them. It is the most general-purpose data structure, capable of modeling any kind of relationship.
Examples: Social networks (users are vertices, friendships are edges), the internet (web pages are vertices, links are edges), maps (cities are vertices, roads are edges).
Searching and Sorting
These are simple to understand but too slow for most real-world applications with large datasets.
Repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The largest elements "bubble" to the end.
Time Complexity: O(n²)
Builds the final sorted array one item at a time. It iterates through the input elements and inserts each element into its correct position in the sorted part of the array.
Time Complexity: O(n²)
These use the "divide and conquer" strategy and are much faster.
It divides the unsorted list into n sublists, each containing one element, and then repeatedly merges sublists to produce new sorted sublists until there is only one sublist remaining.
Time Complexity: O(n log n)
It picks an element as a "pivot" and partitions the given array around the picked pivot. All smaller elements go to the left, all larger elements go to the right. It then recursively applies this to the sub-arrays.
Time Complexity: Average Case O(n log n), Worst Case O(n²)
Your task is to implement the binary search algorithm in TypeScript. This is a foundational "divide and conquer" algorithm that every engineer must know.