- Time Complexity: Measures the amount of time an algorithm takes to run, relative to the input size. It is usually expressed using Big O notation.
- Space Complexity: Measures the amount of memory an algorithm uses relative to the input size.
- Big O: Upper bound of the running time (worst-case scenario).
- Big Omega: Lower bound of the running time (best-case scenario).
- Big Theta: Tight bound, when the upper and lower bounds are the same.
- Recursion: A function that calls itself to solve a smaller instance of the same problem.
- Base Case: The condition that stops the recursion, preventing infinite loops.
- Recursive Case: The part of the function that calls itself with a smaller input.
- Pointers: Variables that store memory addresses.
- Dynamic Memory Allocation: Using
newanddeletein C++ to allocate and deallocate memory at runtime. - Memory Leaks: Occur when memory is allocated but not deallocated, leading to memory inefficiency.
- Templates: Allow functions and classes to operate with generic types.
- Type Flexibility: Enables code reusability across different data types without modification.
- Store elements in a linear sequence.
- Store elements in a grid-like structure (e.g., 2D arrays).
- Resizable arrays that automatically manage their own memory.
- Each node points to the next node.
- Each node points to both the previous and next nodes.
- The last node points back to the first node, forming a loop.
- Use a fixed-size array with a top pointer.
- Use a linked list with operations at the head.
- Expression evaluation, function calls, undo mechanisms.
- FIFO (First-In-First-Out) data structure.
- Optimizes space by wrapping around the array.
- Elements are dequeued in order of priority.
- Allows insertion and deletion from both ends.
- Use a hash function to map keys to indices in an array.
- Techniques like chaining (linked lists) and open addressing (linear probing).
- C++ standard library hash table implementation.
- Each node has up to two children.
- Left child < Parent < Right child.
- Self-balancing BST with a balance factor.
- Self-balancing BST with coloring properties.
- Efficient for range queries and updates.
- Parent is less than or equal to children.
- Parent is greater than or equal to children.
- C++ standard library heap implementation.
- A 2D array representing graph connections.
- A list of lists representing graph connections.
- Edges have a direction.
- Edges have no direction.
- Edges have associated weights.
- Union-Find data structure for managing disjoint sets.
- Arrays of characters terminated by a null character.
- C++ standard string class with dynamic resizing.
- Algorithms like KMP and Rabin-Karp for efficient string searching.
- Repeatedly swaps adjacent elements if they are in the wrong order. O(n²) time.
- Selects the smallest element and places it at the beginning. O(n²) time.
- Builds the final sorted array one item at a time. O(n²) time.
- Divides the array into halves, sorts them, and merges them. O(n log n) time.
- Chooses a pivot and partitions the array around it. O(n log n) average time.
- Uses a heap to repeatedly extract the maximum element. O(n log n) time.
- Non-comparison based sort, efficient for limited range of integers. O(n + k) time, where k is the range.
- Checks each element one by one. O(n) time.
- Divides the search interval in half. O(log n) time for sorted data.
- Divides the search interval into thirds. O(log n) time for sorted data.
- Divides the array into halves, sorts them, and merges them.
- Partitions the array around a pivot and sorts the partitions.
- Divides the search space in half at each step.
- Stores the results of expensive function calls and returns the cached result when the same inputs occur again.
- Solves the problem iteratively, filling a table (array) from the bottom up.
- Select items to maximize value without exceeding capacity.
- Finds the longest subsequence common to all sequences.
- Selects the maximum number of non-overlapping activities.
- Builds an optimal prefix code for compressing data.
- Kruskal's and Prim's algorithms find the MST of a graph.
- Places N queens on an N×N board without attacking each other.
- Fills the grid following the Sudoku rules.
- Finds a cycle that visits each vertex exactly once.
- Traverses the graph level by level.
- Traverses the graph as far as possible along each branch.
- Finds the shortest path from a source to all other vertices in a graph with non-negative weights.
- Computes the shortest paths between all pairs of vertices.
- Finds the shortest path from a source to all other vertices, handling negative weights.
- Finds the MST using a greedy approach with Union-Find.
- Finds the MST using a greedy approach with a priority queue.
- Useful for swapping variables and checking parity.
- Use bits to represent flags or sets.
- Use bits to represent subsets of a set.
- Counts the number of 1s in the binary representation of a number.
- Uses two pointers to traverse arrays or lists efficiently.
- Maintains a window of elements for efficient computation.
- Computes powers efficiently using exponentiation by squaring.
- Orders vertices in a DAG (Directed Acyclic Graph) such that for every directed edge uv, u comes before v.
- Efficient for storing and searching strings with common prefixes.
- Platforms where you can practice coding problems and participate in contests.
- Participate in programming contests to improve problem-solving skills.
- Learn common coding patterns and techniques used in solving problems.
- Focus on mastering algorithms, data structures, and problem-solving techniques for interviews.
- Use tools like debuggers, print statements, and unit tests to find and fix errors.
- Improve algorithm efficiency by reducing time and space complexity.