✅ Top DSA Interview Questions with Answers: Part-2 🧠
11. What is the difference between BFS and DFS?
- BFS (Breadth-First Search): Explores neighbors first (level by level). Uses a queue. ➡️
- DFS (Depth-First Search): Explores depth (child nodes) first. Uses a stack or recursion. ⬇️
Used in graph/tree traversals, pathfinding, cycle detection. 🌳🔎
12. What is a Heap?
A binary tree with heap properties:
- Max-Heap: Parent ≥ children 🔼
- Min-Heap: Parent ≤ children 🔽
Used in priority queues, heap sort, scheduling algorithms. ⏰
13. What is a Trie?
A tree-like data structure used to store strings. 🌲
Each node represents a character.
Used in: autocomplete, spell-checkers, prefix search. 🔡
14. What is a Graph?
A graph is a collection of nodes (vertices) and edges. 🔗
- Can be directed/undirected, weighted/unweighted.
Used in: networks, maps, recommendation systems. 🗺️
15. Difference between Directed and Undirected Graph?
- Directed: Edges have direction (A → B ≠ B → A) ➡️
- Undirected: Edges are bidirectional (A — B) ↔️
Used differently based on relationships (e.g., social networks vs. web links).
16. What is the time complexity of common operations in arrays and linked lists?
- Array: 🔢
- Access: O(1)
- Insert/Delete: O(n)
- Linked List: 🔗
- Access: O(n)
- Insert/Delete: O(1) at head
17. What is recursion?
When a function calls itself to solve a smaller subproblem. 🔄
Requires a base case to stop infinite calls.
Used in: tree traversals, backtracking, divide & conquer. 🌳🧩
18. What are base case and recursive case?
- Base Case: Condition that ends recursion 🛑
- Recursive Case: Part where the function calls itself ➡️
Example:
19. What is dynamic programming?
An optimization technique that solves problems by breaking them into overlapping subproblems and storing their results (memoization). 💾
Used in: Fibonacci, knapsack, LCS. 📈
20. Difference between Memoization and Tabulation?
- Memoization (Top-down): Uses recursion + caching 🧠
- Tabulation (Bottom-up): Uses iteration + table 📊
Both store solutions to avoid redundant calculations.
💬 Double Tap ♥️ For Part-3
11. What is the difference between BFS and DFS?
- BFS (Breadth-First Search): Explores neighbors first (level by level). Uses a queue. ➡️
- DFS (Depth-First Search): Explores depth (child nodes) first. Uses a stack or recursion. ⬇️
Used in graph/tree traversals, pathfinding, cycle detection. 🌳🔎
12. What is a Heap?
A binary tree with heap properties:
- Max-Heap: Parent ≥ children 🔼
- Min-Heap: Parent ≤ children 🔽
Used in priority queues, heap sort, scheduling algorithms. ⏰
13. What is a Trie?
A tree-like data structure used to store strings. 🌲
Each node represents a character.
Used in: autocomplete, spell-checkers, prefix search. 🔡
14. What is a Graph?
A graph is a collection of nodes (vertices) and edges. 🔗
- Can be directed/undirected, weighted/unweighted.
Used in: networks, maps, recommendation systems. 🗺️
15. Difference between Directed and Undirected Graph?
- Directed: Edges have direction (A → B ≠ B → A) ➡️
- Undirected: Edges are bidirectional (A — B) ↔️
Used differently based on relationships (e.g., social networks vs. web links).
16. What is the time complexity of common operations in arrays and linked lists?
- Array: 🔢
- Access: O(1)
- Insert/Delete: O(n)
- Linked List: 🔗
- Access: O(n)
- Insert/Delete: O(1) at head
17. What is recursion?
When a function calls itself to solve a smaller subproblem. 🔄
Requires a base case to stop infinite calls.
Used in: tree traversals, backtracking, divide & conquer. 🌳🧩
18. What are base case and recursive case?
- Base Case: Condition that ends recursion 🛑
- Recursive Case: Part where the function calls itself ➡️
Example:
def fact(n):
if n == 0: return 1 # base case
return n * fact(n-1) # recursive case
19. What is dynamic programming?
An optimization technique that solves problems by breaking them into overlapping subproblems and storing their results (memoization). 💾
Used in: Fibonacci, knapsack, LCS. 📈
20. Difference between Memoization and Tabulation?
- Memoization (Top-down): Uses recursion + caching 🧠
- Tabulation (Bottom-up): Uses iteration + table 📊
Both store solutions to avoid redundant calculations.
💬 Double Tap ♥️ For Part-3
❤7👏1
✅ 15-Day Winter Training by GeeksforGeeks ❄️💻
🎯 Build 1 Industry-Level Project
🏅 IBM Certification Included
👨🏫 Mentor-Led Classroom Learning
📍 Offline in: Noida | Bengaluru | Hyderabad | Pune | Kolkata
🧳 Perfect for Minor/Major Projects Portfolio
🔧 MERN Stack:
https://gfgcdn.com/tu/WC6/
📊 Data Science:
https://gfgcdn.com/tu/WC7/
🔥 What You’ll Build:
• MERN: Full LMS with auth, roles, payments, AWS deploy
• Data Science: End-to-end GenAI apps (chatbots, RAG, recsys)
📢 Limited Seats – Register Now!
🎯 Build 1 Industry-Level Project
🏅 IBM Certification Included
👨🏫 Mentor-Led Classroom Learning
📍 Offline in: Noida | Bengaluru | Hyderabad | Pune | Kolkata
🧳 Perfect for Minor/Major Projects Portfolio
🔧 MERN Stack:
https://gfgcdn.com/tu/WC6/
📊 Data Science:
https://gfgcdn.com/tu/WC7/
🔥 What You’ll Build:
• MERN: Full LMS with auth, roles, payments, AWS deploy
• Data Science: End-to-end GenAI apps (chatbots, RAG, recsys)
📢 Limited Seats – Register Now!
❤8🍌1
✅ Top DSA Interview Questions with Answers: Part-3 🧠
21. What is the Sliding Window technique?
It’s an optimization method used to reduce time complexity in problems involving arrays or strings. You create a "window" over a subset of data and slide it as needed, updating results on the go.
Example use case: Find the maximum sum of any k consecutive elements in an array.
22. Explain the Two-Pointer technique.
This involves using two indices (pointers) to traverse a data structure, usually from opposite ends or the same direction. It's helpful for searching pairs or reversing sequences efficiently.
Common problems: Two-sum, palindrome check, sorted array partitioning.
23. What is the Binary Search algorithm?
It’s an efficient algorithm to find an element in a sorted array by repeatedly dividing the search range in half.
Time Complexity: O(log n)
Key idea: Compare the target with the middle element and eliminate half the array each step.
24. What is the Merge Sort algorithm?
A divide-and-conquer sorting algorithm that splits the array into halves, sorts them recursively, and then merges them.
Time Complexity: O(n log n)
Stable? Yes
Extra space? Yes, due to merging.
25. What is the Quick Sort algorithm?
It chooses a pivot, partitions the array so elements < pivot are left, and > pivot are right, then recursively sorts both sides.
Time Complexity: Avg – O(n log n), Worst – O(n²)
Fast in practice, but not stable.
26. Difference between Merge Sort and Quick Sort
• Merge Sort is stable, consistent in performance (O(n log n)), but uses extra space.
• Quick Sort is faster in practice and works in-place, but may degrade to O(n²) if pivot is poorly chosen.
27. What is Insertion Sort and how does it work?
It builds the sorted list one item at a time by comparing and inserting items into their correct position.
Time Complexity: O(n²)
Best Case (nearly sorted): O(n)
Stable? Yes
Space: O(1)
28. What is Selection Sort?
It finds the smallest element from the unsorted part and swaps it with the beginning.
Time Complexity: O(n²)
Space: O(1)
Stable? No
Rarely used due to inefficiency.
29. What is Bubble Sort and its drawbacks?
It repeatedly compares and swaps adjacent elements if out of order.
Time Complexity: O(n²)
Space: O(1)
Drawback: Extremely slow for large data. Educational, not practical.
30. What is the time and space complexity of common sorting algorithms?
• Bubble Sort → Time: O(n²), Space: O(1), Stable: Yes
• Selection Sort → Time: O(n²), Space: O(1), Stable: No
• Insertion Sort → Time: O(n²), Space: O(1), Stable: Yes
• Merge Sort → Time: O(n log n), Space: O(n), Stable: Yes
• Quick Sort → Avg Time: O(n log n), Worst: O(n²), Space: O(log n), Stable: No
Double Tap ♥️ For Part-4
21. What is the Sliding Window technique?
It’s an optimization method used to reduce time complexity in problems involving arrays or strings. You create a "window" over a subset of data and slide it as needed, updating results on the go.
Example use case: Find the maximum sum of any k consecutive elements in an array.
22. Explain the Two-Pointer technique.
This involves using two indices (pointers) to traverse a data structure, usually from opposite ends or the same direction. It's helpful for searching pairs or reversing sequences efficiently.
Common problems: Two-sum, palindrome check, sorted array partitioning.
23. What is the Binary Search algorithm?
It’s an efficient algorithm to find an element in a sorted array by repeatedly dividing the search range in half.
Time Complexity: O(log n)
Key idea: Compare the target with the middle element and eliminate half the array each step.
24. What is the Merge Sort algorithm?
A divide-and-conquer sorting algorithm that splits the array into halves, sorts them recursively, and then merges them.
Time Complexity: O(n log n)
Stable? Yes
Extra space? Yes, due to merging.
25. What is the Quick Sort algorithm?
It chooses a pivot, partitions the array so elements < pivot are left, and > pivot are right, then recursively sorts both sides.
Time Complexity: Avg – O(n log n), Worst – O(n²)
Fast in practice, but not stable.
26. Difference between Merge Sort and Quick Sort
• Merge Sort is stable, consistent in performance (O(n log n)), but uses extra space.
• Quick Sort is faster in practice and works in-place, but may degrade to O(n²) if pivot is poorly chosen.
27. What is Insertion Sort and how does it work?
It builds the sorted list one item at a time by comparing and inserting items into their correct position.
Time Complexity: O(n²)
Best Case (nearly sorted): O(n)
Stable? Yes
Space: O(1)
28. What is Selection Sort?
It finds the smallest element from the unsorted part and swaps it with the beginning.
Time Complexity: O(n²)
Space: O(1)
Stable? No
Rarely used due to inefficiency.
29. What is Bubble Sort and its drawbacks?
It repeatedly compares and swaps adjacent elements if out of order.
Time Complexity: O(n²)
Space: O(1)
Drawback: Extremely slow for large data. Educational, not practical.
30. What is the time and space complexity of common sorting algorithms?
• Bubble Sort → Time: O(n²), Space: O(1), Stable: Yes
• Selection Sort → Time: O(n²), Space: O(1), Stable: No
• Insertion Sort → Time: O(n²), Space: O(1), Stable: Yes
• Merge Sort → Time: O(n log n), Space: O(n), Stable: Yes
• Quick Sort → Avg Time: O(n log n), Worst: O(n²), Space: O(log n), Stable: No
Double Tap ♥️ For Part-4
❤13