Data Structures and Algorithms

1. What is dynamic programming?

• A. A programming language feature
• B. Solving complex problems by breaking into overlapping subproblems and storing results ✓
• C. A type of recursion
• D. A sorting algorithm

💡 Dynamic programming solves problems by breaking them into subproblems, solving each once, and storing the results (memoization).

2. What is a stack data structure?

• A. First In First Out (FIFO)
• B. Random access collection
• C. Last In First Out (LIFO) ✓
• D. Sorted collection

💡 A stack follows LIFO — the last item added is the first to be removed. Like a stack of plates.

3. What is the space complexity of storing n elements in an array?

• A. O(1)
• B. O(log n)
• C. O(n) ✓
• D. O(n²)

💡 Storing n elements requires O(n) space — space grows linearly with the number of elements.

4. What is a "heap" data structure?

• A. A sorted array
• B. A type of linked list
• C. A special tree-based structure satisfying the heap property ✓
• D. A type of stack

💡 A heap is a complete binary tree where each parent node is greater (max-heap) or smaller (min-heap) than its children.

5. What is the time complexity of binary search?

• A. O(n)
• B. O(n²)
• C. O(1)
• D. O(log n) ✓

💡 Binary search halves the search space each time, giving O(log n) time complexity.

6. What is the difference between BFS and DFS?

• A. BFS uses a stack; DFS uses a queue
• B. BFS is slower than DFS always
• C. BFS explores level by level; DFS explores as deep as possible first ✓
• D. They are the same algorithm

💡 BFS (Breadth First Search) explores neighbors level by level. DFS (Depth First Search) goes deep along each branch first.

7. What is a queue data structure?

• A. Last In First Out
• B. Random access
• C. First In First Out (FIFO) ✓
• D. Sorted collection

💡 A queue follows FIFO — the first item added is the first to be removed. Like a queue of people.

8. What is a hash table?

• A. A sorted list
• B. A type of binary tree
• C. A data structure that maps keys to values using a hash function ✓
• D. A type of queue

💡 A hash table uses a hash function to compute an index into an array of buckets for fast key-value lookups.

9. What is a linked list?

• A. A sorted array
• B. A type of tree
• C. A collection of nodes where each node points to the next ✓
• D. A type of hash table

💡 A linked list consists of nodes where each node contains data and a pointer to the next node.

10. What does LIFO stand for?

• A. Last Input First Output
• B. Linear In First Out
• C. Last In First Out ✓
• D. Linked Input Flow Output

💡 LIFO stands for Last In First Out — the principle used by stack data structures.

11. What is a binary tree?

• A. A tree with two roots
• B. A sorted list
• C. A tree where each node has at most two children ✓
• D. A type of linked list

💡 A binary tree is a tree data structure where each node has at most two children: left and right.

12. What is the worst-case time complexity of Bubble Sort?

• A. O(log n)
• B. O(n log n)
• C. O(n)
• D. O(n²) ✓

💡 Bubble Sort compares adjacent elements repeatedly, giving O(n²) in the worst case.

13. What is "recursion" in programming?

• A. A type of loop
• B. A function that calls itself ✓
• C. A type of variable
• D. A sorting algorithm

💡 Recursion is when a function calls itself with a modified input until it reaches a base case.

14. Which sorting algorithm has the best average time complexity?

• A. Bubble Sort
• B. Selection Sort
• C. Insertion Sort
• D. Quick Sort ✓

💡 Quick Sort has an average time complexity of O(n log n), making it one of the fastest sorting algorithms.

15. What does O(1) time complexity mean?

• A. Linear time
• B. Quadratic time
• C. Logarithmic time
• D. Constant time — independent of input size ✓

💡 O(1) means the operation takes the same time regardless of input size. Example: array index access.