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

Intermediate

Jun 2026

Summary

Amazon SDE 2 coding question involving sticks and rectangles. Pretty much a greedy/sorting problem dressed up in game flavor text, which honestly took me a second to cut through.

Questions Asked (1)

Given an array of stick lengths, find the maximum total area of rectangles you can form, where each rectangle needs two pairs of equal-length sticks and you can shorten any stick by at most 1. Return the result modulo 10^9 + 7.

Algorithms & Data Structures

Author's notes

The game framing slowed me down more than the actual problem did.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Sort the array and use a greedy approach to pair sticks, considering the option to shorten by 1 to maximize matches. Compute areas of rectangles formed by consecutive pairs and sum them, taking modulo 10^9+7.

Pro tip: Clarify that shortening a stick by 1 can only help form pairs, so always check if adjusting a stick creates a match with the next one. Also, mention that modulo is applied to the final sum to prevent overflow.

1. Sort the array

Sort the stick lengths in non-decreasing order to easily identify potential pairs.

2. Pair sticks greedily

Iterate from the largest sticks, and for each stick, check if it can pair with the next stick either directly or by shortening by 1. If paired, remove both and record the side length.

3. Form rectangles

Use the recorded side lengths to form rectangles by taking two pairs at a time (largest sides first) to maximize area.

4. Compute total area

Multiply the side lengths of each rectangle to get its area, sum all areas, and take modulo 10^9+7.

Key Points to Mention

Greedy strategy: pairing largest possible sticks maximizes area.
Handling the shortening operation: check if a stick can be reduced by 1 to match the next stick.
Sorting is crucial for efficient pairing.
Modulo operation to handle large numbers.
Time complexity: O(n log n) due to sorting, and O(n) for pairing.
Edge cases: empty array, insufficient sticks, and multiple rectangles.

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