Intermediate to advanced questions on arrays, linked lists, trees and common problem-solving techniques.
Arrays
How do you find the missing number in an array of size n containing numbers from 1 to n+1?
Calculate the sum of the first n+1 natural numbers and subtract the sum of the array's elements. The difference is the missing number.
How do you find the duplicate number in an array?
Use a hash set, or treat the array as a linked list and apply Floyd's cycle detection. For arrays holding the numbers 1 to n, negative marking also works.
How do you rotate an array by k positions?
Reverse the whole array, then reverse the first k elements and the last n-k elements. Alternatives are copying into an extra array or using cyclic replacements.
Linked lists
How do you detect a cycle in a linked list?
Use Floyd's cycle detection algorithm (tortoise and hare). Move one pointer a single step at a time and the other two steps. If they ever meet, the list has a cycle.
How do you reverse a singly linked list?
Iteratively, walk the list with three pointers (previous, current, next) and flip each link as you go. Recursively, reverse the rest of the list first, then point the next node back at the current one.
Trees
What is the difference between BFS and DFS traversal in trees?
Breadth-first search (BFS) visits the tree level by level using a queue. Depth-first search (DFS) goes as deep as possible down each branch before backtracking, using a stack or recursion.
How do you find the lowest common ancestor (LCA) of two nodes in a binary tree?
Recurse from the root. If one node is found in the left subtree and the other in the right, the current node is the LCA. Otherwise, the LCA lies in whichever subtree returned a match.
Techniques
Explain the two-pointer technique with an example.
Two pointers reduce time complexity by scanning from two positions at once. To find a pair in a sorted array that sums to a target, start one pointer at each end and move them inwards depending on whether the sum is too small or too large.
Explain Kadane's algorithm for maximum subarray sum.
Kadane's algorithm uses dynamic programming to find the contiguous subarray with the largest sum in O(n) time. It tracks the best sum ending at the current element and the best sum seen overall.
What is the sliding window technique?
A sliding window replaces nested loops with a single O(n) pass. You keep a window of elements and move it across the array, updating the result as elements enter and leave. It suits subarray and substring problems.
Related: JavaScript coding interview questions, Java interview questions and hire software developers.

