DSA Interview Questions & Answers | Preplance

Mobile App Now Available

Master Interviews
Anywhere, Anytime

Get the Preplance app for a seamless learning experience. Practice offline, get daily streaks, and stay ahead with real-time interview updates.

Get it on

Google Play

4.9/5 Rating on Store

9. What is a Data Structure? Explain the difference between linear and non-linear data structures with examples.

Difficulty: EasyType: SubjectiveTopic: Data Structure Types

A data structure is a specialized format for organizing, storing, and manipulating data in a computer's memory. It defines the relationship between data elements and the operations that can be performed on them. Data structures enable efficient access and modification of data, which is crucial for writing optimized programs. Linear data structures arrange elements in a sequential manner where each element has a predecessor and successor, except for the first and last elements. Elements are stored in a contiguous or linked manner, and you can traverse all elements in a single run. Examples include arrays where elements are stored in consecutive memory locations, linked lists where nodes are connected via pointers, stacks that follow Last In First Out principle, and queues that follow First In First Out principle. Non-linear data structures organize elements in a hierarchical or interconnected manner where one element can be connected to multiple elements. Elements are not arranged sequentially, and you cannot traverse all elements in a single run. Examples include trees which are hierarchical structures with parent-child relationships like binary trees and binary search trees, graphs which consist of vertices connected by edges representing complex relationships, heaps which are complete binary trees used for priority queues, and tries which are tree-like structures for efficient string retrieval. The choice between linear and non-linear structures depends on the application. Linear structures are simpler and efficient for sequential access, while non-linear structures are better for representing hierarchical or network relationships and enable more complex operations.

Example Code

// Linear Data Structure - Array
int[] linearArray = {1, 2, 3, 4, 5};
// Sequential access: arr[0], arr[1], arr[2]...

// Linear Data Structure - Linked List
class Node {
    int data;
    Node next;
}
// Sequential: node1 -> node2 -> node3 -> node4

// Non-Linear Data Structure - Binary Tree
class TreeNode {
    int data;
    TreeNode left, right;
}
//       1
//      / \
//     2   3
//    / \
//   4   5
// Hierarchical structure, not sequential

10. Explain the differences between arrays and linked lists. When would you choose one over the other?

Difficulty: MediumType: SubjectiveTopic: Array vs Linked List

Arrays and linked lists are both linear data structures, but they differ fundamentally in how they store and access elements. Arrays store elements in contiguous memory locations, allowing direct access to any element using its index in O of 1 time. The size is fixed at creation, making insertion and deletion expensive operations requiring shifting of elements, with time complexity of O of n. Arrays use less memory per element as they only store data, and they provide better cache locality due to contiguous storage. Linked lists store elements as nodes scattered in memory, with each node containing data and a pointer to the next node. Access to elements requires traversal from the head, taking O of n time. The size is dynamic and can grow or shrink as needed. Insertion and deletion are efficient at O of 1 if you have a reference to the position, requiring only pointer updates. However, linked lists use more memory per element due to storing pointers, and they have poor cache locality. Choose arrays when you need fast random access by index, when the size is known beforehand and does not change frequently, when memory efficiency is critical as arrays have less overhead, and when you need to perform many read operations compared to insertions and deletions. Arrays are ideal for implementing other data structures like heaps and hash tables, and for scenarios requiring sorted data with binary search. Choose linked lists when the size is unknown or changes frequently, when you need frequent insertions and deletions especially at the beginning or middle, when you do not need random access to elements, and when implementing data structures like stacks, queues, and graphs. Linked lists are better when memory is fragmented and contiguous allocation is difficult.

Example Code

// Array - Fixed size, contiguous memory
int[] array = new int[5];
array[2] = 10;  // O(1) access by index

// Insertion requires shifting - O(n)
for (int i = size; i > pos; i--) {
    array[i] = array[i-1];
}
array[pos] = newValue;

// Linked List - Dynamic size, scattered memory
class Node {
    int data;
    Node next;
}

// Access requires traversal - O(n)
Node current = head;
while (current != null) {
    if (current.data == target) break;
    current = current.next;
}

// Insertion at position - O(1) with reference
Node newNode = new Node(value);
newNode.next = current.next;
current.next = newNode;

11. What is a stack data structure? Explain its operations and provide real-world applications.

Difficulty: MediumType: SubjectiveTopic: Stack Implementation

A stack is a linear data structure that follows the Last In First Out principle, meaning the last element added is the first one to be removed. Think of it like a stack of plates where you can only add or remove plates from the top. The fundamental operations of a stack are push which adds an element to the top with O of 1 time complexity, pop which removes and returns the top element with O of 1 complexity, peek or top which returns the top element without removing it in O of 1 time, isEmpty which checks if the stack is empty, and size which returns the number of elements. All these operations work only at one end called the top of the stack. Stacks can be implemented using arrays with a fixed size where we maintain a top pointer, or using linked lists which provide dynamic size by adding and removing nodes at the head. The array implementation is simple and provides fast access, but has size limitations. The linked list implementation offers dynamic sizing but uses extra memory for pointers. Real-world applications of stacks are numerous. In function call management, the call stack maintains execution contexts for nested and recursive function calls. For expression evaluation, stacks convert infix expressions to postfix or prefix notation and evaluate postfix expressions efficiently. In undo and redo operations, applications like text editors use stacks to track states. For syntax parsing, compilers use stacks to check balanced parentheses, brackets, and braces in code. In backtracking algorithms, stacks store decision points in problems like maze solving and the N-Queens puzzle. Web browsers use stacks to implement the back button functionality by storing visited pages.

Example Code

// Stack implementation using array
class Stack {
    private int[] arr;
    private int top;
    private int capacity;
    
    Stack(int size) {
        arr = new int[size];
        capacity = size;
        top = -1;
    }
    
    void push(int value) {
        if (top == capacity - 1) {
            System.out.println("Stack Overflow");
            return;
        }
        arr[++top] = value;
    }
    
    int pop() {
        if (isEmpty()) {
            System.out.println("Stack Underflow");
            return -1;
        }
        return arr[top--];
    }
    
    int peek() {
        if (isEmpty()) return -1;
        return arr[top];
    }
    
    boolean isEmpty() {
        return top == -1;
    }
}

// Application: Balanced Parentheses
boolean isBalanced(String str) {
    Stack<Character> stack = new Stack<>();
    for (char c : str.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else if (c == ')' || c == '}' || c == ']') {
            if (stack.isEmpty()) return false;
            char top = stack.pop();
            if (!isMatchingPair(top, c)) return false;
        }
    }
    return stack.isEmpty();
}

12. Explain the queue data structure, its operations, and compare it with a stack. Provide use cases for each.

Difficulty: MediumType: SubjectiveTopic: Queue Operations

A queue is a linear data structure that follows the First In First Out principle, meaning the first element added is the first one to be removed. It operates like a real-world queue or line where people are served in the order they arrive. The fundamental operations of a queue are enqueue which adds an element to the rear end with O of 1 time complexity, dequeue which removes and returns the element from the front in O of 1 time, front or peek which returns the front element without removing it, rear which returns the last element, isEmpty which checks if the queue is empty, and size which returns the number of elements. Operations happen at two different ends unlike stacks where all operations occur at one end. Queues can be implemented using arrays which provide fast access but have fixed size, using linked lists which offer dynamic size and efficient enqueue and dequeue operations, or using circular arrays which efficiently utilize space by wrapping around when reaching the end. The key difference between stack and queue is the order of element removal. Stacks use Last In First Out where the most recently added element is removed first, like a stack of books. Queues use First In First Out where the oldest element is removed first, like a waiting line. Stacks have one access point called top, while queues have two points called front and rear. Use cases for stacks include function call management in recursion, undo and redo operations, expression evaluation and syntax parsing, backtracking in algorithms, and browser back button functionality. Use cases for queues include CPU and disk scheduling in operating systems, handling asynchronous data transfer like IO buffers and pipes, breadth-first search traversal in graphs and trees, printer job scheduling where documents are printed in order received, and call center systems where calls are answered in order they arrive.

Example Code

// Queue implementation using linked list
class Queue {
    class Node {
        int data;
        Node next;
        Node(int data) { this.data = data; }
    }
    
    private Node front, rear;
    
    void enqueue(int value) {
        Node newNode = new Node(value);
        if (rear == null) {
            front = rear = newNode;
            return;
        }
        rear.next = newNode;
        rear = newNode;
    }
    
    int dequeue() {
        if (front == null) {
            System.out.println("Queue is empty");
            return -1;
        }
        int value = front.data;
        front = front.next;
        if (front == null) rear = null;
        return value;
    }
    
    int peek() {
        if (front == null) return -1;
        return front.data;
    }
    
    boolean isEmpty() {
        return front == null;
    }
}

// Stack vs Queue comparison
Stack: push(1), push(2), push(3), pop() -> 3 (LIFO)
Queue: enqueue(1), enqueue(2), enqueue(3), dequeue() -> 1 (FIFO)

13. What is algorithm analysis? Explain time complexity and space complexity with examples.

Difficulty: MediumType: SubjectiveTopic: Algorithm Analysis

Algorithm analysis is the process of determining the computational complexity of algorithms, measuring how their time and space requirements grow as the input size increases. This helps us compare different algorithms and choose the most efficient one for a given problem. Time complexity measures the amount of time an algorithm takes to complete as a function of input size. It represents the number of basic operations executed. We express time complexity using Big O notation which describes the worst-case, upper bound on growth rate. Common time complexities from best to worst are O of 1 for constant time where execution time does not depend on input size, O of log n for logarithmic time like binary search, O of n for linear time like linear search, O of n log n for algorithms like merge sort and quick sort, O of n squared for nested loops like bubble sort, and O of 2 to the power n for exponential time like recursive Fibonacci. Space complexity measures the amount of memory an algorithm uses as a function of input size. It includes space for input data, temporary variables, and recursive call stack. For example, O of 1 space means using a fixed amount of memory regardless of input size, O of n space means memory grows linearly with input, and O of n squared space means memory grows quadratically. For example, linear search has time complexity O of n because in worst case it checks every element, and space complexity O of 1 because it uses only a few variables. Binary search has time complexity O of log n because it halves the search space each time, and space complexity O of 1 for iterative implementation or O of log n for recursive due to call stack. Merge sort has time complexity O of n log n for all cases because it divides array in half recursively and merges in linear time, and space complexity O of n for the temporary arrays used during merging.

Example Code

// Example 1: O(1) time, O(1) space
int getFirstElement(int[] arr) {
    return arr[0];  // Constant time, constant space
}

// Example 2: O(n) time, O(1) space
int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {  // Loop n times
        if (arr[i] == target) return i;
    }
    return -1;
}

// Example 3: O(log n) time, O(1) space
int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

// Example 4: O(n^2) time, O(1) space
void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// Example 5: O(n log n) time, O(n) space
void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);  // Uses O(n) extra space
    }
}

14. Explain different types of linked lists. How would you detect a cycle in a linked list?

Difficulty: HardType: SubjectiveTopic: Linked List Operations

A linked list is a linear data structure where elements called nodes are connected via pointers or references. Each node contains data and a reference to the next node, forming a chain-like structure. There are several types of linked lists. A singly linked list has nodes with data and a pointer to the next node only, allowing traversal in one direction from head to tail. A doubly linked list has nodes with data and two pointers, one to the next node and one to the previous node, allowing bidirectional traversal. A circular linked list has the last node pointing back to the first node instead of null, forming a circle. This can be singly or doubly circular. Advantages of linked lists include dynamic size that can grow or shrink at runtime, efficient insertion and deletion at O of 1 when you have a reference to the position, and no memory wastage as nodes are allocated only when needed. Disadvantages include no random access requiring O of n time to reach an element, extra memory for storing pointers in each node, and poor cache locality as nodes are scattered in memory. To detect a cycle in a linked list, the most efficient method is Floyd's Cycle Detection Algorithm, also called the tortoise and hare algorithm. Use two pointers, slow and fast, both starting at the head. Move slow pointer one step at a time and fast pointer two steps at a time. If there is a cycle, the fast pointer will eventually meet the slow pointer inside the cycle because the fast pointer gains one step on slow pointer in each iteration. If there is no cycle, the fast pointer will reach null. This algorithm has time complexity O of n where n is the number of nodes, and space complexity O of 1 as it uses only two pointers. Alternative methods include using a hash set to store visited nodes with O of n space, or modifying the linked list structure to mark visited nodes, but Floyd's algorithm is preferred for its constant space usage.

Example Code

// Singly Linked List Node
class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

// Doubly Linked List Node
class DNode {
    int data;
    DNode next, prev;
    DNode(int data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

// Floyd's Cycle Detection Algorithm
boolean hasCycle(Node head) {
    if (head == null) return false;
    
    Node slow = head;
    Node fast = head;
    
    while (fast != null && fast.next != null) {
        slow = slow.next;           // Move 1 step
        fast = fast.next.next;      // Move 2 steps
        
        if (slow == fast) {         // Cycle detected
            return true;
        }
    }
    
    return false;  // No cycle
}

// Time: O(n), Space: O(1)
// If cycle exists, fast catches slow in at most n steps
// If no cycle, fast reaches null in n/2 steps

15. Compare different sorting algorithms. When would you choose Quick Sort over Merge Sort?

Difficulty: HardType: SubjectiveTopic: Sorting Algorithms

Sorting algorithms arrange elements in a specific order, typically ascending or descending. Understanding their characteristics helps choose the right algorithm for different scenarios. Bubble sort repeatedly swaps adjacent elements if they are in wrong order, with time complexity O of n squared for average and worst cases and O of n for best case when array is already sorted. Space complexity is O of 1. It is simple but inefficient for large datasets and rarely used in practice. Selection sort finds the minimum element and places it at the beginning, repeating for remaining elements. Time complexity is O of n squared for all cases and space complexity is O of 1. It performs fewer swaps than bubble sort but still inefficient for large data. Insertion sort builds sorted array one element at a time by inserting each element into its correct position. Time complexity is O of n squared for average and worst cases, O of n for nearly sorted data, and space complexity is O of 1. It is efficient for small datasets and nearly sorted data, used in hybrid algorithms like TimSort. Merge sort divides array into halves recursively, sorts them, and merges sorted halves. Time complexity is O of n log n for all cases, guaranteed, and space complexity is O of n for temporary arrays. It is stable, predictable, and good for large datasets, but requires extra space. Quick sort selects a pivot, partitions array around it, and recursively sorts partitions. Time complexity is O of n log n average case, O of n squared worst case with bad pivot selection, and space complexity is O of log n for recursion stack. It is fastest in practice for most data and sorts in-place with less memory than merge sort, but not stable and worst case can be bad. Heap sort builds a max heap and repeatedly extracts maximum to build sorted array. Time complexity is O of n log n for all cases and space complexity is O of 1. It guarantees O of n log n and uses no extra space, but slower than quick sort in practice and not stable. Choose Quick Sort over Merge Sort when average-case performance matters more than worst-case, when memory is limited as quick sort uses O of log n space versus merge sort's O of n, when you need in-place sorting, when stability is not required, and for general-purpose sorting of random data. Choose Merge Sort when you need guaranteed O of n log n time complexity, when you need a stable sort preserving relative order of equal elements, when working with linked lists as merge sort works well without random access, and when extra space is available and acceptable.

Example Code

// Quick Sort - O(n log n) average, O(n^2) worst
void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr, i + 1, high);
    return i + 1;
}

// Merge Sort - O(n log n) always
void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

void merge(int[] arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int[] L = new int[n1];
    int[] R = new int[n2];
    
    // Copy data and merge sorted arrays
    // Requires O(n) extra space
}

// Choose Quick Sort: Random data, limited memory
// Choose Merge Sort: Need stability, guaranteed O(n log n)

23. Explain the different tree traversal techniques: In-order, Pre-order, and Post-order. Provide use cases for each.

Difficulty: MediumType: SubjectiveTopic: Tree Traversals

Tree traversal is the process of visiting all nodes in a tree data structure in a specific order. There are three main depth-first traversal techniques that differ in the order they visit the root node relative to its children. In-order traversal visits nodes in the order: left subtree, root, right subtree. For binary search trees, in-order traversal visits nodes in sorted ascending order, making it useful for retrieving sorted data. The algorithm recursively traverses the left subtree, processes the current node, then recursively traverses the right subtree. Time complexity is O of n and space complexity is O of h where h is tree height due to recursion stack. Pre-order traversal visits nodes in the order: root, left subtree, right subtree. This is useful for creating a copy of the tree, getting prefix expression of an expression tree, and serializing the tree structure. The root is processed before its children, so you see the hierarchical structure from top to bottom. It is commonly used in file system traversal where you want to process directories before their contents. Post-order traversal visits nodes in the order: left subtree, right subtree, root. This is useful for deleting a tree as you delete children before parents, evaluating postfix expressions in expression trees, and calculating directory sizes as you need child sizes before parent size. The root is processed last after all descendants have been processed. Level-order traversal, also called breadth-first traversal, visits nodes level by level from left to right using a queue. It is useful for finding the shortest path in unweighted trees, level-wise printing, and checking if a tree is complete. Time complexity is O of n and space complexity is O of w where w is maximum width of the tree. The choice of traversal depends on the problem requirements. Use in-order for BST operations requiring sorted order, pre-order for tree serialization and copying, post-order for deletion and cleanup operations, and level-order for breadth-first processing.

Example Code

class TreeNode {
    int data;
    TreeNode left, right;
}

// In-order: Left, Root, Right
void inOrder(TreeNode root) {
    if (root == null) return;
    inOrder(root.left);           // Visit left
    System.out.print(root.data);  // Process root
    inOrder(root.right);          // Visit right
}

// Pre-order: Root, Left, Right
void preOrder(TreeNode root) {
    if (root == null) return;
    System.out.print(root.data);  // Process root
    preOrder(root.left);          // Visit left
    preOrder(root.right);         // Visit right
}

// Post-order: Left, Right, Root
void postOrder(TreeNode root) {
    if (root == null) return;
    postOrder(root.left);         // Visit left
    postOrder(root.right);        // Visit right
    System.out.print(root.data);  // Process root
}

// Example tree:
//        1
//       / \
//      2   3
//     / \
//    4   5
// In-order: 4 2 5 1 3
// Pre-order: 1 2 4 5 3
// Post-order: 4 5 2 3 1

24. What is a Binary Search Tree? Explain its properties and the time complexity of its operations.

Difficulty: MediumType: SubjectiveTopic: Binary Search Tree

A Binary Search Tree is a binary tree with a specific ordering property: for every node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater than the node's value. This property makes BSTs efficient for search, insertion, and deletion operations. The key properties of a BST are that each node has at most two children called left and right, the left subtree of a node contains only values less than the node's value, the right subtree contains only values greater than the node's value, and both left and right subtrees must also be valid BSTs. This recursive property ensures the tree maintains its ordering throughout. Search operation starts at root and compares the target value with current node. If equal, we found the value. If target is less, search left subtree. If target is greater, search right subtree. Average time complexity is O of log n for balanced trees, worst case is O of n for skewed trees. Insertion follows the same path as search to find the correct position, then inserts the new node as a leaf. This maintains the BST property. Time complexity is O of log n average case, O of n worst case. Deletion has three cases. If the node has no children, simply remove it. If the node has one child, replace it with its child. If the node has two children, find the in-order successor which is the minimum value in right subtree or in-order predecessor which is maximum in left subtree, copy its value to the node being deleted, then delete the successor or predecessor. Time complexity is O of log n average, O of n worst case. The performance of BST operations depends heavily on tree balance. In the best case with a balanced tree, height is log n and operations are efficient. In the worst case with a skewed tree where nodes form a chain, height is n and operations degrade to linear time. This is why self-balancing trees like AVL and Red-Black trees are used to guarantee logarithmic performance.

Example Code

class BSTNode {
    int data;
    BSTNode left, right;
}

// Search - O(log n) average, O(n) worst
BSTNode search(BSTNode root, int key) {
    if (root == null || root.data == key)
        return root;
    if (key < root.data)
        return search(root.left, key);
    return search(root.right, key);
}

// Insert - O(log n) average, O(n) worst
BSTNode insert(BSTNode root, int key) {
    if (root == null)
        return new BSTNode(key);
    if (key < root.data)
        root.left = insert(root.left, key);
    else if (key > root.data)
        root.right = insert(root.right, key);
    return root;
}

// Example BST:
//        50
//       /  \
//      30   70
//     / \   / \
//    20 40 60 80
// Property: 20<30<40<50<60<70<80

// Balanced: height = log(n)
// Skewed (worst):
// 50
//  \
//   60
//    \
//     70  height = n

25. Explain how a min-heap works. How do you insert an element and extract the minimum element?

Difficulty: HardType: SubjectiveTopic: Heap Operations

A min-heap is a complete binary tree where the value of each node is less than or equal to the values of its children. The minimum element is always at the root, making min-heaps perfect for implementing priority queues. The heap property states that for any node i, the value at i is less than or equal to values at its children. This property must be maintained after every insertion and deletion. Heaps are typically implemented using arrays for space efficiency, with parent-child relationships calculated using index formulas. To insert an element, first add the new element at the end of the array to maintain the complete binary tree property. This may violate the heap property, so perform heapify-up also called bubble-up or percolate-up. Compare the new element with its parent. If the new element is smaller, swap them. Continue this process moving up the tree until the heap property is restored or you reach the root. Time complexity is O of log n as you traverse at most the height of the tree. To extract the minimum element, the minimum is always the root at index 0. Remove and return this element. Replace the root with the last element in the array to maintain completeness. This likely violates the heap property, so perform heapify-down also called bubble-down or percolate-down. Compare the new root with its children. Swap with the smaller child if the root is larger. Continue this process moving down the tree until the heap property is restored or you reach a leaf. Time complexity is O of log n. Heapify-up starts at the inserted position and moves toward the root. At each step, if current node is smaller than parent, swap and continue. Stop when current node is greater than or equal to parent or reach root. Heapify-down starts at the root and moves toward leaves. At each step, find the smallest among current node and its children. If current is not smallest, swap with the smallest child and continue. Stop when current is smallest or reach a leaf. Min-heaps are commonly used in Dijkstra's shortest path algorithm, heap sort, finding the k smallest elements efficiently, and implementing priority queues where tasks with lower priority values are processed first.

Example Code

class MinHeap {
    int[] heap;
    int size;
    int capacity;
    
    // Helper methods
    int parent(int i) { return (i - 1) / 2; }
    int left(int i) { return 2 * i + 1; }
    int right(int i) { return 2 * i + 2; }
    
    // Insert - O(log n)
    void insert(int value) {
        if (size == capacity) return;
        
        // Add at end
        heap[size] = value;
        int i = size++;
        
        // Heapify-up
        while (i > 0 && heap[parent(i)] > heap[i]) {
            swap(heap, i, parent(i));
            i = parent(i);
        }
    }
    
    // Extract Min - O(log n)
    int extractMin() {
        if (size == 0) return -1;
        
        int min = heap[0];
        heap[0] = heap[--size];  // Replace with last
        
        // Heapify-down
        int i = 0;
        while (left(i) < size) {
            int smallest = i;
            int l = left(i);
            int r = right(i);
            
            if (l < size && heap[l] < heap[smallest])
                smallest = l;
            if (r < size && heap[r] < heap[smallest])
                smallest = r;
            
            if (smallest == i) break;
            swap(heap, i, smallest);
            i = smallest;
        }
        
        return min;
    }
}

// Example:
// Insert 3, 2, 15, 5, 4, 45
//        2
//       / \
//      3   4
//     / \ /
//    5 15 45

26. Explain different ways to represent graphs in memory. Compare adjacency matrix and adjacency list.

Difficulty: MediumType: SubjectiveTopic: Graph Representations

Graphs can be represented in memory using two main methods: adjacency matrix and adjacency list. Each has different space and time trade-offs. An adjacency matrix is a 2D array of size V by V where V is the number of vertices. The cell at row i and column j contains 1 or true if there is an edge from vertex i to vertex j, and 0 or false otherwise. For weighted graphs, the cell contains the edge weight instead of 1. Space complexity is O of V squared which is inefficient for sparse graphs with few edges. Time complexity to check if an edge exists is O of 1 which is very fast, but adding or removing a vertex takes O of V squared time. It is suitable for dense graphs where the number of edges is close to V squared, when you need to quickly check if an edge exists between any two vertices, and when the graph is small. An adjacency list uses an array of lists where each index represents a vertex and contains a list of adjacent vertices. For vertex i, the list at index i contains all vertices that are directly connected to i. Space complexity is O of V plus E where E is the number of edges, which is much more efficient for sparse graphs. Time complexity to check if an edge exists is O of degree of v where degree is the number of adjacent vertices, which can be up to V in worst case. Adding a vertex is O of 1 and adding an edge is O of 1. It is suitable for sparse graphs with few edges, when you need to iterate over neighbors of vertices frequently, and when memory is limited. For undirected graphs, each edge appears twice in the adjacency list, once in each vertex's list. For directed graphs, an edge from u to v appears only in u's list. Weighted graphs can be represented by storing pairs of vertex and weight in the adjacency list. In practice, adjacency lists are more commonly used because most real-world graphs are sparse. Social networks, web graphs, and road networks typically have far fewer edges than the maximum possible V squared edges. However, adjacency matrices are simpler to implement and can be more efficient for dense graphs or when edge existence checks are very frequent.

Example Code

// Adjacency Matrix - O(V^2) space
class GraphMatrix {
    int V;
    int[][] adj;
    
    GraphMatrix(int V) {
        this.V = V;
        adj = new int[V][V];
    }
    
    void addEdge(int u, int v) {
        adj[u][v] = 1;  // O(1)
    }
    
    boolean hasEdge(int u, int v) {
        return adj[u][v] == 1;  // O(1)
    }
}

// Adjacency List - O(V+E) space
class GraphList {
    int V;
    List<List<Integer>> adj;
    
    GraphList(int V) {
        this.V = V;
        adj = new ArrayList<>();
        for (int i = 0; i < V; i++)
            adj.add(new ArrayList<>());
    }
    
    void addEdge(int u, int v) {
        adj.get(u).add(v);  // O(1)
    }
    
    boolean hasEdge(int u, int v) {
        return adj.get(u).contains(v);  // O(degree)
    }
}

// Example Graph: 0-1, 0-2, 1-2, 2-3
// Matrix:
//   0 1 2 3
// 0[0 1 1 0]
// 1[0 0 1 0]
// 2[0 0 0 1]
// 3[0 0 0 0]

// List:
// 0: [1, 2]
// 1: [2]
// 2: [3]
// 3: []

27. Compare Breadth-First Search and Depth-First Search. When would you use each algorithm?

Difficulty: HardType: SubjectiveTopic: BFS vs DFS

Breadth-First Search and Depth-First Search are fundamental graph traversal algorithms with different exploration strategies and use cases. BFS explores the graph level by level, visiting all neighbors of a vertex before moving to the next level. It uses a queue data structure to maintain the order of vertices to visit. Starting from a source vertex, BFS visits all vertices at distance 1, then all at distance 2, and so on. Time complexity is O of V plus E and space complexity is O of V for the queue and visited array. BFS guarantees finding the shortest path in unweighted graphs. DFS explores the graph by going as deep as possible along each branch before backtracking. It uses a stack explicitly or implicitly through recursion. Starting from a source vertex, DFS explores one neighbor completely before exploring other neighbors. Time complexity is O of V plus E and space complexity is O of V for the recursion stack or explicit stack in worst case. DFS is more memory efficient for deep graphs. Use BFS when you need to find the shortest path in an unweighted graph, when you want to find all vertices within a given distance, for level-order traversal of trees, in social networking applications to find people within a certain degree of connection, and when you want to find connected components. BFS is also useful in web crawlers for breadth-first exploration and in GPS navigation for finding nearby locations. Use DFS when you need to detect cycles in a graph, for topological sorting in directed acyclic graphs, to find strongly connected components, when checking if a path exists between two vertices, in maze and puzzle solving where you want to explore all possibilities, and when memory is limited as DFS typically uses less memory than BFS. DFS is also used in game tree evaluation, finding articulation points and bridges in graphs, and solving constraint satisfaction problems. A key difference is that BFS finds the shortest path and explores nearest vertices first making it suitable for level-wise processing, while DFS explores deeper before going wide making it suitable for exhaustive search and backtracking scenarios. BFS uses more memory storing entire levels while DFS memory grows with depth. Choose based on whether you need shortest paths or deep exploration.

Example Code

// BFS - Queue, Level-order
void BFS(int start) {
    boolean[] visited = new boolean[V];
    Queue<Integer> queue = new LinkedList<>();
    
    visited[start] = true;
    queue.add(start);
    
    while (!queue.isEmpty()) {
        int u = queue.poll();
        System.out.print(u + " ");
        
        // Visit all unvisited neighbors
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                queue.add(v);
            }
        }
    }
}

// DFS - Stack/Recursion, Depth-first
void DFS(int u, boolean[] visited) {
    visited[u] = true;
    System.out.print(u + " ");
    
    // Visit all unvisited neighbors
    for (int v : adj[u]) {
        if (!visited[v]) {
            DFS(v, visited);
        }
    }
}

// Example graph:
//     0
//    / \
//   1   2
//  /     \
// 3       4

// BFS from 0: 0 1 2 3 4 (level-by-level)
// DFS from 0: 0 1 3 2 4 (depth-first)

// BFS: Shortest path guarantee
// DFS: Memory efficient for deep graphs

28. How do you find the height of a binary tree? Explain the algorithm and its complexity.

Difficulty: HardType: SubjectiveTopic: Tree Problems

The height of a binary tree is the number of edges in the longest path from the root to a leaf node. An empty tree has height negative 1, a tree with only root has height 0, and so on. Finding the height is a fundamental tree operation. The recursive algorithm is based on the observation that the height of a tree equals one plus the maximum height of its subtrees. For any node, we recursively calculate the height of the left subtree and the height of the right subtree, then return one plus the maximum of these two heights. The base case is when we reach a null node, which has height negative 1. The algorithm works as follows. If the node is null, return negative 1. Recursively find the height of the left subtree. Recursively find the height of the right subtree. Return one plus the maximum of the left and right heights. This one accounts for the edge from the current node to its child. Time complexity is O of n where n is the number of nodes, because we visit each node exactly once. Space complexity is O of h where h is the height of the tree, due to the recursion call stack. In the worst case of a skewed tree, this becomes O of n. For a balanced tree, space complexity is O of log n. The iterative approach uses level-order traversal with a queue. We process the tree level by level, incrementing a counter for each level. Initialize height to 0 and use a queue containing the root. While the queue is not empty, get the number of nodes at current level, process all nodes at this level by dequeuing and enqueuing their children, and increment height after processing each level. This approach has O of n time and O of w space where w is the maximum width of the tree. Variations of this problem include finding the diameter of a tree which is the longest path between any two nodes, checking if a tree is balanced where heights of subtrees differ by at most 1, and finding the minimum depth which is the shortest path from root to a leaf.

Example Code

class TreeNode {
    int data;
    TreeNode left, right;
}

// Recursive approach - O(n) time, O(h) space
int height(TreeNode root) {
    // Base case: empty tree
    if (root == null)
        return -1;
    
    // Recursive case
    int leftHeight = height(root.left);
    int rightHeight = height(root.right);
    
    // Height = 1 + max of subtree heights
    return 1 + Math.max(leftHeight, rightHeight);
}

// Iterative approach - Level-order
int heightIterative(TreeNode root) {
    if (root == null) return -1;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    int height = -1;
    
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        
        // Process entire level
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        height++;
    }
    return height;
}

// Example:
//        1        height = 2
//       / \
//      2   3     height = 1
//     /
//    4            height = 0
// height(1) = 1 + max(height(2), height(3))
//           = 1 + max(1, 0) = 2

29. Explain cycle detection in a graph. How do you detect cycles in directed and undirected graphs?

Difficulty: HardType: SubjectiveTopic: Graph Algorithms

Cycle detection is the problem of determining whether a graph contains a cycle, which is a path where you can start at a vertex and return to it without repeating edges. The approach differs for directed and undirected graphs. For undirected graphs, we use DFS with parent tracking. A cycle exists if during DFS traversal, we encounter a visited vertex that is not the parent of the current vertex. The algorithm maintains a visited array and passes the parent vertex in recursive calls. Start DFS from any unvisited vertex. For each neighbor of the current vertex, if the neighbor is not visited, recursively visit it. If the neighbor is visited and is not the parent of current vertex, a cycle exists. Time complexity is O of V plus E and space complexity is O of V. The key insight for undirected graphs is that if we reach an already visited vertex that is not our immediate parent, we must have reached it through a different path, forming a cycle. We need the parent check because in an undirected graph, the edge connecting a node to its parent would otherwise be detected as a cycle. For directed graphs, we use DFS with recursion stack tracking. A cycle exists if we encounter a vertex that is currently in the recursion stack, meaning we found a back edge. The algorithm maintains two arrays: visited to track all visited vertices, and recursion stack to track vertices in the current DFS path. Start DFS from any unvisited vertex. Mark current vertex as visited and add to recursion stack. For each neighbor, if it is not visited, recursively visit it. If it is in the recursion stack, a cycle exists. After processing all neighbors, remove current vertex from recursion stack. Time complexity is O of V plus E and space complexity is O of V. The difference is crucial because in directed graphs, visiting an already visited vertex only indicates a cycle if that vertex is in our current path. A vertex visited in a different DFS path does not form a cycle with our current path. Applications of cycle detection include deadlock detection in operating systems where processes are vertices and resource requests are edges, checking for circular dependencies in build systems or package managers, detecting infinite loops in finite state machines, and verifying if topological sorting is possible which requires a directed acyclic graph.

Example Code

// Undirected Graph - DFS with parent tracking
boolean hasCycleUndirected(int v, boolean[] visited, int parent) {
    visited[v] = true;
    
    for (int neighbor : adj[v]) {
        // If neighbor not visited, recurse
        if (!visited[neighbor]) {
            if (hasCycleUndirected(neighbor, visited, v))
                return true;
        }
        // If visited and not parent, cycle exists
        else if (neighbor != parent) {
            return true;
        }
    }
    return false;
}

// Directed Graph - DFS with recursion stack
boolean hasCycleDirected(int v, boolean[] visited, boolean[] recStack) {
    visited[v] = true;
    recStack[v] = true;  // Add to current path
    
    for (int neighbor : adj[v]) {
        // If not visited, recurse
        if (!visited[neighbor]) {
            if (hasCycleDirected(neighbor, visited, recStack))
                return true;
        }
        // If in recursion stack, back edge found
        else if (recStack[neighbor]) {
            return true;
        }
    }
    
    recStack[v] = false;  // Remove from current path
    return false;
}

// Example Undirected:
// 0 - 1 - 2
// |       |
// 3 ----- 4
// Cycle: 1-2-4-3-0-1

// Example Directed:
// 0 -> 1 -> 2
// ^         |
// |         v
// 4 <------ 3
// Cycle: 0->1->2->3->4->0

37. Compare linear search and binary search. In what scenarios is each algorithm preferred?

Difficulty: MediumType: SubjectiveTopic: Searching Algorithms

Linear search and binary search are fundamental searching algorithms with different requirements, performance characteristics, and use cases. Linear search examines each element sequentially from start to end until the target is found or the array ends. It works by checking if the current element equals the target, returning the index if found, or continuing to the next element. Time complexity is O of 1 best case when element is first, O of n average and worst case. Space complexity is O of 1 as no extra space is needed. Linear search works on both sorted and unsorted arrays, and it works on any data structure with sequential access including linked lists. Binary search divides the search space in half repeatedly by comparing the target with the middle element. It requires a sorted array. If the middle element equals target, return it. If target is smaller, search left half. If larger, search right half. Time complexity is O of log n for all cases. Space complexity is O of 1 for iterative implementation or O of log n for recursive due to call stack. Binary search only works on sorted arrays and requires random access, making it unsuitable for linked lists. Use linear search when the array is unsorted and sorting overhead exceeds search benefit, when the array is very small where O of n is acceptable, when searching linked lists or data structures without random access, when you need to find all occurrences of an element, and when implementing simple search without complexity. Linear search is also useful when the target is likely to be near the beginning. Use binary search when the array is already sorted or will be searched multiple times justifying the sorting cost, when dealing with large datasets where O of log n significantly outperforms O of n, when you need to find first or last occurrence in sorted array, when implementing range queries or finding closest elements, and when memory allows random access. Binary search is essential in scenarios requiring logarithmic performance like database indexing. For example, with an array of 1 million elements, linear search might examine up to 1 million elements in worst case, while binary search examines at most 20 elements, demonstrating the massive performance difference for large datasets.

Example Code

// Linear Search - O(n)
int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target)
            return i;
    }
    return -1;
}

// Binary Search - O(log n)
int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target)
            return mid;
        if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

// Performance comparison:
// Array size: 1,000,000
// Linear: up to 1,000,000 comparisons
// Binary: up to 20 comparisons

// When to use:
// Linear: [3, 1, 4, 1, 5] unsorted, small
// Binary: [1, 1, 3, 4, 5] sorted, large

38. Explain Merge Sort algorithm. How does it work and what are its advantages and disadvantages?

Difficulty: HardType: SubjectiveTopic: Sorting Algorithms

Merge Sort is a divide-and-conquer sorting algorithm that recursively divides the array into halves, sorts them, and merges the sorted halves back together. It guarantees O of n log n time complexity for all cases. The algorithm works in three main steps. First, divide the array into two halves by finding the middle index. Continue dividing recursively until each subarray has one element, which is inherently sorted. Second, conquer by recursively sorting the two halves. The base case is when a subarray has one or zero elements. Third, merge the two sorted halves back together by comparing elements from both halves and placing them in correct order. The merge operation works by maintaining two pointers, one for each sorted half. Compare elements at both pointers and place the smaller element in the result array. Move the pointer of the array from which element was taken. Continue until all elements from both halves are merged. Time complexity is O of n for merging as we process each element once. Time complexity analysis shows that dividing the array creates log n levels because we halve the array each time. At each level, we perform O of n work to merge all subarrays at that level. Total time is O of n log n for all cases, whether best, average, or worst. Space complexity is O of n because we need temporary arrays to store the merged results. This is the main disadvantage as it requires extra space proportional to array size. Advantages of Merge Sort include guaranteed O of n log n time complexity regardless of input, making it predictable and reliable. It is a stable sort preserving the relative order of equal elements, which is important for multi-key sorting. It works well with linked lists where no extra space is needed for merging. It is suitable for external sorting when data does not fit in memory. The algorithm is parallelizable as independent subarrays can be sorted concurrently. Disadvantages include O of n space complexity requiring extra memory for temporary arrays, which can be prohibitive for large datasets. It is slower than Quick Sort in practice for arrays due to the overhead of copying elements. It cannot take advantage of nearly sorted data unlike Insertion Sort. It is not an in-place algorithm, requiring additional space allocation. Merge Sort is preferred when you need guaranteed O of n log n performance, when stability is required, when dealing with linked lists, or when the dataset is too large to fit in memory requiring external sorting.

Example Code

// Merge Sort - O(n log n) always
void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        // Divide
        int mid = left + (right - left) / 2;
        
        // Conquer
        mergeSort(arr, left, mid);      // Sort left half
        mergeSort(arr, mid + 1, right); // Sort right half
        
        // Combine
        merge(arr, left, mid, right);
    }
}

void merge(int[] arr, int left, int mid, int right) {
    // Create temp arrays
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int[] L = new int[n1];
    int[] R = new int[n2];
    
    // Copy data
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
    
    // Merge back
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j])
            arr[k++] = L[i++];
        else
            arr[k++] = R[j++];
    }
    
    // Copy remaining
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

// Example: [38, 27, 43, 3]
// Split: [38, 27] [43, 3]
// Split: [38] [27] [43] [3]
// Merge: [27, 38] [3, 43]
// Merge: [3, 27, 38, 43]

39. Explain Quick Sort algorithm. How does partitioning work and how can you optimize pivot selection?

Difficulty: HardType: SubjectiveTopic: Quick Sort

Quick Sort is a highly efficient divide-and-conquer sorting algorithm that works by selecting a pivot element and partitioning the array around it. It is widely used due to its excellent average-case performance and in-place sorting capability. The algorithm works as follows. First, choose a pivot element from the array using various strategies. Second, partition the array so that all elements smaller than the pivot come before it and all elements greater come after it. This puts the pivot in its final sorted position. Third, recursively apply Quick Sort to the subarrays before and after the pivot. The base case is when a subarray has one or zero elements. The partitioning operation is the key to Quick Sort. Using the Lomuto partition scheme, we maintain an index i that tracks the boundary between smaller and larger elements. We iterate through the array with index j. If the current element is smaller than the pivot, we increment i and swap elements at i and j. This moves smaller elements to the left. Finally, we swap the pivot to its correct position at index i plus 1. Time complexity of partitioning is O of n as we examine each element once. The Hoare partition scheme is an alternative that uses two pointers moving from both ends. Start with pointers at both ends. Move the left pointer right until finding an element greater than or equal to pivot. Move the right pointer left until finding an element less than or equal to pivot. Swap the elements at these pointers. Continue until pointers cross. This scheme makes fewer swaps on average than Lomuto. Time complexity analysis shows that in the best and average cases, the pivot divides the array into roughly equal halves, creating log n levels of recursion with O of n work at each level, giving O of n log n total. In the worst case with poor pivot selection, each partition has size n minus 1 and 0, creating n levels with O of n work each, giving O of n squared. Space complexity is O of log n for the recursion stack in average case, O of n in worst case. Pivot selection strategies significantly impact performance. Choosing the first or last element is simple but leads to worst case on sorted or reverse sorted arrays. Random pivot selection provides good average performance and avoids worst case on specific inputs. Median-of-three selects the median of first, middle, and last elements, providing good balance while being deterministic. Some implementations use median-of-five or even deterministic median-finding algorithms for guaranteed good pivots. Advantages of Quick Sort include O of n log n average case with low constant factors making it faster than Merge Sort in practice. It sorts in-place requiring only O of log n extra space for recursion. It has good cache performance due to localized memory access. It is easy to implement and widely used in standard libraries. Disadvantages include O of n squared worst case which can occur with poor pivot selection, though randomization makes this extremely unlikely. It is not stable as equal elements may be reordered. Recursive implementation can cause stack overflow for large arrays if not optimized with tail recursion or switching to Heap Sort for deep recursion.

Example Code

// Quick Sort - O(n log n) average
void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        // Partition and get pivot index
        int pi = partition(arr, low, high);
        
        // Sort elements before and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// Lomuto Partition Scheme
int partition(int[] arr, int low, int high) {
    int pivot = arr[high];  // Choose last as pivot
    int i = low - 1;        // Index of smaller element
    
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr, i + 1, high);
    return i + 1;
}

// Improved pivot selection
int choosePivot(int[] arr, int low, int high) {
    // Median-of-three
    int mid = low + (high - low) / 2;
    int a = arr[low], b = arr[mid], c = arr[high];
    
    if ((a <= b && b <= c) || (c <= b && b <= a))
        return mid;
    if ((b <= a && a <= c) || (c <= a && a <= b))
        return low;
    return high;
}

// Example: [7, 2, 1, 6, 8, 5, 3, 4]
// Pivot: 4
// Partition: [2,1,3] [4] [6,8,5,7]
// Recurse on both sides

40. What is recursion? Explain with examples and discuss when recursion is preferred over iteration.

Difficulty: MediumType: SubjectiveTopic: Recursion Concepts

Recursion is a programming technique where a function calls itself to solve a problem by breaking it down into smaller, similar subproblems. Each recursive call works on a simpler version of the original problem until reaching a base case that can be solved directly. The essential components of recursion are the base case which is the simplest scenario that can be solved without recursion and stops the recursive calls, and the recursive case which breaks the problem into smaller instances and makes recursive calls. Each recursive call should move closer to the base case, and the function combines results from recursive calls to solve the original problem. A simple example is calculating factorial. Factorial of n is defined as n times factorial of n minus 1, with base case factorial of 0 or 1 equals 1. This naturally maps to a recursive function. Another example is the Fibonacci sequence where each number is the sum of the two preceding ones. The base cases are F of 0 equals 0 and F of 1 equals 1. The recursive case is F of n equals F of n minus 1 plus F of n minus 2. How recursion works internally involves the call stack. When a function calls itself, the current execution state including parameters and local variables is saved on the call stack. The recursive call executes as a new function invocation. When a recursive call completes, its result is returned and the previous state is restored from the stack. The stack unwinds as recursive calls return, eventually returning to the original caller. Advantages of recursion include code simplicity and elegance for naturally recursive problems like tree traversal and divide-and-conquer algorithms. It provides a clear mathematical correspondence for problems defined recursively. It eliminates complex loop logic and state management. Some algorithms like tree and graph traversal are more naturally expressed recursively. Disadvantages include performance overhead as function calls have overhead and recursion can be slower than iteration. Each recursive call consumes stack space which can lead to stack overflow for deep recursion. There is redundant computation in naive recursive solutions like Fibonacci calculating same values repeatedly. Debugging can be harder as the call stack becomes complex. Use recursion when the problem has a recursive structure like trees, graphs, or divide-and-conquer algorithms. Use it when the recursive solution is significantly clearer than iterative as in tree traversal or backtracking. Use it when the recursion depth is manageable and will not cause stack overflow. Use it when the problem naturally divides into smaller similar subproblems. Examples include tree and graph traversal, divide-and-conquer algorithms like Merge Sort and Binary Search, backtracking problems like N-Queens and Sudoku, dynamic programming when combined with memoization, and problems involving recursive data structures. Use iteration when performance is critical and recursion overhead matters, when recursion depth could cause stack overflow, when the iterative solution is equally clear or clearer, and when space complexity needs to be minimized. Many recursive algorithms can be converted to iterative using explicit stacks or queues.

Example Code

// Factorial - Natural recursion
int factorial(int n) {
    // Base case
    if (n <= 1)
        return 1;
    
    // Recursive case
    return n * factorial(n - 1);
}

// Fibonacci - Multiple recursive calls
int fibonacci(int n) {
    // Base cases
    if (n <= 1)
        return n;
    
    // Recursive case
    return fibonacci(n - 1) + fibonacci(n - 2);
}

// Binary Search - Divide and conquer
int binarySearch(int[] arr, int target, int left, int right) {
    // Base case
    if (left > right)
        return -1;
    
    // Recursive case
    int mid = left + (right - left) / 2;
    if (arr[mid] == target)
        return mid;
    if (arr[mid] > target)
        return binarySearch(arr, target, left, mid - 1);
    return binarySearch(arr, target, mid + 1, right);
}

// Call stack for factorial(5):
// factorial(5) -> 5 * factorial(4)
// factorial(4) -> 4 * factorial(3)
// factorial(3) -> 3 * factorial(2)
// factorial(2) -> 2 * factorial(1)
// factorial(1) -> 1 (base case)
// Returns: 1 * 2 * 3 * 4 * 5 = 120

41. Explain the backtracking technique with the N-Queens problem as an example. How does it differ from brute force?

Difficulty: HardType: SubjectiveTopic: Backtracking

Backtracking is an algorithmic technique for solving problems by trying to build a solution incrementally and abandoning candidates as soon as it determines they cannot lead to a valid solution. This pruning of the search space makes it more efficient than brute force. The backtracking approach follows a general pattern. Start with an empty solution. At each step, try to extend the partial solution by adding one more element. Check if the current partial solution is valid using constraint checking. If valid, recursively continue building the solution. If the partial solution violates constraints or cannot lead to a complete solution, backtrack by removing the last added element and try a different choice. If a complete valid solution is found, record it. Continue until all possibilities are explored. The N-Queens problem asks to place N queens on an N by N chessboard such that no two queens attack each other. Queens attack horizontally, vertically, and diagonally. The backtracking solution works row by row. For each row, try placing the queen in each column. Check if placing the queen in current position is safe by verifying no queen in previous rows attacks this position. If safe, mark this position and recursively solve for the next row. If recursive call returns false meaning no solution found, unmark this position and try next column. If all columns tried without success, backtrack to previous row. If all N queens are placed successfully, a solution is found. The safe check verifies three conditions. First, check the column to ensure no queen in the same column in previous rows. Second, check the left diagonal by verifying positions where row minus column is constant. Third, check the right diagonal by verifying positions where row plus column is constant. We only check previous rows because we place queens row by row. Comparing backtracking to brute force shows significant efficiency gains. Brute force would try all possible placements of N queens on N squared positions and then check if valid. This gives C of N squared choose N possibilities, which is astronomical even for small N. For N equals 8, this is over 4 billion combinations. Backtracking prunes invalid partial solutions early. If placing a queen makes position invalid, we do not explore any completions of that partial solution. For 8-Queens, backtracking explores around 15,000 nodes compared to billions in brute force. The time complexity of backtracking is O of N factorial in worst case for N-Queens, as we have N choices for first row, N minus 1 for second row after pruning, and so on. However, practical performance is much better due to pruning. Space complexity is O of N for the recursion stack and the board representation. Backtracking is applicable to many problems including Sudoku solver where we try numbers 1 to 9 in empty cells and backtrack if invalid, generating all permutations or combinations by building them element by element, solving constraint satisfaction problems, maze solving where we try paths and backtrack if we hit dead ends, and the knapsack problem with constraints. The key advantage is pruning the search space by abandoning partial solutions that violate constraints, making it far more efficient than exhaustive brute force.

42. How do you analyze the time and space complexity of recursive algorithms? Explain with examples.

Difficulty: MediumType: SubjectiveTopic: Complexity Analysis

Analyzing the complexity of recursive algorithms requires understanding the recursion tree, recurrence relations, and the work done at each level. The approach differs from iterative algorithms because we must account for the recursive calls and the call stack. To analyze time complexity, first identify the base case and its complexity, usually O of 1. Second, determine the number of recursive calls made at each level. Third, calculate the work done in each call excluding recursive calls. Fourth, determine the depth of recursion which is how many levels deep the recursion goes. Fifth, combine these factors using recurrence relations or the recursion tree method. The recursion tree method visualizes each function call as a node. The root is the initial call, and children are recursive calls. Each level represents one step of recursion depth. Count the total work done across all nodes. For example, in binary tree traversal, each node is visited once, giving O of n time complexity. Recurrence relations express the running time as a function of the input size. For example, T of n equals 2 times T of n divided by 2 plus O of n for Merge Sort, where 2 times T of n divided by 2 represents two recursive calls on half-sized arrays, and O of n is the merge operation. Solving this using the Master Theorem or recursion tree gives O of n log n. Common patterns include linear recursion with one recursive call like factorial where T of n equals T of n minus 1 plus O of 1, giving O of n total. Binary recursion with two calls like Fibonacci has T of n equals T of n minus 1 plus T of n minus 2 plus O of 1, giving O of 2 to the power n. Divide and conquer with balanced splits like Binary Search has T of n equals T of n divided by 2 plus O of 1, giving O of log n. Multiple branching with equal work like Merge Sort has T of n equals 2 times T of n divided by 2 plus O of n, giving O of n log n. Space complexity analysis must consider both the call stack and auxiliary space. The call stack depth equals the maximum recursion depth. Each recursive call adds a frame to the stack. For example, factorial has recursion depth n giving O of n space. Binary Search has recursion depth log n giving O of log n space. Auxiliary space is extra space used within function calls excluding the stack. For instance, Merge Sort uses O of n auxiliary space for temporary arrays. Examples show these principles. For factorial, we have one recursive call with O of 1 work per call, recursion depth n, giving time O of n and space O of n for the call stack. For Fibonacci naive recursion, we have two recursive calls, O of 1 work per call, recursion depth n, but the tree has 2 to the power n total nodes, giving time O of 2 to the power n and space O of n for maximum stack depth. For Binary Search, we have one recursive call, O of 1 work per call, recursion depth log n, giving time O of log n and space O of log n. For Merge Sort, we have two recursive calls, O of n work for merging, recursion depth log n, giving time O of n log n and space O of n for auxiliary arrays plus O of log n for stack. Optimizing recursive algorithms can convert to iterative using explicit stack or queue to avoid call stack overhead. Use memoization to cache results of repeated recursive calls as in dynamic programming. Apply tail call optimization where the recursive call is the last operation, allowing some compilers to optimize space to O of 1. Use divide and conquer efficiently to minimize the work at each level.

Example Code

// Example 1: Factorial - O(n) time, O(n) space
int factorial(int n) {
    if (n <= 1) return 1;  // O(1)
    return n * factorial(n-1);  // 1 recursive call
}
// T(n) = T(n-1) + O(1) = O(n)
// Space: O(n) stack frames

// Example 2: Fibonacci - O(2^n) time, O(n) space
int fib(int n) {
    if (n <= 1) return n;  // O(1)
    return fib(n-1) + fib(n-2);  // 2 recursive calls
}
// T(n) = T(n-1) + T(n-2) + O(1) = O(2^n)
// Space: O(n) max stack depth

// Example 3: Binary Search - O(log n) time, O(log n) space
int binarySearch(int[] arr, int target, int l, int r) {
    if (l > r) return -1;  // O(1)
    int mid = l + (r-l)/2;
    if (arr[mid] == target) return mid;
    if (arr[mid] > target)
        return binarySearch(arr, target, l, mid-1);  // 1 call
    return binarySearch(arr, target, mid+1, r);
}
// T(n) = T(n/2) + O(1) = O(log n)
// Space: O(log n) stack frames

// Example 4: Merge Sort - O(n log n) time, O(n) space
void mergeSort(int[] arr, int l, int r) {
    if (l < r) {
        int mid = (l+r)/2;
        mergeSort(arr, l, mid);       // T(n/2)
        mergeSort(arr, mid+1, r);     // T(n/2)
        merge(arr, l, mid, r);        // O(n)
    }
}
// T(n) = 2T(n/2) + O(n) = O(n log n)
// Space: O(n) auxiliary + O(log n) stack

43. Explain Insertion Sort and Bubble Sort. When is Insertion Sort preferred despite having O(n^2) complexity?

Difficulty: MediumType: SubjectiveTopic: Sorting Applications

Insertion Sort and Bubble Sort are simple comparison-based sorting algorithms with quadratic time complexity, but they have different characteristics and use cases. Bubble Sort works by repeatedly comparing adjacent elements and swapping them if they are in wrong order. It makes multiple passes through the array. In each pass, the largest unsorted element bubbles up to its correct position at the end. The algorithm continues until a complete pass is made without any swaps, indicating the array is sorted. Time complexity is O of n squared for average and worst cases, O of n for best case when array is already sorted. Space complexity is O of 1 as it sorts in-place. Bubble Sort is rarely used in practice due to poor performance, but it is simple to implement and understand. Insertion Sort works like sorting playing cards in your hands. It builds the sorted array one element at a time by taking each element and inserting it into its correct position among the previously sorted elements. Start from the second element. Compare it with elements in the sorted portion, moving them right to make space. Insert the current element in its correct position. Repeat for all elements. Time complexity is O of n squared for average and worst cases when array is reverse sorted, O of n for best case when array is already sorted. Space complexity is O of 1 as it sorts in-place. Insertion Sort is preferred over other O of n squared algorithms and sometimes even over O of n log n algorithms in specific scenarios. First, for small arrays typically fewer than 10 to 50 elements, Insertion Sort outperforms complex algorithms like Quick Sort and Merge Sort due to low constant factors and no recursion overhead. Many optimized sorting implementations like TimSort use Insertion Sort for small subarrays. Second, for nearly sorted data, Insertion Sort performs close to O of n because each element is already close to its correct position, requiring few comparisons and shifts. This makes it excellent for sorting data that is already mostly ordered or for maintaining sorted order as new elements arrive. Third, Insertion Sort is stable, preserving the relative order of equal elements. This is crucial when sorting by multiple keys or when the original order matters for equal elements. Fourth, it is simple to implement with minimal code, making it suitable for embedded systems or when code simplicity is important. Fifth, it is adaptive, meaning it takes advantage of existing order in the data. The more sorted the data, the faster it runs. Sixth, it is an online algorithm that can sort data as it is received, useful for streaming scenarios. Finally, it has minimal memory overhead using only O of 1 extra space. Bubble Sort is rarely preferred as it has worse performance than Insertion Sort in practice, lacks the adaptive property to the same degree, and has no significant advantages. Insertion Sort should be preferred for small datasets, nearly sorted data, when stability is required, in embedded systems with memory constraints, as a subroutine in hybrid sorting algorithms, and when data arrives in a stream. For example, Python's TimSort uses Insertion Sort for small subarrays during its merge process. When sorting an array of 10 elements, Insertion Sort is faster than Quick Sort due to lower constant factors. When adding a single element to a sorted array of 1000 elements, Insertion Sort finds the position in O of n time.

Example Code

// Insertion Sort - O(n^2) worst, O(n) best
void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        
        // Move elements greater than key
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

// Bubble Sort - O(n^2) worst, O(n) best
void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
                swapped = true;
            }
        }
        if (!swapped) break;  // Array is sorted
    }
}

// Example - Insertion Sort on nearly sorted:
// [1, 2, 3, 5, 4] - Only 4 needs insertion
// Compare 4 with 5, shift 5, insert 4
// Result: [1, 2, 3, 4, 5] - O(n) time

// When to use Insertion Sort:
// - Array size < 50
// - Data nearly sorted
// - Need stable sort
// - Streaming data

51. What is Dynamic Programming? Explain its key principles and when to use it.

Difficulty: MediumType: SubjectiveTopic: Dynamic Programming

Dynamic programming is an algorithmic technique for solving optimization problems by breaking them down into simpler overlapping subproblems and storing their solutions to avoid redundant computation. It is applicable when a problem exhibits two key properties: optimal substructure and overlapping subproblems. Optimal substructure means that the optimal solution to a problem can be constructed from optimal solutions to its subproblems. For example, the shortest path from A to C through B is the shortest path from A to B plus the shortest path from B to C. If a problem lacks this property, DP cannot be applied. Overlapping subproblems means that the same subproblem is solved multiple times during the recursive solution. This is where DP provides its efficiency gain. For example, computing Fibonacci of 5 requires computing Fibonacci of 3 twice through different recursive paths. By storing the result of Fibonacci of 3 the first time, we can reuse it instead of recalculating. There are two main approaches to dynamic programming. The top-down approach, called memoization, starts with the original problem and uses recursion to break it down into subproblems. It stores results in a cache such as an array or hash map to avoid recomputing. The code is often more intuitive as it follows the natural recursive structure. However, it has recursion overhead and may compute only necessary subproblems. The bottom-up approach, called tabulation, starts with the smallest subproblems and iteratively builds up to the solution. It fills a DP table in a specific order ensuring dependencies are satisfied. The code uses iteration instead of recursion, avoiding stack overflow. It may compute all subproblems even if some are unnecessary, but often allows better space optimization. To identify when to use dynamic programming, look for these signals. The problem asks for optimization such as maximum, minimum, longest, or shortest. The problem can be broken into similar smaller subproblems. Solving subproblems independently and combining results gives the solution. A naive recursive solution has exponential time complexity due to repeated calculations. The problem involves counting ways or possibilities. Examples include finding minimum or maximum values, counting paths or arrangements, and problems with choices at each step. The typical steps to solve a DP problem are: first, define the DP state clearly, identifying what each DP entry represents. Second, establish the recurrence relation showing how to compute a state from previous states. Third, identify base cases where the answer is known without computation. Fourth, determine the evaluation order ensuring dependencies are computed before they are needed. Fifth, implement using either memoization or tabulation. Sixth, optimize space if the solution uses too much memory. Common DP patterns include linear DP where state depends on previous states in a sequence like Fibonacci or climbing stairs, interval DP where state represents a range of elements like matrix chain multiplication, subset DP where we consider including or excluding elements like knapsack, grid DP where we move through a 2D grid like unique paths, and string DP involving operations on strings like edit distance or LCS.

Example Code

// Problem: Climbing Stairs
// You can climb 1 or 2 steps at a time
// How many ways to reach step n?

// 1. Define state: dp[i] = ways to reach step i
// 2. Recurrence: dp[i] = dp[i-1] + dp[i-2]
//    (come from step i-1 or i-2)
// 3. Base cases: dp[0]=1, dp[1]=1

// Memoization (Top-down)
int climbStairsMemo(int n, int[] memo) {
    if (n <= 1) return 1;
    if (memo[n] != 0) return memo[n];
    
    memo[n] = climbStairsMemo(n-1, memo) + 
              climbStairsMemo(n-2, memo);
    return memo[n];
}

// Tabulation (Bottom-up)
int climbStairsTab(int n) {
    if (n <= 1) return 1;
    int[] dp = new int[n+1];
    dp[0] = 1; dp[1] = 1;
    
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i-1] + dp[i-2];
    
    return dp[n];
}

// Space optimized - O(1)
int climbStairsOpt(int n) {
    if (n <= 1) return 1;
    int prev2 = 1, prev1 = 1, curr = 0;
    
    for (int i = 2; i <= n; i++) {
        curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return curr;
}

52. Explain the 0/1 Knapsack problem and its dynamic programming solution. What is the difference between 0/1 and fractional knapsack?

Difficulty: HardType: SubjectiveTopic: Knapsack Problem

The 0 or 1 Knapsack problem is a classic optimization problem where you have n items, each with a weight and value, and a knapsack with capacity W. The goal is to select items to maximize total value without exceeding the capacity. Each item can be either taken completely or not taken at all, hence the name 0 or 1. The problem exhibits optimal substructure because the optimal solution for n items and capacity W either includes the nth item or excludes it. If we include the nth item, we need the optimal solution for n minus 1 items with capacity W minus weight of nth item. If we exclude it, we need the optimal solution for n minus 1 items with capacity W. We take the maximum of these two choices. The DP solution uses a 2D table where dp of i of w represents the maximum value achievable using the first i items with capacity w. The recurrence relation is: if weight of item i is less than or equal to w, then dp of i of w equals max of value of i plus dp of i minus 1 of w minus weight of i, which is including the item, and dp of i minus 1 of w, which is excluding the item. Otherwise, dp of i of w equals dp of i minus 1 of w as we cannot include the item. Base cases are dp of 0 of w equals 0 for all w, meaning with zero items we get zero value, and dp of i of 0 equals 0 for all i, meaning with zero capacity we get zero value. The evaluation order is row by row, processing items one by one, and within each row, processing capacities from 0 to W. The final answer is dp of n of W. Time complexity is O of n times W where n is the number of items and W is knapsack capacity. We fill a table of size n plus 1 by W plus 1 with constant work per cell. Space complexity is O of n times W for the 2D table, though it can be optimized to O of W using a 1D array by processing items one at a time. The space-optimized solution uses only one row by observing that we only need the previous row to compute the current row. We can use a single array and update it in-place by iterating from right to left to avoid overwriting values we still need. The fractional knapsack problem differs in that you can take fractions of items, not just whole items. This changes the problem fundamentally. Fractional knapsack can be solved optimally using a greedy approach. Sort items by value-to-weight ratio in descending order. Take items in this order, taking as much as possible of each item until the knapsack is full. If an item does not fit completely, take the fraction that fits. Time complexity is O of n log n for sorting. The key difference is that 0 or 1 knapsack requires dynamic programming with O of n times W time because you cannot make locally optimal choices. You must consider combinations of items. Fractional knapsack can use greedy with O of n log n time because taking items with highest value-to-weight ratio is always optimal when fractions are allowed. Applications of 0 or 1 knapsack include resource allocation with constraints, portfolio optimization, cargo loading where items cannot be split, and project selection with budget constraints. The problem is NP-complete in general, but the DP solution is pseudo-polynomial with time depending on W.

Example Code

// 0/1 Knapsack - DP Solution
int knapsack01(int[] values, int[] weights, int W, int n) {
    int[][] dp = new int[n+1][W+1];
    
    // Build table bottom-up
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            // Can we include item i-1?
            if (weights[i-1] <= w) {
                // Max of include vs exclude
                dp[i][w] = Math.max(
                    values[i-1] + dp[i-1][w - weights[i-1]], // Include
                    dp[i-1][w]                                // Exclude
                );
            } else {
                // Cannot include, carry forward
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    return dp[n][W];
}
// Time: O(n*W), Space: O(n*W)

// Space Optimized - 1D array
int knapsackOptimized(int[] values, int[] weights, int W, int n) {
    int[] dp = new int[W+1];
    
    for (int i = 0; i < n; i++) {
        // Traverse right to left to avoid overwriting
        for (int w = W; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], 
                            values[i] + dp[w - weights[i]]);
        }
    }
    return dp[W];
}
// Time: O(n*W), Space: O(W)

// Fractional Knapsack - Greedy
double fractionalKnapsack(int[] values, int[] weights, int W) {
    // Sort by value/weight ratio
    Item[] items = createItems(values, weights);
    Arrays.sort(items, (a,b) -> 
        Double.compare(b.ratio, a.ratio));
    
    double totalValue = 0;
    for (Item item : items) {
        if (W >= item.weight) {
            W -= item.weight;
            totalValue += item.value;
        } else {
            totalValue += item.value * ((double)W / item.weight);
            break;
        }
    }
    return totalValue;
}
// Time: O(n log n), Space: O(n)

53. Explain the Longest Common Subsequence problem and its relationship to Edit Distance. How do you solve LCS using dynamic programming?

Difficulty: HardType: SubjectiveTopic: LCS and Edit Distance

The Longest Common Subsequence problem finds the longest sequence that appears in both strings in the same order, but not necessarily contiguously. For example, LCS of ABCDGH and AEDFHR is ADH with length 3. This is different from longest common substring which requires consecutive characters. LCS exhibits optimal substructure. If the last characters of both strings match, the LCS length is 1 plus the LCS of the remaining strings. If they do not match, the LCS is the maximum of two possibilities: LCS excluding the last character of the first string, or LCS excluding the last character of the second string. The DP solution uses a 2D table where dp of i of j represents the length of LCS of the first i characters of string 1 and the first j characters of string 2. The recurrence relation is: if s1 of i minus 1 equals s2 of j minus 1, then dp of i of j equals dp of i minus 1 of j minus 1 plus 1, meaning characters match so extend LCS. Otherwise, dp of i of j equals max of dp of i minus 1 of j and dp of i of j minus 1, meaning take best of excluding one character. Base cases are dp of 0 of j equals 0 for all j, meaning empty string 1 has LCS length 0, and dp of i of 0 equals 0 for all i, meaning empty string 2 has LCS length 0. The final answer is dp of m of n where m and n are the string lengths. Time complexity is O of m times n as we fill an m plus 1 by n plus 1 table with constant work per cell. Space complexity is O of m times n for the table, though it can be optimized to O of min of m comma n by keeping only the current and previous rows since we only look at adjacent cells. To reconstruct the actual LCS sequence, not just its length, we backtrack through the DP table. Start at dp of m of n. If characters match, include this character and move diagonally to dp of i minus 1 of j minus 1. If characters do not match, move to the cell with larger value, either dp of i minus 1 of j or dp of i of j minus 1. Continue until reaching a cell with value 0. Edit Distance, also called Levenshtein distance, is closely related to LCS. It finds the minimum number of operations insertions, deletions, or substitutions needed to transform one string into another. The relationship is: edit distance equals m plus n minus 2 times LCS length. This is because we need to delete characters from string 1 not in LCS and insert characters from string 2 not in LCS. The Edit Distance DP is similar to LCS but tracks operation costs. dp of i of j represents minimum operations to transform first i characters of string 1 to first j characters of string 2. If characters match, dp of i of j equals dp of i minus 1 of j minus 1 with no operation needed. If they do not match, dp of i of j equals 1 plus min of dp of i minus 1 of j for deletion, dp of i of j minus 1 for insertion, and dp of i minus 1 of j minus 1 for substitution. Applications of LCS include comparing DNA sequences in bioinformatics, finding similarities between text documents, version control systems to show file differences, and plagiarism detection. Edit Distance is used in spell checkers, DNA sequence analysis, speech recognition, and approximate string matching.

Example Code

// Longest Common Subsequence
int longestCommonSubsequence(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m+1][n+1];
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i-1) == s2.charAt(j-1))
                // Characters match, extend LCS
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                // Take max of two options
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[m][n];
}
// Time: O(m*n), Space: O(m*n)

// Reconstruct LCS
String getLCS(String s1, String s2, int[][] dp) {
    StringBuilder lcs = new StringBuilder();
    int i = s1.length(), j = s2.length();
    
    while (i > 0 && j > 0) {
        if (s1.charAt(i-1) == s2.charAt(j-1)) {
            lcs.append(s1.charAt(i-1));
            i--; j--;
        } else if (dp[i-1][j] > dp[i][j-1])
            i--;
        else
            j--;
    }
    return lcs.reverse().toString();
}

// Edit Distance
int editDistance(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m+1][n+1];
    
    // Base cases
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i-1) == s2.charAt(j-1))
                dp[i][j] = dp[i-1][j-1];
            else
                dp[i][j] = 1 + Math.min(
                    dp[i-1][j],      // Delete
                    Math.min(
                        dp[i][j-1],  // Insert
                        dp[i-1][j-1] // Replace
                    )
                );
        }
    }
    return dp[m][n];
}

54. What are Greedy Algorithms? Explain when they work and provide examples of problems that can and cannot be solved greedily.

Difficulty: MediumType: SubjectiveTopic: Greedy Algorithms

Greedy algorithms solve optimization problems by making the locally optimal choice at each step with the hope of finding a global optimum. Unlike dynamic programming which considers all possibilities, greedy algorithms commit to choices immediately without reconsidering them. The greedy approach works when a problem exhibits two properties. First, greedy choice property means that a globally optimal solution can be arrived at by making locally optimal choices. At each step, we can make a choice that looks best at the moment without worrying about future consequences. Second, optimal substructure means that an optimal solution to the problem contains optimal solutions to subproblems. The greedy algorithm strategy follows this pattern. Sort or organize the input if needed to identify the locally optimal choice at each step. Make the greedy choice based on some criterion like maximum value, minimum cost, earliest finish time, or highest ratio. Update the problem state after making the choice. Repeat until a solution is complete or no more choices are possible. Return the solution. Advantages of greedy algorithms include simplicity as they are usually easy to understand and implement. They have efficiency with often linear or O of n log n time complexity. They use minimal space with typically O of 1 extra space. They are intuitive as the logic mirrors natural human decision-making. Disadvantages include that they do not guarantee optimal solutions for all problems. They may get stuck in local optima missing the global optimum. They require proof of correctness which can be difficult. They cannot backtrack if a choice leads to suboptimal results. Problems that CAN be solved optimally with greedy include Activity Selection where we select maximum non-overlapping activities by choosing earliest finish time. Huffman Coding creates optimal prefix codes by building tree from lowest frequency nodes. Dijkstra's Shortest Path finds shortest paths by always exploring nearest unvisited vertex. Fractional Knapsack maximizes value by taking items with highest value-to-weight ratio. Minimum Spanning Tree using Kruskal's or Prim's algorithm adds minimum weight edges avoiding cycles. Coin Change for certain coin systems like US coins where greedy gives optimal solutions. Problems that CANNOT be solved optimally with greedy include 0 or 1 Knapsack where we cannot take fractions requiring DP. Coin Change for arbitrary coin systems like coins of 1, 3, 4 where greedy fails for amount 6. Traveling Salesman Problem where choosing nearest city repeatedly does not give optimal tour. Longest Path in a graph where greedy choices lead to local optima. Subset Sum where selecting largest elements first may miss optimal combinations. To determine if greedy works for a problem, try the greedy approach and test with examples. Check if locally optimal choices lead to global optimum. Look for counterexamples where greedy fails. Prove the greedy choice property mathematically if possible. If greedy fails, consider dynamic programming or other approaches. The Activity Selection problem is a classic greedy example. Given activities with start and finish times, select maximum non-overlapping activities. The greedy choice is to always pick the activity with the earliest finish time. This works because choosing earliest finish leaves maximum room for future activities. Sort by finish time, select first activity, then repeatedly select next activity that starts after previous finish.

Example Code

// Activity Selection - Greedy works!
int activitySelection(int[] start, int[] finish) {
    // Sort by finish time
    int n = start.length;
    Activity[] activities = new Activity[n];
    for (int i = 0; i < n; i++)
        activities[i] = new Activity(start[i], finish[i]);
    Arrays.sort(activities, (a,b) -> a.finish - b.finish);
    
    int count = 1;  // Select first
    int lastFinish = activities[0].finish;
    
    for (int i = 1; i < n; i++) {
        if (activities[i].start >= lastFinish) {
            count++;
            lastFinish = activities[i].finish;
        }
    }
    return count;
}
// Greedy: Always pick earliest finish
// Time: O(n log n), Space: O(n)

// Fractional Knapsack - Greedy works!
double fractionalKnapsack(int[] values, int[] weights, int W) {
    int n = values.length;
    Item[] items = new Item[n];
    for (int i = 0; i < n; i++)
        items[i] = new Item(values[i], weights[i]);
    
    // Sort by value/weight ratio
    Arrays.sort(items, (a,b) -> 
        Double.compare(b.ratio, a.ratio));
    
    double totalValue = 0;
    for (Item item : items) {
        if (W >= item.weight) {
            W -= item.weight;
            totalValue += item.value;
        } else {
            totalValue += item.value * ((double)W / item.weight);
            break;
        }
    }
    return totalValue;
}
// Greedy: Highest value/weight ratio first

// 0/1 Knapsack - Greedy FAILS!
// Need DP instead

55. Explain both the Coin Change problems: minimum coins needed and number of ways to make change. Why does greedy work for some coin systems but not others?

Difficulty: HardType: SubjectiveTopic: Coin Change Problem

There are two classic Coin Change problems. The first asks for the minimum number of coins needed to make a given amount. The second asks for the number of different ways to make the amount. Both require different approaches and have different properties. The Minimum Coins problem gives you coin denominations and a target amount, and asks for the minimum number of coins needed to make that amount. This is an optimization problem requiring dynamic programming in the general case. The DP state is dp of i equals minimum coins needed to make amount i. The recurrence relation is: dp of i equals 1 plus min of dp of i minus coin for all coins where coin is less than or equal to i. Base case is dp of 0 equals 0 as zero coins make amount 0. Time complexity is O of n times amount where n is number of coin types. Space complexity is O of amount. The greedy approach for minimum coins always picks the largest coin possible. For certain coin systems like US coins with denominations 1, 5, 10, 25, this greedy approach gives optimal solutions. For example, making 30 cents greedily gives 25 plus 5 equals 2 coins, which is optimal. However, for arbitrary coin systems, greedy may fail. Consider coins 1, 3, 4 and amount 6. The greedy approach picks 4 plus 1 plus 1 equals 3 coins. But the optimal solution is 3 plus 3 equals 2 coins. This shows greedy does not work for all coin systems. The reason is that taking the largest coin first may prevent using combinations of smaller coins that sum to the optimal solution. Canonical coin systems are those where greedy always gives optimal solutions. US coins are canonical. For a coin system to be canonical, it must satisfy certain mathematical properties related to how denominations relate to each other. Proving canonicity requires checking all possible amounts up to a certain threshold. The Counting Ways problem asks for the number of different combinations of coins that sum to the target amount. Order does not matter, so 1 plus 2 and 2 plus 1 count as the same way. This is a counting problem also requiring DP. The DP state is dp of i equals number of ways to make amount i. The recurrence relation is: dp of i plus equals dp of i minus coin for all coins where coin is less than or equal to i. Base case is dp of 0 equals 1 as one way to make zero using no coins. A crucial difference is the iteration order. To avoid counting duplicate combinations, we iterate over coins in the outer loop and amounts in the inner loop. This ensures each combination is counted once. If we iterate amounts in outer loop, we count permutations instead of combinations. The unbounded version allows using each coin unlimited times. The bounded version limits how many times each coin can be used, requiring tracking both amount and coin counts. Applications include making change in vending machines and stores, currency conversion and exchange, resource allocation problems where resources have different values, and optimizing payments in financial systems. Dynamic programming is essential for arbitrary coin systems to guarantee optimal or correct solutions.

Example Code

// Minimum Coins - DP Solution
int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);  // Initialize to impossible
    dp[0] = 0;  // Base case
    
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}
// Time: O(n * amount), Space: O(amount)

// Example: coins=[1,3,4], amount=6
// dp[0]=0
// dp[1]=1 (1)
// dp[2]=2 (1+1)
// dp[3]=1 (3)
// dp[4]=1 (4)
// dp[5]=2 (4+1)
// dp[6]=2 (3+3) NOT 3 (4+1+1)

// Number of Ways - DP Solution
int coinChangeWays(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;  // One way to make 0
    
    // Iterate coins in outer loop to avoid duplicates
    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }
    return dp[amount];
}
// Time: O(n * amount), Space: O(amount)

// Example: coins=[1,2,3], amount=4
// Ways: [1,1,1,1], [1,1,2], [2,2], [1,3]
// Total: 4 ways

// Greedy (only works for canonical systems)
int coinChangeGreedy(int[] coins, int amount) {
    Arrays.sort(coins);  // Sort descending
    int count = 0;
    for (int i = coins.length - 1; i >= 0; i--) {
        count += amount / coins[i];
        amount %= coins[i];
    }
    return amount == 0 ? count : -1;
}
// Works for US coins [1,5,10,25]
// Fails for arbitrary systems

56. Explain the Matrix Chain Multiplication problem and how dynamic programming solves it optimally.

Difficulty: HardType: SubjectiveTopic: Matrix Chain Multiplication

Matrix Chain Multiplication is a classic optimization problem where you need to find the most efficient way to multiply a sequence of matrices. The order of multiplication matters because matrix multiplication is associative but the number of scalar multiplications depends on the parenthesization. Given matrices A1, A2, dot dot dot, An with dimensions, we want to fully parenthesize the product to minimize the total number of scalar multiplications. For example, multiplying matrices A with dimensions 10 by 30, B with 30 by 5, and C with 5 by 60 can be done as either A times B times C which is 10 times 30 times 5 plus 10 times 5 times 60 equals 1500 plus 3000 equals 4500 operations, or A times B times C which is 30 times 5 times 60 plus 10 times 30 times 60 equals 9000 plus 18000 equals 27000 operations. The first order is much more efficient. The problem exhibits optimal substructure. The optimal way to multiply matrices from i to j includes an optimal split at some k, where we optimally multiply matrices from i to k, matrices from k plus 1 to j, and then multiply the two results. We try all possible splits and choose the one with minimum cost. The DP solution uses a 2D table where dp of i of j represents the minimum number of scalar multiplications needed to multiply matrices from i to j. The recurrence relation is: dp of i of j equals min over all k from i to j minus 1 of dp of i of k plus dp of k plus 1 of j plus cost of multiplying resulting matrices. The cost of multiplying two matrices with dimensions p times q and q times r is p times q times r. Base cases are dp of i of i equals 0 for all i, as multiplying a single matrix costs nothing. The evaluation order is critical. We cannot fill the table row by row or column by column because dp of i of j depends on values in the same row to the left and same column below. Instead, we fill by chain length. First compute all chains of length 1, then length 2, and so on. This ensures dependencies are computed before needed. The algorithm stores matrix dimensions in an array where matrix i has dimensions dimensions of i minus 1 by dimensions of i. For chain length len from 2 to n, for each starting position i from 1 to n minus len plus 1, compute ending position j equals i plus len minus 1. Try all split positions k from i to j minus 1. For each k, compute cost equals dp of i of k plus dp of k plus 1 of j plus dimensions of i minus 1 times dimensions of k times dimensions of j. Update dp of i of j to minimum cost found. Time complexity is O of n cubed because we have O of n squared subproblems, each requiring O of n work to try all splits. Space complexity is O of n squared for the DP table. To reconstruct the optimal parenthesization, we maintain an auxiliary table split of i of j that stores the optimal split point for matrices i to j. After filling the DP table, we can recursively build the parenthesization using these split points. The algorithm can be extended to print the optimal solution as a string with parentheses. Starting from split of 1 of n, recursively construct left and right subproblems until reaching base cases. Applications include optimizing database query execution where operations can be reordered, optimizing expression evaluation in compilers, and any scenario involving associative operations where order affects cost. The problem demonstrates the power of DP for problems with optimal substructure where trying all possibilities directly would be exponential.

Example Code

// Matrix Chain Multiplication - DP
int matrixChainMultiplication(int[] dims) {
    int n = dims.length - 1;  // Number of matrices
    int[][] dp = new int[n+1][n+1];
    int[][] split = new int[n+1][n+1];  // For reconstruction
    
    // Base case: single matrix costs 0
    for (int i = 1; i <= n; i++)
        dp[i][i] = 0;
    
    // Fill by chain length
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i <= n - len + 1; i++) {
            int j = i + len - 1;
            dp[i][j] = Integer.MAX_VALUE;
            
            // Try all split points
            for (int k = i; k < j; k++) {
                // Cost = left + right + merge
                int cost = dp[i][k] + dp[k+1][j] + 
                          dims[i-1] * dims[k] * dims[j];
                
                if (cost < dp[i][j]) {
                    dp[i][j] = cost;
                    split[i][j] = k;
                }
            }
        }
    }
    return dp[1][n];
}
// Time: O(n^3), Space: O(n^2)

// Reconstruct optimal parenthesization
String getParenthesization(int[][] split, int i, int j) {
    if (i == j)
        return "A" + i;
    
    return "(" + 
           getParenthesization(split, i, split[i][j]) + 
           " x " + 
           getParenthesization(split, split[i][j]+1, j) + 
           ")";
}

// Example: Matrices with dimensions
// A1: 10x30, A2: 30x5, A3: 5x60
// dims = [10, 30, 5, 60]
//
// DP table:
//     1   2   3
// 1   0  1500 4500
// 2   0   0   9000
// 3   0   0    0
//
// Optimal: ((A1 x A2) x A3) = 4500 operations

57. What are common optimization techniques in dynamic programming? Explain space optimization and when to apply it.

Difficulty: HardType: SubjectiveTopic: DP Optimization Techniques

Dynamic programming solutions often use significant memory, but many problems allow space optimization. Understanding these techniques is crucial for efficient implementations, especially with large inputs or memory constraints. The most common space optimization is reducing dimensions when the current state depends only on a fixed number of previous states. In Fibonacci, the standard DP uses an array of size n, but since F of i depends only on F of i minus 1 and F of i minus 2, we can use just two variables, reducing space from O of n to O of 1. For 2D DP problems, if row i depends only on row i minus 1, we can use two 1D arrays instead of a 2D array, alternating between them. This reduces space from O of n times m to O of m. For example, in Longest Common Subsequence, we only need the current and previous rows. Further optimization uses a single 1D array by carefully choosing the iteration order. If we process columns from right to left, we avoid overwriting values we still need. The 0 or 1 Knapsack problem demonstrates this: iterating capacity from high to low allows using one array. Sliding window optimization applies when the DP state depends only on a fixed-size window of previous states. Instead of storing all states, maintain only the window. This is useful in problems involving sequences or arrays. State compression uses bitmasking for problems with small sets. Instead of storing multi-dimensional state, compress it into a single integer. Traveling Salesman Problem uses this to represent visited cities as bits, allowing DP of position of visited set instead of exponential states. Matrix exponentiation optimizes linear recurrence relations like Fibonacci. Instead of iterating n times, represent the recurrence as matrix multiplication and use fast exponentiation to compute in O of log n time. This reduces time from O of n to O of log n. Memoization with hash maps provides space optimization for sparse DP tables where most entries are unused. Instead of allocating the full table, store only computed states in a hash map. This is efficient when the state space is large but only a small fraction is accessed. Bottom-up DP often allows better optimization than top-down because the iteration order is explicit. We can carefully choose the order to enable space reuse. Top-down with memoization typically requires storing all states. When to apply space optimization depends on several factors. If memory is limited and the problem has large state space, optimization is essential. If the DP solution uses nested loops where inner states depend only on adjacent outer states, dimension reduction works well. If you need to reconstruct the solution path, full tables may be necessary as reconstruction requires tracing through states. Trade-offs exist between space and other factors. Some optimizations increase code complexity. Reconstruction becomes harder or impossible with reduced storage. Debugging is more difficult without seeing the full table. Cache performance may change as data locality is affected. Best practices include implementing the standard solution first to ensure correctness, then optimize if needed. Measure memory usage to determine if optimization is necessary. Test optimized code thoroughly as subtle bugs can occur. Document optimization techniques used for code maintainability. Consider whether reconstruction is needed before optimizing away the full table. Common patterns include 1D array for Fibonacci-like sequences depending on constant previous values, two rows for 2D grid problems depending on previous row, one array with reverse iteration for knapsack-type problems, and sliding window for problems with fixed-window dependencies.

Example Code

// Example: 0/1 Knapsack Space Optimization

// Standard DP - O(n * W) space
int knapsackStandard(int[] val, int[] wt, int W, int n) {
    int[][] dp = new int[n+1][W+1];
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (wt[i-1] <= w)
                dp[i][w] = Math.max(val[i-1] + dp[i-1][w-wt[i-1]], 
                                   dp[i-1][w]);
            else
                dp[i][w] = dp[i-1][w];
        }
    }
    return dp[n][W];
}

// Two rows - O(2 * W) space
int knapsackTwoRows(int[] val, int[] wt, int W, int n) {
    int[][] dp = new int[2][W+1];
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            int curr = i % 2, prev = 1 - curr;
            if (wt[i-1] <= w)
                dp[curr][w] = Math.max(val[i-1] + dp[prev][w-wt[i-1]], 
                                      dp[prev][w]);
            else
                dp[curr][w] = dp[prev][w];
        }
    }
    return dp[n % 2][W];
}

// One array - O(W) space
int knapsackOneArray(int[] val, int[] wt, int W, int n) {
    int[] dp = new int[W+1];
    for (int i = 0; i < n; i++) {
        // Iterate RIGHT TO LEFT to avoid overwriting
        for (int w = W; w >= wt[i]; w--) {
            dp[w] = Math.max(dp[w], val[i] + dp[w - wt[i]]);
        }
    }
    return dp[W];
}

// Fibonacci space optimization
int fibOptimized(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}
// Space: O(1) instead of O(n)

DSA Interview Questions & Answers | Preplance | Preplance

Master Interviews Anywhere, Anytime

All DSA Interview Questions

Overview

1. Which of the following is a non-linear data structure?

2. Which data structure is used for implementing recursion?

Continue your preparation

3. Which of the following data structures are indexed structures?

4. What is the worst-case time complexity of inserting n elements into an empty linked list that must be kept in sorted order?

5. Stack data structure cannot be used for which of the following?

6. A directed graph is _______ if there is a path from each vertex to every other vertex in the graph.

7. The binary search method needs no more than ________ comparisons for an array of size n.

8. In what traversal do we process all of a vertex's descendants before we move to an adjacent vertex?

9. What is a Data Structure? Explain the difference between linear and non-linear data structures with examples.

10. Explain the differences between arrays and linked lists. When would you choose one over the other?

11. What is a stack data structure? Explain its operations and provide real-world applications.

12. Explain the queue data structure, its operations, and compare it with a stack. Provide use cases for each.

13. What is algorithm analysis? Explain time complexity and space complexity with examples.

14. Explain different types of linked lists. How would you detect a cycle in a linked list?

15. Compare different sorting algorithms. When would you choose Quick Sort over Merge Sort?

16. Which of the following are properties of a binary tree?

17. Which of the following data structures is preferred in the implementation of a database system?

18. Which of the following data structures is best for searching words in dictionaries?

19. How can memory be saved when storing colour information in a Red-Black tree?

20. What type of tree is a heap?

21. What are the two main components of a graph?

22. In an AVL tree, what is the maximum height difference allowed between left and right subtrees of any node?

23. Explain the different tree traversal techniques: In-order, Pre-order, and Post-order. Provide use cases for each.

24. What is a Binary Search Tree? Explain its properties and the time complexity of its operations.

25. Explain how a min-heap works. How do you insert an element and extract the minimum element?

26. Explain different ways to represent graphs in memory. Compare adjacency matrix and adjacency list.

27. Compare Breadth-First Search and Depth-First Search. When would you use each algorithm?

28. How do you find the height of a binary tree? Explain the algorithm and its complexity.

29. Explain cycle detection in a graph. How do you detect cycles in directed and undirected graphs?

30. What is the prerequisite for applying binary search on an array?

31. Which of the following sorting algorithms is stable?

32. What is the most critical component of a recursive function?

33. Which sorting algorithm has the best average-case time complexity?

34. What is the key characteristic of backtracking algorithms?

35. What is the time complexity of linear search in the worst case?

36. What causes Quick Sort to have O(n^2) worst-case time complexity?

37. Compare linear search and binary search. In what scenarios is each algorithm preferred?

38. Explain Merge Sort algorithm. How does it work and what are its advantages and disadvantages?

39. Explain Quick Sort algorithm. How does partitioning work and how can you optimize pivot selection?

40. What is recursion? Explain with examples and discuss when recursion is preferred over iteration.

41. Explain the backtracking technique with the N-Queens problem as an example. How does it differ from brute force?

42. How do you analyze the time and space complexity of recursive algorithms? Explain with examples.

43. Explain Insertion Sort and Bubble Sort. When is Insertion Sort preferred despite having O(n^2) complexity?

44. What is the key principle behind dynamic programming?

45. What is the difference between memoization and tabulation in dynamic programming?

46. What is the key characteristic of a greedy algorithm?

47. For which problem does a greedy approach NOT guarantee an optimal solution?

48. What is the space complexity of the optimized Fibonacci DP solution?

49. Which of the following problems uses Catalan numbers?

50. What is the time complexity of finding the Longest Common Subsequence (LCS) of two strings using dynamic programming?

51. What is Dynamic Programming? Explain its key principles and when to use it.

52. Explain the 0/1 Knapsack problem and its dynamic programming solution. What is the difference between 0/1 and fractional knapsack?

53. Explain the Longest Common Subsequence problem and its relationship to Edit Distance. How do you solve LCS using dynamic programming?

54. What are Greedy Algorithms? Explain when they work and provide examples of problems that can and cannot be solved greedily.

55. Explain both the Coin Change problems: minimum coins needed and number of ways to make change. Why does greedy work for some coin systems but not others?

56. Explain the Matrix Chain Multiplication problem and how dynamic programming solves it optimally.

57. What are common optimization techniques in dynamic programming? Explain space optimization and when to apply it.

58. Which of the following strings is a palindrome?

59. Two strings are anagrams if:

60. What is the time complexity of the naive substring search algorithm for text of length n and pattern of length m?

61. What is the main advantage of the KMP algorithm over the naive pattern matching approach?

62. Which concept does the Rabin–Karp algorithm use for pattern matching?

63. What data structure is commonly used to find the longest substring without repeating characters efficiently?

64. Which algorithm is best suited for multiple pattern matching in a large text?

65. Write a program to reverse a string. Explain both iterative and recursive methods.

66. Explain how to find the longest palindromic substring in a string.

67. What is the Edit Distance problem? Explain its dynamic programming solution.

68. Explain the dynamic programming approach for finding the longest common subsequence between two strings.

69. How do you check if one string is a rotation of another?

70. Explain how to count all distinct substrings of a string efficiently.

71. Which data structure gives expected O(1) average time for insert, delete and lookup operations?

72. Which approach efficiently finds the longest consecutive elements sequence in an unsorted array of integers?

73. In the Two Sum problem (find two indices whose values sum to target), what’s the optimal time solution using extra space?

74. What is the efficient way to count number of set bits (1s) in a 32‐bit integer?

75. Given n numbers in range [0,n] with one missing, how do you find the missing number in O(n) time and O(1) space?

76. Explain how to count sub-arrays whose sum equals K in an integer array (with positive and negative values).

Master Interviews
Anywhere, Anytime