15 Essential Data Structures and Algorithms (DSA) Coding Interview Questions by Category Quiz

Explore five must-know DSA interview questions in arrays, strings, and linked lists to sharpen your programming fundamentals. This quiz covers diverse topics that routinely appear in coding interviews.

1. Two Sum Problem

   Given an array of integers and a target value, what is the most efficient approach to determine if any two distinct numbers add up to the target?

   1. Sort the array and perform a linear search for each element
   2. Count the frequency of each number then check for pairs
   3. Use a hash set to track complements while iterating through the array
   4. Use nested loops to try all pairs

   Explanation: Using a hash set allows you to check in constant time if the complement of the current number has been seen, resulting in O(n) time complexity. Sorting with linear search is slower (O(n log n) + O(n^2)). Nested loops try all pairs in O(n^2) time, which is inefficient. Counting frequencies works only for counting pairs, not finding indices or handling all edge cases.

2. Longest Substring Without Repeating Characters

   Which technique efficiently finds the length of the longest substring without repeating characters in a string?

   1. Binary search for substring lengths
   2. Counting character frequencies with an array
   3. Recursion with memoization
   4. Sliding window with a hash map

   Explanation: A sliding window combined with a hash map is optimal for tracking repeated characters and expanding or shrinking the window appropriately, achieving O(n) time. Recursion and memoization are unnecessary for this linear problem. A frequency array does not track window position. Binary search does not suit problems needing contiguous scans.

3. Reverse a Linked List

   What is the standard in-place algorithm to reverse a singly linked list?

   1. Iteratively change the next pointers to previous nodes
   2. Insert nodes into a stack and rebuild the list
   3. Sort the nodes and reconnect them
   4. Recursively traverse until the end and rewire pointers during unwinding

   Explanation: The most common method is to move through the list, changing each node's next pointer to the previous node, which reverses the list in O(n) time and O(1) space. Sorting is unrelated to reversal. Using a stack increases space complexity, and recursion achieves reversal but may not be optimal for long lists due to stack overflow risks.

4. Product of Array Except Self

   Given an array of n integers, how can you compute a new array so that each element is the product of all elements except itself, without using division?

   1. Use division to divide the total product by the current element
   2. Compute prefix and suffix products and multiply them for each position
   3. Sum all elements and subtract the current element
   4. Replace each value with zero and compute the product

   Explanation: The correct approach builds two arrays: one with products to the left of each index (prefix) and one to the right (suffix), then multiplies these for each index. Summing values does not yield the correct result. Division is disallowed by the problem. Replacing values with zero is not relevant or correct.

5. Detect Cycle in a Linked List

   What is a common approach to efficiently detect if a singly linked list contains a cycle?

   1. Mark nodes by overwriting their values
   2. Store all nodes in an array and check for repeats
   3. Use two pointers moving at different speeds (slow and fast)
   4. Count the total number of nodes in the list

   Explanation: The fast/slow pointer method (Floyd's Cycle Detection) finds cycles in O(n) time and O(1) space. Overwriting values is unsafe if node values aren't unique or writeable. Storing nodes increases space usage to O(n). Counting nodes does not detect cycles, as lists with cycles have no well-defined length.