Arrays & Strings interview questions

In-place manipulation, prefix sums, and the string-scanning problems that open most coding rounds.

4 questions in Data Structures & Algorithms.

Data Structures & AlgorithmsA 26-minute read on how the topic fits together, before the questions.Data structures and algorithms fundamentals54 short answers on one page, for revising rather than studying.

medium4

mediumCoding

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.

6 minmid, senior

mediumCoding

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.

4 minentry, mid, senior

mediumCoding

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.

3 minentry, mid, senior

mediumCoding

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.

4 minentry, mid, senior