⏱️ 𝑹𝒆𝒂𝒅𝒊𝒏𝒈 𝑻𝒊𝒎𝒆: 9 𝘮𝘪𝘯𝘶𝘵𝘦𝘴 ⚡️

Basic Concepts

1. What is a data structure?
   • A data structure is a way of organizing and storing data to enable efficient access and modification.
2. What are algorithms?
   • Algorithms are step-by-step procedures or formulas for solving problems.
3. What is the difference between an array and a linked list?
   • An array is a collection of elements identified by index, while a linked list consists of nodes where each node points to the next node.
4. What is a stack?
   • A stack is a linear data structure that follows the Last In First Out (LIFO) principle.
5. What is a queue?
   • A queue is a linear data structure that follows the First In First Out (FIFO) principle.

Array Questions

6. How do you reverse an array?
   • Use two pointers: one at the start and one at the end. Swap elements until they meet in the middle.
7. How do you find the maximum and minimum in an array?
   • Iterate through the array, keeping track of the maximum and minimum values found.
8. How do you remove duplicates from an array?
   • Use a hash set to store unique elements or sort the array and then remove duplicates.
9. What is the time complexity to search for an element in a sorted array?
   • O(log n) using binary search.
10. How do you rotate an array to the right by k steps?
    • Reverse the whole array, then reverse the first k elements and finally reverse the remaining elements.

Linked List Questions

11. How do you reverse a linked list?
    • Use three pointers: prev, curr, and next. Adjust the pointers iteratively until you reach the end.
12. How do you detect a cycle in a linked list?
    • Use Floyd’s Tortoise and Hare algorithm. If two pointers meet, a cycle exists.
13. How do you merge two sorted linked lists?
    • Use a dummy node and iterate through both lists, attaching the smaller node to the merged list.
14. How do you find the middle of a linked list?
    • Use two pointers; move one pointer twice as fast as the other. When the fast pointer reaches the end, the slow pointer is at the middle.
15. How do you remove the N-th node from the end of a linked list?
    • Use two pointers; advance the first pointer N nodes ahead, then move both pointers until the first reaches the end.

Stack Questions

16. How do you implement a stack using an array?
    • Use an array to store elements and an integer to keep track of the top index.
17. How do you check for balanced parentheses using a stack?
    • Push opening brackets onto the stack; pop for closing brackets. If the stack is empty at the end, it’s balanced.
18. How do you sort a stack?
    • Use another stack to hold sorted elements; repeatedly pop from the original stack and place elements in order in the second stack.
19. What is the time complexity of stack operations (push, pop, peek)?
    • O(1) for all operations.
20. How do you evaluate a postfix expression using a stack?
    • Use a stack to push operands. On encountering an operator, pop the necessary operands, compute the result, and push it back onto the stack.

Queue Questions

21. How do you implement a queue using two stacks?
    • Use one stack for enqueue and another for dequeue. Transfer elements from the first stack to the second when dequeuing.
22. What is a circular queue?
    • A circular queue connects the end of the queue back to the front, effectively reusing empty spaces.
23. How do you find the first non-repeating character in a stream of characters using a queue?
    • Use a queue to keep track of characters and a hash map to count occurrences. Remove from the queue when a character repeats.
24. What is the time complexity of queue operations (enqueue, dequeue)?
    • O(1) for both operations.
25. How do you implement a priority queue?
    • Use a heap data structure where each element has a priority, allowing retrieval of the highest priority element efficiently.

Tree Questions

26. What is a binary tree?
    • A tree data structure where each node has at most two children, referred to as left and right.
27. How do you traverse a binary tree?
    • Use in-order, pre-order, or post-order traversal methods.
28. How do you find the height of a binary tree?
    • Recursively calculate the height of the left and right subtrees, returning the greater height plus one.
29. What is a binary search tree (BST)?
    • A binary tree where the left child has a smaller value than the parent, and the right child has a larger value.
30. How do you insert a node in a BST?
    • Compare the value with the root; go left if smaller, right if larger, and recursively insert in the appropriate subtree.

Graph Questions

31. What is a graph?
    • A collection of nodes (vertices) and edges connecting them.
32. What are the differences between directed and undirected graphs?
    • In directed graphs, edges have a direction; in undirected graphs, they do not.
33. How do you perform a Depth-First Search (DFS)?
    • Use a stack or recursion to explore as far as possible along each branch before backtracking.
34. How do you perform a Breadth-First Search (BFS)?
    • Use a queue to explore all neighbors at the present depth prior to moving on to nodes at the next depth level.
35. What is Dijkstra’s algorithm?
    • An algorithm for finding the shortest path from a starting node to all other nodes in a graph with non-negative weights.

Sorting Questions

36. What is the time complexity of bubble sort?
    • O(n^2).
37. What is the time complexity of merge sort?
    • O(n log n).
38. How does quicksort work?
    • Select a pivot element, partition the array into elements less than and greater than the pivot, and recursively sort the partitions.
39. What is the difference between merge sort and quicksort?
    • Merge sort is stable and uses additional space, while quicksort is in-place but not stable.
40. What is a stable sorting algorithm?
    • A sorting algorithm that maintains the relative order of equal elements.

Searching Questions

41. What is linear search?
    • A method of finding an element by checking each element sequentially.
42. What is binary search?
    • A method of finding an element in a sorted array by repeatedly dividing the search interval in half.
43. What is the time complexity of binary search?
    • O(log n).
44. How do you find the first and last occurrence of a sorted element?
    • Use binary search to find the first occurrence, and then perform another binary search for the last occurrence.
45. How do you search in a rotated sorted array?
    • Use modified binary search to find the pivot point and determine which half to search.

Hashing Questions

46. What is a hash table?
    • A data structure that implements an associative array, mapping keys to values using a hash function.
47. How do you handle collisions in a hash table?
    • Common methods include chaining (using linked lists) and open addressing (probing).
48. What is the time complexity of searching in a hash table?
    • O(1) on average.
49. What is a hash function?
    • A function that converts an input (or key) into a fixed-size string of bytes.
50. How do you implement a simple hash map?
    • Use an array of linked lists (or buckets) to store key-value pairs.

Dynamic Programming Questions

51. What is dynamic programming?
    • A method for solving complex problems by breaking them down into simpler subproblems and storing their solutions.
52. What is the difference between dynamic programming and recursion?
    • Dynamic programming stores solutions to subproblems to avoid redundant calculations, whereas recursion may solve the same subproblem multiple times.
53. How do you solve the Fibonacci sequence using dynamic programming?
    • Store previously computed Fibonacci numbers in an array to avoid recalculating them.
54. What is the 0/1 Knapsack problem?
    • A problem where you must maximize the value of items in a knapsack without exceeding its weight limit.
55. How do you solve the longest common subsequence problem?
    • Use a 2D array to store lengths of common subsequences and build the solution incrementally.

Miscellaneous Questions

56. What is a trie?
    • A tree-like data structure used to store a dynamic set of strings, allowing for efficient retrieval.
57. What is the difference between a binary tree and a binary search tree?
    • A binary tree has no specific order for nodes, while a binary search tree maintains a specific order based on node values.
58. How do you implement a deque?
    • Use a doubly linked list or a circular array to allow insertion and deletion from both ends.

59. What is a heap?

• A complete binary tree that satisfies the heap property: in a max heap, every parent node is greater than or equal to its child nodes; in a min heap, every parent node is less than or equal to its child nodes.

60. How do you insert an element into a heap?

• Add the element at the end of the heap, then “bubble up” to restore the heap property.

61. How do you delete the root of a heap?

• Replace the root with the last element, then “bubble down” to restore the heap property.

62. What is the time complexity of heap sort?

• O(n log n).

63. How do you find the K-th largest element in an array?

• Use a min heap of size K to keep track of the K largest elements; the root will be the K-th largest.

Advanced Data Structures

64. What is a segment tree?

• A binary tree used for storing intervals or segments, allowing for efficient range queries and updates.

65. What is a Fenwick tree (Binary Indexed Tree)?

• A data structure that provides efficient methods for cumulative frequency tables and range queries.

66. What are disjoint sets (Union-Find)?

• A data structure that keeps track of a partition of a set into disjoint subsets and supports union and find operations.

67. How do you implement a LRU Cache?

• Use a hash map for fast access and a doubly linked list to keep track of the order of usage.

68. What is a bloom filter?

• A space-efficient probabilistic data structure used to test whether an element is a member of a set, allowing false positives but not false negatives.

String Questions

69. How do you reverse a string?

• Convert the string to a list of characters, then swap characters from both ends until the middle is reached.

70. What is the time complexity to check if two strings are anagrams?

• O(n) using a character frequency count.

71. How do you find the longest substring without repeating characters?

• Use a sliding window technique with a hash map to track characters and their indices.

72. What is the Rabin-Karp algorithm?

• A string search algorithm that uses hashing to find any one of a set of pattern strings in a text.

73. How do you perform a substring search using the Knuth-Morris-Pratt (KMP) algorithm?

• Preprocess the pattern to create a longest prefix-suffix (LPS) array, then use this to avoid unnecessary comparisons in the search.

Backtracking Questions

74. What is backtracking?

• A problem-solving approach that incrementally builds candidates for solutions and abandons a candidate as soon as it is determined that it cannot lead to a valid solution.

75. How do you solve the N-Queens problem?

• Use backtracking to place queens on the board, ensuring no two queens threaten each other.

76. How do you generate all permutations of a string?

• Use backtracking to swap characters and build permutations recursively.

77. What is the subset sum problem?

• A problem that asks if there is a subset of a given set with a sum equal to a given target.

78. How do you solve Sudoku using backtracking?

• Attempt to fill the board with valid numbers, backtracking whenever a number placement leads to an invalid state.

Greedy Algorithm Questions

79. What is a greedy algorithm?

• An algorithm that builds up a solution piece by piece, always choosing the next piece that offers the most immediate benefit.

80. What is the activity selection problem?

• A problem where you select the maximum number of activities that don’t overlap, solvable using a greedy approach based on finish times.

81. How do you solve the coin change problem using a greedy algorithm?

• Use the largest denomination coin possible until the amount is reached or cannot be made anymore.

82. What is Kruskal’s algorithm?

• An algorithm to find the minimum spanning tree for a connected graph by sorting edges and adding the smallest edge that doesn’t form a cycle.

83. What is Prim’s algorithm?

• An algorithm for finding a minimum spanning tree by growing the tree one vertex at a time, starting from an arbitrary vertex.

Mathematical Questions

84. How do you calculate the factorial of a number?

• Use recursion or iteration to multiply the number by the factorial of the number minus one.

85. What is the time complexity of calculating Fibonacci numbers recursively?

• O(2^n) due to repeated calculations.

86. How do you find the GCD of two numbers?

• Use Euclid’s algorithm, which involves repeated division.

87. What is the Sieve of Eratosthenes?

• An efficient algorithm to find all prime numbers up to a specified integer by marking the multiples of each prime.

88. How do you check if a number is prime?

• Check divisibility from 2 to the square root of the number.

Miscellaneous Algorithms

89. What is topological sorting?

• An ordering of the vertices in a directed acyclic graph where for every directed edge u → v, vertex u comes before v.

90. How do you find the shortest path in an unweighted graph?

• Use BFS to explore the shortest path from the source to each node.

91. What is the Floyd-Warshall algorithm?

• An algorithm for finding shortest paths in a weighted graph with positive or negative edge weights.

92. How do you detect cycles in a directed graph?

• Use DFS to track visited nodes and check for back edges.

93. How do you find connected components in an undirected graph?

• Use DFS or BFS to explore and mark all vertices connected to a starting vertex.

Problem-Solving Questions

94. How do you solve the problem of finding duplicates in an array?

• Use a hash set to track seen elements or sort the array and look for adjacent duplicates.

95. What is the two-sum problem?

• Finding two numbers in an array that add up to a target sum. Use a hash map for O(n) time complexity.

96. How do you implement binary search?

• Check the middle element; if it’s the target, return its index. If the target is smaller, repeat for the left half, and if larger, repeat for the right half.

97. What is the longest increasing subsequence problem?

• Find the longest subsequence where each element is greater than the previous one. Use dynamic programming to solve it.

98. How do you find the missing number in an array of size n containing numbers from 1 to n?

• Calculate the expected sum and subtract the actual sum of the array to find the missing number.

99. How do you implement an algorithm to find the longest palindrome substring?

• Use dynamic programming or expand around potential centers of the palindrome.

100. What is the maximum subarray problem?

• Use Kadane’s algorithm to find the contiguous subarray with the maximum sum in linear time.