Microsoft DSA Interview Questions

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

4. 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.

6. 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

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. 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();
}

11. 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
    }
}

16. 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

17. 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

19. 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

21. 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

25. 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;
}

26. 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];
}

27. 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

35. 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

37. 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

43. 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)

Microsoft DSA Interview Questions | Preplance | Preplance

Master Interviews Anywhere, Anytime

Quick overview

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

Continue your preparation

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

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

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

5. Which data structure is used for implementing recursion?

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

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

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. What is a stack data structure? Explain its operations and provide real-world applications.

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

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

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

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

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

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

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

18. 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?

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

20. Which of the following sorting algorithms is stable?

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

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

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

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

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

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

27. 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?

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

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

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

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

32. Explain how to check whether an integer is a power of two using bit manipulation.

33. How to count unique pairs in an array whose XOR equals a given value K? Outline an efficient method.

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

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

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

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

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

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

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

41. What is the key principle behind dynamic programming?

42. Which of the following problems uses Catalan numbers?

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

44. Describe how you would implement an LRU cache with O(1) get and put operations, using hashing and a doubly linked list.

Master Interviews
Anywhere, Anytime