Easy Data Structures and Algorithms Interview Questions

Show answer

Time complexity describes how the number of steps an algorithm performs grows as the input size n grows, ignoring machine speed. Big-O gives an upper bound on that growth for large n and drops constants and lower terms, so 3n squared plus 5n becomes O(n squared). It lets you compare approaches before coding; for example binary search at O(log n) beats linear search at O(n) on large sorted data.

What is the difference between Big-O, Big-Omega and Big-Theta?

Show answer

Big-O is an upper bound: the algorithm grows no faster than this. Big-Omega is a lower bound: it grows at least this fast. Big-Theta is a tight bound, when the upper and lower bounds match. Merge sort is Theta(n log n) because it always does that much work. In interviews people usually say Big-O to mean the tight worst-case bound, but you should know the formal difference.

What is space complexity and how is auxiliary space different?

Show answer

Space complexity is the total memory an algorithm uses relative to input size, including the input itself. Auxiliary space counts only the extra memory beyond the input, such as temporary arrays, hash maps and the recursion stack. Merge sort needs O(n) auxiliary space for merging, while heap sort needs O(1). Interviewers usually mean auxiliary space when they ask you to reduce space usage.

List common complexity classes from fastest to slowest with examples.

Show answer

O(1): array index access or a hash lookup on average. O(log n): binary search. O(n): linear scan. O(n log n): merge sort and heap sort. O(n squared): nested loops over pairs, as in bubble sort. O(2 to the power n): generating all subsets. O(n factorial): generating all permutations. For n around one lakh, anything up to O(n log n) is comfortable, while O(n squared) usually times out.

What is recursion and why is a base case essential?

Show answer

Recursion is when a function solves a problem by calling itself on smaller subproblems. Each call gets its own frame on the call stack holding parameters and local variables. The base case is the condition where the function returns directly without recursing, such as n equal to 0 for factorial. Without a correct base case, calls never stop and the program fails with a stack overflow.

Write recursive Fibonacci and then optimise it with memoisation.

Show answer

from functools import lru_cache def fib_naive(n): # O(2^n) time if n < 2: return n return fib_naive(n - 1) + fib_naive(n - 2) @lru_cache(maxsize=None) def fib_memo(n): # O(n) time, O(n) space if n < 2: return n return fib_memo(n - 1) + fib_memo(n - 2) def fib_iter(n): # O(n) time, O(1) space a, b = 0, 1 for _ in range(n): a, b = b, a + b return a

Solve the Tower of Hanoi problem recursively.

Show answer

def hanoi(n, src, dst, aux, moves): if n == 0: return hanoi(n - 1, src, aux, dst, moves) # move n-1 disks out of the way moves.append((src, dst)) # move the largest disk hanoi(n - 1, aux, dst, src, moves) # move n-1 disks on top of it moves = [] hanoi(3, 'A', 'C', 'B', moves) print(len(moves)) # 7, since the count is 2^n - 1

Find the GCD of two numbers using the Euclidean algorithm.

Show answer

// Java static long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); } static long lcm(long a, long b) { return a / gcd(a, b) * b; // divide first to avoid overflow } // Runs in O(log(min(a, b))) because remainders shrink quickly.

How do you approach a coding problem you have never seen before in an interview?

Show answer

Situation: in a mock interview I got an unfamiliar graph problem. Task: solve it while keeping the interviewer involved. Action: I restated the problem, asked about constraints and edge cases, worked through a small example by hand, explained a brute-force idea with its complexity, then improved it step by step and coded only after agreement. I tested with edge cases aloud. Result: I reached an optimal solution and got positive feedback on communication.

What is the difference between a static array and a dynamic array?

Show answer

A static array has a fixed size set at creation, such as int[] in Java, and offers O(1) index access with contiguous memory. A dynamic array such as Java ArrayList or Python list grows automatically by allocating a larger block and copying elements, giving amortised O(1) append. Both have O(n) insertion or deletion in the middle because elements must shift. Dynamic arrays trade a little memory for flexibility.

What is the two pointer technique and when is it used?

Show answer

Two pointers move through an array or string, often from both ends or at different speeds, to avoid nested loops. On a sorted array you can find a pair with a given sum in O(n) by moving left or right depending on the current sum. It is also used for reversing, removing duplicates in place, merging sorted arrays, palindrome checks and partitioning. It usually needs sorted data or a monotonic condition.

Strings are immutable in Java and Python. How does that affect algorithm complexity?

Show answer

Every modification creates a new string, so building a string by concatenation inside a loop can copy characters repeatedly and become O(n squared). Use StringBuilder in Java or collect parts in a list and call join in Python, which is O(n) overall. Immutability also makes strings safe as hash map keys and lets runtimes cache their hash codes, which is why they are good dictionary keys.

What is the difference between a subarray, a subsequence and a substring?

Show answer

A subarray is a contiguous part of an array, and an array of n elements has n times n plus 1 over 2 of them. A substring is the same idea for strings. A subsequence keeps the original order but may skip elements, so there are 2 to the power n of them. This matters for choosing techniques: sliding window and prefix sums suit subarrays, while subsequence problems often need dynamic programming.

How would you check whether two strings are anagrams, and what changes if input can contain any Unicode characters?

Show answer

For lowercase English letters, compare character counts using an array of 26 integers in O(n) time and O(1) space; sorting both strings also works in O(n log n). With arbitrary Unicode, use a hash map of counts instead of a fixed array. I would also clarify whether case and spaces matter and whether to normalise accented characters, since visually identical text can have different code point sequences.

Solve two sum: return the indices of two numbers that add up to the target.

Show answer

def two_sum(nums, target): seen = {} # value -> index for i, x in enumerate(nums): need = target - x if need in seen: return [seen[need], i] seen[x] = i return [] # two_sum([2, 7, 11, 15], 9) -> [0, 1] # O(n) time, O(n) space; sorting + two pointers gives O(1) space but loses indices

Implement Kadane's algorithm for the maximum subarray sum.

Show answer

def max_subarray(nums): best = current = nums[0] for x in nums[1:]: current = max(x, current + x) # extend or start fresh best = max(best, current) return best # max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) -> 6 (subarray 4, -1, 2, 1)

Check whether a string is a palindrome, ignoring case and non-alphanumeric characters.

Show answer

// Java static boolean isPalindrome(String s) { int i = 0, j = s.length() - 1; while (i < j) { char a = s.charAt(i), b = s.charAt(j); if (!Character.isLetterOrDigit(a)) { i++; continue; } if (!Character.isLetterOrDigit(b)) { j--; continue; } if (Character.toLowerCase(a) != Character.toLowerCase(b)) return false; i++; j--; } return true; } // Two pointers, O(n) time, O(1) space.

Describe a time you got stuck during a coding interview or contest. How did you recover?

Show answer

Situation: in an online round I could not find an efficient approach for a subarray problem. Task: still score well under time pressure. Action: I first submitted a correct brute-force solution for partial marks, then wrote out small examples and noticed the prefix sums pattern, which led to an O(n) solution with a hash map. Result: I solved it with ten minutes left and learned to secure a working solution before optimising.

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

Show answer

An array stores elements contiguously, giving O(1) index access and good cache performance, but inserting or deleting in the middle costs O(n) because elements shift. A linked list stores nodes with pointers to the next node, so insertion and deletion at a known node are O(1), but finding the i-th element takes O(n) and each node has pointer overhead. Arrays suit read-heavy work, lists suit frequent splicing.

Compare singly, doubly and circular linked lists.

Show answer

A singly linked list node points only to the next node, using less memory but allowing traversal in one direction. A doubly linked list node also points to the previous node, enabling backward traversal and O(1) deletion of a given node, which LRU caches need. A circular list connects the last node back to the first, useful for round-robin scheduling and buffers. Each extra pointer adds memory and update complexity.

What is a stack and where is it used?

Show answer

A stack is a last-in, first-out structure with push, pop and peek, each O(1). It can be built on an array or a linked list. Uses include function call management, undo features, expression evaluation and conversion between infix and postfix, bracket matching, browser history and iterative DFS. In Java use ArrayDeque rather than the legacy Stack class; in Python a list with append and pop works well.

What are a queue, a deque and a circular queue?

Show answer

A queue is first-in, first-out with enqueue at the back and dequeue at the front, used in BFS, task scheduling and buffering. A deque allows insertion and removal at both ends in O(1), as in Python collections.deque or Java ArrayDeque. A circular queue uses a fixed array with head and tail indices that wrap around modulo capacity, avoiding shifting and wasted space, common in ring buffers and OS schedulers.

How would you implement browser back and forward navigation?

Show answer

Use two stacks plus the current page. Visiting a new page pushes the current page onto the back stack, sets the new page as current and clears the forward stack. Back pushes current onto the forward stack and pops the back stack into current. Forward does the reverse. Each operation is O(1). A doubly linked list with a cursor is an alternative that makes it easy to show the full history.

Users enter formulas with brackets in a spreadsheet tool. How do you validate that the brackets are balanced?

Show answer

Scan the formula once with a stack. Push every opening bracket; on a closing bracket, check that the stack is not empty and its top is the matching opening type, then pop. Ignore other characters. At the end the stack must be empty. This is O(n) time and handles nested mixes such as parentheses inside square brackets. To show useful errors, record the position of the first mismatch or unclosed bracket.

Merge two sorted linked lists into one sorted list.

Show answer

class ListNode: def __init__(self, val=0, nxt=None): self.val = val self.next = nxt def merge(a, b): dummy = tail = ListNode() while a and b: if a.val <= b.val: tail.next, a = a, a.next else: tail.next, b = b, b.next tail = tail.next tail.next = a or b return dummy.next # O(m + n) time, O(1) extra space

Check whether a string of brackets is valid.

Show answer

// Java static boolean isValid(String s) { Deque<Character> st = new ArrayDeque<>(); for (char c : s.toCharArray()) { if (c == '(') st.push(')'); else if (c == '[') st.push(']'); else if (c == '{') st.push('}'); else if (st.isEmpty() || st.pop() != c) return false; } return st.isEmpty(); } // Push the expected closing bracket; O(n) time, O(n) space.

Explain basic binary tree terminology: root, leaf, height and depth.

Show answer

The root is the top node with no parent. A leaf has no children. The depth of a node is the number of edges from the root to it, and the height of a node is the number of edges on the longest path down to a leaf; the tree's height is the root's height. In a binary tree each node has at most two children. A tree with n nodes has n minus 1 edges.

What are inorder, preorder, postorder and level order traversals?

Show answer

Inorder visits left subtree, node, then right subtree, and gives sorted order for a BST. Preorder visits node, left, then right, which is useful for copying or serialising a tree. Postorder visits left, right, then node, used for deleting trees or computing subtree results. Level order visits nodes level by level using a queue. All take O(n) time; recursive versions use O(h) stack space.

What is a binary search tree and what is its time complexity?

Show answer

In a BST every node's left subtree contains smaller keys and the right subtree larger keys. Search, insert and delete follow one path from the root, so they take O(h) time, where h is the height. A balanced tree has h about log n, giving O(log n). Inserting sorted data into a plain BST creates a skewed tree that behaves like a linked list with O(n) operations, which is why balanced variants exist.

What is the difference between full, complete and perfect binary trees?

Show answer

In a full binary tree every node has zero or two children. In a complete binary tree every level except possibly the last is completely filled, and the last level is filled from the left, which is exactly the shape of a binary heap and allows array storage. A perfect binary tree has all internal nodes with two children and all leaves at the same level, containing 2 to the power h plus 1, minus 1 nodes.

Write an iterative inorder traversal of a binary tree.

Show answer

def inorder(root): result, stack = [], [] node = root while node or stack: while node: # go as far left as possible stack.append(node) node = node.left node = stack.pop() result.append(node.val) # visit node = node.right # then the right subtree return result # O(n) time, O(h) space; no recursion limit issues

Find the maximum depth of a binary tree.

Show answer

// Java static int maxDepth(TreeNode root) { if (root == null) return 0; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); } // Each node visited once: O(n) time, O(h) stack space. // BFS alternative: count levels while processing the queue level by level.

Tell me about the project you are most proud of.

Show answer

Situation: in college I noticed students struggled to find relevant previous-year questions. Task: build a searchable question bank. Action: I built a small web app with a trie-based autocomplete for topics and an inverted index for keyword search, wrote tests and collected feedback from classmates. Result: over 400 students used it during exams, search stayed under 50 milliseconds, and I learned how data structure choices affect real users.

What is a heap and how is it stored in an array?

Show answer

A binary heap is a complete binary tree where every parent is smaller than its children in a min-heap or larger in a max-heap, so the root is the minimum or maximum. Because the tree is complete, it is stored in an array without pointers: for index i, children are at 2i plus 1 and 2i plus 2 and the parent at (i minus 1) divided by 2. This layout is compact and cache friendly.

How do you use a priority queue in Java and Python?

Show answer

Java's PriorityQueue is a min-heap by default; pass Comparator.reverseOrder() or a lambda for a max-heap or custom ordering, and use offer, poll and peek. Python's heapq module works on a plain list as a min-heap with heappush, heappop and heapify. For a max-heap in Python, push negated values. To order by priority with ties, push tuples such as (priority, counter, item).

A cashier system uses the greedy rule of always giving the largest coin first. When can this fail?

Show answer

Greedy coin change is optimal for canonical systems such as Indian rupee denominations, but fails for arbitrary coin sets. With coins 1, 3 and 4 and amount 6, greedy gives 4 plus 1 plus 1, three coins, while 3 plus 3 uses only two. For arbitrary denominations, use dynamic programming where dp of x is the minimum coins for amount x, computed in O(amount times number of coins).

Find the kth largest element in an array using a heap.

Show answer

import heapq def kth_largest(nums, k): heap = [] for x in nums: heapq.heappush(heap, x) if len(heap) > k: heapq.heappop(heap) # drop the smallest return heap[0] # smallest of the k largest # kth_largest([3, 2, 1, 5, 6, 4], 2) -> 5 # O(n log k) time, O(k) space; quickselect gives O(n) average

Tell me about a time you had to make a decision with incomplete information.

Show answer

Situation: during a release, a performance test showed occasional slow responses but the logs were incomplete. Task: decide whether to ship on schedule. Action: I listed what we knew, estimated the impact using the available percentiles, proposed shipping behind a feature flag with extra monitoring, and prepared a rollback plan. Result: we shipped on time, the extra metrics revealed a slow cache warm-up that we fixed in the next patch with no user complaints.

Why do you want to work at a product company as a software engineer?

Show answer

Situation: during my internship I worked on a feature used by thousands of people and saw how algorithm choices changed response times. Task: I want a role where engineering quality directly affects users. Action: I have practised data structures, system basics and clean coding, and built projects end to end. Result: I believe a product company will let me own features, learn from strong engineers and see the real impact of my work.

What are the ways to represent a graph and when would you use each?

Show answer

An adjacency list stores, for each vertex, a list of neighbours, using O(V plus E) memory; it is best for sparse graphs such as road or social networks and makes iterating neighbours fast. An adjacency matrix uses a V by V grid, O(V squared) memory, with O(1) edge checks; it suits dense or small graphs and Floyd-Warshall. An edge list is a simple list of pairs, convenient for Kruskal's algorithm.

What is the difference between BFS and DFS, and when do you use each?

Show answer

BFS explores level by level with a queue and finds shortest paths in unweighted graphs, such as minimum moves on a board. DFS goes as deep as possible with recursion or a stack and suits cycle detection, topological sorting, connected components, path existence and backtracking. Both run in O(V plus E). BFS can use more memory on wide graphs, while DFS can hit recursion limits on deep ones.

Explain directed, undirected, weighted graphs and DAGs.

Show answer

In an undirected graph edges work both ways, like friendships. In a directed graph edges have direction, like follows or web links. A weighted graph attaches a cost to each edge, like distance or price, which matters for shortest path algorithms. A DAG is a directed acyclic graph with no cycles; it models dependencies such as course prerequisites or build steps and allows topological ordering and linear-time shortest paths.

A metro app must find the route with the fewest stations between two stops. Which algorithm would you use?

Show answer

If every hop counts equally, the network is an unweighted graph and BFS from the source gives the minimum number of stations in O(V plus E). I would store a parent for each visited station to reconstruct the path. If the goal changes to minimum travel time with different segment durations or interchange penalties, I would switch to Dijkstra with those weights, adding interchange cost as edges between line nodes.

A satellite image is a grid of land and water cells. How do you count the islands?

Show answer

Treat each land cell as a vertex connected to its four neighbours that are also land. Scan the grid; when you find unvisited land, increase the island count and run DFS or BFS to mark the whole connected island as visited. Each cell is visited once, so the time is O(rows times columns). Use BFS or an explicit stack for very large grids to avoid recursion limits, or Union-Find if cells arrive over time.

Count the number of islands in a grid of 1s and 0s.

Show answer

// Java static int numIslands(char[][] g) { int count = 0; for (int r = 0; r < g.length; r++) for (int c = 0; c < g[0].length; c++) if (g[r][c] == '1') { count++; sink(g, r, c); } return count; } static void sink(char[][] g, int r, int c) { if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != '1') return; g[r][c] = '0'; // mark visited sink(g, r + 1, c); sink(g, r - 1, c); sink(g, r, c + 1); sink(g, r, c - 1); } // O(rows * cols) time

Where do you see yourself in five years?

Show answer

Situation: I am starting my career with a strong interest in solving algorithmic and system problems. Task: grow into an engineer others rely on. Action: in the first years I want to master the codebase, deliver features reliably and deepen my skills in data structures, system design and the domain. Result: in five years I see myself as a senior engineer owning important components, mentoring juniors and contributing to design decisions in this team.

What is dynamic programming, and what are overlapping subproblems and optimal substructure?

Show answer

Dynamic programming solves a problem by combining solutions of smaller subproblems and storing them so each is computed only once. It applies when a problem has overlapping subproblems, meaning the same smaller problems repeat, as in Fibonacci, and optimal substructure, meaning the best answer can be built from best answers to subproblems, as in shortest paths. DP often turns exponential brute force into polynomial time.

What is the difference between memoisation and tabulation?

Show answer

Memoisation is top-down: write the natural recursion and cache results in a map or array, so only needed states are computed, but recursion depth can be a problem. Tabulation is bottom-up: fill a table iteratively from base cases in an order where dependencies are ready, avoiding recursion overhead and making space optimisation easier. Both usually have the same time complexity; choose whichever is clearer for the problem.

A warehouse robot moves only right or down on a grid with some blocked cells. How do you count the number of paths?

Show answer

Use DP where dp[r][c] is the number of ways to reach cell r, c. A blocked cell has 0 ways; the start has 1; every other cell is dp[r-1][c] plus dp[r][c-1]. Fill row by row in O(rows times columns), and keep a single row array to use O(columns) space. Counts can become huge, so problems often ask for the result modulo 10 to the power 9 plus 7.

Solve climbing stairs: how many ways are there to climb n steps taking 1 or 2 steps at a time?

Show answer

def climb_stairs(n): if n <= 2: return n prev2, prev1 = 1, 2 # ways(1), ways(2) for _ in range(3, n + 1): prev2, prev1 = prev1, prev1 + prev2 return prev1 # ways(n) = ways(n-1) + ways(n-2): a Fibonacci pattern # climb_stairs(5) -> 8; O(n) time, O(1) space

Solve house robber: maximise money robbed from houses in a row without robbing two adjacent houses.

Show answer

def rob(nums): take, skip = 0, 0 # best if the previous house is taken or skipped for x in nums: take, skip = skip + x, max(take, skip) return max(take, skip) # rob([2, 7, 9, 3, 1]) -> 12 (2 + 9 + 1) # dp[i] = max(dp[i-1], dp[i-2] + nums[i]); O(n) time, O(1) space

Tell me about a time you kept working on a hard problem when others had given up.

Show answer

Situation: a scheduling feature produced suboptimal plans and the team was ready to accept it. Task: I believed an exact solution was possible for our sizes. Action: I spent evenings modelling it, found the number of shifts was small enough for bitmask DP, built a prototype, and validated it against the old greedy output on 200 real cases. Result: plans improved by about 12 percent in cost, and the feature shipped with the new algorithm.

How does binary search work and what does it require?

Show answer

Binary search works on sorted data or any monotonic condition. Compare the middle element with the target; if equal, return it, if the target is smaller search the left half, otherwise the right half. Each step halves the search space, giving O(log n) time, so a million elements need about 20 comparisons. It requires random access, so it suits arrays but not linked lists.

What is a stable sort and why does stability matter?

Show answer

A stable sort keeps elements with equal keys in their original relative order. It matters when sorting by multiple keys in passes: sort employees by salary, then stably by department, and salaries stay ordered within each department. Merge sort, insertion sort and Timsort are stable; quicksort and heap sort usually are not. Java uses a stable sort for objects, and Python's sorted is always stable.

What is backtracking?

Show answer

Backtracking builds a solution step by step and abandons a partial solution as soon as it cannot lead to a valid answer, then undoes the last choice and tries the next. It is a DFS over the space of choices. It solves permutations, combinations, subsets, N-Queens, Sudoku and word search. The worst case is often exponential, so good pruning, such as checking constraints early, is what makes it practical.

A bug appeared somewhere in the last 1000 commits. How would you find the commit that introduced it quickly?

Show answer

Commits form an ordered sequence where everything after the bad commit fails and everything before passes, which is a monotonic condition, so binary search applies. Test the middle commit; if it fails, search the earlier half, otherwise the later half. About 10 tests find the culprit among 1000 commits. git bisect automates this, and git bisect run can execute a test script at each step.

HR wants an employee list sorted by department, and by salary within each department. How would you do it?

Show answer

Either sort once with a composite key, department first and salary second, using a comparator in Java or a tuple key in Python, or do two passes with a stable sort: first by salary, then by department, relying on stability to keep salary order within departments. The single composite-key sort is clearer. Both are O(n log n), and I would clarify whether salary should be ascending or descending.

Write an iterative binary search that returns the index of a target or -1.

Show answer

// Java static int binarySearch(int[] a, int target) { int lo = 0, hi = a.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; // avoids overflow if (a[mid] == target) return mid; if (a[mid] < target) lo = mid + 1; else hi = mid - 1; } return -1; } // O(log n) time, O(1) space

Compute the integer square root of a number using binary search.

Show answer

def int_sqrt(x): lo, hi = 0, x ans = 0 while lo <= hi: mid = (lo + hi) // 2 if mid * mid <= x: ans = mid # mid is a valid candidate lo = mid + 1 else: hi = mid - 1 return ans # int_sqrt(8) -> 2, int_sqrt(16) -> 4; O(log x)

Tell me about yourself for a software engineer role.