Top 9 Arrays Interview Questions
Browse 9 real-world technical and behavioral interview questions about Arrays. Review scenarios, edge cases, and architectural best practices.
Find the largest rectangle in a histogram in linear time, and tell me what the stack holds at every step.
Keep a stack of bar indices with strictly increasing heights. When a bar no taller than the top arrives, pop: the popped bar's rectangle runs from just after the new top to just before the current bar. A height-zero sentinel flushes the stack. Each index is pushed once and popped at most once, so it is O(n).
Return the maximum of every window of size k as it slides across the array. Why a deque, and what is the invariant?
Keep a deque of indices whose values strictly decrease from front to back. Each step drops the front if it has left the window, pops smaller or equal values from the back, then appends. The front is the window maximum. Each index enters and leaves once, so it is amortised O(n), against O(n log k) for a balanced tree.
Insert, delete and get-a-uniformly-random-member all have to be O(1). What breaks when you delete from the middle?
Uniform sampling needs a gapless array you can index, so a deletion cannot leave a hole and cannot shift the tail. You overwrite the hole with the last element and shrink by one, which costs a fixed amount of work but silently moves another member, so the map from value to index must be corrected for the element that moved and not only for the one removed.
Find the largest sum obtainable from a contiguous run of elements in an array.
Walk the array once, keeping the best sum ending at the current element - that element alone, or that element added to the best run ending before it. The maximum of those is the answer, and the familiar version that resets the running sum to zero is wrong when every element is negative.
For each element of an array, find the first element to its right that is larger. State the invariant your stack maintains.
Scan left to right holding a stack of indices whose answers are still unknown, kept strictly decreasing by value. Each new element resolves and pops everything smaller than it, then pushes itself. Every index is pushed once and popped at most once, so the scan is O(n) despite the inner loop.
For every index, give me the product of all the other elements - and you cannot use division.
Two passes over the array do it: a left-to-right pass writes the product of everything before each index into the output, then a right-to-left pass multiplies in a running product of everything after it. Linear time, no working array beyond the output, and it is unbothered by zeros.
Rotate an array k positions to the right, in place.
Rotate array by k in place by normalising k modulo n, reversing the whole array, then reversing the first k and remaining n-k elements. It is O(n) time, O(1) extra space, and avoids the cyclic-replacement pitfalls unless write count matters. Use this ARRAYS answer to show the decision, trade-off, and evidence rather than a memorised definition.
Return every distinct triplet in the array that sums to zero.
Sort the array, fix each element as an anchor, then converge two pointers inwards from both ends of the remaining range. The sort is asymptotically free against the O of n squared scan, and it is what lets you skip duplicate values positionally instead of deduplicating a set of results afterwards. It also connects sorting to the point an interviewer is testing.
Given the heights of a row of bars, work out how much rainwater is trapped between them. Do it in constant extra space.
Water above a bar is the smaller of the tallest bar to its left and the tallest to its right, minus its own height. Walking inwards from both ends and always advancing the shorter side works because that side's running maximum is the binding constraint there, whatever heights remain unseen in the middle.