Amazon·Software Engineer·Online Assessment (OA)·Junior

Junior

Apr 2026

Summary

Amazon OA for a new grad SWE role, one coding problem about counting subarrays that meet a specific remainder condition. Pretty niche problem, not your typical two-sum warmup.

Questions Asked (1)

Given an array of integers (PIDs) and an integer k, count the number of contiguous subarrays where the sum modulo k equals the length of that subarray.

Algorithms & Data Structures

Author's notes

The problem wraps a modular arithmetic condition in a security tool story, which is fine but kind of distracting.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Transform the condition (sum mod k = length) into a prefix sum equation: (prefix[j] - prefix[i]) mod k = j - i, which rearranges to (prefix[j] - j) mod k = (prefix[i] - i) mod k. Then use a hash map to count pairs of indices with the same value of (prefix[i] - i) mod k, handling negative values correctly. This yields an O(n) time, O(k) space solution.

Pro tip: Always clarify edge cases upfront, such as negative numbers and k=1, and mention that you'll use modulo normalization to keep values in [0, k-1]. This shows attention to detail and prevents bugs in implementation.

1. Clarify and Restate

Confirm the problem: count contiguous subarrays where (sum of elements) mod k equals the subarray length. Ask about constraints (array size, value ranges, k>0) and whether negative numbers are allowed.

2. Derive Mathematical Condition

Let prefix[i] be sum of first i elements. For subarray (i, j], condition is (prefix[j] - prefix[i]) mod k = j - i. Rearrange to (prefix[j] - j) mod k = (prefix[i] - i) mod k.

3. Design Algorithm

Use a hash map to store counts of (prefix[i] - i) mod k for each i from 0 to n. Initialize with key 0 having count 1 (empty prefix). Iterate j from 1 to n, compute key, add map[key] to answer, then increment map[key].

4. Handle Modulo and Edge Cases

Ensure modulo operation returns non-negative results (e.g., ((x % k) + k) % k). Handle k=1 (all subarrays satisfy condition) and negative numbers correctly.

5. Analyze Complexity and Test

State time complexity O(n) and space O(k) (or O(n) if using hash map). Walk through a small example to verify correctness, including negative numbers.

Key Points to Mention

Prefix sum transformation and algebraic rearrangement to (prefix[i] - i) mod k equality.
Use of hash map to count frequencies of transformed prefix values.
Modulo normalization for negative numbers to ensure consistent keys.
Initialization with key 0 count 1 to account for subarrays starting at index 0.
Time complexity O(n) and space complexity O(min(n, k)) or O(n) with hash map.
Edge cases: k=1, negative integers, empty array, and large input sizes.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.