This repository contains implementations of various algorithms and data structures in TypeScript. It is designed to help individuals prepare for software engineering interviews where these concepts are crucial.
- Arrays
- Linked Lists
- Stacks
- Queues
- Hash Tables (Hash Maps)
- Trees
- Graphs
- Advanced Data Structures
- Algorithms
- Additional Concepts
- Static Arrays: Fixed size arrays, straightforward to implement but lack flexibility.
- Dynamic Arrays: Arrays that resize automatically when they reach capacity, providing more flexibility but requiring more complex memory management.
- Arrays with more than one dimension, useful for representing grids, matrices, etc.
- A list where each element points to the next, allowing for efficient insertions and deletions.
- A list where each element points to both the next and previous elements, providing efficient bidirectional traversal.
- A linked list where the last element points back to the first, forming a circle.
- Array-based Stacks: Simple but may require resizing.
- Linked List-based Stacks: More flexible with efficient dynamic memory usage.
- Expression Evaluation: Using stacks to evaluate postfix or prefix expressions.
- Backtracking: Using stacks to remember choices while exploring possibilities (e.g., in puzzles).
- A basic FIFO (First-In-First-Out) structure.
- A queue where the end wraps around to the beginning, optimizing space usage.
- A queue where elements are dequeued based on priority rather than order of insertion.
- A queue where elements can be added or removed from both ends.
- Techniques to convert keys into indices (e.g., division method, multiplication method).
- Chaining: Using linked lists to handle collisions at each bucket.
- Open Addressing: Finding another open slot within the table (e.g., linear probing, quadratic probing).
- Trees where each node has at most two children.
- Binary trees with the left child smaller and the right child larger than the parent node.
- Self-balancing BSTs where the height difference between left and right subtrees is at most 1.
- Self-balancing BSTs with additional properties to ensure balance after insertions and deletions.
- Complete binary trees used to implement priority queues, where the parent node is either smaller (min-heap) or larger (max-heap) than its children.
- Trees used to store a dynamic set of strings where keys are usually strings.
- Adjacency Matrix: A 2D array to represent graph connections.
- Adjacency List: An array of lists to represent graph connections more efficiently.
- Directed Graphs: Edges have a direction.
- Undirected Graphs: Edges have no direction.
- Graphs where edges have weights or costs associated with them.
- Trees used for answering range queries efficiently.
- Data structures that provide efficient methods for cumulative frequency tables.
- Data structures to keep track of a partition of a set into disjoint subsets.
- Repeatedly swaps adjacent elements if they are in the wrong order.
- Selects the smallest (or largest) element and swaps it with the first unsorted element.
- Builds the final sorted array one item at a time.
- Divides the array into halves, sorts them, and merges them back together.
- Picks an element as a pivot and partitions the array around the pivot.
- Uses a heap to repeatedly extract the maximum element.
- Counts the number of objects with distinct key values.
- Sorts numbers by processing individual digits.
- Distributes elements into buckets and sorts each bucket individually.
- Searches for an element by checking each element in the array sequentially.
- Searches a sorted array by repeatedly dividing the search interval in half.
- Explores as far as possible along each branch before backtracking.
- Explores all neighbors at the present depth before moving on to nodes at the next depth level.
- Finds the shortest path from a single source to all other nodes in a weighted graph.
- Computes shortest paths from a single source, allowing for negative weights.
- Computes shortest paths between all pairs of nodes.
- Finds a minimum spanning tree for a weighted undirected graph.
- Finds a minimum spanning tree by sorting edges and adding them to the tree if they don’t form a cycle.
- Orders nodes in a directed acyclic graph (DAG).
- Memoization: Top-down approach using recursion and caching.
- Tabulation: Bottom-up approach using iterative computation.
- Knapsack: Maximizes the total value without exceeding the weight capacity.
- Longest Common Subsequence: Finds the longest subsequence common to two sequences.
- Longest Increasing Subsequence: Finds the longest subsequence that is strictly increasing.
- Fibonacci Sequence: Computes the Fibonacci numbers efficiently.
- Activity Selection: Selects the maximum number of activities that don’t overlap.
- Huffman Coding: Constructs an optimal prefix code for a set of symbols.
- Coin Change Problem: Finds the minimum number of coins for a given amount.
- Merge Sort: Divides the array, sorts, and merges.
- Quick Sort: Partitions the array and sorts the partitions.
- Binary Search: Recursively divides the search interval.
- Strassen’s Matrix Multiplication: Multiplies matrices faster than the standard method.
- N-Queens Problem: Places N queens on an N×N chessboard so that no two queens threaten each other.
- Sudoku Solver: Solves the Sudoku puzzle.
- Subset Sum Problem: Finds a subset that sums to a given value.
- Naive: Checks for the presence of a pattern in the text.
- KMP (Knuth-Morris-Pratt): Searches for a pattern using a partial match table.
- Rabin-Karp: Uses hashing to find a pattern.
- Uses a trie (prefix tree) for efficient string manipulation.
- Finds the longest substring common to two strings.
- Finds the longest substring that is a palindrome.
- Operations like AND, OR, XOR, NOT, bit shifts, etc.
- Efficient solutions using bitwise operations (e.g., checking power of two).
- Key concepts for writing recursive functions.
- Recursion where the recursive call is the last operation, allowing for optimization.