Mastering the Fundamentals: 35 Key Data Structures and Algorithms Questions Quiz

Explore essential data structure and algorithm topics with these carefully crafted questions, perfect for interview preparation and strengthening your core programming knowledge.

1. Two Sum Problem

   Given an array of integers and a target sum, which data structure allows the most efficient searching to determine if two numbers add up to the target in linear time?

   1. Stack
   2. Linked List
   3. Queue
   4. Hash Map

   Explanation: A hash map enables constant time lookups for complements, making it possible to solve the Two Sum problem in linear time. Using a stack or queue would require scanning the array multiple times, resulting in less efficiency. A linked list does not provide constant time lookups, so it is also less optimal for this task.

2. Reversing a String

   What is the most efficient time complexity for reversing a string of length n?

   1. O(n^2)
   2. O(log n)
   3. O(n)
   4. O(1)

   Explanation: Reversing a string requires visiting each character once, resulting in O(n) time complexity. O(1) is for constant time operations, which does not apply here. O(log n) and O(n^2) are not achievable or optimal for this straightforward linear process.

3. Detecting Cycle in a Linked List

   Which algorithm efficiently detects a cycle in a singly linked list with constant space?

   1. Dijkstra's Algorithm
   2. Merge Sort
   3. Floyd's Tortoise and Hare
   4. Depth-First Search

   Explanation: Floyd's Tortoise and Hare uses two pointers moving at different speeds to detect a cycle in O(n) time and O(1) space. Merge Sort is for sorting, not cycle detection. DFS could detect cycles in general graphs but requires extra space. Dijkstra's Algorithm is for shortest paths in graphs.

4. Binary Search Tree Validation

   What property must every node in a binary search tree satisfy?

   1. All levels are fully filled
   2. All nodes have two children
   3. No duplicate values allowed
   4. Left child is less, right child is greater

   Explanation: A BST requires that each left child has a value less than its parent and each right child has a value greater. Requiring all nodes to have two children or all levels to be fully filled describes a different structure, like a complete or full tree. Duplicates are sometimes allowed depending on implementation.

5. Time Complexity of Merge Sort

   What is the average case time complexity for the merge sort algorithm?

   1. O(n)
   2. O(log n)
   3. O(n log n)
   4. O(n^2)

   Explanation: Merge sort consistently operates in O(n log n) time for all cases due to its divide-and-conquer approach. O(n^2) is common for simple sorts like bubble sort. O(log n) and O(n) are not achievable for comparison-based sorting of general data.