Data structures and algorithms (DSA) are the core of coding rounds at product companies and many IT services companies. These DSA interview questions cover arrays, linked lists, stacks, queues and Big O for freshers, then trees, graphs, hashing, sorting, dynamic programming and problem-solving patterns for experienced candidates.
30 questions · Updated
Fundamentals, definitions and simple scenarios. Good for freshers and warm-ups.
Big O describes how an algorithm's running time or memory grows as the input size grows, in the worst case, ignoring constants.
Common complexities are O(1) constant, O(log n) such as binary search, O(n) linear scan, O(n log n) efficient sorting, O(n²) nested loops, and O(2ⁿ) brute-force subsets.
It lets you compare approaches before writing code.
An array stores elements in contiguous memory, so access by index is O(1), but inserting or deleting in the middle is O(n) because elements must shift. A linked list stores nodes with pointers to the next node, so inserting or deleting at a known position is O(1), but access by index is O(n) and it uses extra memory for pointers and has poor cache locality.
A stack is last in, first out (LIFO): push adds to the top and pop removes from the top.
It is used for function calls, undo, and matching brackets.
A queue is first in, first out (FIFO): enqueue at the back, dequeue at the front, used for task scheduling and breadth-first search.
A deque allows both ends; a priority queue removes the highest-priority item first.
Binary search finds a value in a sorted array by comparing it with the middle element and discarding the half that cannot contain it, repeating until found or the range is empty, in O(log n) time.
Watch out for off-by-one errors and overflow when calculating the middle (use low + (high - low) / 2).
The same idea applies to "binary search on the answer" problems.
You can often make an algorithm faster by using more memory, and the reverse.
For example, checking for duplicates with nested loops takes O(n²) time and O(1) extra space, while a hash set takes O(n) time and O(n) space.
Caching and memoisation trade memory for speed.
The right choice depends on input size and memory limits.
Recursion is when a function calls itself on a smaller version of the problem, with a base case that stops it, such as factorial(n) = n × factorial(n − 1) with factorial(0) = 1.
It suits trees, graphs and divide-and-conquer.
Each call uses stack space, so deep recursion can cause a stack overflow, and naive recursion can repeat work, which memoisation fixes.
A singly linked list has nodes pointing to the next node only.
A doubly linked list has pointers to both next and previous nodes, which allows removal of a known node in O(1) and backward traversal, at the cost of extra memory.
A circular linked list connects the last node back to the first, which suits round-robin scheduling.
A heap is a complete binary tree, usually stored in an array, where each parent is smaller than its children (min-heap) or larger (max-heap).
The smallest or largest element is always at the top, insertion and removal take O(log n), and building a heap takes O(n).
Heaps implement priority queues and are used in Dijkstra's algorithm, scheduling and "top k" problems.
Depth-first traversals: inorder (left, node, right), which gives sorted order in a binary search tree; preorder (node, left, right), used to copy a tree; and postorder (left, right, node), used to delete a tree or evaluate expressions.
Breadth-first (level order) traversal visits level by level using a queue.
All run in O(n) time.
An adjacency list stores, for each vertex, a list of its neighbours, using O(V + E) space, which is efficient for sparse graphs and the usual choice.
An adjacency matrix is a V by V grid where each cell shows whether an edge exists, using O(V²) space but checking an edge in O(1), which suits dense graphs.
An edge list suits algorithms such as Kruskal's.
Two pointers move through an array, often from both ends towards each other or at different speeds, to solve problems in O(n) without extra space. Examples are checking if a string is a palindrome, finding a pair with a given sum in a sorted array, removing duplicates in place, and detecting a cycle in a linked list with slow and fast pointers.
Applied problems, trade-offs and questions about your own projects.
A hash table stores key-value pairs in an array.
A hash function converts each key into an index.
Collisions, where two keys map to the same index, are handled by chaining (a list per bucket) or open addressing (probing for another slot).
With a good hash function and resizing when the load factor gets high, insert, delete and lookup are O(1) on average and O(n) in the worst case.
In a binary search tree, each node's left subtree has smaller values and the right subtree larger values, so search, insert and delete take O(height).
A balanced tree has height O(log n), but inserting sorted data into a plain BST creates a chain of height n, making operations O(n).
Self-balancing trees such as AVL and red-black trees keep the height logarithmic.
Breadth-first search explores a graph level by level using a queue, and finds the shortest path in an unweighted graph.
Depth-first search goes as deep as possible along each branch before backtracking, using recursion or a stack, and suits cycle detection, topological sorting and exploring all paths.
Both run in O(V + E) time.
Merge sort divides the array, sorts halves and merges them; it is always O(n log n) and stable but needs O(n) extra space.
Quick sort partitions around a pivot; it is O(n log n) on average and very fast in practice, but O(n²) in the worst case and not stable.
Heap sort uses a heap, is O(n log n) in all cases with O(1) extra space, but is not stable.
A sliding window keeps a range of elements and moves its edges forward instead of recomputing from scratch, turning O(n²) solutions into O(n). A fixed-size window solves problems such as the maximum sum of k consecutive elements; a variable-size window expands and shrinks to solve problems such as the longest substring without repeating characters, often with a hash map of counts.
A prefix sum array stores the running total up to each index, so the sum of any range from i to j is prefix[j + 1] − prefix[i] in O(1) after O(n) preparation. Combined with a hash map, it solves problems such as counting subarrays that sum to k. The idea extends to two dimensions for matrix region sums.
A trie (prefix tree) stores strings character by character, with each path from the root spelling a prefix.
Inserting and searching take O(length of the word), regardless of how many words are stored, and finding all words with a given prefix is efficient.
Tries are used for autocomplete, spell checkers and IP routing, at the cost of extra memory.
Union-find (disjoint set union) tracks which elements belong to the same group, with find (which group is this element in?) and union (merge two groups).
With path compression and union by rank, both operations take almost constant time.
It is used to detect cycles in undirected graphs, in Kruskal's minimum spanning tree algorithm and to count connected components.
A topological sort orders the vertices of a directed acyclic graph so every edge goes from earlier to later, such as ordering courses with prerequisites or build steps with dependencies.
Kahn's algorithm repeatedly removes vertices with no incoming edges using a queue, and the DFS method adds vertices after visiting their descendants.
If not all vertices can be ordered, the graph has a cycle.
A greedy algorithm makes the best local choice at each step and never reconsiders, which is fast but only correct when the problem has the greedy-choice property, such as activity selection or Huffman coding. Dynamic programming considers all relevant choices by solving overlapping subproblems, so it is correct more generally, such as coin change with arbitrary coins, where greedy can fail.
Backtracking builds a solution step by step and abandons a path as soon as it cannot lead to a valid solution, then tries the next option.
It is used for generating permutations, combinations and subsets, solving N-Queens and Sudoku, and word search.
Its worst case is exponential, so pruning invalid branches early is what makes it practical.
System design, deep internals, leadership and tough follow-ups.
Dynamic programming solves problems by breaking them into overlapping subproblems and storing their results to avoid recomputation.
A problem fits DP when it has optimal substructure (the best solution is built from best solutions to subproblems) and overlapping subproblems, often when asked for the minimum, maximum or number of ways.
Examples are knapsack, longest common subsequence and coin change, solved top-down with memoisation or bottom-up with a table.
Dijkstra's algorithm finds shortest paths from one source when all edge weights are non-negative, using a priority queue in O((V + E) log V).
Bellman-Ford handles negative weights and detects negative cycles in O(V × E).
Floyd-Warshall finds shortest paths between all pairs in O(V³).
For unweighted graphs, BFS is enough, and A* uses a heuristic to speed up searches like maps.
I clarify the problem, inputs, outputs and edge cases with examples, then describe a brute-force solution and its complexity.
I look for patterns such as two pointers, sliding window, hashing, binary search, BFS or DFS, heaps or dynamic programming to improve it, and explain the trade-offs before coding.
I write clean code, test it with examples and edge cases, and state the final time and space complexity.
Both answer range queries on an array that changes.
A Fenwick tree (binary indexed tree) supports prefix sums and point updates in O(log n) with very little code.
A segment tree is more general: it supports range sums, minimums, maximums and, with lazy propagation, range updates, all in O(log n).
They appear in competitive programming and advanced interviews.
An LRU cache evicts the least recently used item when full, with get and put in O(1).
Combine a hash map from keys to nodes with a doubly linked list ordered by use: on access, move the node to the front; on insert, add at the front and remove the tail if over capacity.
Many languages offer shortcuts, such as LinkedHashMap in Java or OrderedDict in Python.
Amortised analysis averages the cost of operations over a sequence, so occasional expensive operations are balanced by many cheap ones. Appending to a dynamic array is O(1) amortised: most appends are cheap, and when the array is full it doubles in size, copying all elements, but this happens rarely enough that the average cost per append stays constant.
A minimum spanning tree connects all vertices of a weighted, undirected graph with the lowest total edge weight and no cycles, which models cheapest network wiring.
Kruskal's algorithm sorts edges by weight and adds each one that does not create a cycle, using union-find, in O(E log E).
Prim's algorithm grows the tree from one vertex using a priority queue, in O(E log V).
n & (n − 1) removes the lowest set bit, so it checks for a power of two and counts set bits. x ^ x = 0, so XOR of all elements finds the one number that appears once. n & 1 checks for odd numbers, shifts multiply or divide by powers of two, and masks represent subsets, used in bitmask dynamic programming.
Tasks you build live in 30 to 60 minutes. What interviewers look for, plus a compact solution to compare with yours.
A classic.
Walk the list once, reversing each next pointer, in O(n) time and O(1) space.
Be ready to write the recursive version too.
def reverse_list(head):
prev = None
while head:
head.next, prev, head = prev, head, head.next
return prevFloyd's tortoise and hare: a slow pointer moves one step and a fast pointer two; if there is a cycle they meet. O(n) time and O(1) space, better than storing visited nodes in a set.
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
return True
return FalseTests stack usage. Push opening brackets; on a closing bracket, the top of the stack must be its matching opener.
def is_balanced(s):
pairs = {')': '(', ']': '[', '}': '{'}
stack = []
for ch in s:
if ch in '([{':
stack.append(ch)
elif ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
return not stack
is_balanced("{[()]}") # TrueA sliding-window problem. Track the last index of each character and move the window start past any repeat, in O(n).
def longest_unique(s):
last, start, best = {}, 0, 0
for i, ch in enumerate(s):
if ch in last and last[ch] >= start:
start = last[ch] + 1
last[ch] = i
best = max(best, i - start + 1)
return best
longest_unique("abcabcbb") # 3See all Software Engineer interview questions, covering Data Structures, Algorithms, OOP, System Design, Operating Systems and more.