Online Assessment Question | Amazon

Anonymous3 days ago

I got this question in my Amazon OA and wasn't able to solve it during the test. Sharing it here in case someone can explain the optimal approach.

Problem

You are given:

  • An array shipmentOrder of length n

  • shipmentOrder is a permutation of numbers from 1 to n

  • An integer windowSize

You have to perform the following operation exactly once:

  1. Choose any contiguous subarray of length windowSize.

  2. Sort that subarray in ascending order.

  3. Keep all other elements unchanged.

Your goal is to find the lexicographically largest array possible after performing this operation.

An array is lexicographically larger if, at the first position where two arrays differ, it has the larger value.

Example

shipmentOrder = [5, 1, 4, 3, 2]
windowSize = 3

There are 3 possible windows:

Choose index 1:

[5, 1, 4] → [1, 4, 5]

Result: [1, 4, 5, 3, 2]

Choose index 2:

[1, 4, 3] → [1, 3, 4]

Result: [5, 1, 3, 4, 2]

Choose index 3:

[4, 3, 2] → [2, 3, 4]

Result: [5, 1, 2, 3, 4]

Now compare the three results:

[1, 4, 5, 3, 2]
[5, 1, 3, 4, 2]
[5, 1, 2, 3, 4]

The lexicographically largest array is:

[5, 1, 3, 4, 2]

Another Example

shipmentOrder = [5, 4, 3, 2, 1]
windowSize = 3

Possible results:

Choose 1 → [3, 4, 5, 2, 1]
Choose 2 → [5, 2, 3, 4, 1]
Choose 3 → [5, 4, 1, 2, 3]

The answer is:

[5, 4, 1, 2, 3]

because it preserves the longest possible prefix [5, 4].

Constraints

1 <= windowSize <= n <= 2 * 10^5
shipmentOrder is a permutation of [1, 2, ..., n]

Function

maximizeShipmentOrder(shipmentOrder, windowSize)

Return the lexicographically largest array that can be obtained.

I couldn't figure out an efficient approach for n up to 2 * 10^5.

Can anyone explain the optimal approach or provide a solution?

Recommended Reads

Post

IBM Round 2 Physical Coding Assessment Experience

I recently appeared for the IBM Round 2 coding assessment in physical mode . Question 1: Array-Based Logic We were given an array of integers. For each element,

Post

Does language effect in DSA ??

So I am curious about whether the lang matters for DSA in today&#39;s industry too ?

Interview Experience

Keychain | Lead Backend Engineer | Interview Experience | Rejected

The interview process involved an initial discussion with a Senior Engineering Manager, an HLD round, a take-home assignment, a review of the assignment, and a

Post

Databricks Hiring | Software Engineer, Backend

About Role Company: Databricks Position: Software Engineer - Backend Experience: 3+ years Location: Bengaluru, India Apply Here What You’ll Build Develop founda

Interview Experience

PhonePe | Software Engineer | Interview Experience | Selected

Company: PhonePe Role: Software Engineer Experience: 3 years and 4 months Location: Bangalore Final Result: Selected The interview process consisted of four rou

Comments1
  • Anonymous2d ago

    #include <iostream> #include <vector> #include <deque> #include <algorithm> using namespace std; vector<int> maximizeShipmentOrder(vector<int>& shipmentOrder, int windowSize) { int n = shipmentOrder.size(); int k = windowSize; // Step 1: Compute minimum of every sliding window of size k in O(N) time deque<int> dq; // Stores indices vector<int> windowMin(n - k + 1); for (int i = 0; i < n; i++) { // Remove indices outside current window if (!dq.empty() && dq.front() <= i - k) { dq.pop_front(); } // Remove elements larger than current element while (!dq.empty() && shipmentOrder[dq.back()] >= shipmentOrder[i]) { dq.pop_back(); } dq.push_back(i); // Record minimum for window starting at index (i - k + 1) if (i >= k - 1) { windowMin[i - k + 1] = shipmentOrder[dq.front()]; } } // Step 2: Find the optimal window to sort // We want to preserve the longest prefix possible. int chosenWindow = n - k; // Default to the last window if no earlier window reduces values for (int i = 0; i <= n - k; i++) { // If sorting window `i` puts a smaller element at index `i`, // this is the first index where sorting forces a change. if (windowMin[i] < shipmentOrder[i]) { chosenWindow = i; break; } } // Step 3: Sort only the chosen window sort(shipmentOrder.begin() + chosenWindow, shipmentOrder.begin() + chosenWindow + k); return shipmentOrder; }

    0replies