Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Interview questions › DSA

DSA interview questions

1. What is time complexity and why do we use Big-O?

Easy

Time complexity describes how the running time grows with input size n. Big-O gives the upper bound of that growth, ignoring constants and lower-order terms, so we can compare algorithms independent of hardware (e.g. O(n) vs O(n²)).

2. What is the difference between an array and a linked list?

Easy

An array stores elements contiguously: O(1) random access, but insert/delete in the middle is O(n) and size is fixed (or needs resizing). A linked list stores nodes with pointers: O(1) insert/delete when you have the node, but O(n) access and extra memory for pointers.

3. What is the difference between a stack and a queue?

Easy

A stack is LIFO (last in, first out) — push/pop at the top; used for function calls, undo, parentheses matching. A queue is FIFO (first in, first out) — enqueue at the rear, dequeue from the front; used for BFS, scheduling, buffering.

4. How does binary search work and what is its complexity?

Easy

On a sorted array, compare the target with the middle element; discard the half that cannot contain it and repeat. Each step halves the range, so it takes O(log n) time and O(1) space (iterative).

5. Compare Bubble, Selection, Insertion, Merge and Quick sort.

Medium

Sort Best Average Worst Stable
Bubble O(n) O(n²) O(n²) Yes
Selection O(n²) O(n²) O(n²) No
Insertion O(n) O(n²) O(n²) Yes
Merge O(n log n) O(n log n) O(n log n) Yes
Quick O(n log n) O(n log n) O(n²) No

6. What is a stable sorting algorithm?

Easy

A sort is stable if equal elements keep their original relative order. Example: sorting students by marks with a stable sort keeps students with equal marks in their earlier (e.g. alphabetical) order. Merge sort and insertion sort are stable; quick sort and heap sort are not.

7. Why is quick sort preferred over merge sort for arrays?

Medium

Quick sort works in place (O(log n) stack space vs O(n) extra for merge sort) and has excellent cache locality, so it is usually faster in practice. Its O(n²) worst case is avoided with random or median-of-three pivots. Merge sort is preferred for linked lists and when stability is required.

8. What is a hash table and how are collisions handled?

Medium

A hash table maps keys to array indices using a hash function, giving O(1) average insert/search/delete. Collisions (two keys → same index) are handled by chaining (a list at each bucket) or open addressing (linear/quadratic probing, double hashing). A good load factor keeps operations fast.

9. What is the worst-case complexity of a hash map lookup?

Medium

O(n) — if many keys collide into the same bucket the lookup degrades to scanning them all. Java 8+ HashMap converts long chains into balanced trees, making the worst case O(log n).

10. What is recursion? What is a base case?

Easy

Recursion is a function solving a problem by calling itself on a smaller version of the same problem. The base case is the condition where it stops calling itself; without it the recursion never ends and causes a stack overflow.

11. What is the difference between recursion and iteration?

Easy

Recursion uses function calls (and the call stack) and often gives cleaner code for trees, divide & conquer and backtracking. Iteration uses loops, needs no extra stack memory and is usually faster. Any recursion can be converted to iteration with an explicit stack.

12. What is dynamic programming?

Medium

DP solves problems with overlapping subproblems and optimal substructure by storing results of subproblems so each is computed once. Two styles: memoization (top-down recursion + cache) and tabulation (bottom-up table). Examples: Fibonacci, knapsack, LCS.

13. Memoization vs tabulation?

Medium

Memoization is top-down: recursive, computes only the states that are needed, but uses the call stack. Tabulation is bottom-up: iterative, fills the whole table in order, no recursion overhead and often allows space optimisation.

14. What is a greedy algorithm? When does it fail?

Medium

A greedy algorithm makes the locally best choice at each step hoping to reach a global optimum (e.g. activity selection, Huffman coding, Dijkstra). It fails when local choices don't lead to the best overall answer — e.g. coin change with coins {1, 3, 4} for amount 6: greedy gives 4+1+1 (3 coins) but the optimum is 3+3 (2 coins).

15. What is a binary tree? What is a binary search tree?

Easy

A binary tree is a tree where each node has at most two children. A BST additionally keeps all values in the left subtree smaller and all values in the right subtree larger than the node, enabling O(h) search, insert and delete.

16. What are the tree traversals?

Easy

DFS: Inorder (Left, Root, Right) — gives sorted order for a BST; Preorder (Root, Left, Right) — used to copy/serialize; Postorder (Left, Right, Root) — used to delete/evaluate. BFS: Level order using a queue.

17. What is a balanced binary tree? Why does it matter?

Medium

A tree is balanced when the heights of left and right subtrees of every node differ by at most a small amount (1 for AVL). Balance keeps height O(log n), so BST operations stay O(log n) instead of degrading to O(n) like a skewed tree.

18. What is a heap? What is it used for?

Medium

A heap is a complete binary tree where every parent is ≥ (max-heap) or ≤ (min-heap) its children, usually stored in an array. It gives O(1) access to the max/min and O(log n) insert/extract. Used for priority queues, heap sort, Dijkstra, top-K problems and finding medians.

19. How do you find the kth largest element efficiently?

Medium

Keep a min-heap of size k: push every element and pop when size exceeds k — the root is the answer, O(n log k). Quickselect gives O(n) average time.

20. What is a graph? How can it be represented?

Easy

A graph is a set of vertices connected by edges (directed/undirected, weighted/unweighted). Representations: adjacency matrix (O(V²) space, O(1) edge check) and adjacency list (O(V + E) space, efficient for sparse graphs — most common).

21. BFS vs DFS?

Easy

BFS explores level by level using a queue; finds shortest paths in unweighted graphs. DFS goes deep using recursion/stack; used for cycle detection, topological sort, connected components and backtracking. Both are O(V + E).

22. Explain Dijkstra's algorithm and its limitation.

Medium

Dijkstra finds shortest paths from a source in a graph with non-negative weights. It repeatedly picks the unvisited node with the smallest distance (using a min-priority queue) and relaxes its edges. Complexity O((V + E) log V). It fails with negative edge weights — use Bellman-Ford instead.

23. What is topological sorting?

Medium

A linear ordering of vertices of a DAG such that for every edge u → v, u comes before v. Done with DFS (push to stack after visiting children) or Kahn's algorithm (repeatedly remove nodes with indegree 0). Used for task scheduling and build systems.

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

Medium

Floyd's tortoise and hare: move a slow pointer one step and a fast pointer two steps. If they meet, there is a cycle; if fast reaches null, there isn't. To find the cycle start, reset one pointer to head and move both one step until they meet. O(n) time, O(1) space.

25. How do you reverse a linked list?

Easy

Iteratively keep three pointers prev = null, curr = head, next. For each node: save next = curr.next, point curr.next = prev, move prev = curr, curr = next. At the end prev is the new head. O(n) time, O(1) space.

26. What is the two-pointer technique?

Easy

Using two indices that move through the data (from both ends or at different speeds) to avoid nested loops. Typical uses: pair sum in a sorted array, removing duplicates, reversing, palindrome check, merging sorted arrays — usually reducing O(n²) to O(n).

27. What is the sliding window technique?

Easy

Maintaining a window [l, r] over an array/string and updating its result incrementally as the window moves, instead of recomputing. Fixed-size windows (max sum of k elements) and variable-size windows (longest substring without repeats) both run in O(n).

28. What is the difference between a tree and a graph?

Easy

A tree is a special graph that is connected and acyclic, with exactly n − 1 edges and one path between any two nodes. Graphs can have cycles, be disconnected and have any number of edges.

29. What is a trie and where is it used?

Medium

A trie (prefix tree) stores strings character by character along paths from the root. Search/insert take O(length of word). Used for autocomplete, spell check, prefix matching and IP routing.

30. What is a disjoint set (Union-Find)?

Medium

A structure that keeps elements in non-overlapping sets with two operations: find (which set?) and union (merge sets). With path compression and union by rank both are nearly O(1). Used in Kruskal's MST and cycle detection.

31. What is a minimum spanning tree? Name two algorithms.

Medium

An MST connects all vertices of a weighted undirected graph with the minimum total edge weight and no cycles. Kruskal's sorts edges and adds the smallest that doesn't form a cycle (using DSU); Prim's grows the tree from a vertex using a priority queue.

32. What is the difference between O(log n) and O(n log n)?

Easy

O(log n) grows extremely slowly — e.g. binary search on a million items takes ~20 steps. O(n log n) does a log n amount of work for each of n items — typical of efficient sorting (merge sort) and is much larger than O(n) but far smaller than O(n²).

33. What is space complexity? Does recursion use extra space?

Easy

Space complexity is the extra memory an algorithm needs as a function of input size. Yes — every recursive call adds a frame to the call stack, so a recursion of depth d uses O(d) space (e.g. O(n) for naive recursive factorial).

34. What is amortized time complexity?

Medium

The average cost per operation over a sequence of operations. Example: a dynamic array occasionally doubles its size (O(n)), but averaged over many push_back calls each costs O(1) amortized.

35. What is a deque?

Easy

A double-ended queue that allows insert and delete at both ends in O(1). Used for sliding window maximum (monotonic deque), palindrome checks and implementing both stacks and queues.

36. What is a priority queue and how is it implemented?

Easy

A queue where each element has a priority and the highest (or lowest) priority element is removed first. It is usually implemented with a binary heap: O(log n) insert and remove, O(1) peek.

37. What is a monotonic stack?

Medium

A stack whose elements are kept in increasing or decreasing order — elements that break the order are popped. It solves "next greater/smaller element", stock span and largest rectangle in a histogram in O(n).

38. Why is the worst case of quick sort O(n²)?

Medium

If the pivot is always the smallest or largest element (e.g. first-element pivot on an already sorted array), each partition removes only one element, giving n + (n−1) + … = O(n²). Randomised or median-of-three pivots make this very unlikely.

39. Explain the difference between memo DP state and transition.

Hard

The state is the minimal set of parameters that describes a subproblem (e.g. dp[i][w] = best value using first i items with capacity w). The transition is the formula combining smaller states into the current one (take or skip item i). Defining these two is the core of every DP solution.

40. What is backtracking?

Medium

Building a solution step by step and undoing (backtracking) a choice when it can't lead to a valid solution. Used for N-Queens, Sudoku, permutations, subsets and maze paths. Pruning invalid branches early keeps it practical.

41. What is the Kadane algorithm?

Medium

An O(n) DP for the maximum subarray sum: keep cur = max(a[i], cur + a[i]) (best sum ending at i) and best = max(best, cur). It works because a negative running sum never helps a future subarray.

42. What is Floyd–Warshall used for?

Hard

Finding shortest paths between all pairs of vertices with DP over intermediate vertices: d[i][j] = min(d[i][j], d[i][k] + d[k][j]). Complexity O(V³). It handles negative edges (not negative cycles).

43. What is the difference between a complete and a full binary tree?

Easy

A full binary tree: every node has 0 or 2 children. A complete binary tree: all levels are filled except possibly the last, which is filled from the left. Heaps are complete binary trees.

44. How would you find duplicates in an array?

Easy

Use a hash set: insert each element and report it if it is already there — O(n) time, O(n) space. Alternatively sort and compare neighbours — O(n log n) time, O(1) extra space. If values are in 1..n, index marking with negation works in O(1) space.

45. What is the difference between LRU cache and LFU cache?

Hard

LRU evicts the least recently used item (hash map + doubly linked list gives O(1) get/put). LFU evicts the least frequently used item. LRU adapts quickly to changing access patterns; LFU keeps long-term popular items.

46. What are AVL and Red-Black trees?

Hard

Both are self-balancing BSTs with O(log n) operations. AVL trees are more strictly balanced (faster lookups, more rotations on insert/delete). Red-Black trees are looser (fewer rotations) and are used in std::map, Java TreeMap and the Linux scheduler.

47. What is bit manipulation? Give useful tricks.

Medium

Working directly with bits using & | ^ ~ << >>. Tricks: n & 1 checks odd; n & (n−1) removes the lowest set bit (and is 0 for powers of two); x ^ x = 0 finds the unique element; 1 << k builds masks.

48. How do you approach a DSA problem in an interview?

Easy

  1. Clarify the problem, inputs and edge cases. 2) Start with a brute-force idea and its complexity. 3) Optimise using a pattern (hashing, two pointers, binary search, DP…). 4) Dry-run on an example. 5) Write clean code. 6) Test edge cases and state the final time/space complexity.

49. What is the difference between divide-and-conquer and DP?

Medium

Both break problems into subproblems. In divide and conquer subproblems are independent (merge sort, binary search). In DP subproblems overlap, so results are stored and reused to avoid recomputation.

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

Medium

Run DFS keeping a recursion stack (or colours white/grey/black): reaching a node that is currently on the stack (grey) means a back edge, i.e. a cycle. Alternatively, Kahn's algorithm: if the topological sort can't include every node, the graph has a cycle. O(V + E).

More topics