Interview conceptCoding & Algorithms

Linear Array, Hashing, Prefix/Suffix, And Cycle Techniques

Asked of: Software Engineer

Last updated

A clean decision flowchart maps linear-array problem signals to prefix/suffix products, Floyd cycle detection, or hash-map and two-pointer techniques.

What's being tested

These problems test linear-array reasoning: choosing hashing, two pointers, cycle detection, or prefix/suffix accumulation to achieve O(n) time. You must preserve index semantics, handle duplicates and zeros correctly, and explain why the chosen approach meets constraints such as constant extra space or lexicographic ordering.

Patterns & templates

  • Floyd’s tortoise-and-hare treats nums[i] as a pointer; detect the duplicate cycle in O(n) time and O(1) space without modifying the array.

  • Hash-map Two Sum stores value → earliest index, enabling O(n) lookup; explicitly define whether lexicographic order means smallest first index, then smallest second.

  • For lexicographically smallest pairs, scan indices in ascending order and update only when (i, j) is strictly smaller than the current best candidate.

  • Prefix/suffix products compute output[i] = prefix[i] × suffix[i] without division, using a prefix pass and a right-to-left accumulator in O(n) time.

  • Initialize each product output to 1; multiply the running prefix before or after assignment consistently, especially at the first and last indices.

  • Handle zero, multiple zeros, negatives, repeated values, empty arrays, and integer overflow; use a wider numeric type when products can exceed the 32-bit range.

Common pitfalls

Pitfall: Using a set or sorting solves duplicate detection but violates the constant-space or non-mutating constraint; explain Floyd’s cycle mapping instead.

Pitfall: Returning the first valid Two Sum pair is not necessarily lexicographically smallest; compare index pairs or prove the scan order guarantees optimality.

Pitfall: Division-based products fail with zeros and violate the requirement; use prefix and suffix products with clearly stated update order.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.

Practice questions

Related concepts