Common Data Structures and Algorithms Interview Questions

Coding interviews look endless from the outside: thousands of problems, dozens of data structures, a new "top 150" list every month. From the inside they are much smaller. Most interview problems are built on about ten data structures and a dozen patterns, and the interviewer is checking whether you can recognise which one fits, explain why, and write it cleanly.

This guide covers the common data structures and algorithms that interviews ask about, the questions that come with each, and the patterns that solve most problems. Every section ends with what you should be able to say out loud, because that is what gets tested.

How DSA interviews are scored

A typical round gives you one or two problems in 45 minutes. You are judged on four things, roughly in this order:

• Problem solving – do you clarify the input, find a working approach, then improve it?
• Complexity – can you state the time and space cost of your solution, and of the alternatives?
• Code – is it correct, readable and free of off-by-one errors?
• Testing – do you walk through an example and the edge cases (empty input, one element, duplicates, negatives) before saying "done"?

Starting with a brute-force solution is fine. Silence is not. Say the brute force, state its cost, then say what you will improve.

Arrays and strings

Arrays give constant-time access by index and are where most interviews start. Strings are arrays of characters with one trap: in Java they are immutable, so building one with + in a loop is quadratic. Use StringBuilder.

Common questions: two sum, best time to buy and sell a stock, maximum subarray (Kadane's algorithm), move zeroes, rotate an array, longest substring without repeating characters, valid anagram, longest palindromic substring.

Be able to say: access is O(1), inserting or deleting in the middle is O(n) because elements shift, and a dynamic array (ArrayList) appends in amortised O(1).

Hashing: HashMap and HashSet

A hash map trades memory for speed: average O(1) insert and lookup. It is the most common way to turn an O(n²) solution into O(n). Whenever you write a nested loop that searches for something, ask whether a map could remember it instead.

// Two sum: return the indices of two numbers that add up to target. O(n) time, O(n) space.
int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();   // value -> index
    for (int i = 0; i < nums.length; i++) {
        Integer j = seen.get(target - nums[i]);
        if (j != null) return new int[] { j, i };
        seen.put(nums[i], i);
    }
    return new int[0];
}

Common questions: two sum, group anagrams, longest consecutive sequence, subarray sum equals K (prefix sums plus a map), first non-repeating character, top K frequent elements.

Be able to say: lookup is O(1) on average but O(n) in the worst case when many keys collide (Java 8+ turns a long bucket into a balanced tree, so the worst case becomes O(log n)). Keys need consistent equals and hashCode.

Linked lists

Linked lists test pointer handling more than algorithms. Draw the nodes before you code, and use a dummy head node to avoid special-casing the first element.

Common questions: reverse a linked list, detect a cycle (Floyd's slow and fast pointers), find the middle node, merge two sorted lists, remove the Nth node from the end, check whether a list is a palindrome, LRU cache (a hash map plus a doubly linked list).

ListNode reverse(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

Be able to say: insert and delete at a known node are O(1), but finding the node is O(n); there is no random access.

Stacks and queues

A stack is last in, first out; a queue is first in, first out. In Java use ArrayDeque for both rather than the legacy Stack class.

Common questions: valid parentheses, min stack, evaluate reverse Polish notation, daily temperatures and next greater element (a monotonic stack), implement a queue with two stacks, sliding window maximum (a monotonic deque).

Be able to say: a monotonic stack keeps its elements in increasing or decreasing order, so each element is pushed and popped at most once and "next greater element" runs in O(n), not O(n²).

Trees and binary search trees

Most tree problems are recursion: solve the problem for the left subtree, for the right subtree, and combine. Know the three depth-first orders (pre-, in- and post-order) and level-order traversal with a queue.

Common questions: maximum depth, invert a binary tree, check whether a tree is balanced, validate a binary search tree, lowest common ancestor, level-order traversal, diameter of a binary tree, serialize and deserialize a tree, kth smallest element in a BST.

int maxDepth(TreeNode node) {
    if (node == null) return 0;
    return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
}

Be able to say: an in-order traversal of a BST visits values in sorted order; search is O(log n) only while the tree is balanced and O(n) when it degenerates into a line. Recursion uses O(h) stack space, where h is the height.

Heaps and priority queues

A heap gives you the smallest (or largest) element in O(1) and removes it in O(log n). Reach for one whenever a problem says "top K", "Kth largest" or "merge K sorted".

Common questions: Kth largest element, top K frequent words, merge K sorted lists, find the median from a data stream (two heaps), task scheduler, meeting rooms II.

Be able to say: keeping a min-heap of size K gives the K largest elements in O(n log K), which beats sorting everything (O(n log n)) when K is small. Java's PriorityQueue is a min-heap by default; pass Comparator.reverseOrder() for a max-heap.

Graphs: BFS and DFS

Many problems are graphs in disguise: a grid of islands, a course schedule, word ladders, friend networks. Store the graph as an adjacency list and pick the traversal by the question.

• BFS (a queue) visits nodes in order of distance, so it finds the shortest path in an unweighted graph.
• DFS (recursion or a stack) explores a whole path first: connected components, cycle detection, topological sort, backtracking.
• Dijkstra (a heap) finds shortest paths when edges have non-negative weights.

Common questions: number of islands, clone a graph, course schedule (cycle detection or topological sort), rotting oranges (multi-source BFS), word ladder, network delay time (Dijkstra), number of connected components (also union-find).

Be able to say: BFS and DFS are O(V + E). Always keep a visited set, or a cycle will loop forever.

Sorting and binary search

You rarely write a sort in an interview, but you must know the trade-offs: merge sort is O(n log n) in every case and stable; quicksort is O(n log n) on average, O(n²) in the worst case, and sorts in place. Java sorts objects with a stable merge-sort variant (TimSort) and primitives with a dual-pivot quicksort.

Binary search is the pattern people underestimate. It works on any range where a condition flips from false to true once, not only on sorted arrays: "the smallest capacity that ships all packages in D days" is a binary search over the answer.

// First index whose value is >= target (or nums.length if none). O(log n).
int lowerBound(int[] nums, int target) {
    int lo = 0, hi = nums.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;   // avoids int overflow of (lo + hi)
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

Common questions: search in a rotated sorted array, find the first and last position of an element, find a peak element, Koko eating bananas, median of two sorted arrays, merge intervals (sort first).

Dynamic programming

Dynamic programming (DP) applies when a problem breaks into overlapping subproblems: the same smaller question gets asked again and again. Write the recursive solution first, cache its results (memoisation), then, if asked, turn it into a table filled bottom-up.

// Climbing stairs: ways to reach step n taking 1 or 2 steps. O(n) time, O(1) space.
int climbStairs(int n) {
    int prev = 1, curr = 1;            // ways to reach step 0 and step 1
    for (int i = 2; i <= n; i++) {
        int next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

Common questions: climbing stairs, house robber, coin change, longest increasing subsequence, longest common subsequence, 0/1 knapsack, word break, edit distance, unique paths.

Be able to say: the state (what the subproblem is), the transition (how it is built from smaller ones), the base case and the order of evaluation. If you can say those four things, the code follows.

Greedy and backtracking

A greedy algorithm makes the locally best choice at each step and never revisits it. It is fast but only correct when you can argue why the local choice is safe: interval scheduling (sort by end time), jump game, gas station.

Backtracking builds a solution step by step and undoes a step when it cannot lead anywhere: subsets, permutations, combination sum, N-Queens, word search. Its cost is exponential, so interviewers mostly check that you prune early and restore state correctly when you step back.

The patterns that solve most problems

• Two pointers – sorted arrays, pairs, palindromes, removing duplicates in place.
• Sliding window – "longest or shortest subarray or substring that…".
• Prefix sums – range sums and "subarray sum equals K".
• Hash map counting – frequencies, anagrams, "have I seen this before?".
• Binary search on the answer – "minimum X such that…".
• Monotonic stack – next greater or smaller element, histogram areas.
• BFS / DFS – grids, graphs, trees, shortest unweighted paths.
• Heap – top K, Kth element, merging sorted streams.
• Dynamic programming – counting ways, min or max cost, overlapping subproblems.
• Backtracking – "all combinations", "all permutations", puzzles.

Complexity you should know without thinking

• Array: access O(1), search O(n), insert in the middle O(n).
• Hash map: insert, delete and lookup O(1) on average.
• Balanced BST (TreeMap): insert, delete and lookup O(log n), plus sorted order.
• Heap: peek O(1), insert and remove O(log n), build from n elements O(n).
• Sorting: O(n log n). Binary search: O(log n).
• BFS and DFS: O(V + E).

How to prepare without drowning

• Study by pattern, not by problem count. Five problems per pattern that you truly understand beat fifty you skimmed.
• Re-solve, don't re-read. Come back to a problem three days later and write it from a blank file.
• Time yourself. Aim for a working solution to a medium problem in about 25 minutes.
• Keep short notes. One page per pattern with its template and two example problems is enough to revise from. We wrote about that in how to make DSA handwritten notes that you actually revise from.
• Practise out loud. A mock interview with a friend shows gaps that silent practice hides.

Preparing for a Java role? DSA is one hour a day in our 30-day Java interview roadmap, alongside core Java, collections and Spring Boot.

Go further

Our handwritten DSA notes condense every topic above, with diagrams and flowcharts, for quick revision before an interview. For hundreds of coding problems with worked explanations, see Java Learning Resources.