Q1. What is a data structure, and why is it important?
Answer: A data structure is a way of organizing and storing data so it can be accessed and modified efficiently. Choosing the right data structure improves the time and memory efficiency of a program.
Q2. Differentiate between linear and non-linear data structures.
Answer:
Q3. What is an Abstract Data Type (ADT)?
Answer: An ADT defines the data and operations available on it without specifying their implementation. For example, a stack ADT supports push, pop, and peek, regardless of whether it is implemented using an array or linked list.
Q4. Explain the difference between time complexity and space complexity.
Answer:
Q5. What is the difference between O(n), Ω(n), and Θ(n)?
Answer:
Q6. Arrange the following complexities from most efficient to least efficient for sufficiently large n: O(n²), O(1), O(log n), O(n log n), O(n).
Answer:
O(1) < O(log n) < O(n) < O(n log n) < O(n²).
Q7. What is an algorithm, and what properties should a good algorithm have?
Answer: An algorithm is a finite sequence of well-defined steps for solving a problem. A good algorithm should have clearly defined inputs and outputs, unambiguous steps, correctness, finiteness, and reasonable time and space requirements.
Q8. What is recursion, and what is its main disadvantage?
Answer: Recursion occurs when a function calls itself to solve smaller instances of a problem. Its main disadvantage is additional function-call overhead and stack memory usage, which can lead to stack overflow for deep recursion.
Q9. What is the difference between an iterative and a recursive algorithm?
Answer: An iterative algorithm uses loops to repeat operations, while a recursive algorithm calls itself. Iteration often uses less auxiliary memory, while recursion can provide a simpler solution for naturally recursive problems such as tree traversal.
Q10. If an algorithm performs 3n² + 5n + 10 operations, what is its asymptotic time complexity?
Answer: Θ(n²) because the quadratic term dominates as n becomes large.
Q11. Why does accessing an array element by index generally take O(1) time?
Answer: Array elements occupy contiguous memory locations. The address of an element can be calculated directly from the base address, index, and element size.
Q12. What is the time complexity of inserting an element at the beginning of an array containing n elements?
Answer: O(n) because existing elements generally must be shifted one position to the right.
Q13. An array contains [4, 7, 2, 9, 5]. What is the minimum number of comparisons needed to find the maximum using a standard linear scan?
Answer: 4 comparisons. The first element is the initial maximum, and each of the remaining four elements is compared with it.
Q14. What is the difference between a one-dimensional array and a two-dimensional array?
Answer: A one-dimensional array stores elements along one index, while a two-dimensional array organizes elements using two indices, commonly representing rows and columns.
Q15. What is a sparse matrix, and why is special storage useful for it?
Answer: A sparse matrix contains mostly zero elements. Storing only nonzero values and their positions can reduce memory usage compared with storing every element.
Q16. A 100 × 100 matrix contains only 150 nonzero elements. How many zero elements does it contain?
Answer: The matrix contains 10,000 total elements.
Zero elements = 10,000 − 150 = 9,850.
Q17. What is the time complexity of searching for a value in an unsorted array of n elements?
Answer: O(n) in the worst case because every element may need to be examined.
Q18. How can two arrays be merged efficiently when both are already sorted?
Answer: Use two pointers, one for each array. Compare the pointed-to elements, append the smaller element, and advance its pointer. Continue until one array is exhausted, then append the remaining elements.
For arrays of sizes n and m, the time complexity is O(n + m).
Q19. What is the difference between a static array and a dynamic array?
Answer: A static array generally has a fixed size, whereas a dynamic array can grow or shrink as needed. Dynamic arrays may occasionally require resizing and copying elements.
Q20. What is the time complexity of deleting an element from the middle of an array?
Answer: O(n) in the worst case because subsequent elements usually must be shifted to fill the gap.
Q21. What is a linked list, and how does it differ from an array?
Answer: A linked list consists of nodes containing data and links to other nodes. Unlike an array, its nodes need not occupy contiguous memory locations. Linked lists support efficient insertion and deletion when the relevant node or position is already known.
Q22. What is the time complexity of inserting a node at the beginning of a singly linked list?
Answer: O(1) because the new node points to the current head, and the head is updated.
Q23. Why is accessing the kth element of a singly linked list O(n) in the worst case?
Answer: A singly linked list does not provide direct indexed access. The list must be traversed from the head until the kth node is reached.
Q24. What is the difference between singly and doubly linked lists?
Answer:
A doubly linked list supports backward traversal but requires additional memory.
Q25. What is a circular linked list?
Answer: A circular linked list is a linked list in which the final node points back to the first node rather than to NULL.
Q26. How can you detect a cycle in a linked list using O(1) auxiliary space?
Answer: Use Floyd's cycle-detection algorithm, also called the slow-and-fast pointer method. Move one pointer one step at a time and another two steps at a time. If they meet, a cycle exists. If the fast pointer reaches NULL, there is no cycle.
Q27. How can a singly linked list be reversed iteratively?
Answer: Maintain three pointers: previous, current, and next. For each node, save the next node, point the current node backward, and advance the pointers. Finally, set the head to the previous pointer.
Time complexity: O(n). Auxiliary space: O(1).
Q28. What is the time complexity of deleting a node from a singly linked list when only its pointer is given?
Answer: If it is a non-tail node, its data and next pointer can be replaced using the next node's contents, allowing O(1) deletion in typical implementations. This technique cannot be used for the tail node, and it changes which physical node represents the data.
Q29. How can you find the middle node of a singly linked list in one traversal?
Answer: Use slow and fast pointers. Move the slow pointer one node and the fast pointer two nodes at a time. When the fast pointer reaches the end, the slow pointer is at the middle.
Q30. What is the main disadvantage of a linked list compared with an array?
Answer: Linked lists do not provide O(1) indexed access, require extra memory for pointers, and often have poorer cache locality than arrays.
Q31. What is a stack, and what principle does it follow?
Answer: A stack is a linear data structure that follows LIFO (Last In, First Out). The most recently inserted element is removed first.
Q32. What are the basic operations of a stack and their typical time complexities?
Answer:
push: O(1)pop: O(1)peek or top: O(1)These complexities assume a suitable implementation and no costly resizing operation.
Q33. How can a stack be used to check whether parentheses are balanced?
Answer: Scan the expression from left to right. Push each opening bracket onto the stack. For each closing bracket, check whether the top contains the matching opening bracket. Reject the expression if no match exists. At the end, the expression is balanced only if the stack is empty.
Q34. Convert the infix expression A + B * C into postfix notation.
Answer: A B C * +
Multiplication has higher precedence than addition, so B * C is evaluated first.
Q35. Evaluate the postfix expression 5 3 2 * + 4 -.
Answer:
3 * 2 = 65 + 6 = 1111 - 4 = 7Result: 7
Q36. What is a queue, and what principle does it follow?
Answer: A queue follows FIFO (First In, First Out). The first element inserted is the first element removed.
Q37. What is the difference between a stack and a queue?
Answer: A stack inserts and removes elements at the same end, following LIFO. A queue typically inserts at the rear and removes from the front, following FIFO.
Q38. Why is a circular queue more space-efficient than a simple array-based queue in some implementations?
Answer: A circular queue reuses positions freed by earlier deletions. This avoids wasting the beginning portion of an array when the rear reaches the end.
Q39. What is a deque?
Answer: A deque, or double-ended queue, allows insertion and deletion at both the front and rear.
Q40. What is a priority queue, and how is it different from a normal queue?
Answer: A priority queue removes elements according to their priority rather than strictly according to insertion order. A normal FIFO queue removes the earliest inserted element first.
Q41. What is a tree in data structures?
Answer: A tree is a hierarchical, non-linear data structure consisting of nodes connected by edges. In a rooted tree, each node other than the root has one parent.
Q42. What is the difference between a binary tree and a binary search tree (BST)?
Answer: A binary tree allows each node to have at most two children without requiring a particular ordering. A BST follows an ordering rule: values in the left subtree are smaller than the node's value, and values in the right subtree are larger, subject to the implementation's duplicate-key policy.
Q43. What is the maximum number of nodes at level L of a binary tree when the root is at level 0?
Answer: The maximum is 2^L.
For example, level 4 can contain at most 16 nodes.
Q44. What is the maximum number of nodes in a binary tree of height h when height is measured in edges?
Answer: For a tree with root height h, the maximum number of nodes is:
2^(h + 1) − 1
This occurs when every level is completely filled.
Q45. What is the difference between a full, complete, and perfect binary tree?
Answer:
Q46. What are the three main depth-first traversal methods for binary trees?
Answer:
Q47. Given a BST with keys 50, 30, 70, 20, 40, 60, and 80, what is its inorder traversal?
Answer: 20, 30, 40, 50, 60, 70, 80
Inorder traversal of a BST with distinct keys produces sorted order.
Q48. What is the average and worst-case search complexity of a BST?
Answer:
Q49. What is an AVL tree?
Answer: An AVL tree is a self-balancing BST in which the height difference between the left and right subtrees of every node is at most one. Rotations restore balance after insertions and deletions.
Q50. What are the four AVL tree imbalance cases?
Answer:
Q51. Why do AVL trees provide efficient searching?
Answer: AVL balancing keeps the tree height O(log n), so searching, insertion, and deletion take O(log n) time in the worst case.
Q52. What is a red-black tree?
Answer: A red-black tree is a self-balancing BST whose nodes have red or black colors. Its color and black-height rules restrict the tree's height, ensuring O(log n) worst-case search, insertion, and deletion.
Q53. How does a red-black tree differ from an AVL tree?
Answer: AVL trees enforce stricter height balance, which can make searches particularly efficient. Red-black trees allow somewhat looser balance and often require fewer rotations during updates. Both provide O(log n) worst-case operations.
Q54. What is a B-tree, and where is it commonly used?
Answer: A B-tree is a balanced multiway search tree in which nodes can store multiple keys and have multiple children. It is commonly used in databases and file systems because it reduces the number of disk accesses needed for searching.
Q55. What is the difference between a B-tree and a B+ tree?
Answer: In a B-tree, records or associated data may be stored in internal nodes as well as leaves. In a B+ tree, records are typically stored at the leaves, while internal nodes primarily store separator keys. B+ tree leaves are commonly linked to support efficient range queries.
Q56. Why are B-trees suitable for external-memory storage?
Answer: Their high branching factor reduces tree height, allowing many keys to be processed per disk page and reducing the number of disk I/O operations.
Q57. What is a heap, and what is the heap-order property?
Answer: A heap is a complete binary tree that satisfies a heap-order property:
Q58. What is the difference between a heap and a binary search tree?
Answer: A heap maintains a parent-child priority relationship and efficiently exposes its minimum or maximum. A BST maintains an ordering between left and right subtrees, allowing ordered searching. A heap does not generally support efficient searching for arbitrary values.
Q59. What is the time complexity of inserting an element into a binary heap?
Answer: O(log n) in the worst case, because the new element may move from a leaf to the root.
Q60. What is the time complexity of building a binary heap from an unsorted array using bottom-up heap construction?
Answer: O(n). Although an individual heap insertion takes O(log n), bottom-up heap construction takes linear time overall.
Q61. What is a graph, and what are its main components?
Answer: A graph consists of vertices, also called nodes, and edges connecting pairs of vertices.
Q62. What is the difference between a directed and an undirected graph?
Answer: In a directed graph, edges have direction. In an undirected graph, edges represent bidirectional relationships without a specified direction.
Q63. What is the difference between an adjacency matrix and an adjacency list?
Answer:
Here, V is the number of vertices and E is the number of edges.
Q64. What is Breadth-First Search (BFS), and which data structure does it use?
Answer: BFS explores a graph level by level, visiting nearby vertices before more distant ones. It uses a queue.
Q65. What is Depth-First Search (DFS), and which data structure does it use?
Answer: DFS explores as far as possible along a path before backtracking. It can be implemented using recursion or an explicit stack.
Q66. What are the time complexities of BFS and DFS using an adjacency list?
Answer: Both take O(V + E) time when each vertex and edge is processed a constant number of times.
Q67. How can BFS be used to find the shortest path in an unweighted graph?
Answer: Run BFS from the source and record each vertex's distance and predecessor when it is first discovered. The resulting distances give shortest-path lengths measured in number of edges.
Q68. What is a minimum spanning tree (MST)?
Answer: An MST of a connected, weighted, undirected graph is a spanning tree that connects all vertices with the minimum possible total edge weight. It contains exactly V − 1 edges.
Q69. What is the difference between Prim's and Kruskal's algorithms?
Answer:
Q70. Why is a disjoint-set data structure useful in Kruskal's algorithm?
Answer: It efficiently tracks which vertices belong to the same connected component. The find operation checks component membership, and union merges components. This helps determine whether adding an edge would create a cycle.
Q71. What is linear search, and what is its worst-case time complexity?
Answer: Linear search examines elements one by one until the target is found or the collection ends. Its worst-case time complexity is O(n).
Q72. What condition is required for standard binary search to work correctly?
Answer: The collection must be sorted according to the order used by the search algorithm.
Q73. What is the worst-case time complexity of binary search?
Answer: O(log n) because each comparison reduces the remaining search interval to approximately half its previous size.
Q74. A sorted array contains 1,024 elements. Approximately how many halvings are required to reduce the search interval to one element?
Answer: 10 halvings, because 2¹⁰ = 1,024. A particular search may use fewer comparisons depending on the target and implementation.
Q75. What is the difference between iterative and recursive binary search?
Answer: Iterative binary search uses a loop, while recursive binary search calls itself on the appropriate half of the search interval. Both take O(log n) time, but iterative binary search typically uses O(1) auxiliary space, while recursive binary search uses O(log n) call-stack space.
Q76. What is the worst-case time complexity of bubble sort?
Answer: O(n²). Bubble sort repeatedly compares adjacent elements and swaps them when they are out of order.
Q77. What is the difference between selection sort and insertion sort?
Answer: Selection sort repeatedly finds the minimum element in the unsorted portion and places it next. Insertion sort inserts each new element into its correct position within the already-sorted portion. Both have O(n²) worst-case time complexity, but insertion sort can be efficient on nearly sorted data.
Q78. What is the best-case time complexity of optimized bubble sort?
Answer: O(n) when the array is already sorted and the implementation stops after a pass with no swaps.
Q79. Explain merge sort and its time complexity.
Answer: Merge sort divides the array into smaller halves, recursively sorts them, and merges the sorted halves. Its best-, average-, and worst-case time complexity is O(n log n). Standard array-based implementations generally require O(n) auxiliary space.
Q80. Explain quicksort and its worst-case time complexity.
Answer: Quicksort selects a pivot, partitions elements around it, and recursively sorts the partitions. Its average time complexity is O(n log n), but its worst-case time complexity is O(n²) when partitions are repeatedly highly unbalanced.
Q81. What is the difference between a stable and an unstable sorting algorithm?
Answer: A stable sort preserves the relative order of elements with equal keys. An unstable sort does not guarantee that order.
Q82. Which sorting algorithm is generally preferred when guaranteed O(n log n) worst-case time and stability are required?
Answer: Merge sort is a common choice because it is stable in its standard implementation and has O(n log n) worst-case time complexity.
Q83. What is heap sort, and what is its time complexity?
Answer: Heap sort builds a heap and repeatedly removes the maximum or minimum element to produce sorted order. It has O(n log n) best-, average-, and worst-case time complexity and can sort an array in place with O(1) auxiliary space in a standard implementation.
Q84. What is the main idea behind counting sort?
Answer: Counting sort counts occurrences of each key and uses those counts to place elements in sorted order. It is useful when keys are integers from a reasonably small range. Its time and space requirements depend on the number of elements and the key range.
Q85. Compare the worst-case time complexities of merge sort, quicksort, and heap sort.
Answer:
Quicksort commonly performs well in practice, but its standard form does not guarantee O(n log n) worst-case time.
Q86. What is hashing in data structures?
Answer: Hashing uses a hash function to map a key to an index in a hash table. It enables efficient insertion, searching, and deletion when collisions are handled appropriately.
Q87. What is a hash collision?
Answer: A collision occurs when two different keys map to the same hash-table index.
Q88. What is separate chaining?
Answer: Separate chaining handles collisions by storing multiple entries at the same table index, often in a linked list or another collection.
Q89. What is open addressing?
Answer: Open addressing handles collisions by finding another available slot within the hash table. Common methods include linear probing, quadratic probing, and double hashing.
Q90. What is the load factor of a hash table?
Answer: The load factor is the ratio of the number of stored entries to the number of table slots.
Load factor = Number of stored entries / Table capacity
For example, 75 entries in a table with 100 slots gives a load factor of 0.75.
Q91. What is the expected search time in a well-designed hash table, and what is the worst case?
Answer: Expected search time is often O(1) under suitable assumptions about hashing and load factor. The worst case is O(n) if many keys collide or probing becomes highly inefficient.
Q92. Why might a hash table need resizing?
Answer: As more entries are inserted, the load factor increases and collisions can become more frequent. Resizing increases the table capacity and typically redistributes entries using the hash function.
Q93. In a max-heap, where is the maximum element located, and how long does it take to access it?
Answer: The maximum element is at the root. Accessing it takes O(1) time.
Q94. What is the time complexity of deleting the root of a binary heap?
Answer: O(log n) in the worst case. After removing the root, the last element is moved to the root and sifted down to restore the heap property.
Q95. How can a priority queue be implemented using a binary heap?
Answer: Store the elements in a binary heap. Insertion adds an element and sifts it upward; removal extracts the root and restores the heap property by sifting downward. These operations typically take O(log n) time.
Q96. Which data structure is most appropriate for implementing an undo operation in a text editor, and why?
Answer: A stack is appropriate because the most recent operation is usually the first one to be undone. Each new action can be pushed onto a stack, and undo removes the latest action.
Q97. Which data structure is suitable for processing tasks in arrival order?
Answer: A queue is suitable because it follows FIFO order, processing the earliest-arriving task first.
Q98. A program repeatedly needs to retrieve the smallest element from a changing collection. Which data structure is a good choice?
Answer: A min-heap is a good choice. It provides O(1) access to the minimum and typically supports insertion and removal of the minimum in O(log n) time.
Q99. Suppose a graph is disconnected. Can Prim's algorithm produce a spanning tree containing every vertex?
Answer: No. A disconnected graph has no spanning tree connecting all its vertices. Running Prim's algorithm separately on its connected components can produce a minimum spanning forest instead.
Q100. You must choose a sorting algorithm for a large dataset. The algorithm must guarantee O(n log n) worst-case time and use little additional memory. Which algorithm is a suitable choice?
Answer: Heap sort is a suitable choice because it guarantees O(n log n) worst-case time and can sort an array in place using O(1) auxiliary space. The trade-off is that it is not stable in its standard form.
These questions cover the topics in your DS Tutorial, including arrays, linked lists, stacks, queues, trees, AVL trees, B-trees, graphs, sorting, searching, hashing, and heaps. The questions emphasize algorithm analysis, edge cases, and problem-solving rather than basic definitions.
Q1. An algorithm has the recurrence \(T(n)=2T(n/2)+n\log n\). Find its asymptotic time complexity.
Answer: Using the Master Theorem, \(a=2\), \(b=2\), and \(n^{\log_b a}=n\). Since \(f(n)=n\log n\), this is the second Master Theorem case with an extra logarithmic factor.
Q2. Solve the recurrence \(T(n)=T(n-1)+n\), where \(T(1)=1\).
Answer:
Therefore, \(T(n)=\Theta(n^2)\).
Q3. An algorithm executes an outer loop n times and an inner loop that doubles its counter each iteration. Find its complexity.
Answer: The inner loop takes \(\Theta(\log n)\) iterations. Since it runs for each of the n outer iterations, the total complexity is \(\Theta(n\log n)\).
Q4. Is \(3^n\) asymptotically smaller than \(n!\)?
Answer: Yes. For sufficiently large n, factorial growth exceeds exponential growth with any fixed base. Therefore,
Q5. An algorithm uses O(n) auxiliary memory but O(n²) time. Is it necessarily less efficient than an algorithm using O(n log n) time and O(n²) memory?
Answer: No. Efficiency depends on the requirements. The first algorithm uses less additional memory but more time; the second is faster asymptotically but consumes more memory. The appropriate choice depends on input size and resource constraints.
Q6. What is the complexity of the recurrence \(T(n)=3T(n/2)+n^2\)?
Answer: Here, \(n^{\log_2 3}\) grows more slowly than \(n^2\). The non-recursive work dominates, so by the Master Theorem:
Q7. Why can two algorithms with the same O(n log n) complexity have very different execution times?
Answer: Big-O ignores constant factors and lower-order terms. Actual performance also depends on memory access patterns, cache locality, implementation overhead, input distribution, and hardware.
Q8. What is the worst-case complexity of the recurrence \(T(n)=T(n/2)+1\)?
Answer: Each recursive call halves the input, giving approximately \(\log_2 n\) calls. Therefore, \(T(n)=\Theta(\log n)\).
Q9. A program performs n operations, then n/2, then n/4, and continues halving the number of operations. Find its complexity.
Answer:
This geometric series is bounded by a constant multiple of n. The complexity is \(\Theta(n)\).
Q10. Can an algorithm have O(1) time complexity while processing an arbitrary-length input?
Answer: It can perform a constant-time operation on an input of arbitrary length, but it generally cannot inspect every element of that input in O(1) time. Complexity depends on what the algorithm must accomplish and what input information it needs to examine.
Q11. An array contains n distinct integers from 1 to n+1, with one number missing. Design an O(n)-time, O(1)-auxiliary-space solution.
Answer: Compute the expected sum and subtract the actual sum:
Time complexity: O(n). Auxiliary space: O(1). For very large values, use a sufficiently wide integer type to prevent overflow.
Q12. How can you find all duplicate values in an array of n integers in O(n) expected time?
Answer: Use a hash set. Scan the array once; if a value is already present, report it as a duplicate. Otherwise, insert it. Expected time is O(n), with O(n) auxiliary space.
Q13. An n × n matrix is stored in row-major order. What is the memory offset of element \(A[i][j]\), assuming zero-based indices and element size s?
Answer:
If the base address is \(B\), its address is \(B+(in+j)s\).
Q14. How can you rotate an n × n matrix 90 degrees clockwise in place?
Answer: First transpose the matrix, then reverse every row.
Transpose: swap \(A[i][j]\) with \(A[j][i]\) for \(i<j\).
Reverse each row.
Time complexity: O(n²). Auxiliary space: O(1), excluding temporary storage for individual swaps.
Q15. How can two sorted arrays of sizes n and m be merged without using an additional array?
Answer: One approach for arrays that must remain separately stored is to use a gap-based method. Compare elements separated by a decreasing gap across the combined logical sequence, swapping out-of-order pairs until the gap reaches zero. This can use O(1) auxiliary space but typically takes more time than the standard O(n+m)-space merge.
Q16. How can a matrix be represented efficiently when it contains very few nonzero elements?
Answer: Use a sparse representation that stores only nonzero values and their row and column indices. A coordinate-list representation stores triples of the form (row, column, value), reducing storage when the number of nonzero entries is much smaller than the total number of cells.
Q17. How do you find the maximum sum of a contiguous subarray in O(n) time?
Answer: Use Kadane's algorithm. Maintain the maximum sum ending at the current position and the best sum found overall:
Update the global maximum at every step. The algorithm takes O(n) time and O(1) auxiliary space.
Q18. Why does binary search fail on an unsorted array?
Answer: Binary search discards half of the search interval based on the assumption that elements are ordered. Without that ordering, the target may be in the discarded half, so the algorithm is not correct.
Q19. Given an array and a target sum, how can you determine whether two distinct elements add up to the target in expected O(n) time?
Answer: Maintain a hash set of previously seen values. For each value x, check whether target − x is already in the set. If it is, a pair exists; otherwise, insert x.
Q20. What is the difference between prefix sums and a segment tree for range-sum queries?
Answer: Prefix sums provide O(1) range-sum queries after O(n) preprocessing, but changing one array element generally requires updating O(n) prefix sums. A segment tree supports range-sum queries and point updates in O(log n) time, with O(n) storage.
Q21. How can you determine whether a linked list is a palindrome in O(n) time and O(1) auxiliary space?
Answer: Find the midpoint with slow and fast pointers. Reverse the second half, compare corresponding elements from both halves, and restore the reversed portion if required. Time complexity is O(n), with O(1) auxiliary space.
Q22. How can you find the starting node of a cycle in a linked list?
Answer: First use slow and fast pointers to detect a meeting point. If they meet, move one pointer to the head while leaving the other at the meeting point. Advance both one node at a time. Their next meeting point is the cycle's starting node.
Q23. How can two sorted singly linked lists be merged into one sorted list in O(n+m) time?
Answer: Maintain pointers to both lists and repeatedly attach the smaller current node to the output list. When one list ends, attach the remaining nodes from the other. Reusing existing nodes requires only O(1) auxiliary pointer space.
Q24. Why is deleting a node from a singly linked list more difficult than deleting one from a doubly linked list?
Answer: In a singly linked list, deleting a node generally requires access to its predecessor so that the predecessor can point to the next node. A doubly linked list stores a previous pointer, allowing the neighboring links to be updated directly when the node is known.
Q25. How can you determine whether two singly linked lists intersect by node identity?
Answer: Find their lengths, advance the pointer in the longer list by the length difference, and then advance both pointers together. If they reach the same node object, the lists intersect. If both reach NULL, they do not.
Q26. Can two singly linked lists with different head pointers share a common tail?
Answer: Yes. They can share a tail if they eventually point to the same node object. From that node onward, their links are shared.
Q27. How can you reverse a linked list in groups of size k?
Answer: Traverse each group, reverse its links, connect the previous group's tail to the new group head, and connect the group's original head to the next group. The treatment of a final group smaller than k depends on the problem specification.
Time complexity: O(n). Auxiliary space can be O(1) for an iterative implementation.
Q28. Why is a linked list not usually the best data structure for binary search?
Answer: Binary search requires efficient access to the middle element of each search interval. A linked list must traverse nodes to reach the middle, so repeatedly locating middle elements destroys the usual O(log n) time advantage.
Q29. What is the time complexity of deleting the last node from a singly linked list when only the head pointer is available?
Answer: O(n) in the general case, because the list must be traversed to find the second-to-last node.
Q30. How can a circular linked list be traversed without entering an infinite loop?
Answer: Save the starting node and stop when traversal returns to it. Unlike a non-circular list, a circular list does not necessarily terminate at NULL.
Q31. How can you implement a queue using two stacks so that enqueue is amortized O(1) and dequeue is amortized O(1)?
Answer: Use an input stack and an output stack. Enqueue pushes onto the input stack. For dequeue, if the output stack is empty, transfer all input elements to it, reversing their order, and then pop the output stack. Each element is transferred at most once, giving amortized O(1) per operation.
Q32. How can you evaluate an infix arithmetic expression containing parentheses and operator precedence?
Answer: Use two stacks: one for operands and one for operators. Push operands, manage parentheses, and apply operators according to precedence and associativity. A closing parenthesis triggers operations until the matching opening parenthesis is reached.
Q33. What is the time complexity of finding the next greater element for every element in an array using a monotonic stack?
Answer: O(n). Each element is pushed and popped at most once, so the total number of stack operations is linear.
Q34. What is a monotonic stack, and when is it useful?
Answer: A monotonic stack maintains elements in increasing or decreasing order. It is useful for next-greater-element problems, next-smaller-element problems, stock-span calculations, and finding certain histogram or range boundaries.
Q35. How can a stack support retrieving its minimum element in O(1) time?
Answer: Maintain an auxiliary stack of minimums. Whenever an element is pushed that is no larger than the current minimum, push it onto the minimum stack too. When that element is popped from the main stack, pop it from the minimum stack as well.
Q36. What is the difference between a circular queue and a deque?
Answer: A circular queue reuses array positions by wrapping indices around the end. A deque allows insertion and deletion at both ends. These describe different properties, so a deque can also be implemented using circular storage.
Q37. How can a queue be used to perform level-order traversal of a binary tree?
Answer: Enqueue the root. Repeatedly dequeue a node, visit it, and enqueue its existing children. The queue processes nodes in level order.
Q38. Why is a queue used in BFS rather than a stack?
Answer: A queue processes vertices in the order they are discovered, allowing BFS to explore distance layers in increasing order. A stack instead drives depth-first exploration.
Q39. How can you check whether a sequence of push and pop operations is valid for a stack?
Answer: Simulate the operations. Push the specified values and, for every pop, verify that the stack is nonempty and its top matches the expected value. The sequence is valid only if every operation is legal and the required output sequence is produced.
Q40. What is the worst-case time complexity of converting an infix expression of length n to postfix notation using an operator stack?
Answer: O(n), assuming each token is processed a constant number of times and each operator is pushed and popped at most once.
Q41. A binary tree has 31 nodes and is perfect. What is its height when height is measured in edges?
Answer: For a perfect binary tree,
Thus \(2^{h+1}=32=2^5\), so \(h=4\).
Q42. Can preorder and inorder traversals uniquely determine a binary tree?
Answer: Yes, when node values are distinct. The preorder traversal identifies the root, and inorder identifies the left and right subtrees. With duplicate values, the traversals may not uniquely determine the tree without additional information.
Q43. Can preorder and postorder traversals uniquely determine an arbitrary binary tree?
Answer: Not in general. For example, a single-child node can be interpreted as having its child on either the left or right. Additional constraints, such as the tree being full and values being distinct, can make reconstruction possible.
Q44. Why does inorder traversal of a BST produce sorted keys?
Answer: The BST ordering property places all keys in the left subtree before the root and all keys in the right subtree after it. Inorder traversal visits left subtree, root, then right subtree, producing nondecreasing order when duplicates are allowed by the implementation's policy.
Q45. How can you verify whether a binary tree is a valid BST?
Answer: Traverse the tree while maintaining valid lower and upper bounds for each node. A node must satisfy both bounds, and the bounds are updated as traversal proceeds into the left or right subtree. This takes O(n) time.
Q46. What is the worst-case height of an unbalanced BST containing n nodes?
Answer: n − 1 edges, occurring when the tree is completely skewed. Its search complexity can therefore degrade to O(n).
Q47. How can you find the lowest common ancestor (LCA) of two nodes in a BST?
Answer: Starting from the root, if both target values are smaller, move left. If both are larger, move right. Otherwise, the current node is their lowest common ancestor, assuming both targets exist in the tree.
Q48. How can you find the kth smallest element in a BST?
Answer: Perform an inorder traversal, counting visited nodes. The kth visited node is the kth smallest key. A full traversal takes O(n); if the tree is balanced, traversal can stop earlier when the kth node is reached.
Q49. How can a BST be converted into a sorted doubly linked list?
Answer: Perform an inorder traversal and link each node to its predecessor and successor. The result is sorted because inorder traversal visits BST keys in order. An in-place implementation can use O(h) recursion stack space, where h is the tree height.
Q50. Why can deleting a node with two children from a BST be more complicated than deleting a leaf?
Answer: A leaf can simply be removed. A node with two children must be replaced by its inorder successor or predecessor, after which that replacement node must be removed from its original location while preserving BST ordering.
Q51. What is the balance factor of a node in an AVL tree?
Answer:
For a valid AVL tree, the balance factor of every node must be −1, 0, or +1.
Q52. When inserting a key into an AVL tree, how do you identify the required rotation?
Answer: Identify the first unbalanced ancestor after insertion:
LL: right rotation.
RR: left rotation.
LR: left rotation on the left child, then right rotation.
RL: right rotation on the right child, then left rotation.
Q53. Why do AVL trees guarantee O(log n) search time?
Answer: AVL balancing ensures that the minimum number of nodes in a tree of height h grows exponentially with h. Consequently, the height is O(log n), making search, insertion, and deletion O(log n) in the worst case.
Q54. Why might a red-black tree be preferred over an AVL tree in some applications?**
Answer: Red-black trees permit looser balance and may require fewer rotations during updates. Both support O(log n) worst-case search, insertion, and deletion, but the preferred choice depends on the workload and implementation.
Q55. What properties prevent a red-black tree from becoming a linear chain?**
Answer: Its coloring rules prohibit red nodes from having red children, require the same black-height on all paths from a node to its descendant NIL leaves, and constrain the root and leaf sentinels. These rules keep the height logarithmic.
Q56. What is the role of node splitting in a B-tree?**
Answer: When a node exceeds its allowed number of keys, it is split around a median key. The median is promoted to the parent, which may itself split if it overflows. This process preserves B-tree balance.
Q57. Why are B+ trees particularly suitable for range queries?**
Answer: Their records are stored at the leaves, and leaf nodes are commonly linked in key order. After locating the first matching key, the database can scan successive leaf nodes to retrieve a range efficiently.
Q58. What is the maximum number of children of an order-m B-tree under the common maximum-children definition of order?**
Answer: m children, with at most m − 1 keys in a node. Minimum occupancy requirements depend on whether the node is the root and on the precise B-tree convention being used.
Q59. How does the height of a B-tree compare with the height of a binary search tree?
Answer: A B-tree stores multiple keys and has many children per node, so it generally has a much smaller height than a binary tree with the same number of keys. This reduces the number of node accesses and disk I/O operations.
Q60. What happens if deleting a key causes a B-tree node to fall below its minimum occupancy?
Answer: The tree attempts to redistribute keys from a sibling through the parent. If redistribution is impossible, it merges nodes and moves a separator key down from the parent. The repair can propagate upward and may reduce the tree height.
Q61. Why does BFS find shortest paths in an unweighted graph but not necessarily in a weighted graph?
Answer: BFS minimizes the number of edges in a path. In an unweighted graph, every edge has equal cost, so minimizing edge count also minimizes path cost. In a weighted graph, a path with fewer edges may have a larger total weight.
Q62. What is the time complexity of BFS on an adjacency matrix?
Answer: O(V²) in the usual implementation because scanning a vertex's row takes O(V) time, and this may be done for each vertex.
Q63. How can you detect a cycle in an undirected graph using DFS?
Answer: Track visited vertices and each vertex's parent. If DFS encounters a visited neighbor that is not the current vertex's parent, a cycle exists. This assumes the standard undirected adjacency representation.
Q64. How can you detect a cycle in a directed graph using DFS?
Answer: Track the current recursion path using three states: unvisited, active, and finished. An edge to an active vertex indicates a directed cycle.
Q65. What is topological sorting, and when is it possible?
Answer: Topological sorting orders the vertices of a directed graph so every edge goes from an earlier vertex to a later vertex. It is possible only for a directed acyclic graph (DAG).
Q66. How can Kahn's algorithm perform topological sorting?
Answer: Calculate each vertex's indegree. Enqueue all vertices with indegree zero, repeatedly remove one and append it to the order, then decrement the indegree of its outgoing neighbors. If fewer than V vertices are processed, the graph contains a directed cycle.
Q67. What is the difference between a minimum spanning tree and a shortest-path tree?**
Answer: A minimum spanning tree minimizes the total weight of edges connecting all vertices. A shortest-path tree preserves shortest paths from a designated source. They solve different optimization problems and need not be the same tree.
Q68. Why can Kruskal's algorithm be implemented efficiently using a disjoint-set union structure?**
Answer: Disjoint-set union supports near-constant amortized component operations when path compression and union by rank or size are used. This helps detect cycles while processing sorted edges.
Q69. What is the time complexity of Kruskal's algorithm?**
Answer: Typically O(E log E), dominated by sorting the E edges. The disjoint-set operations add a near-linear total cost.
Q70. When can Prim's algorithm and Kruskal's algorithm produce different minimum spanning trees?
Answer: When the graph has multiple valid MSTs, different tie-breaking choices can produce different trees with the same minimum total weight. If the MST is unique, both algorithms produce that same tree.
Q71. Why is binary search O(log n), even though the array may contain millions of elements?
Answer: Each comparison approximately halves the remaining search interval. After k steps, the interval is approximately \(n/2^k\). Reducing it to one element requires roughly \(\log_2 n\) steps.
Q72. What is the worst-case time complexity of quicksort, and why does it occur?
Answer: O(n²). It occurs when the pivot repeatedly produces highly unbalanced partitions, such as one element on one side and nearly all remaining elements on the other.
Q73. How does randomized quicksort reduce the likelihood of worst-case behavior?**
Answer: Randomly selecting the pivot makes consistently poor partitions unlikely for many input arrangements. Its expected running time is O(n log n), although its theoretical worst case remains O(n²).
Q74. Why is merge sort often preferred for linked lists over array-based quicksort?**
Answer: Linked lists can be split and merged by adjusting pointers without requiring random access. Merge sort offers O(n log n) time and can use O(1) auxiliary node storage for iterative linked-list implementations, excluding any fixed temporary pointers.
Q75. Is comparison-based sorting possible in o(n log n) worst-case time for arbitrary distinct keys?**
Answer: No. In the comparison model, sorting arbitrary distinct keys requires \(\Omega(n\log n)\) comparisons in the worst case. Non-comparison sorts can beat this bound under additional assumptions about the keys.
Q76. What is the main limitation of counting sort?
Answer: Its memory and time requirements depend on the range of keys, not only the number of elements. If the key range is extremely large relative to n, counting sort may be impractical.
Q77. Why is heap sort not stable in its standard array implementation?**
Answer: Heap construction and repeated root replacement can move equal-key elements past one another, changing their relative order. Additional mechanisms would be needed to guarantee stability.
Q78. Which sorting algorithm is often most efficient for nearly sorted arrays, and why?**
Answer: Insertion sort is often efficient because elements move only short distances when the array is nearly sorted. Its best-case time is O(n), though its worst case is O(n²).
Q79. What is the difference between internal and external sorting?**
Answer: Internal sorting is performed when the data fits in main memory. External sorting handles datasets too large to fit in memory and uses external storage, often merging sorted runs to reduce disk I/O.
Q80. Why is merge sort suitable for external sorting?
Answer: It supports sequential processing and merging of sorted runs. External merge sort can process large files by sorting manageable chunks in memory and merging them in passes.
Q81. What is the load factor of a hash table, and why does it matter?**
Answer: The load factor is the number of stored entries divided by the number of table slots. In many implementations, a high load factor increases collisions and may reduce performance.
Q82. How does linear probing handle collisions, and what is primary clustering?**
Answer: Linear probing checks successive table positions until it finds a suitable slot. Primary clustering occurs when long consecutive runs of occupied slots form, causing further collisions and longer probe sequences.
Q83. How does double hashing reduce clustering compared with linear probing?**
Answer: Double hashing uses a second hash function to determine the probe step size. Different keys can therefore follow different probe sequences, reducing primary clustering when the functions are chosen well.
Q84. Why must a hash-table deletion sometimes use a tombstone instead of clearing a slot?**
Answer: In open addressing, clearing a slot can prematurely terminate a later search for a key that lies further along its probe sequence. A tombstone marks the slot as deleted while allowing searches to continue.
Q85. What makes a hash function suitable for a hash table?**
Answer: It should distribute keys uniformly across the table, be inexpensive to compute, and behave consistently for equal keys. The quality needed depends on the expected key distribution and collision strategy.
Q86. Why is a hash table not always guaranteed to provide O(1) search time?**
Answer: O(1) is generally an expected or average-case claim under suitable assumptions. Poor hash distribution, heavy collisions, or an excessive load factor can cause operations to degrade to O(n).
Q87. What is rehashing?**
Answer: Rehashing creates a larger or otherwise redesigned table and reinserts existing keys, typically using the new table capacity in the hash computation. It helps restore efficient operation as the table grows.
Q88. Why does deleting the root from a binary heap take O(log n) time?
Answer: After removing the root, the final element is moved to the root. It may then need to move down the height of the heap to restore heap order. A complete binary tree has height O(log n).
Q89. How can a priority queue efficiently support repeated extraction of the minimum element?**
Answer: Use a min-heap. The minimum is at the root and can be accessed in O(1) time; extracting it takes O(log n), making repeated minimum extraction efficient.
Q90. What is the difference between a binary heap and a balanced BST for priority-queue operations?**
Answer: A binary heap provides O(1) access to the minimum or maximum and O(log n) insertion and root extraction. A balanced BST supports O(log n) insertion, deletion, and search, and can also find the minimum or maximum in O(log n) worst-case time, or O(1) if the appropriate extreme node is maintained.
Q91. Given a stream of integers, how can you maintain the kth largest element seen so far?
Answer: Maintain a min-heap of size k. Insert each new value; if the heap grows beyond k, remove the minimum. Once k elements have been seen, the root is the kth largest element. Each update takes O(log k) time.
Q92. How can you find the median of a stream of integers efficiently?
Answer: Use two heaps:
A max-heap for the lower half.
A min-heap for the upper half.
Balance their sizes so they differ by at most one. The median is the root of the larger heap when the count is odd, or the average of both roots when the count is even. Each insertion takes O(log n).
Q93. How can you find the shortest path in a weighted graph with nonnegative edge weights?**
Answer: Use Dijkstra's algorithm. Maintain tentative distances from the source and repeatedly finalize the unprocessed vertex with the smallest tentative distance. A min-priority queue can improve efficiency.
Q94. Why does Dijkstra's algorithm fail to guarantee correct results when negative-weight edges are present?**
Answer: It assumes that once a vertex with the smallest tentative distance is finalized, no later path can improve that distance. A negative edge can violate this assumption. Bellman–Ford is suitable for graphs with negative edges, provided there is no relevant reachable negative cycle when finite shortest distances are required.
Q95. What is the time complexity of Dijkstra's algorithm using an adjacency list and a binary heap?**
Answer: A common implementation takes O((V + E) log V) time, often written as O(E log V) for connected graphs with E at least V − 1.
Q96. How can you detect a negative-weight cycle reachable from a source vertex?**
Answer: Run Bellman–Ford for V − 1 rounds of edge relaxation. Then scan all edges once more. If any distance can still be reduced through a reachable edge, a reachable negative-weight cycle exists.
Q97. What is the difference between a connected component and a strongly connected component?**
Answer: In an undirected graph, a connected component is a maximal set of vertices connected by paths. In a directed graph, a strongly connected component is a maximal set where every vertex can reach every other vertex by directed paths.
Q98. How can you determine whether an undirected graph is a tree?**
Answer: A graph is a tree if it is connected and has no cycles. For a simple undirected graph with V vertices, an equivalent test is that it is connected and has exactly V − 1 edges.
Q99. A connected undirected graph has V vertices and V − 1 edges. Must it be a tree?**
Answer: Yes, assuming a standard simple undirected graph. A connected graph with V − 1 edges cannot contain a cycle, because removing an edge from a cycle would leave it connected with fewer than V − 1 edges, which is impossible for a connected graph.
Q100. You need to design a system that supports frequent insertions, deletions, ordered traversal, and finding the minimum and maximum. Which data structure would you choose, and why?**
Answer: A balanced BST, such as an AVL tree or red-black tree, is a strong choice. It supports search, insertion, and deletion in O(log n) worst-case time, and inorder traversal produces keys in sorted order in O(n) time. The minimum and maximum can be found in O(log n) time, or O(1) if pointers to the extreme nodes are maintained.