Hi everyone,

Today I had the opportunity to appear for Amazon’s SDE II Online Assessment.
Honestly, this was way harder than what I expected. I was literally staring at the screen for an hour and still couldn’t figure out the problem statements. These were nothing like standard textbook LeetCode problems where you can directly apply 2-pointers, heaps, sliding window, or classical DP.

Here are the 2 questions I faced:

Q1. Sequence Construction
Given integers n and target, construct a sequence of length n such that:

1. The absolute values are a permutation of {1..n}.
2. The sum of the sequence equals target.

Among all valid sequences, return the lexicographically smallest.

Input: n=4, target=-2

Valid sequences:
[-1, -2, -3, 4]
[ 3, -2, 1, -4]
[-4, -2, 1, 3] <-- lexicographically smallest

Output: [-4, -2, 1, 3]

Q2. String Expansion with !
You are given a string consisting of characters '0', '1', and '!'.

1. Each '!' can be replaced by either '0' or '1'.
2. For each expansion, count the total number of subsequences "01" and "10".

Return the minimum possible count over all expansions, modulo 1e9+7.

Example: s => "0!1!"
Ouptut: 3

Explanation:
There are 2^2 = 4 expansions (replace each ! by 0 or 1):

1. "0 0 1 0" → "0010"

total subsequences = 3

(explicit: "01" = 2 pairs, "10" = 1 pair)

2. "0 0 1 1" → "0011"

total subsequences = 4

(explicit: "01" = 4, "10" = 0)

3. "0 1 1 0" → "0110"

total subsequences =4

(explicit: "01" = 2, "10" = 2)

4. "0 1 1 1" → "0111"

total subsequences = 3

(explicit: "01" = 3, "10" = 0)

Minimum total over all expansions = 3.

This was my first time appearing for such an OA, and honestly, I didn’t expect the difficulty to be this high.
Does anyone have suggestions or advice on how to prepare better for such non-standard problems in the future?

Thanks in advance 🙏