Data Structures and Algorithms Mock Interview: 20 Questions in 50 Minutes

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.

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).

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.

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.

Lower bound returns the first index whose value is not less than the target, and upper bound the first index whose value is greater, so their difference counts occurrences. Common bugs are off-by-one errors in the loop condition, infinite loops when mid does not move, and integer overflow from (low plus high) divided by 2 in Java or C++; use low plus (high minus low) divided by 2. Python's bisect module provides both functions.

Let dp[i][w] be the maximum value using the first i items with capacity w. For item i with weight wt and value val, either skip it, giving dp[i-1][w], or take it if wt is at most w, giving dp[i-1][w - wt] plus val; take the larger. Base cases are zero items or zero capacity. Time and space are O(n times W), and space can drop to O(W) by iterating w downwards in a single array.

Signals include asking for a minimum, maximum, count of ways or whether something is possible, with choices at each step that affect later options. Start from brute-force recursion and ask what parameters fully describe a subproblem, such as index, remaining capacity or last chosen item; those become the state. Then write the transition between states, the base cases and the order of computation, and check the state count times transition cost fits limits.

A graph is bipartite if its vertices can be split into two groups so every edge connects vertices from different groups, which is equivalent to having no odd-length cycle. To check, colour vertices with BFS or DFS: give the start vertex colour 0, its neighbours colour 1 and so on; if any edge connects two vertices of the same colour, it is not bipartite. Run it on each component, O(V plus E).

Choosing the activity that finishes earliest leaves the most remaining time for others, and an exchange argument shows that any optimal schedule can swap its first activity for the earliest-finishing one without losing count. Sorting by start time fails when an early activity runs very long, and sorting by duration fails when a short activity overlaps two compatible ones. The algorithm is O(n log n) for sorting plus one pass.

Model courses as vertices with an edge from each prerequisite to the course that needs it, then run topological sort with Kahn's algorithm. Courses with no pending prerequisites enter a queue first, and taking one reduces the in-degree of dependent courses. If the output has fewer courses than the total, there is a cycle, so no valid order exists, and I would report the courses involved so the content team can fix them.

The capacity lies between the heaviest package and the total weight, and if a capacity works, any larger one also works, so binary search the answer. For a candidate capacity, greedily load packages day by day, starting a new day when the next package does not fit, and count days. If the days are within D, try smaller; otherwise try larger. Time is O(n log of total weight).

For each user keep a deque of request timestamps. On a request, pop timestamps older than now minus 60 seconds from the front, then allow the request only if fewer than 100 remain, pushing the new timestamp at the back. This sliding window log is exact but uses memory per request. At scale I would use a sliding window counter or token bucket stored in Redis with atomic operations to save memory and work across servers.

The loop is O(users times orders), so when both grow ten times, the work grows a hundred times. I would explain this with numbers and a quick profile. The fix is to group orders by user ID once using a hash map, making the total O(users plus orders), or to push the grouping into a database query with an index. I would add a performance test with production-scale data.

The BST property applies to entire subtrees, not just direct children. A node deep in the left subtree could be larger than the root and still pass the local check. The correct approach passes a valid range down the recursion: the left child must lie between the lower bound and the node value, the right child between the node value and the upper bound. Alternatively, check that an inorder traversal is strictly increasing.

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.

Situation: in my current role I have learned a lot maintaining internal tools for two years. Task: I want to grow into harder engineering problems. Action: I have been strengthening my data structures, system design and backend skills through projects and by taking ownership of performance work in my team. Result: I am now ready for a role with larger scale and more technical depth, which is why this position appeals to me.

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.

Situation: a product manager asked why a search feature became slow as data grew. Task: explain the cause and the fix without jargon. Action: I compared the current approach to checking every book in a library one by one and the fix to using the catalogue index, then showed a simple chart of response times before and after a prototype. Result: the manager approved two sprints for the change and later reused my analogy with clients.