Find Minimum Machines Size
Updated
Problem statement
A sequence of n machines is tasked with stocking or retrieving items. You are given the individual stocking/retrieving capacity values of each machine as an integer array, machineCapacity.
The Efficiency of a sequence is defined as the sum of the absolute differences between consecutive machine capacities. For a sequence a of length k, the efficiency is |a[0]-a[1]| + |a[1]-a[2]| + ... + |a[k-2]-a[k-1]|. The efficiency of a sequence consisting of a single machine is 0.
Your task is to remove zero or more machines from the sequence so that the remaining sequence has the same efficiency as the original sequence. When machines are removed, the relative order of the remaining machines must be preserved (the result must be a subsequence of the original array, not a reordering).
Among all subsequences whose efficiency equals the original efficiency, return the minimum possible number of machines (the smallest subsequence length). The remaining sequence must contain at least one machine. If the original array already has all equal elements (efficiency 0), the minimum is 1, since a single machine also has efficiency 0.
If it is impossible to remove any machine while preserving the original efficiency, return n, the original number of machines.
Function
findMinimumMachinesSize(machineCapacity: int[]) → int findMinimumMachinesSize() has the following parameter(s):
int machineCapacity[n]: the stocking/retrieval capacity of each machine
- Returns
int: the minimum number of machines in the resulting sequence required to achieve the same efficiency score.
Examples
Example 1
machineCapacity = [1, 2, 2, 1, 1]return = 3Efficiency initially for [1, 2, 2, 1, 1]: |1-2| + |2-2| + |2-1| + |1-1| = 1 + 0 + 1 + 0 = 2. After removing the machines at positions [2] and [3] (0-indexed), the remaining subsequence is [1, 2, 1] (relative order preserved), whose efficiency is |1-2| + |2-1| = 1 + 1 = 2, which equals the original efficiency. No smaller efficiency-preserving subsequence exists, so the minimum number of machines is 3.
Constraints
1 ≤ n ≤ 2×10^50 ≤ machineCapacity[i] ≤ 10^9
More Amazon interview questions
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Maximal SquareONSITE INTERVIEW · Seen Nov 2026
- Serialize and Deserialize a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Diagonal Traversal of a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Spread Through a GridPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Consistent-Hash Packet RouterPHONE SCREEN · Seen Nov 2026
- Count Connected ComponentsPHONE SCREEN · Seen Nov 2026
- Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
Similar questions at other companies
- Minimum Cost to Merge Values into OnePayPal · OAPayPal interview questions
- Minimum Operations to Sort with Rotations Then SwapsBank of New York Mellon · OA
- Minimum Rounds to Complete All TasksInfosys · OAInfosys interview questions
- Reschedule Meetings for Maximum Free TimeFivetran · OAFivetran interview questions
- Maximum Easy Tasks After RearrangingIBM · OAIBM interview questions
- Minimum Cost K-Capable ModelsMicrosoft · OAMicrosoft interview questions
- Maximum ScoreNVIDIA · OANVIDIA interview questions
- Maximum Distinct Values After Unit AdjustmentsBirla Pivot · OA
- Minimize Adjacent Squared-Difference Cost with One InsertionMcKinsey & Company · OAMcKinsey & Company interview questions
- Maximize Revenue from Decreasing InventoryChubb · OAChubb interview questions