Most Asked DSA Interview Questions and Answers for Freshers & Experienced

• By Devraj

• 15th September 2026

Preparing for a technical interview can feel challenging, especially when you are not sure which DSA interview questions to practice first. Data Structures and Algorithms (DSA) are among the most common topics asked in software development and technical interviews, from fresher-level roles to experienced developer positions.

The good news is that you don’t need to memorize hundreds of solutions. You need to understand the right concepts, problem-solving patterns, data structures, algorithms, and time and space complexity.

This guide covers the 100 most asked DSA interview questions and answers for freshers and experienced candidates, including arrays, strings, linked lists, stacks, queues, trees, graphs, hashing, sorting, searching, dynamic programming, and more. Each question includes a simple explanation, example, complexity, or interview tip to make preparation easier.

Whether you are preparing for your first coding interview or targeting an experienced developer role, this list can help you revise important DSA concepts and practice the problem-solving approach interviewers expect.

100 Most Asked DSA Interview Questions and Answers

Part 1: Basic DSA Interview Questions

These questions are particularly useful for freshers, interns, junior developers, and candidates with 0–2 years of experience.

1. What is DSA?

Answer: DSA stands for Data Structures and Algorithms. Data structures organize and store data efficiently, while algorithms define the steps used to process that data and solve a problem.

Interview tip: Explain DSA together rather than treating them as completely separate concepts.

2. What is a data structure?

Answer: A data structure is a way of organizing and storing data so that operations such as insertion, deletion, searching, and retrieval can be performed efficiently.

Examples: Array, linked list, stack, queue, tree, graph, heap, and hash table.

Complexity: Depends on the structure.

Follow-up: How would you choose a data structure for a problem?

3. What are the main types of data structures?

Answer: Data structures are commonly divided into:

• Linear: arrays, linked lists, stacks, queues
• Non-linear: trees, graphs
• Hash-based: hash tables/maps
• Specialized: heaps, tries, union-find

They can also be classified as static or dynamic depending on how memory changes.

Interview tip: Be ready to explain why a particular structure is appropriate for a particular operation.

4. What is an array?

Answer: An array stores elements in contiguous memory locations and generally provides constant-time access by index.

Example: arr[3] directly accesses the fourth element.

Complexity:

• Access: O(1)
• Search: O(n) unsorted
• Insert/delete at middle: O(n)

Interview tip: Mention that arrays provide excellent cache locality.

5. Array vs linked list — what is the difference?

Array	Linked List
Contiguous memory	Nodes can be scattered
O(1) indexed access	O(n) access
Insertion may require shifting	Easy insertion after known node
Better cache locality	Extra pointer memory

Example: Arrays suit indexed records; linked lists can suit frequently changing sequences.

Interview tip: Never say linked lists are simply “better for insertion.” Finding the insertion location may still take O(n).

6. What is a linked list?

Answer: A linked list is a sequence of nodes where each node stores data and a reference to another node.

Types: Singly, doubly, and circular linked lists.

Example: A playlist where each song points to the next song.

Complexity:

• Access: O(n)
• Search: O(n)
• Insert at head: O(1)
• Delete known node: O(1)

7. What is a stack?

Answer: A stack is a LIFO (Last In, First Out) data structure.

Operations: Push, pop, peek/top.

Example: Browser back history, undo functionality, function call stack.

Complexity: Push/pop/peek are normally O(1).

Follow-up: How can you implement a stack using an array or linked list?

8. What is a queue?

Answer: A queue follows FIFO (First In, First Out).

Operations: Enqueue and dequeue.

Example: Print jobs waiting for a printer.

Complexity: O(1) with a suitable implementation such as a linked list or circular queue.

Follow-up: What is the difference between a queue and a deque?

9. What is a circular queue?

Answer: A circular queue connects the end of the queue back to its beginning so previously freed positions can be reused.

Example: CPU scheduling or a fixed-size network buffer.

Complexity: Enqueue and dequeue are O(1).

Interview tip: Know how the front and rear pointers wrap around.

10. What is a deque?

Answer: A deque, or double-ended queue, allows insertion and deletion from both ends.

Example: A task scheduler may add urgent tasks at one end and regular tasks at another.

Complexity: O(1) for end operations with an appropriate implementation.

Follow-up: How can a deque implement both stack and queue behavior?

11. What is a hash table?

Answer: A hash table stores key-value pairs and uses a hash function to determine where values should be stored.

Example: {userID → userProfile}.

Average complexity:

• Search: O(1)
• Insert: O(1)
• Delete: O(1)

Worst case can reach O(n).

Interview tip: Understand collisions.

12. What is a hash collision?

Answer: A collision occurs when two different keys produce the same hash-table location.

Common solutions:

• Separate chaining
• Open addressing

Example: Multiple usernames hashing to the same bucket.

Complexity: Average operations remain O(1) with a good hash function and controlled load factor.

13. What is recursion?

Answer: Recursion occurs when a function calls itself to solve smaller instances of the same problem.

Every recursive solution should have:

1. Base case
2. Recursive case

Example: Factorial.

factorial(n) = n × factorial(n-1)

Complexity: Factorial takes O(n) time and O(n) call-stack space.

Interview tip: Always identify the base case first.

14. What is Big O notation?

Answer: Big O describes how an algorithm’s resource usage grows as input size increases.

Common complexities:

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

Example: Searching a sorted million-item dataset using binary search instead of linear search.

Interview tip: Interviewers frequently ask you to optimize an O(n²) solution.

15. What is the difference between time and space complexity?

Answer: Time complexity estimates how running time grows with input size. Space complexity estimates additional memory requirements.

Example: Merge sort:

• Time: O(n log n)
• Auxiliary space: O(n)

Follow-up: Can you improve space without increasing time?

16. What is linear search?

Answer: Linear search checks elements sequentially until the target is found.

for each element:

if element == target:

return index

Complexity: O(n) time, O(1) space.

Example: Searching an unsorted list of employee IDs.

17. What is binary search?

Answer: Binary search repeatedly divides a sorted search space into two halves.

Example: Searching for 73 in a sorted array.

Complexity: O(log n) time, O(1) iterative space.

Interview tip: Mention that the input must satisfy the ordering condition.

18. What is the difference between linear and binary search?

Linear Search	Binary Search
O(n)	O(log n)
Works on unsorted data	Usually requires sorted data
Simple	Requires careful boundaries

Follow-up: Can binary search be used without an explicitly sorted array?

Answer: Yes, when searching a monotonic answer space.

19. What is sorting?

Answer: Sorting arranges elements according to a chosen order.

Common algorithms include:

• Bubble sort
• Selection sort
• Insertion sort
• Merge sort
• Quick sort
• Heap sort

Example: Sorting products by price.

20. What is bubble sort?

Answer: Bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order.

Complexity: O(n²) average/worst case; O(n) best case with an optimization.

Space: O(1).

Interview tip: Know why bubble sort is rarely preferred in production.

21. What is insertion sort?

Answer: Insertion sort builds the sorted portion one element at a time.

Best case: O(n)

Average/worst: O(n²)

Space: O(1)

Example: Sorting a small hand of playing cards.

22. What is selection sort?

Answer: Selection sort repeatedly finds the minimum element from the unsorted section and places it at the correct position.

Time: O(n²)

Space: O(1)

Interview tip: Its number of swaps can be lower than some simple sorting methods.

23. What is a stable sorting algorithm?

Answer: A stable sort preserves the relative order of equal-valued elements.

Examples: Merge sort and insertion sort are commonly stable.

Example: Sorting employees by department while preserving their previous salary ordering.

Follow-up: Is quicksort always stable? No.

24. What is a binary tree?

Answer: A binary tree is a tree in which each node has at most two children: left and right.

Example: Expression trees and hierarchical decision structures.

Complexity: Traversing all nodes takes O(n).

25. What is a Binary Search Tree?

Answer: A BST is a binary tree where values in the left subtree are smaller and values in the right subtree are larger, assuming the chosen duplicate policy.

Average search: O(log n)

Worst case: O(n)

Interview tip: A skewed BST behaves like a linked list.

26. What is tree traversal?

Answer: Traversal means visiting all nodes according to a specific order.

Main methods:

• Preorder
• Inorder
• Postorder
• Level order

Example: Processing hierarchical folders.

27. What is inorder traversal?

Answer: Inorder traversal visits:

Left → Root → Right

For a valid BST, inorder traversal produces sorted values.

Complexity: O(n) time and O(h) recursion/stack space.

28. What is preorder traversal?

Answer: Preorder visits:

Root → Left → Right

Use case: Serializing or copying tree structures.

Complexity: O(n).

29. What is postorder traversal?

Answer: Postorder visits:

Left → Right → Root

Use case: Deleting a tree or evaluating expression trees.

Complexity: O(n).

30. What is BFS?

Answer: Breadth-First Search explores nodes level by level, normally using a queue.

Complexity: O(V + E) for an adjacency-list graph.

Example: Finding the shortest number of connections in an unweighted social network.

31. What is DFS?

Answer: Depth-First Search explores as far as possible along one branch before backtracking.

It can be implemented using recursion or an explicit stack.

Complexity: O(V + E).

Example: Exploring connected components in a network.

32. BFS vs DFS?

BFS	DFS
Queue	Stack/recursion
Level by level	Depth first
Good for unweighted shortest paths	Good for exhaustive exploration
Can use more memory on wide graphs	Can use more stack on deep graphs

33. What is a graph?

Answer: A graph consists of vertices/nodes and edges connecting them.

Graphs can be:

• Directed/undirected
• Weighted/unweighted
• Cyclic/acyclic

Example: Cities connected by roads.

Complexity: Depends on representation and operation.

34. What is an adjacency list?

Answer: An adjacency list stores the neighbors of every vertex.

Space: O(V + E)

It is usually preferable for sparse graphs.

Example: A social network where each person has a list of connections.

34. What is an adjacency list?

Answer: An adjacency list stores the neighbors of every vertex.

Space: O(V + E)

It is usually preferable for sparse graphs.

Example: A social network where each person has a list of connections.

Part 2: Intermediate DSA Interview Questions

These questions focus more on problem solving, optimization, implementation, and recognizing interview patterns.

35. How do you reverse an array?

Answer: Use two pointers, one at each end, and swap until they meet.

left = 0
right = n - 1

while left < right:
    swap(arr[left], arr[right])
    left++
    right--

Time: O(n)

Space: O(1)

Pattern: Two pointers.

36. How do you find the largest and smallest element in an array?

Answer: Scan the array once while maintaining minimum and maximum values.

Time: O(n)

Space: O(1)

Example: Finding the highest and lowest transaction amounts.

Follow-up: Can you find the second-largest element in one pass?

37. How do you remove duplicates from a sorted array?

Answer: Use a slow pointer to maintain the position of the next unique element while a fast pointer scans the array.

Time: O(n)

Space: O(1)

Pattern: Two pointers.

38. How do you solve the Two Sum problem?

Answer: Store previously seen values in a hash map. For each number x, check whether target – x has already been seen.

Time: O(n) average

Space: O(n)

Example: [2,7,11,15], target 9 → 2 + 7.

Follow-up: What if the array is already sorted? Use two pointers with O(1) extra space.

39. What is the sliding-window technique?

Answer: Sliding window maintains a moving range over an array or string instead of repeatedly processing overlapping elements.

Example: Find the maximum sum of any subarray of size k.

Time: Usually O(n)

Space: Often O(1), depending on the problem.

Example: Calculating a rolling average of website traffic.

40. What are two pointers?

Answer: Two pointers use two indexes that move through a data structure to avoid unnecessary nested loops.

Example: Finding whether a sorted array contains two numbers with a target sum.

Time: O(n)

Space: O(1)

Interview tip: Ask whether the data is sorted before choosing this approach.

41. How do you check whether a string is a palindrome?

Answer: Compare characters from both ends while moving toward the center.

Time: O(n)

Space: O(1)

Example: “racecar” is a palindrome.

Follow-up: How would you handle spaces and uppercase letters?

42. How do you find the first non-repeating character?

Answer: Count character frequencies with a hash map, then scan the string again for the first character with frequency one.

Time: O(n)

Space: O(k), where k is the character set size.

Example: Finding the first unique character in a username.

43. How do you check whether two strings are anagrams?

Answer: Count the frequency of each character in both strings and compare the counts.

Time: O(n)

Space: O(k)

Example: “listen” and “silent” are anagrams.

44. How do you reverse a linked list?

Answer: Maintain prev, current, and next pointers and reverse each link.

prev = null
current = head

while current:
    next = current.next
    current.next = prev
    prev = current
    current = next

Time: O(n)

Space: O(1)

Follow-up: Implement it recursively.

45. How do you detect a cycle in a linked list?

Answer: Use Floyd’s slow and fast pointer algorithm.

• Slow moves one step.
• Fast moves two steps.
• If they meet, a cycle exists.

Time: O(n)

Space: O(1)

Example: Detecting an unintended circular reference in a linked data structure.

46. How do you find the middle of a linked list?

Answer: Move one pointer one step and another two steps. When the fast pointer reaches the end, the slow pointer is at the middle.

Time: O(n)

Space: O(1)

Pattern: Fast and slow pointers.

47. How do you merge two sorted linked lists?

Answer: Compare the current nodes of both lists and repeatedly attach the smaller node.

Time: O(n + m)

Space: O(1) extra space if nodes are reused.

Example: Merging sorted streams of records.

48. How do you implement a stack using queues?

Answer: One common method rearranges queue elements after each push so the newest element appears at the front.

Push: O(n)

Pop: O(1)

Alternative designs can trade the complexities.

Interview tip: Explain the trade-off rather than presenting only one implementation.

49. How do you implement a queue using stacks?

Answer: Use two stacks:

• Input stack for enqueue
• Output stack for dequeue

Transfer elements only when the output stack is empty.

Amortized complexity: O(1) per operation.

Space: O(n).

50. What is a priority queue?

Answer: A priority queue removes the element with the highest or lowest priority rather than simply following insertion order.

A heap is commonly used to implement it.

Complexity with binary heap:

• Insert: O(log n)
• Remove: O(log n)
• Peek: O(1)

Example: CPU task scheduling.

51. What is a heap?

Answer: A heap is a complete binary tree satisfying a heap-order property.

• Min heap: parent ≤ children
• Max heap: parent ≥ children

Typical representation: Array.

Build heap: O(n)

52. How do you find the K largest elements?

Answer: Maintain a min-heap of size k.

For each element:

• Add it.
• If heap size exceeds k, remove the smallest.

Time: O(n log k)

Space: O(k)

Example: Finding the top 10 products by sales.

53. What is merge sort?

Answer: Merge sort divides an array into halves, recursively sorts each half, and merges them.

Time: O(n log n)

Space: O(n)

Advantage: Predictable performance and stable sorting.

Example: Sorting large datasets where predictable performance matters.

54. What is quicksort?

Answer: Quicksort selects a pivot, partitions the elements around it, and recursively sorts the partitions.

Average: O(n log n)

Worst: O(n²)

Typical stack: O(log n) average.

Interview tip: Explain pivot selection and worst-case behavior.

55. Merge sort vs quicksort?

Merge Sort	Quick Sort
O(n log n) worst-case	O(n²) worst-case
O(n) auxiliary array space	Usually in-place
Stable in standard form	Usually not stable
Predictable	Often fast in practice

56. What is a hash map’s load factor?

Answer: Load factor is approximately:

number of stored entries / number of buckets

When the load factor becomes too high, hash-table implementations may resize and rehash.

Interview tip: Understand why resizing helps maintain average O(1) operations.

57. What is memoization?

Answer: Memoization stores results of previously solved subproblems so they don’t have to be recalculated.

Example: Recursive Fibonacci.

Without memoization, Fibonacci has exponential repeated work. With memoization, it becomes O(n).

Space: O(n).

58. What is dynamic programming?

Answer: Dynamic programming solves problems with overlapping subproblems and optimal substructure by storing previously computed results.

Two common approaches:

• Top-down memoization
• Bottom-up tabulation

Example: Budget optimization and resource allocation.

59. What is the difference between recursion and dynamic programming?

Answer: Recursion describes how a problem is broken into smaller problems. DP adds reuse of repeated subproblem results.

Example: Recursive Fibonacci is inefficient because it recomputes values; DP stores them.

60. What is Kadane’s algorithm?

Answer: Kadane’s algorithm finds the maximum-sum contiguous subarray.

For each element, decide whether to:

• Extend the current subarray
• Start a new subarray

Time: O(n)

Space: O(1)

Example: [-2,1,-3,4,-1,2,1,-5,4] → maximum sum is 6.

61. How do you merge overlapping intervals?

Answer: Sort intervals by start time, then compare each interval with the end of the last merged interval.

Time: O(n log n) due to sorting.

Space: O(n) for output.

Example: Combining overlapping employee meeting schedules.

62. What is a monotonic stack?

Answer: A monotonic stack maintains elements in increasing or decreasing order to efficiently answer next-greater/next-smaller type questions.

Example: Next Greater Element.

Time: O(n), because each element is pushed and popped at most once.

Example: Stock-price or temperature trend analysis.

63. How do you solve the Valid Parentheses problem?

Answer: Push opening brackets onto a stack. For a closing bracket, check whether it matches the top opening bracket.

Time: O(n)

Space: O(n)

Example: “({[]})” → valid.

Follow-up: How would you support additional bracket types?

64. How do you find the intersection of two arrays?

Answer: Use a hash set to store elements from one array, then check the second array.

Time: O(n + m) average

Space: O(n)

If arrays are sorted, two pointers can achieve O(n + m) with less extra space.

65. How do you find a missing number from 1 to n?

Answer: Use the mathematical sum or XOR technique.

For XOR:

1 ^ 2 ^ ... ^ n ^ array elements

The duplicates cancel, leaving the missing value.

Time: O(n)

Space: O(1)

66. What is a trie?

Answer: A trie is a tree-like structure used to store strings character by character.

Operations: Insert, search, prefix search.

Time: O(L), where L is the word length.

Example: Autocomplete and dictionary applications.

67. What is a graph’s adjacency matrix?

Answer: An adjacency matrix uses a V × V matrix to indicate whether an edge exists between two vertices.

Space: O(V²)

Advantage: O(1) edge lookup.

Disadvantage: Wasteful for sparse graphs.

68. Adjacency list vs adjacency matrix?

Adjacency List	Adjacency Matrix
O(V+E) space	O(V²) space
Good for sparse graphs	Good for dense graphs
Neighbor traversal efficient	Edge lookup O(1)

Part 3: Advanced DSA Interview Questions

These questions are particularly useful for experienced developers, senior engineers, product-company interviews, and candidates targeting harder technical rounds.

69. What is Dijkstra’s algorithm?

Answer: Dijkstra’s algorithm finds shortest paths from a source vertex to other vertices in a graph with non-negative edge weights.

With a binary heap and adjacency list:

Time: O((V + E) log V)

Example: Finding the shortest road route.

Important: It does not correctly handle negative edge weights.

70. Dijkstra vs Bellman-Ford?

Dijkstra	Bellman-Ford
No negative edges	Supports negative edges
Faster generally	Slower
Cannot detect negative cycles	Can detect negative cycles

Bellman-Ford: O(VE)

71. What is the Floyd-Warshall algorithm?

Answer: Floyd-Warshall finds shortest paths between every pair of vertices.

Time: O(V³)

Space: O(V²)

It can handle negative edges but not negative cycles meaningfully for shortest-path output.

Use case: Dense graphs and all-pairs shortest-path problems.

72. What is topological sorting?

Answer: Topological sorting orders vertices in a directed acyclic graph (DAG) so every directed edge u → v places u before v.

Methods:

• DFS
• Kahn’s algorithm using indegrees

Time: O(V + E)

Example: Scheduling courses based on prerequisites.

73. How do you detect a cycle in a directed graph?

Answer: DFS can track nodes currently in the recursion stack. Encountering a node already in that stack indicates a cycle.

Alternatively, Kahn’s algorithm can detect a cycle if fewer than V nodes can be processed.

Time: O(V + E)

74. How do you detect a cycle in an undirected graph?

Answer: During DFS, track the parent of each node. If you encounter an already visited neighbor that is not the parent, a cycle exists.

Another approach is Union-Find.

Time: O(V + E) using DFS.

75. What is Union-Find / Disjoint Set Union?

Answer: DSU maintains a collection of disjoint sets and supports:

• Find
• Union

With path compression and union by rank/size, operations are nearly constant amortized time:

O(α(n))

Example: Network connectivity and grouping components.

76. What is Kruskal’s algorithm?

Answer: Kruskal’s algorithm constructs a minimum spanning tree by sorting edges by weight and adding an edge if it does not create a cycle.

It commonly uses Union-Find.

Time: O(E log E)

Example: Designing a low-cost network connecting multiple locations.

77. What is Prim’s algorithm?

Answer: Prim’s algorithm grows a minimum spanning tree by repeatedly selecting the cheapest edge connecting the current tree to an unvisited vertex.

Using a binary heap:

Time: O(E log V)

Follow-up: Compare Prim’s and Kruskal’s algorithms.

78. What is a minimum spanning tree?

Answer: An MST connects all vertices of a connected, weighted, undirected graph with minimum possible total edge weight and no cycles.

Applications: Network, road, and cable design.

Algorithms: Prim and Kruskal.

79. What is the 0/1 Knapsack problem?

Answer: Given items with weights and values, maximize total value without exceeding capacity, where each item can be selected at most once.

Typical DP:

dp[i][w] = maximum value using first i items with capacity w

Time: O(nW)

Space: O(nW), reducible to O(W).

Interview tip: Explain why greedy does not generally solve 0/1 knapsack optimally.

80. What is the Longest Common Subsequence problem?

Answer: LCS finds the longest sequence that appears in two strings in the same relative order, not necessarily contiguously.

Example:

ABCBDAB and BDCABA

LCS length is 4.

Time: O(nm)

Space: O(nm), reducible for length-only computation.

81. What is the Longest Increasing Subsequence?

Answer: LIS finds the longest subsequence whose values are strictly increasing.

A classic optimized solution uses binary search over maintained tails.

Time: O(n log n)

Space: O(n)

Interview tip: Understand the difference between a subsequence and a subarray.

82. What is backtracking?

Answer: Backtracking builds a solution incrementally and abandons a partial solution when it cannot lead to a valid answer.

Common problems:

• N-Queens
• Sudoku
• Permutations
• Combinations
• Subsets

Complexity: Usually exponential.

Example: Constraint-based scheduling or configuration search.

83. How do you solve the N-Queens problem?

Answer: Place one queen per row while tracking occupied columns and diagonals. If a placement creates a conflict, backtrack.

Typical complexity: O(N!) upper-bound style analysis, with pruning improving practical performance.

Space: O(N) auxiliary tracking plus recursion.

84. How do you generate all permutations?

Answer: Use backtracking. At each position, choose an unused element, recurse, and then undo the choice.

For n unique elements:

Time: O(n × n!) to output all permutations.

Space: O(n) recursion excluding output.

85. How do you generate all subsets?

Answer: For each element, make two choices:

1. Include it.
2. Exclude it.

There are 2ⁿ subsets.

Time: O(n × 2ⁿ) if explicitly constructing each subset.

Space: O(n) auxiliary recursion excluding output.

86. What is the difference between greedy algorithms and dynamic programming?

Greedy algorithms make the best local decision at each step and never revisit it.

DP evaluates and stores solutions to subproblems.

Example:

• Fractional knapsack → greedy works.
• 0/1 knapsack → DP is generally required.

Interview tip: Never assume a greedy solution is optimal without proving the greedy-choice property.

87. What is the Activity Selection problem?

Answer: Select the maximum number of non-overlapping activities.

Sort activities by finishing time and repeatedly choose the next compatible activity.

Time: O(n log n) including sorting.

Space: O(1) auxiliary depending on implementation.

Pattern: Greedy.

88. What is binary search on the answer?

Answer: Instead of searching an array for a value, binary search is performed over a numerical answer range when the feasibility condition is monotonic.

Example: Find the minimum shipping capacity needed to deliver packages within D days.

Complexity: Usually O(n log R), where R is the answer range.

89. What is the “Merge K Sorted Lists” problem?

Answer: Use a min-heap containing the smallest current node from each list. Remove the minimum and insert the next node from that list.

Time: O(N log k)

Space: O(k)

where N is the total number of nodes and k is the number of lists.

Example: Merging sorted database or log streams.

90. How do you find the median from a data stream?

Answer: Use two heaps:

• Max-heap for the smaller half.
• Min-heap for the larger half.

Keep their sizes balanced.

Insertion: O(log n)

Median: O(1)

Example: Tracking a live median of transaction values.

91. What is an LRU cache?

Answer: LRU means Least Recently Used. When the cache is full, the least recently accessed item is removed.

A standard O(1) design combines:

• Hash map
• Doubly linked list

Get: O(1) average

Put: O(1) average

Space: O(capacity)

This is one of the classic questions where the interviewer tests whether you can combine two data structures.

92. What is the difference between a B-tree and B+ tree?

Answer: Both are balanced multiway search trees commonly associated with database/storage indexing.

A B+ tree generally stores records or record pointers in leaf nodes, with internal nodes primarily serving as routing/index nodes. Leaf nodes are commonly linked, making range scans efficient.

Example: Database indexes.

Interview tip: Know why disk/page-oriented structures prefer high branching factors.

93. What is a segment tree?

Answer: A segment tree supports efficient range queries and updates over an array.

For many standard operations:

• Build: O(n)
• Query: O(log n)
• Update: O(log n)
• Space: O(n)

Example: Range sum/minimum queries with updates.

94. What is a Fenwick Tree / Binary Indexed Tree?

Answer: A Fenwick tree supports prefix aggregation and point updates efficiently.

Typical operations:

• Update: O(log n)
• Prefix query: O(log n)
• Space: O(n)

Use case: Dynamic prefix sums and frequency counting.

95. What is a sparse table?

Answer: A sparse table is a static range-query structure built using overlapping intervals.

For idempotent operations such as minimum/maximum:

• Preprocessing: O(n log n)
• Query: O(1)
• Space: O(n log n)

Important: It is best when the array does not change frequently.

96. What is an AVL tree?

Answer: An AVL tree is a self-balancing binary search tree where the height difference between the left and right subtrees of every node is at most one.

Search: O(log n)

Insert: O(log n)

Delete: O(log n)

Interview tip: Know rotations:

• LL
• RR
• LR
• RL

97. What is a Red-Black Tree?

Answer: A Red-Black Tree is a self-balancing BST that uses node colors and structural rules to keep its height logarithmic.

Search/insert/delete: O(log n)

Real-world use: Many standard-library ordered maps/sets use balanced tree structures such as Red-Black Trees.

Follow-up: Compare AVL and Red-Black Trees.

98. What is the difference between BFS and Dijkstra’s algorithm?

Answer:

BFS finds shortest paths in terms of the number of edges when all edges have equal cost.

Dijkstra handles non-negative weighted edges.

Example:

• Unweighted social-network connections → BFS
• Road distances → Dijkstra

Complexity:

• BFS: O(V + E)
• Dijkstra with binary heap: O((V+E) log V)

99. How would you optimize an O(n²) solution?

Answer: First identify why the nested loops exist. Then consider:

• Hashing
• Sorting
• Two pointers
• Sliding window
• Binary search
• Heap
• Stack
• Prefix sums
• Dynamic programming

Example: Two Sum can be changed from O(n²) brute force to O(n) average using a hash map.

Interview tip: Don’t optimize blindly. Explain the trade-off between time and memory.

100. How do you choose the right data structure for an interview problem?

Answer: Start with the operations the problem requires.

Best interview answer: Don’t say “I know this data structure.” Say why this data structure gives the required complexity for the problem.

DSA Interview Pattern Cheat Sheet

A major difference between average and strong candidates is recognizing the pattern behind a problem.

This pattern-based approach is also reflected in current DSA resources, which increasingly emphasize recognizing reusable techniques instead of memorizing hundreds of unrelated problems.

Most Important DSA Complexities to Remember

How Interviewers Usually Increase the Difficulty

A strong interviewer rarely stops after the first correct answer.

For example:

Interviewer: Find two numbers that add up to a target.

Candidate: I can use a hash map in O(n).

Interviewer: What is the space complexity?

Candidate: O(n).

Interviewer: What if the array is sorted?

Candidate: I can use two pointers and reduce extra space to O(1).

Interviewer: What if the array is too large to fit into memory?

Candidate: Then I would reconsider the storage/streaming model and possibly use external sorting or a streaming approach depending on the exact constraints.

This is the level of reasoning experienced candidates should practice.

Final Thoughts: Prepare DSA With the Right Approach

DSA interview preparation is not about remembering every solution. It is about understanding how to approach a problem, choose the right data structure, identify the right algorithm, and explain your solution clearly.

Start with the basics, practice common patterns, and gradually move toward advanced problems. For every question, try to understand why a particular approach works, what its time and space complexity is, and how it can be optimized.

If you are a student or beginner looking to build stronger programming and technical interview skills, Skill Hives can help you develop practical knowledge through structured IT training and hands-on learning.

Keep practicing, solve problems consistently, and focus on improving your problem-solving skills one question at a time. With the right preparation and regular practice, DSA can become much easier to handle in technical interviews.

Frequently Asked DSA Interview Questions

1. What DSA topics should a fresher prepare first?

Start with arrays, strings, linked lists, stacks, queues, hashing, recursion, searching, sorting, trees, and basic graphs. Then move to patterns such as two pointers, sliding window, binary search, BFS, DFS, and basic dynamic programming.

2. Which DSA questions are most commonly asked?

Frequently recurring problems include Two Sum, reverse linked list, linked-list cycle detection, binary search, valid parentheses, tree traversal, BFS/DFS, merge intervals, maximum subarray, top-K problems, shortest path, and dynamic programming problems. Current 2026 question lists repeatedly feature these problem families.

3. Are DSA questions important for experienced developers?

Yes. Experienced candidates are often expected to go beyond definitions and demonstrate optimization, complexity analysis, trade-offs, advanced graph/tree algorithms, concurrency-aware data-structure choices, and scalable solutions.

4. Should I memorize DSA solutions?

No. Memorize patterns and principles, not complete solutions. You should be able to reconstruct the solution when constraints change.

5. How much DSA should I prepare for a technical interview?

A useful preparation target is to become comfortable with the major patterns and solve a representative set of easy, medium, and hard problems rather than trying to memorize hundreds of unrelated questions.

6. Which programming language is best for DSA interviews?

Python, Java, C++, and JavaScript can all work. The best language is generally the one in which you can write correct code quickly and explain the implementation clearly.

7. What should I say when I don’t know the optimal solution?

Explain the brute-force approach first, state its complexity, identify its bottleneck, and then reason toward an optimization. Interviewers often evaluate the problem-solving process, not just whether you immediately know the final algorithm.

8. Is Big O important in DSA interviews?

Yes. You should be able to explain both time and space complexity and justify why your chosen approach meets the input constraints.

9. What is more important: data structures or algorithms?

Neither can be considered in isolation. The right algorithm often depends on the data structure. For example, Dijkstra’s algorithm becomes much more efficient with an appropriate priority queue.

10. How should I explain a DSA solution in an interview?

Use this sequence:

Clarify → Brute Force → Identify Bottleneck → Optimize → Explain Data Structure → Write Code → Test Edge Cases → Give Complexity.

Final DSA Interview Preparation Strategy