Question 1

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

Accepted Answer

You can find the missing number by calculating the sum of the first (n+1) natural numbers and subtracting the sum of the elements in the array.

Question 2

How do you detect a cycle in a linked list?

Accepted Answer

You can use Floyd’s Cycle Detection Algorithm (Tortoise and Hare). Use two pointers—one moves one step at a time, the other two. If they meet, there's a cycle.

Question 3

What is the difference between BFS and DFS traversal in trees?

Accepted Answer

BFS (Breadth-First Search) traverses level-by-level using a queue. DFS (Depth-First Search) explores as far as possible along each branch before backtracking, using a stack or recursion.

Question 4

Explain the two-pointer technique with an example.

Accepted Answer

The two-pointer technique is used to reduce time complexity. For example, in a sorted array, to find a pair that sums to a target, use one pointer at the start and one at the end.

Question 5

How do you find the lowest common ancestor (LCA) of two nodes in a binary tree?

Accepted Answer

Traverse the tree from the root. If one node is found in the left subtree and the other in the right, current node is LCA. Use recursion to check subtrees.

Question 6

How do you find the duplicate number in an array?

Accepted Answer

You can use Floyd's cycle detection (treating array as linked list) or hash set. For arrays with numbers 1..n, you can also use negative marking.

Question 7

Explain the Kadane’s algorithm for maximum subarray sum.

Accepted Answer

Kadane’s algorithm uses dynamic programming to find the contiguous subarray with the largest sum in O(n) time by maintaining current max and global max.

Question 8

What is the sliding window technique?

Accepted Answer

Sliding window is used to reduce nested loops to O(n) by maintaining a window of elements and moving it across the array. Useful for subarray/substring problems.

Question 9

How do you rotate an array by k positions?

Accepted Answer

You can reverse the entire array, then reverse first k and last n-k elements. Alternatively, use extra array or cyclic replacements.

Question 10

How do you reverse a singly linked list?

Accepted Answer

Iteratively, use three pointers to reverse links. Recursively, reverse the rest and adjust pointers.

Data Structures Interview Questions & Answers

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

How do you detect a cycle in a linked list?

What is the difference between BFS and DFS traversal in trees?

Explain the two-pointer technique with an example.

How do you find the lowest common ancestor (LCA) of two nodes in a binary tree?

How do you find the duplicate number in an array?

Explain the Kadane’s algorithm for maximum subarray sum.

What is the sliding window technique?

How do you rotate an array by k positions?

How do you reverse a singly linked list?

How do you find the middle of a linked list?

How do you merge two sorted linked lists?

How do you perform an inorder traversal without recursion?

How do you check if a binary tree is a binary search tree?

What is the diameter of a binary tree?

How do you serialize and deserialize a binary tree?

Explain the concept of dynamic programming with an example.

What is the time complexity of quicksort?

What is the difference between merge sort and quicksort?

Explain the concept of backtracking with an example.

Prepare for Your Next Interview