80%
DSA 28 interview questions0/28 questions known
1. Foundations
QWhat is Big-O? Give the complexity of common operations.Big-O describes how time or memory grows with input size in the worst case, ignoring constants: O(2n + 5) is O(n).
QArray vs linked list: when would you use each?Array: contiguous memory.
QRecursion vs iteration: trade-offs?Any recursion can be written as iteration with an explicit stack, and vice versa.
QHow do you approach a coding problem you have never seen before?Interviewers grade the process as much as the code:
2. Arrays & hashing
QTwo Sum: find indices of two numbers that add up to a target.Brute force checks every pair: O(n^2).
QGroup anagrams together.Anagrams share the same letters, so give each word a canonical key and group by it in a hash map.
QMaximum subarray sum (Kadane's algorithm).At each element decide: extend the previous subarray or start fresh here.
QMerge overlapping intervals.Sort by start, then sweep.
QSort an array of 0s, 1s and 2s in one pass (Dutch national flag).Three pointers split the array into regions: [0, low) holds 0s, [low, mid) 1s, (high, end] 2s, and [mid, high] is unknown.
3. Patterns
QWhat is the two-pointer technique? Give examples.Two indexes move through the data instead of nested loops, turning O(n^2) into O(n).
QLongest substring without repeating characters (sliding window).A sliding window keeps a range [left, right] that satisfies a condition.
QImplement binary search. What is "binary search on the answer"?On a sorted array, compare with the middle and discard half each step: O(log n) time, O(1) space.
4. Lists & stacks
QReverse a singly linked list.Walk the list once and flip each next pointer to point backwards.
QDetect a cycle in a linked list (Floyd's algorithm).Floyd's tortoise and hare: move slow one step and fast two steps at a time.
QValid parentheses: check that brackets are balanced.Use a stack.
QDesign and implement an LRU cache with O(1) get and put.Classic design: a hash map for O(1) lookup plus a doubly linked list ordered by recency.
5. Trees
QExplain tree traversals: preorder, inorder, postorder, level order.Depth-first orders differ in when you visit the node relative to its children: - Preorder (node, left, right): copy or serialise a tree -…
QFind the maximum depth of a binary tree.Recursive definition: an empty tree has depth 0; otherwise depth is 1 + max(depth(left), depth(right)).
QCheck whether a binary tree is a valid binary search tree.The trap: checking only left.val < node.val < right.val is not enough.
QLowest common ancestor in a BST (and in a plain binary tree).In a BST, use the ordering: if both values are smaller than the node, go left; if both are larger, go right; otherwise the paths split…
QWhat is a trie and when would you use one?A trie (prefix tree) stores strings character by character: each node has children keyed by letter and an end flag.
6. Heaps & sorting
QFind the top K frequent elements. How does a heap help?Count frequencies with a hash map, then keep a min-heap of size k: push each item, and if the heap grows past k, pop the smallest.
QFind the kth largest element in an array.Three answers, from simplest to best: - Sort descending and take index k - 1: O(n log n) - Min-heap of size k: the top is the kth largest…
QCompare quicksort, mergesort and heapsort. What is a stable sort?- Quicksort: average O(n log n), worst O(n^2) (bad pivots; randomise), O(log n) stack space, in place, not stable.
7. Graphs
QBFS vs DFS: how do they differ and when do you use each?BFS explores level by level using a queue.
QDetect a cycle in a directed graph and produce a topological order (course schedule).A topological order lists nodes so every edge u -> v has u before v (build order, course prerequisites).
QHow does Dijkstra's algorithm work?Dijkstra finds the shortest paths from one source in a graph with non-negative edge weights.
8. Dynamic programming
QDynamic programming: memoisation vs tabulation (climbing stairs, coin change).DP applies when a problem has overlapping subproblems and optimal substructure.