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

Intermediate

Apr 2026

Summary

Amazon SWE online assessment with a math-heavy coding problem about maximizing unique hash values. Pretty niche problem, not your typical array or graph question.

Questions Asked (1)

Given an array of integers called param, construct a secretKey array of the same length such that hash[i] = secretKey[i] % param[i] produces the maximum number of unique values across the hash array. Return that maximum count.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

Took me a while to even figure out what was being asked.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize that the problem reduces to selecting a distinct hash value for each index, where the available values for index i are 0 to param[i]-1. Model this as a bipartite matching problem between indices and possible hash values, then find the maximum matching size. Alternatively, sort indices by param[i] and greedily assign the smallest available hash value to each index, which yields the optimal count.

Pro tip: Mention that the greedy approach works because the intervals [0, param[i]-1] are nested when sorted by param[i], so assigning the smallest available value preserves future options. This demonstrates insight into the problem's structure and avoids overcomplicating with full matching algorithms.

1. Clarify the problem

Restate the goal: we need to choose secretKey[i] such that hash[i] = secretKey[i] % param[i] are all distinct, and we want to maximize the number of distinct hash values. Note that secretKey[i] can be any integer, so hash[i] can be any integer from 0 to param[i]-1.

2. Model as assignment

For each index i, the set of possible hash values is {0, 1, ..., param[i]-1}. We need to pick one value per index such that all picked values are distinct. This is a bipartite matching problem between indices and hash values.

3. Identify greedy strategy

Sort indices by param[i] in ascending order. For each index, assign the smallest non-negative integer not yet used that is less than param[i]. If no such integer exists, skip that index (it cannot be assigned a unique hash).

4. Prove optimality

Argue that the greedy choice is safe: because intervals are nested, using the smallest available value leaves larger values for indices with larger param[i], maximizing the total number of assignments. This is equivalent to the standard interval scheduling/matching greedy proof.

5. Analyze complexity

Sorting takes O(n log n). Assigning values can be done in O(n) using a pointer or a set. Overall O(n log n) time and O(n) space. Mention that a full bipartite matching would be O(n^2) or worse, so greedy is more efficient.

Key Points to Mention

The problem is equivalent to finding a maximum matching in a bipartite graph where left nodes are indices and right nodes are possible hash values.
The intervals [0, param[i]-1] are nested when sorted by param[i], enabling a greedy solution.
Greedy algorithm: sort by param[i], assign the smallest available value less than param[i].
Proof of optimality via exchange argument: assigning the smallest available value never hurts future assignments.
Time complexity O(n log n) due to sorting, space O(n) for tracking used values.
Edge cases: param[i] = 0 (no possible hash), duplicate param values, and large n requiring efficient implementation.

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