Top 20 DSA Interview Questions

An array stores elements in contiguous memory locations, allowing for fast O(1) random access, but its size is fixed. A linked list consists of nodes scattered in memory that point to each other, allowing for dynamic resizing, but accessing an element takes O(N) time because you must traverse the list.

The most efficient way is to calculate the expected sum of the first N numbers using the formula n(n+1)/2, and then subtract the actual sum of the array's elements. Alternatively, you can use the XOR bitwise operator to find the missing number without worrying about integer overflow.

The problem asks you to find two numbers in an array that add up to a specific target. While a nested loop takes O(N²), the optimal solution uses a HashMap to store elements and their indices as you iterate, bringing the time complexity down to O(N).

Kadane's algorithm is a highly efficient O(N) approach used to find the maximum contiguous subarray sum within a one-dimensional array of numbers.

It is a problem-solving pattern used to optimize algorithms that iterate over contiguous subarrays or substrings. By maintaining a "window" that slides across the data, it reduces nested loops, often dropping time complexity from O(N²) to O(N).

A stack is a linear data structure that operates on the Last In, First Out (LIFO) principle. Common operations are push (add) and pop (remove). It is widely used in undo mechanisms, evaluating mathematical expressions, checking balanced parentheses, and managing recursion.

A queue is a linear data structure that follows the First In, First Out (FIFO) principle, meaning the first element added is the first one removed. Queues are typically used in scenarios like job scheduling and Breadth-First Search (BFS).

You reverse it by iterating through the nodes and changing the next pointer of each node to point to its previous node. You will need three pointers (prev, current, and next) to keep track of the list as you reverse the links.

The most optimal way is the two-pointer technique (Tortoise and Hare algorithm). You use a slow pointer that moves one step at a time and a fast pointer that moves two steps. When the fast pointer reaches the end, the slow pointer will be exactly at the middle node.

Like finding the middle node, you use Floyd's Cycle-Finding Algorithm with a slow and a fast pointer. If the linked list contains a cycle, the fast pointer will eventually loop around and meet the slow pointer.

A binary tree is a hierarchical structure where each node has at most two children. A Binary Search Tree is a specialized version where every node follows a strict rule: the left child's value is smaller than the parent, and the right child's value is larger. This makes searching in a BST highly efficient (O(log N) in a balanced tree).

The primary depth-first traversals are Inorder (Left, Root, Right), Preorder (Root, Left, Right), and Postorder (Left, Right, Root). Level-order (BFS) visits nodes layer by layer and is common for shortest-path style tree problems.

A heap is a specialized tree-based structure that satisfies the heap property (either a Min-Heap or a Max-Heap). It is primarily used to implement priority queues and to efficiently solve "Top K" or "Kth largest/smallest" problems.

A Trie (or prefix tree) is a specialized tree used for efficiently storing and retrieving strings. It is heavily used in spell checkers, dictionary lookups, and autocomplete systems.

Breadth-First Search (BFS) explores a graph level by level and uses a Queue. Depth-First Search (DFS) explores as far as possible down one branch before backtracking, typically using a Stack or recursion.

A HashMap (or hash table) stores data in key-value pairs for rapid lookups. A collision happens when a hash function assigns two different keys to the same index. Collisions are commonly resolved using techniques like chaining (storing a linked list at the index) or open addressing.

Dynamic Programming (DP) is an algorithmic technique for solving complex problems by breaking them into overlapping subproblems. It stores the results of these subproblems (via memoization or tabulation) so they don't have to be recomputed, drastically reducing time complexity.

Recursion happens when a function calls itself to solve smaller instances of the same problem, requiring a base case to avoid infinite loops. Iteration uses loops (like for or while) to repeat a block of code. Recursion can be cleaner to read but consumes more memory due to the call stack.

Time complexity evaluates how the runtime of an algorithm scales as the input size grows. Space complexity evaluates how much extra memory the algorithm requires during execution.

Big O notation is the mathematical standard used to describe the worst-case scenario for time and space complexity. Common examples include O(1) for constant time, O(N) for linear time, and O(log N) for logarithmic time.