Top 50 DSA Interview Questions and Answers

DSA stands for Data Structures and Algorithms.

• Data Structures: Ways to organize and store data efficiently for particular operations.
• Algorithms: Step-by-step procedures or formulas for solving a problem or performing a computation.
• Together, DSA forms the backbone of efficient programming and problem-solving in computer science.

An algorithm is a well-defined, step-by-step procedure or set of rules to solve a specific problem or perform a task.

• It takes an input, processes it, and produces an output.
• Must be finite, unambiguous, and effective.
• Examples include sorting numbers, searching for an item, or finding the shortest path between two points.

A data structure is a specialized format for organizing and storing data in a computer so that it can be accessed and modified efficiently.

• It dictates the relationships between data items and the operations that can be performed on them.
• Examples include arrays, linked lists, trees, graphs, and hash tables.

Time complexity measures the amount of time an algorithm takes to run as a function of the length of its input.

• It quantifies the number of operations an algorithm performs, independent of the actual machine speed.
• Expressed using Big O notation, it describes the worst-case scenario or the upper bound of the growth rate.
• Helps compare the efficiency of different algorithms for the same problem.

Space complexity measures the amount of memory (space) an algorithm takes to run as a function of the length of its input.

• It accounts for the memory used by input, output, and auxiliary space required during execution.
• Also expressed using Big O notation, focusing on the worst-case memory usage.
• Important for algorithms running on systems with limited memory.

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. In DSA, it describes the worst-case or upper bound on the time or space complexity of an algorithm.

• Importance:
  • Performance Analysis: Allows developers to compare the efficiency of different algorithms in a standardized way.
  • Scalability Prediction: Helps predict how an algorithm will perform as the input size grows, independent of hardware or programming language.
  • Optimization: Guides in identifying bottlenecks and optimizing code for better performance.

Common Big O time complexities, ordered from most efficient to least efficient, are:

• O(1) - Constant time (e.g., accessing an array element by index).
• O(log n) - Logarithmic time (e.g., binary search).
• O(n) - Linear time (e.g., traversing a list).
• O(n log n) - Linearithmic time (e.g., efficient sorting algorithms like Merge Sort, Quick Sort).
• O(n^2) - Quadratic time (e.g., nested loops, Bubble Sort, Selection Sort).
• O(2^n) - Exponential time (e.g., recursive calculation of Fibonacci without memoization).
• O(n!) - Factorial time (e.g., solving the Traveling Salesperson Problem using brute force).

Analyzing recursive algorithms often involves setting up a recurrence relation and then solving it.

• Substitution Method: Guess a solution and prove it using mathematical induction.
• Recursion Tree Method: Draw a tree representing recursive calls, sum the costs at each level, and sum all levels.
• Master Theorem: A formulaic approach for solving recurrence relations of the form T(n) = aT(n/b) + f(n), where:
  • a >= 1 is the number of subproblems.
  • b > 1 is the factor by which the input size is divided.
  • f(n) is the cost of the work done outside the recursive calls (e.g., splitting/merging).

An array is a fundamental linear data structure that stores a fixed-size collection of elements of the same data type in contiguous memory locations.

• Indexed Access: Elements are accessed using an integer index, typically starting from 0.
• Homogeneous: All elements must be of the same data type.
• Fixed Size: The size of a traditional array is determined at creation time and cannot be changed during runtime (though dynamic arrays overcome this).

Arrays offer several trade-offs:

• Advantages:
  • Fast Access: O(1) time complexity for accessing any element using its index due to contiguous memory allocation.
  • Memory Locality: Good cache performance due to elements being stored close together.
  • Simple Implementation: Easy to understand and implement.
• Disadvantages:
  • Fixed Size: Cannot dynamically grow or shrink once declared (for static arrays).
  • Insertion/Deletion Costly: Inserting or deleting an element in the middle requires shifting subsequent elements, taking O(n) time.
  • Memory Waste: If allocated size is larger than needed, memory can be wasted. If smaller, overflow.

A dynamic array is implemented by using a static array internally and resizing it when it becomes full.

• Initialization: Start with a small, fixed-size underlying array.
• Adding Elements: When an element is added and the internal array is full:
  1. Create a new, larger array (typically double the current size).
  2. Copy all existing elements from the old array to the new array.
  3. Add the new element to the new array.
  4. The old array is then garbage collected.
• Amortized Analysis: While resizing is O(n), adding n elements typically results in an amortized O(1) time complexity for append operations due to infrequent resizes.

This can be solved efficiently using the Two-Pointer Technique for a sorted array.

• Approach:
  1. Initialize two pointers: left at the beginning of the array and right at the end.
  2. While left < right:
     • Calculate the current_sum = array[left] + array[right].
     • If current_sum == target, return (array[left], array[right]).
     • If current_sum < target, increment left (need a larger sum).
     • If current_sum > target, decrement right (need a smaller sum).
• Time Complexity: O(n) because each pointer traverses the array at most once.
• Space Complexity: O(1) as no extra space is used.

def find_sum_pair(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            return arr[left], arr[right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return None # No such pair found

A linked list is a linear data structure where elements are not stored in contiguous memory locations. Instead, each element (called a node) contains:

• The data itself.
• A pointer (or reference) to the next node in the sequence.
• The last node's pointer typically points to null (or None), indicating the end of the list.

The main differences lie in the number and direction of pointers in each node:

• Singly Linked List:
  • Each node points only to the next node.
  • Traversal is unidirectional (forward only).
  • Efficient for insertions/deletions at the beginning.
• Doubly Linked List:
  • Each node has two pointers: one to the next node and one to the previous node.
  • Traversal is bidirectional (forward and backward).
  • More memory overhead due to the extra pointer.
• Circular Linked List:
  • Can be singly or doubly linked.
  • The last node's pointer points back to the first node (head), forming a circle.
  • Useful for continuous loops (e.g., round-robin scheduling) or easily traversing the entire list from any point.

Linked lists and arrays have different strengths:

• Advantages of Linked Lists:
  • Dynamic Size: Can grow or shrink during runtime without explicit resizing logic.
  • Efficient Insertions/Deletions: O(1) time complexity if the insertion/deletion point is known (or O(n) to find it).
  • No Memory Waste: Allocates memory only as needed.
• Disadvantages of Linked Lists:
  • No Random Access: O(n) time to access an element by index, as you must traverse from the beginning.
  • More Memory: Each node requires extra memory for pointers.
  • Cache Performance: Poorer cache performance due to non-contiguous memory locations.

Reversing a singly linked list can be done iteratively or recursively. The iterative approach is generally preferred for avoiding recursion overhead.

• Iterative Approach:
  1. Initialize three pointers: prev (to None), current (to head), and next_node.
  2. Iterate while current is not None:
     • Store current.next in next_node to save the rest of the list.
     • Change current.next to prev (reversing the pointer).
     • Move prev to current.
     • Move current to next_node.
  3. The prev pointer will be the new head of the reversed list when the loop finishes.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def reverse_linked_list(head):
    prev = None
    current = head
    while current:
        next_node = current.next # Store next node
        current.next = prev      # Reverse current node's pointer
        prev = current           # Move prev to current node
        current = next_node      # Move current to next node
    return prev # New head of the reversed list

The most common and efficient method is Floyd's Tortoise and Hare algorithm (also known as the cycle-finding algorithm).

• Approach:
  1. Initialize two pointers, slow and fast, both starting at the head.
  2. slow moves one step at a time (slow = slow.next).
  3. fast moves two steps at a time (fast = fast.next.next).
  4. If there's a cycle, fast will eventually catch up to slow (i.e., fast == slow).
  5. If fast reaches the end of the list (fast is None or fast.next is None), there is no cycle.
• Time Complexity: O(n).
• Space Complexity: O(1).

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def detect_cycle(head):
    if not head or not head.next:
        return False
    
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True # Cycle detected
    return False # No cycle

A Stack is a linear data structure that follows the LIFO (Last In, First Out) principle.

• LIFO Principle: The element that was most recently added is the first one to be removed.
• Imagine a stack of plates: the last plate placed on top is the first one taken off.
• Common operations are push (add an element) and pop (remove an element), both occurring at the top of the stack.

The primary operations on a Stack, typically performed in O(1) time, are:

• push(element): Adds an element to the top of the stack.
• pop(): Removes and returns the element from the top of the stack. An error occurs if the stack is empty.
• peek() (or top()): Returns the element at the top of the stack without removing it. An error occurs if the stack is empty.
• isEmpty(): Checks if the stack is empty, returning True or False.

A Queue is a linear data structure that follows the FIFO (First In, First Out) principle.

• FIFO Principle: The element that was added first is the first one to be removed.
• Imagine a line of people waiting: the first person in line is the first one served.
• Elements are added at the rear (or tail) and removed from the front (or head) of the queue.

The primary operations on a Queue, typically performed in O(1) time, are:

• enqueue(element): Adds an element to the rear of the queue.
• dequeue(): Removes and returns the element from the front of the queue. An error occurs if the queue is empty.
• front() (or peek()): Returns the element at the front of the queue without removing it. An error occurs if the queue is empty.
• isEmpty(): Checks if the queue is empty, returning True or False.

A Stack can be implemented using two queues, q1 and q2, by ensuring that the most recently added element is always at the front of one queue.

• push(x) operation:
  1. Add x to q2.
  2. Move all elements from q1 to q2.
  3. Swap the names q1 and q2 (effectively, q1 now contains x followed by the old elements in LIFO order). This makes push O(n) as elements are moved.
• pop() operation:
  1. Simply dequeue() from q1. This makes pop O(1).

Alternatively, push can be O(1) and pop O(n) by emptying n-1 elements from q1 to q2 before dequeuing the last one.

A Queue can be implemented using two stacks, stack1 (for enqueuing) and stack2 (for dequeuing).

• enqueue(x) operation:
  1. push x onto stack1. This is an O(1) operation.
• dequeue() operation:
  1. If stack2 is empty, transfer all elements from stack1 to stack2 by repeatedly popping from stack1 and pushing onto stack2.
  2. Then, pop the top element from stack2. *This dequeue operation is O(1) amortized, because elements are moved between stacks only when stack2 is empty, and each element is moved at most twice.

A Hash Table (or Hash Map) is a data structure that stores key-value pairs. It provides efficient retrieval of values by computing an index (called a hash) into an array of buckets or slots, from which the desired value can be found.

• Key Idea: Map keys to array indices using a hash function.
• Average O(1) Operations: Insertion, deletion, and search operations are typically O(1) on average, making them very fast.

A hash function is a function that takes an input (or 'key') and returns a fixed-size integer value (a 'hash code' or 'hash value').

• Purpose: To map keys to indices in a hash table's underlying array.
• Properties of a Good Hash Function:
  • Deterministic: The same key always produces the same hash value.
  • Fast Computation: Should be quick to compute.
  • Uniform Distribution: Distributes keys as evenly as possible across the hash table's indices to minimize collisions.
  • Low Collision Rate: Minimizes the chance of different keys producing the same hash value.

A collision occurs in a hash table when two different keys map to the same index (or 'bucket') after being processed by the hash function.

• Collision Resolution Strategies:
  • Chaining: Each bucket in the hash table array stores a reference to a linked list (or another data structure) of all key-value pairs that hash to that index. When a collision occurs, the new key-value pair is simply added to the linked list at that index.
  • Open Addressing: If a collision occurs, the algorithm probes (searches) for the next available empty slot in the array. Common probing methods include:
    • Linear Probing: Searches sequentially (index+1, index+2, etc.).
    • Quadratic Probing: Searches by squares (index+1^2, index+2^2, etc.).
    • Double Hashing: Uses a second hash function to determine the step size for probing.

Hash tables offer powerful trade-offs:

• Advantages:
  • Fast Operations: Average O(1) time complexity for insert, delete, and search operations.
  • Efficient Lookups: Very efficient for exact match lookups.
  • Flexible Keys: Can use various data types as keys (strings, objects, etc.).
• Disadvantages:
  • Worst-Case Performance: In the worst-case (e.g., all keys hash to the same bucket due to a poor hash function or many collisions), operations can degrade to O(n).
  • Space Overhead: May require more space than other data structures, especially with chaining.
  • No Ordered Traversal: Elements are not stored in any particular order, so ordered traversal is not efficient.
  • Rehashing Cost: Resizing (rehashing) can be an expensive O(n) operation.

A Tree is a non-linear, hierarchical data structure that consists of nodes connected by edges.

• Root: The topmost node, with no parent.
• Parent/Child: A node directly above another is its parent; the node directly below is its child.
• Siblings: Nodes with the same parent.
• Leaf Node: A node with no children.
• Edge: The link connecting two nodes.
• Subtree: Any node and all of its descendants.
• Acyclic: There are no cycles or loops in a tree.

A Binary Tree is a special type of tree where each node can have at most two children: a left child and a right child.

• Key Property: The order of children matters (left vs. right).
• Types of Binary Trees:
  • Full Binary Tree: Every node has either 0 or 2 children.
  • Complete Binary Tree: All levels are completely filled except possibly the last level, which is filled from left to right.
  • Perfect Binary Tree: All internal nodes have two children, and all leaf nodes are at the same level.
  • Balanced Binary Tree: The heights of the left and right subtrees of any node differ by at most 1.

A Binary Search Tree (BST) is a binary tree with a specific ordering property that allows for efficient search, insertion, and deletion operations.

• BST Property:
  • For any given node, all values in its left subtree are less than the node's value.
  • For any given node, all values in its right subtree are greater than the node's value.
  • Both the left and right subtrees must also be BSTs.
• Average Time Complexity: O(log n) for search, insert, and delete in a balanced BST. O(n) in the worst case (skewed tree).

Tree traversal refers to the process of visiting each node in a tree exactly once. Common methods for binary trees include:

• Depth-First Traversals:
  • In-order (Left -> Root -> Right): Visits the left subtree, then the root, then the right subtree. Produces sorted output for a BST.
  • Pre-order (Root -> Left -> Right): Visits the root, then the left subtree, then the right subtree. Useful for copying a tree or prefix expressions.
  • Post-order (Left -> Right -> Root): Visits the left subtree, then the right subtree, then the root. Useful for deleting a tree or postfix expressions.
• Breadth-First Traversal:
  • Level-order (Level by Level): Visits nodes level by level from top to bottom, and left to right within each level. Typically implemented using a queue.

# In-order traversal example
def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.data) # Visit root
        inorder_traversal(node.right)

BFS (Breadth-First Search) on a tree visits nodes level by level, starting from the root. It uses a queue data structure to keep track of nodes to visit.

• Steps:
  1. Create an empty queue and enqueue the root node.
  2. While the queue is not empty:
     • Dequeue a node current_node.
     • Process current_node (e.g., print its value).
     • Enqueue current_node's left child (if it exists).
     • Enqueue current_node's right child (if it exists).
• Time Complexity: O(N), where N is the number of nodes (each node visited once).
• Space Complexity: O(W) where W is the maximum width of the tree (number of nodes at the widest level), which can be O(N) in the worst case.

from collections import deque

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def bfs_tree(root):
    if not root:
        return

    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.val, end=" ")

        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

DFS (Depth-First Search) on a tree explores as far as possible along each branch before backtracking. It can be implemented using recursion (implicit stack) or an explicit stack data structure.

• Recursive (Pre-order example):
  1. Process the current node.
  2. Recursively call DFS on the left child.
  3. Recursively call DFS on the right child.
• Iterative (using a stack):
  1. Create an empty stack and push the root node.
  2. While the stack is not empty:
     • Pop a node current_node.
     • Process current_node.
     • Push current_node's right child (if it exists).
     • Push current_node's left child (if it exists). Left child is pushed last so it's processed first (LIFO).
• Time Complexity: O(N).
• Space Complexity: O(H), where H is the height of the tree (for recursion stack or explicit stack), which can be O(N) in the worst case (skewed tree).

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def dfs_preorder_recursive(node):
    if node:
        print(node.val, end=" ") # Process node
        dfs_preorder_recursive(node.left)
        dfs_preorder_recursive(node.right)

def dfs_preorder_iterative(root):
    if not root:
        return
    
    stack = [root]
    while stack:
        node = stack.pop()
        print(node.val, end=" ")
        if node.right: # Push right first so left is processed first (LIFO)
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

BFS and DFS are two primary graph (and tree) traversal algorithms, differing in their exploration strategy:

• BFS (Breadth-First Search):
  • Strategy: Explores level by level, visiting all neighbors at the current depth before moving to the next depth.
  • Data Structure: Uses a Queue.
  • Applications: Shortest path in unweighted graphs, finding all nodes within a certain distance, web crawlers, social network analysis.
• DFS (Depth-First Search):
  • Strategy: Explores as deeply as possible along each branch before backtracking.
  • Data Structure: Uses a Stack (explicit or implicit via recursion).
  • Applications: Cycle detection, topological sorting, finding connected components, pathfinding (not necessarily shortest), solving puzzles with one solution (e.g., mazes).

A Heap is a special tree-based data structure that satisfies the heap property.

• It is typically implemented as a complete binary tree, meaning all levels are fully filled except possibly the last one, and nodes are filled from left to right.
• Heap Property:
  • Min-Heap: For every node i other than the root, the value of i is greater than or equal to the value of its parent p (value(i) >= value(p)). The smallest element is always at the root.
  • Max-Heap: For every node i other than the root, the value of i is less than or equal to the value of its parent p (value(i) <= value(p)). The largest element is always at the root.

Heaps are most commonly implemented using an array or a list.

• Array Representation: Due to the complete binary tree property, nodes can be mapped to array indices without explicit pointers:
  • If a node is at index i:
    • Its parent is at index (i-1) // 2 (integer division).
    • Its left child is at index 2*i + 1.
    • Its right child is at index 2*i + 2.
• This array-based implementation is very space-efficient and allows O(1) access to parent/children, making heap operations (insertion, deletion) efficient at O(log n).

A Priority Queue is an abstract data type (ADT) that is similar to a regular queue, but each element has an associated 'priority'.

• Key Operations:
  • insert(element, priority): Adds an element with a given priority.
  • extractMin() (or extractMax()): Removes and returns the element with the highest (or lowest) priority.
• Relationship to Heaps: Heaps are the most common and efficient data structure used to implement a priority queue.
  • A Min-Heap is used for priority queues that always extract the minimum element.
  • A Max-Heap is used for priority queues that always extract the maximum element.
  • Heap-based priority queues provide O(log n) time complexity for insert and extractMin/Max operations.

A Graph is a non-linear data structure consisting of a finite set of vertices (or nodes) and a set of edges that connect pairs of vertices.

• Vertices (Nodes): The fundamental entities in a graph.
• Edges: Connections between vertices.
• Graphs can represent various real-world scenarios, such as social networks, road maps, or computer networks.

The distinction lies in the directionality of the edges:

• Undirected Graph:
  • Edges have no direction. If an edge connects vertex A and vertex B, it means A is connected to B, and B is connected to A symmetrically.
  • Represented as a pair (u, v).
  • Example: Friendships on Facebook (if A is friend with B, B is friend with A).
• Directed Graph (Digraph):
  • Edges have a direction. An edge from vertex A to vertex B (A -> B) means there is a connection from A to B, but not necessarily from B to A.
  • Represented as an ordered pair <u, v>.
  • Example: Following relationships on Twitter (A follows B doesn't mean B follows A).

The difference is whether edges have associated costs or values:

• Unweighted Graph:
  • Edges do not have any associated numerical value or cost.
  • All edges are considered to have the same 'cost' (e.g., 1 unit).
  • Useful for problems like finding the shortest path in terms of number of edges (e.g., BFS).
• Weighted Graph:
  • Edges do have an associated numerical value or 'weight', representing cost, distance, time, capacity, etc.
  • Useful for problems like finding the shortest path in terms of total cost (e.g., Dijkstra's algorithm, Prim's algorithm).
  • Example: A road map where weights represent distances or travel times between cities.

Two common ways to represent graphs in memory are:

• Adjacency Matrix:
  • Uses a V x V 2D array (where V is the number of vertices).
  • matrix[i][j] = 1 (or weight w) if an edge exists from i to j, otherwise 0 (or infinity).
  • Pros: O(1) check for edge existence, simple to implement for dense graphs.
  • Cons: O(V^2) space complexity (inefficient for sparse graphs), O(V^2) to add/remove vertices, O(V) to iterate over neighbors.
• Adjacency List:
  • Uses an array or hash map where each index (or key) represents a vertex.
  • Each vertex's entry stores a list (e.g., linked list, dynamic array) of its adjacent vertices (and edge weights, if weighted).
  • Pros: O(V+E) space complexity (more efficient for sparse graphs), O(degree(V)) to iterate over neighbors.
  • Cons: O(degree(V)) to check for edge existence.

# Adjacency List example for an undirected graph
graph_adj_list = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

# Adjacency Matrix example for an undirected graph (4 vertices)
#   A B C D
# A 0 1 1 0
# B 1 0 0 1
# C 1 0 0 1
# D 0 1 1 0
graph_adj_matrix = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 1],
    [0, 1, 1, 0]
]

The choice between BFS and DFS depends on the problem requirements:

• Use BFS (Queue-based) when:
  • You need to find the shortest path in an unweighted graph (BFS explores layer by layer, naturally finding the path with the fewest edges).
  • You need to find all nodes at a certain minimum depth from a source node.
  • Problems like finding connected components, detecting cycles (sometimes), or network broadcasting.
• Use DFS (Stack-based / Recursive) when:
  • You need to explore all paths from a source or deeply into a graph.
  • Problems like topological sorting, finding strongly connected components, or detecting cycles.
  • When the graph is very deep and wide, and you need to prioritize depth over breadth.
  • Solving puzzles where you need to find any path to a solution (e.g., maze solving).

Dijkstra's Algorithm is a popular greedy algorithm used to find the shortest paths from a single source vertex to all other vertices in a weighted graph with non-negative edge weights.

• Purpose: To determine the path with the minimum total weight (cost/distance) from a starting node to every other reachable node.
• How it works:
  1. Maintains a set of visited vertices and a set of unvisited vertices.
  2. Assigns a distance value to every vertex (0 for source, infinity for others).
  3. Repeatedly selects the unvisited vertex with the smallest known distance from the source.
  4. Updates the distances of its neighbors through the current vertex.
• Data Structure: Typically uses a min-priority queue to efficiently extract the vertex with the smallest distance.
• Time Complexity: O((V+E) log V) with a binary heap, or O(E log V) if E is small relative to V^2.

Bubble Sort is a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

• Process: Larger elements

Binary Search is an efficient algorithm for finding an item in a sorted array or list by repeatedly dividing the search interval in half.

• How it works:

  1. Compare the target value to the middle element of the array.
  2. If they match, return the index.
  3. If the target is smaller, repeat the search on the left half.
  4. If the target is larger, repeat the search on the right half.
  5. Repeat until the element is found or the interval is empty.

• Precondition: The input array must be sorted beforehand.

• Time Complexity: O(log n) - because the search space is halved on every comparison, making it vastly faster than a linear scan (O(n)) for large datasets.

• Space Complexity: O(1) for the iterative version, or O(log n) for the recursive version due to the call stack.

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Merge Sort is a highly efficient, comparison-based, divide-and-conquer sorting algorithm.

• Mechanism:
  1. Divide: It recursively divides the unsorted list into two halves until it has n sublists, each containing one element (which is considered sorted).
  2. Conquer/Merge: It then repeatedly merges these sublists to produce new sorted sublists until there is only one sorted list remaining.
• Time Complexity:
  • Worst-case: O(n log n).
  • Average-case: O(n log n).
  • Best-case: O(n log n).
• Space Complexity: O(n) due to the temporary arrays created during the merge step.
• It is a stable sort and well-suited for external sorting.

Quick Sort is an efficient, comparison-based, divide-and-conquer sorting algorithm that uses a pivot element.

• Mechanism:
  1. Choose Pivot: Select an element from the array as the 'pivot' (e.g., first, last, middle, or random).
  2. Partition: Rearrange the array such that all elements smaller than the pivot come before it, and all greater elements come after it. The pivot is now in its final sorted position.
  3. Recurse: Recursively apply Quick Sort to the sub-array of elements smaller than the pivot and separately to the sub-array of elements greater than the pivot.
• Time Complexity:
  • Worst-case: O(n^2) (occurs when the pivot selection consistently leads to highly unbalanced partitions, e.g., already sorted array with first/last element as pivot).
  • Average-case: O(n log n).
  • Best-case: O(n log n).
• Space Complexity: O(log n) on average for recursion stack, O(n) in worst-case.
• It is an in-place sort, generally faster in practice than Merge Sort due to better constant factors.

The choice between Merge Sort and Quick Sort depends on specific requirements and constraints:

• Choose Merge Sort when:
  • Stability is required: Merge Sort is a stable sorting algorithm (maintains the relative order of equal elements).
  • Worst-case performance is critical: It guarantees O(n log n) performance, unlike Quick Sort's worst-case O(n^2).
  • External sorting is needed: Suitable for large datasets that don't fit into memory because it works well with sequential access.
  • Linked Lists are involved: Efficiently sorts linked lists without extra space for pointers.
• Choose Quick Sort when:
  • Average-case performance is the primary concern: Generally faster in practice than Merge Sort due to smaller constant factors.
  • In-place sorting is preferred: Requires less auxiliary space (O(log n) average) than Merge Sort (O(n)).
  • Memory hierarchy is important: Often performs better with cache due to its locality of reference.

Dynamic Programming (DP) is an algorithmic technique for solving complex problems by breaking them down into smaller, simpler subproblems. It typically involves two key characteristics:

• Optimal Substructure: An optimal solution to the problem can be constructed from optimal solutions of its subproblems.
• Overlapping Subproblems: The same subproblems are encountered multiple times when solving the larger problem.
• Mechanism: DP solves each subproblem only once and stores their solutions (often in a table/array) to avoid recomputing them. This is called memoization (top-down) or tabulation (bottom-up).
• Example: Fibonacci Sequence F(n) = F(n-1) + F(n-2)
  • A naive recursive solution recomputes F(k) multiple times.
  • DP solution stores F(k) values as they are computed, allowing O(1) lookup for subsequent calls, reducing complexity from exponential to O(n).

# Dynamic Programming (Memoization/Top-Down) for Fibonacci
memo = {}
def fib_dp(n):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib_dp(n-1) + fib_dp(n-2)
    return memo[n]

# Dynamic Programming (Tabulation/Bottom-Up) for Fibonacci
def fib_tab(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Recursion is a programming technique where a function calls itself, either directly or indirectly, to solve a problem.

• Base Case: Every recursive function must have one or more base cases (terminating conditions) that do not involve further recursion, to prevent infinite loops.
• Recursive Step: The function calls itself with a smaller or simpler version of the original problem, moving closer to the base case.
• When to Use It:
  • When the problem can be broken down into identical subproblems.
  • When the problem's definition is inherently recursive (e.g., tree traversals, fractal generation, factorial calculation).
  • When it leads to a more elegant and readable solution, even if an iterative approach is possible.
  • Examples: Traversing trees/graphs (DFS), calculating factorials, generating permutations/combinations.