QA coding round: arrays with worked solutions

Use these exercises as a whiteboard round: clarify, trace, implement, test. Python lists stand in for interview arrays here; they are not a claim about Java array APIs. Every Python block was executed with Python 3.14.4.

Rank and range

1. What must you clarify before an array problem?

Ask about duplicates, negative values, empty input, ordering and whether mutation is allowed. For [8, 8, 3], second position in descending order is 8, but second distinct largest is 3. Give that counterexample before writing code; it prevents solving the wrong problem elegantly.

2. How do you find the second distinct largest in one pass?

Maintain the largest and runner-up values seen so far. When a new maximum arrives, the old maximum becomes runner-up; otherwise update only for a distinct value between them. None represents an absent answer, so negative inputs do not conflict with a sentinel such as zero.

def second_largest(values):
    first = second = None
    for value in values:
        if first is None or value > first:
            first, second = value, first
        elif value != first and (second is None or value > second):
            second = value
    return second

assert second_largest([8, 8, 3]) == 3
assert second_largest([-8, -2, -5]) == -5
assert second_largest([4, 4]) is None
assert second_largest([]) is None

3. How do you justify the one-pass solution?

After each element, the two variables hold the highest two distinct values of the prefix processed so far. Trace [3, 1, 5, 5, 4]: after the first 5 they are 5 and 3; the repeated 5 changes nothing; 4 replaces 3. The work is O(n) with O(1) additional state; sorting is unnecessary for just two ranks.

4. How do you find a missing number from zero through n?

The subtraction trick requires distinct integers within the range and exactly one missing value. This version validates that contract, because [0, 0, 3] can otherwise produce a plausible but meaningless answer. Validation costs O(n) additional space here; do not advertise the whole function as constant-space.

def missing_number(values):
    n = len(values)
    if (any(type(v) is not int or v < 0 or v > n for v in values)
            or len(set(values)) != n):
        raise ValueError('expected distinct integers from 0 through n')
    return n * (n + 1) // 2 - sum(values)

assert missing_number([3, 0, 1]) == 2
assert missing_number([]) == 0
assert missing_number([0, 1]) == 2
try:
    missing_number([0, 0, 3])
except ValueError:
    pass
else:
    raise AssertionError('duplicate input must be rejected')

5. What if the interviewer guarantees valid missing-number input?

You can omit validation and explain that the arithmetic solution then uses constant auxiliary space. In a fixed-width integer language, also discuss intermediate overflow; Python's integers do not impose that same fixed-width limit. Do not translate the formula into Java and claim it was verified without compiling and testing that translation.

Pair problems

6. How do you find two distinct indices whose values sum to a target?

Keep earlier values and their indices, checking for the complement before inserting the current value. This prevents a single 5 from pairing with itself for target 10, while permitting two different 5s. The function returns the first pair completed during a left-to-right scan; it does not enumerate every pair.

def pair_indices(values, target):
    seen = {}
    for index, value in enumerate(values):
        other = target - value
        if other in seen:
            return (seen[other], index)
        seen.setdefault(value, index)
    return None

assert pair_indices([5], 10) is None
assert pair_indices([5, 5], 10) == (0, 1)
assert pair_indices([2, 7, 4], 11) == (1, 2)
assert pair_indices([], 4) is None

Likely follow-up: Why not return values? The caller asked for indices, and duplicate values make those contracts observably different.

7. How do you return all unique value pairs?

Deduplicate pairs by a canonical order within each pair, not by discarding repeated input values before the scan. For [2, 2] and target 4, the second copy is necessary evidence that the pair exists. This uses extra memory for both seen values and output pairs; sorting the final pairs adds output-ordering cost.

def unique_pairs(values, target):
    seen, pairs = set(), set()
    for value in values:
        other = target - value
        if other in seen:
            pairs.add((min(value, other), max(value, other)))
        seen.add(value)
    return sorted(pairs)

assert unique_pairs([1, 3, 2, 2, 3], 4) == [(1, 3), (2, 2)]
assert unique_pairs([2], 4) == []
assert unique_pairs([-1, 0, 1], 0) == [(-1, 1)]

8. When is a two-pointer pair solution suitable?

When the input is sorted and you need values rather than original indices, compare the sum at the two ends and move the appropriate end inward. Sorting an unsorted input first adds work and loses original positions unless you retain them. For an interview that forbids extra hash storage, explain that tradeoff before choosing an approach.

Mutation and comparison

9. How do you move zeroes to the end without reordering other values?

Write non-zero values into the next free position, then fill the remaining positions with zeroes. The loop reads from the same list, but writes only to the current or an earlier position, so it does not destroy unread input. This function deliberately mutates its argument and uses constant auxiliary space.

def move_zeroes(values):
    write = 0
    for value in values:
        if value != 0:
            values[write] = value
            write += 1
    for index in range(write, len(values)):
        values[index] = 0

items = [0, -2, 0, 3]
move_zeroes(items)
assert items == [-2, 3, 0, 0]
empty = []
move_zeroes(empty)
assert empty == []
all_zero = [0, 0]
move_zeroes(all_zero)
assert all_zero == [0, 0]

10. How do you rotate an array by k places?

Define direction first; here positive k rotates right. Reduce k modulo length so a large rotation becomes a small one, and handle empty input before the modulo. The slicing solution is O(n) time and additional space, not an in-place rotation.

def rotate_right(values, k):
    if not values:
        return []
    k %= len(values)
    return values[-k:] + values[:-k] if k else values[:]

assert rotate_right([1, 2, 3], 4) == [3, 1, 2]
assert rotate_right([1, 2, 3], -1) == [2, 3, 1]
assert rotate_right([], 2) == []
assert rotate_right([1], 0) == [1]

11. Why is set equality insufficient for API array comparisons?

A set ignores multiplicity: [7, 7, 8] and [7, 8] become equal. If the API promises order, compare sequences; if it promises only multiplicities, compare frequency maps; if uniqueness is part of the contract, assert it separately. A tester should derive the comparator from the endpoint contract, not choose whichever assertion goes green.

12. How would you test a second-largest implementation thoroughly?

Use increasing, decreasing, all-equal, duplicate-maximum and all-negative inputs. Include an empty list and one element to establish the no-answer behaviour. As an independent oracle for small random inputs, sort distinct values and compare the second item from the end; keep that slower oracle in tests rather than replacing the one-pass explanation.

Practise it

Solve one rank problem and one pair problem, then change the contract: require original indices or prohibit mutation. Explain which lines must change and why. For realistic test data, compare a fake product-ID response against the displayed listing in ShopLite, without assuming that a set comparison proves ordering.