All topics
Data Structures and Algorithms Interview Questions & Answers
40 questions with detailed answers — for freshers and experienced candidates.
Want to actually learn Data Structures and Algorithms?
Join a hands-on mini internship or training on iCampusLink and earn a certificate.
Explore programs →Fresher Level
Q1. What is an array, and what are its main characteristics?
An array is a fundamental linear data structure that stores a fixed-size sequential collection of elements of the same data type. Its main characteristics include: direct access to elements using an index (O(1) time complexity), contiguous memory allocation, and a fixed size determined at the time of creation. Elements are stored in adjacent memory locations, which contributes to efficient cache utilization. While insertion/deletion in the middle can be O(N) due to shifting, accessing elements by index is very fast. Arrays are foundational for many other data structures.
Q2. Explain Big O notation and its importance in algorithm analysis.
Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. In algorithm analysis, it's used to classify algorithms according to how their running time or space requirements grow as the input size grows. It provides an upper bound on the growth rate, ignoring constant factors and lower-order terms. Understanding Big O helps developers choose the most efficient algorithm for a given problem, especially for large datasets, by predicting performance without running the code and comparing different approaches.
Q3. What is a linked list? How does it differ from an array?
A linked list is a linear data structure where elements are not stored at contiguous memory locations. Instead, each element (node) consists of two parts: data and a pointer (or reference) to the next node in the sequence. This structure allows for dynamic memory allocation. The main differences from an array are: arrays have fixed size and contiguous memory, allowing O(1) random access but O(N) insertion/deletion in the middle. Linked lists have dynamic size, non-contiguous memory, O(N) random access, but O(1) insertion/deletion if the position of insertion/deletion is known.
Q4. Explain the concept of a stack and its primary operations.
A stack is a linear data structure that follows the Last-In, First-Out (LIFO) principle. Imagine a stack of plates: you can only add a plate to the top, and you can only remove the topmost plate. Its primary operations are: `push` (adds an element to the top of the stack), `pop` (removes and returns the topmost element), and `peek` (returns the topmost element without removing it). Stacks are commonly used for function call management, expression evaluation (e.g., converting infix to postfix), and implementing undo/redo functionalities in applications.
Q5. What is a queue, and what are its primary operations?
A queue is a linear data structure that follows the First-In, First-Out (FIFO) principle. Think of a line of people waiting: the first person in line is the first to be served. Its primary operations are: `enqueue` (adds an element to the rear of the queue), `dequeue` (removes and returns the element from the front of the queue), and `front` or `peek` (returns the front element without removing it). Queues are widely used in scenarios like task scheduling, breadth-first search (BFS) in graphs, managing requests in web servers, and buffering data streams.
Q6. Describe binary search. What are its prerequisites?
Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, the algorithm narrows the interval to the lower half. Otherwise, it narrows it to the upper half. This process continues until the value is found or the interval is empty. The crucial prerequisite for binary search is that the input array or list *must be sorted*. If the data is not sorted, binary search cannot be applied correctly, leading to incorrect results.
Q7. What is a binary tree?
A binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child. Unlike arrays or linked lists, trees are non-linear. The topmost node is called the root. Nodes without children are called leaf nodes. Binary trees are fundamental for various applications, including expression parsing, binary search trees (BSTs), and heaps. The structure allows for efficient searching, insertion, and deletion operations in many cases, often with logarithmic time complexity, provided the tree remains relatively balanced.
Q8. Explain the concept of Bubble Sort. Is it efficient?
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. Each pass 'bubbles up' the largest unsorted element to its correct position. While easy to understand and implement, Bubble Sort is generally inefficient for large datasets. Its average and worst-case time complexity is O(N^2), making it much slower than more advanced sorting algorithms like Merge Sort or Quick Sort. It is rarely used in practical applications.
Q9. What is recursion? Provide a simple example.
Recursion is a programming technique where a function calls itself directly or indirectly to solve a problem. A recursive function solves a problem by breaking it down into smaller, identical subproblems until it reaches a base case, which is a simple condition that can be solved without further recursion. Each recursive call builds up a stack frame, and once the base case is hit, the results unwind back up the stack. For example, calculating factorial(n): `def factorial(n): if n == 0 or n == 1: return 1 else: return n * factorial(n - 1)`. It often leads to elegant and concise code but can be less efficient due to overhead and potential for stack overflow if not handled carefully with appropriate base cases.
Q10. What is a hash table (or hash map), and what is its primary use?
A hash table is a data structure that implements an associative array abstract data type, mapping keys to values. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found. The primary use of hash tables is for efficient lookups, insertions, and deletions. On average, these operations take O(1) time complexity, making them extremely fast for retrieving data when the key is known. They are widely used in databases, caches, symbol tables in compilers, and for implementing dictionaries or maps in programming languages.
Q11. Explain the Two-Pointer technique and give an example of where it might be useful.
The Two-Pointer technique is a common algorithmic pattern that involves using two pointers (indices or references) to iterate through a data structure, typically an array or linked list, from different positions or at different speeds. This technique is highly efficient as it often reduces time complexity from O(N^2) to O(N). It's particularly useful for problems involving sorted arrays, finding pairs, or reversing sequences. For example, to find if a sorted array contains two numbers that sum up to a target, one pointer can start at the beginning and the other at the end, moving inward based on the sum.
Q12. How would you reverse a string in-place?
Reversing a string in-place typically means modifying the original string (or character array) without using extra space proportional to the input size. This can be achieved using a two-pointer approach. One pointer starts at the beginning of the string (e.g., `left`), and the other starts at the end (`right`). The characters at these two pointers are swapped, and then both pointers move towards the center (one increments, one decrements) until they meet or cross each other. For example: `def reverse_string_inplace(s_list): left, right = 0, len(s_list) - 1; while left < right: s_list[left], s_list[right] = s_list[right], s_list[left]; left += 1; right -= 1; return s_list`. This process ensures O(N) time complexity and O(1) auxiliary space, making it very memory-efficient.
Intermediate Level
Q1. Describe how to detect a cycle in a singly linked list.
A common and efficient way to detect a cycle in a singly linked list is using Floyd's Cycle-Finding Algorithm, also known as the "tortoise and hare" algorithm. This method uses two pointers, a "slow" pointer and a "fast" pointer. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If there is a cycle in the linked list, the fast pointer will eventually catch up to and meet the slow pointer within the cycle. If the fast pointer reaches the end of the list (None), then there is no cycle. This approach has O(N) time complexity and O(1) space complexity.
Q2. Explain the difference between DFS (Depth-First Search) and BFS (Breadth-First Search) for traversing a tree or graph.
DFS and BFS are two fundamental graph traversal algorithms. DFS explores as far as possible along each branch before backtracking. It typically uses a stack (or recursion, which uses the call stack) to keep track of nodes to visit. Common DFS traversals for trees include pre-order, in-order, and post-order. BFS explores all the neighbor nodes at the present depth level before moving on to nodes at the next depth level. It typically uses a queue to manage nodes to visit, ensuring nodes are visited level by level. DFS is good for pathfinding or detecting cycles, while BFS is optimal for finding the shortest path in an unweighted graph.
Q3. Describe Merge Sort. What is its time complexity?
Merge Sort is an efficient, comparison-based, divide-and-conquer sorting algorithm. It works by recursively dividing an unsorted list into two halves until it has n sublists, each containing one element (which is considered sorted). Then, it repeatedly merges these sublists to produce new sorted sublists until there is only one sorted list remaining. The key operation is the merging step, where two sorted sublists are combined into a single sorted list. Merge Sort has a time complexity of O(N log N) in all cases (best, average, worst), making it very reliable for large datasets. It uses O(N) auxiliary space due to the merging process.
Q4. Describe Quick Sort. What is its average-case time complexity, and why is it often preferred over Merge Sort in practice?
Quick Sort is an efficient, in-place, comparison-based sorting algorithm that uses a divide-and-conquer strategy. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted. Its average-case time complexity is O(N log N). While its worst-case is O(N^2), it's often preferred over Merge Sort in practice due to its generally better constant factors and O(log N) average-case space complexity (for recursion stack), making it faster in many real-world scenarios, especially for in-place sorting where memory is a concern.
Q5. What is a Heap data structure? Describe its two main types.
A heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the value of P is either greater than or equal to (Max Heap) or less than or equal to (Min Heap) the value of C. Heaps are typically implemented as complete binary trees, often stored in an array, allowing for efficient access to the root (max or min element) in O(1) time. The two main types are: 1. **Max Heap**: The value of each node is greater than or equal to its children. The root contains the maximum element. 2. **Min Heap**: The value of each node is less than or equal to its children. The root contains the minimum element. Heaps are crucial for priority queues and heap sort.
Q6. How can a graph be represented in memory? Discuss adjacency matrix vs. adjacency list.
Graphs can be represented in memory primarily using two ways: 1. **Adjacency Matrix**: A 2D array `matrix[V][V]`, where `V` is the number of vertices. `matrix[i][j]` is 1 (or weight) if there's an edge from `i` to `j`, and 0 (or infinity) otherwise. It's good for dense graphs (many edges) and checking for edge existence (O(1)). Space complexity is O(V^2). 2. **Adjacency List**: An array of lists (or vectors). `adj[i]` contains a list of all vertices adjacent to vertex `i`. It's efficient for sparse graphs (few edges) and iterating over neighbors (O(degree(V))). Space complexity is O(V + E), where E is the number of edges. Adjacency list is generally preferred for most algorithms due to its lower space complexity for sparse graphs and better performance for traversing neighbors.
Q7. Explain the concept of Dynamic Programming. What are its two key characteristics?
Dynamic Programming (DP) is an algorithmic technique for solving complex problems by breaking them down into simpler subproblems. It solves each subproblem only once and stores their solutions to avoid recomputation, a process known as memoization (top-down) or tabulation (bottom-up). Its two key characteristics are: 1. **Optimal Substructure**: An optimal solution to the problem can be constructed from optimal solutions of its subproblems. 2. **Overlapping Subproblems**: The same subproblems are encountered multiple times when solving the larger problem. DP is highly effective for optimization problems where a choice at each step affects future states, such as the Fibonacci sequence, shortest path problems, or knapsack problems.
Q8. What is a Binary Search Tree (BST)? What are its advantages and disadvantages?
A Binary Search Tree (BST) is a special type of binary tree where for every node: 1. All keys in the left subtree are less than the key of the node. 2. All keys in the right subtree are greater than the key of the node. 3. Both the left and right subtrees are also BSTs. **Advantages**: Efficient search, insertion, and deletion operations (average O(log N)). Can easily retrieve elements in sorted order (in-order traversal). **Disadvantages**: In the worst-case (e.g., inserting elements in sorted order), a BST can degrade into a linked list, leading to O(N) time complexity for operations. It doesn't guarantee balance, which is addressed by self-balancing BSTs like AVL or Red-Black trees.
Q9. How would you find the maximum subarray sum (Kadane's Algorithm)?
Kadane's Algorithm efficiently solves the maximum subarray sum problem, which asks to find the contiguous subarray within a one-dimensional array of numbers that has the largest sum. The algorithm iterates through the array, maintaining two variables: `max_so_far` (the maximum sum found globally) and `current_max` (the maximum sum ending at the current position). At each element, `current_max` is updated to be the maximum of the current element itself or the current element plus the previous `current_max`. Then, `max_so_far` is updated if `current_max` is greater. For example: `def max_subarray_sum(nums): max_so_far = nums[0]; current_max = nums[0]; for i in range(1, len(nums)): current_max = max(nums[i], current_max + nums[i]); max_so_far = max(max_so_far, current_max); return max_so_far`. This approach guarantees O(N) time complexity, making it highly efficient.
Q10. Explain how to implement an algorithm to check if a string is an anagram of another string.
Two strings are anagrams if they contain the same characters with the same frequencies, regardless of order. A common approach to check for anagrams is to use character count arrays or hash maps. First, check if the lengths of both strings are equal; if not, they cannot be anagrams. Then, iterate through the first string, incrementing the count for each character in a frequency map/array. Subsequently, iterate through the second string, decrementing counts. If at any point a character's count drops below zero, or if any character's final count is not zero, they are not anagrams. For instance: `from collections import Counter; def are_anagrams(s1, s2): if len(s1) != len(s2): return False; counts = Counter(s1); for char in s2: if counts[char] == 0: return False; counts[char] -= 1; return all(c == 0 for c in counts.values())`. This method has a time complexity of O(N) where N is the length of the strings, and O(1) space for a fixed-size alphabet array.
Q11. Describe the "Sliding Window" technique. When is it useful?
The Sliding Window technique is an optimization algorithmic pattern, typically used on arrays or lists, to find a subarray or sub-string in a given array/string that satisfies certain conditions. It involves maintaining a "window" (a range of elements) that slides over the data. The window can be of fixed size or variable size, expanding or shrinking based on the problem's constraints. It's useful for problems that involve finding optimal substructures (e.g., longest, shortest, or maximum sum of a contiguous subarray/substring) within a linear data structure, effectively reducing nested loop complexities (often O(N^2)) to a single pass (O(N)).
Q12. Explain backtracking. How does it relate to recursion?
Backtracking is a general algorithmic technique for finding all (or some) solutions to computational problems, particularly constraint satisfaction problems. It incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly lead to a valid solution. It's essentially a refined brute-force search. Backtracking is inherently recursive; each recursive call explores a new path or choice, and if that path leads to a dead end or invalid state, the function returns, effectively "backtracking" to the previous decision point to try another path. Common problems include N-Queens, Sudoku solver, and finding permutations/combinations.
Q13. What is Dijkstra's algorithm, and what is its purpose? What are its limitations?
Dijkstra's algorithm is a greedy algorithm used to find the shortest paths between nodes in a graph, specifically from a single source node to all other nodes, provided that all edge weights are non-negative. It works by maintaining a set of visited nodes and a set of distances from the source to all other nodes. It repeatedly selects the unvisited node with the smallest known distance from the source, marks it as visited, and updates the distances of its neighbors. **Purpose**: To find the shortest path in a weighted graph. **Limitations**: It cannot handle graphs with negative edge weights. For such cases, algorithms like Bellman-Ford or SPFA are required.
Q14. Explain what a Trie (Prefix Tree) is and its main applications.
A Trie, also known as a prefix tree, is a tree-like data structure used to store a dynamic set or associative array where keys are usually strings. Unlike a binary search tree, nodes in a trie do not store the key directly; instead, the position of a node in the tree defines the key associated with it. Each node typically stores a map of characters to child nodes, and a flag indicating if it marks the end of a word. **Applications**: 1. **Autocomplete/Predictive Text**: Efficiently find words with a given prefix. 2. **Spell Checker**: Quickly check if a word exists and suggest corrections. 3. **IP Routing**: Store IP addresses for longest prefix matching. Its main advantage is fast prefix-based search, often O(L) where L is the length of the key, independent of the number of keys.
Q15. What is a greedy algorithm? Provide an example where it works and one where it fails.
A greedy algorithm is an algorithmic paradigm that makes the locally optimal choice at each stage with the hope of finding a global optimum. It doesn't reconsider past choices. For problems exhibiting optimal substructure and the greedy choice property, a greedy approach can yield the globally optimal solution. **Example (Works): Coin Change Problem (with standard denominations)**: To make change for an amount using the fewest coins, a greedy strategy (always pick the largest denomination coin less than or equal to the remaining amount) works for standard coin systems (e.g., 1, 5, 10, 25 cents). **Example (Fails): Coin Change Problem (with non-standard denominations)**: If denominations are {1, 3, 4} and the target is 6. Greedy would pick 4, then 1, then 1 (total 3 coins). Optimal is 3, 3 (total 2 coins).
Q16. How can you determine if a number is a power of two using bit manipulation?
A positive integer is a power of two if and only if it has exactly one bit set to '1' in its binary representation. For example, 8 is `1000` (binary), 16 is `10000`. A clever bit manipulation trick to check this is `(n > 0) and ((n & (n - 1)) == 0)`. Here's why it works: - If `n` is a power of two, its binary representation is `1` followed by `k` zeros (e.g., `1000`). - `n - 1` would be `k` ones (e.g., `0111`). - Performing a bitwise AND (`&`) operation between `n` and `n - 1` will result in `0` because there are no common set bits. The `n > 0` check handles the case where `n` is 0 or negative.
Q17. Given a sorted array, remove duplicates in-place such that each unique element appears only once.
This problem can be solved efficiently using a two-pointer approach. One pointer, say `i` (the "write" pointer), tracks the position where the next unique element should be placed. The other pointer, say `j` (the "read" pointer), iterates through the array. If `nums[j]` is different from `nums[i]`, it means we've found a new unique element. In this case, we increment `i` and then assign `nums[j]` to `nums[i]`. If `nums[j]` is the same as `nums[i]`, we simply increment `j` to skip the duplicate. For example: `def remove_duplicates(nums): if not nums: return 0; i = 0; for j in range(1, len(nums)): if nums[j] != nums[i]: i += 1; nums[i] = nums[j]; return i + 1`. The process continues until `j` reaches the end. The final `i + 1` gives the length of the new array. This operates in O(N) time and O(1) space.
Advanced Level
Q1. Explain Prim's algorithm for finding the Minimum Spanning Tree (MST).
Prim's algorithm is a greedy algorithm that finds a Minimum Spanning Tree (MST) for a connected, undirected weighted graph. It starts with an arbitrary vertex and grows the MST one edge at a time. At each step, it adds the cheapest edge that connects a vertex in the growing MST to a vertex outside the MST, ensuring no cycles are formed. This process continues until all vertices are included in the MST. A min-priority queue is typically used to efficiently select the minimum-weight edge, leading to a time complexity of O(E log V) or O(E + V log V) depending on the priority queue implementation (e.g., Fibonacci heap for the latter).
Q2. Explain Bellman-Ford algorithm. When would you use it over Dijkstra's?
Bellman-Ford algorithm finds the shortest paths from a single source vertex to all other vertices in a weighted digraph. Unlike Dijkstra's, it can handle graphs with negative edge weights. It works by repeatedly relaxing all edges `|V|-1` times, where `|V|` is the number of vertices. In each relaxation, it checks if the path to a neighbor can be shortened by going through the current vertex. After `|V|-1` iterations, all shortest paths are found. A final `|V|`-th iteration is used to detect negative-weight cycles. **Use over Dijkstra's**: When the graph contains negative edge weights. If a negative cycle is detected, it means a shortest path is undefined (can be infinitely small).
Q3. Explain the 0/1 Knapsack problem and how Dynamic Programming solves it.
The 0/1 Knapsack problem involves selecting a subset of items, each with a weight and a value, to fit into a knapsack with a maximum weight capacity, such that the total value of selected items is maximized. The "0/1" signifies that each item can either be taken entirely (1) or not at all (0); fractional items are not allowed. Dynamic Programming solves this using a 2D table `dp[i][w]`, where `dp[i][w]` represents the maximum value that can be obtained using the first `i` items with a knapsack capacity of `w`. The recurrence relation considers whether to include the current item or not. The time and space complexity are O(N * W), where N is the number of items and W is the knapsack capacity.
Q4. What is the purpose of self-balancing binary search trees (e.g., AVL, Red-Black Trees)?
Self-balancing binary search trees (like AVL trees and Red-Black trees) address the primary disadvantage of standard Binary Search Trees (BSTs): the potential for degradation into a skewed tree (like a linked list) in worst-case insertion/deletion scenarios. When a BST becomes skewed, operations like search, insertion, and deletion degrade from an average O(log N) to O(N). Self-balancing BSTs automatically maintain a balanced structure by performing rotations and color changes (in Red-Black trees) after insertions or deletions. This ensures that the height of the tree remains logarithmic (O(log N)), guaranteeing O(log N) time complexity for all major operations (search, insert, delete) even in the worst case. They are crucial for implementing efficient map/set data structures and databases.
Q5. Explain the Disjoint Set Union (DSU) data structure and its common applications.
The Disjoint Set Union (DSU) data structure, also known as Union-Find, manages a collection of disjoint sets. It provides two primary operations: 1. **Find (or `findSet`)**: Determines which set a particular element belongs to (by returning a representative element of that set). 2. **Union (or `unionSets`)**: Merges two sets into a single set. DSU typically uses a forest of trees, where each tree represents a set and the root of the tree is the set's representative. Path compression and union by rank/size optimizations are used to achieve near-constant amortized time complexity (inverse Ackermann function, α(N)) for both operations. **Applications**: 1. **Kruskal's Algorithm**: For finding the Minimum Spanning Tree. 2. **Connected Components**: Determining connected components in an undirected graph. 3. **Network Connectivity**: Checking if two nodes are connected.
Q6. What is the maximum flow problem, and what algorithm is commonly used to solve it?
The maximum flow problem aims to find the maximum possible flow from a source node to a sink node in a flow network, where each edge has a capacity. A flow network is a directed graph where each edge has a non-negative capacity and a flow amount, and flow must satisfy capacity constraints (flow <= capacity) and conservation of flow (total flow into a node equals total flow out, except for source and sink). The most common algorithm to solve this is the **Edmonds-Karp algorithm**, which is a specific implementation of the Ford-Fulkerson method. It repeatedly finds an augmenting path (a path from source to sink with available capacity) in the residual graph using BFS and increases the flow along that path until no more augmenting paths can be found. Its time complexity is O(VE^2).
Q7. Explain the "Divide and Conquer" paradigm. Provide an example beyond sorting algorithms.
Divide and Conquer is an algorithmic paradigm that involves three steps: 1. **Divide**: Break the problem into smaller subproblems of the same type. 2. **Conquer**: Solve these subproblems recursively. If the subproblem is small enough, solve it directly (base case). 3. **Combine**: Combine the solutions of the subproblems to solve the original problem. This approach often leads to efficient algorithms, especially when the subproblems are independent. **Example (beyond sorting): Closest Pair of Points problem.** Given 'n' points in a 2D plane, find the pair with the smallest distance. Divide: Split points into two halves. Conquer: Recursively find closest pair in each half. Combine: Find min distance, then consider points in a narrow strip around the dividing line, sorted by y-coordinate, for straddling pairs. This yields an O(N log N) solution.
Q8. When would you use a Segment Tree or Fenwick Tree (BIT)?
Both Segment Trees and Fenwick Trees (Binary Indexed Trees or BITs) are advanced data structures used for efficiently handling range queries and point updates on an array. **Segment Tree**: A binary tree for storing information about intervals. Each node represents an interval. Supports: Range Query (sum, min, max in [L, R]) in O(log N) and Point Update in O(log N). It's more flexible for complex range queries. **Fenwick Tree (BIT)**: A more compact and faster data structure for specific range queries, primarily prefix sums. Supports: Prefix Sum Query (sum from 0 to `i`) in O(log N) and Point Update in O(log N). Range sum queries [L, R] are derived from prefix sums. **Use Case**: When you need to perform many range queries and point updates on an array, these trees provide logarithmic time complexity, significantly outperforming naive O(N) approaches.
Q9. Compare recursion and iteration in terms of performance and memory usage.
Both recursion and iteration can solve problems involving repetition, but they differ significantly in performance and memory. **Recursion**: - **Performance**: Can be slower due to function call overhead (stack frame creation, saving/restoring registers). - **Memory**: Uses more memory as each recursive call adds a new stack frame to the call stack. Deep recursion can lead to stack overflow errors. - **Readability**: Often leads to more elegant and concise code for problems with inherent recursive structure (e.g., tree traversals). **Iteration**: - **Performance**: Generally faster as it avoids function call overhead. - **Memory**: Uses less memory as it typically reuses the same memory space for loop variables. No risk of stack overflow. - **Readability**: Can sometimes be less intuitive or require more complex logic for problems naturally suited for recursion. While recursion can be elegant, iteration is usually preferred for performance-critical applications or when dealing with very large inputs to avoid stack limits.
Q10. Explain different techniques for collision resolution in hash tables.
Collision resolution is crucial in hash tables when two different keys hash to the same index. Two primary techniques are: 1. **Separate Chaining**: Each slot in the hash table array points to a linked list that contains all key-value pairs hashing to that index. Collisions are handled by adding to the list. Pros: Simple, flexible, degrades gracefully. Cons: Extra memory for pointers, potential list traversal. 2. **Open Addressing**: All key-value pairs are stored directly in the array. When a collision occurs, the algorithm probes for the next available empty slot. Methods include Linear Probing (sequential search, suffers from primary clustering), Quadratic Probing (quadratic steps, reduces primary but introduces secondary clustering), and Double Hashing (uses a second hash function for step size, best distribution). Pros: Better cache performance, no extra pointer memory. Cons: Table can fill, complex deletion, sensitive to load factor.
Q11. What is topological sorting, and what are its applications?
Topological sorting is a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge `u -> v`, vertex `u` comes before vertex `v` in the ordering. It's only possible for DAGs; graphs with cycles cannot be topologically sorted. Two common algorithms are Kahn's Algorithm (BFS-based) and a DFS-based algorithm. **Applications**: 1. **Scheduling Tasks**: Ordering tasks based on dependencies (e.g., build systems, course prerequisites). 2. **Course Scheduling**: Determining the order in which courses must be taken. 3. **Compilation Process**: Ordering modules for compilation based on their dependencies. 4. **Data Serialization**: Ordering objects to be serialized based on their inter-dependencies to ensure correct reconstruction.
Prepared by iCampusLink. 40 Data Structures and Algorithms interview questions.