Server Selection
Updated
Problem statement
Amazon Web Services (AWS) provides highly scalable solutions for applications hosted on their servers. A company using AWS is planning to scale up horizontally and wants to buy servers from a list of available options.
Find the maximum number of servers (as a subsequence from the list) that can be rearranged so that the absolute difference between adjacent servers (including circular adjacency) is ≤ 1.
Conditions:
- A circular sequence is formed, so the first and last servers are also considered adjacent.
- A subsequence means elements can be removed, but you are free to rearrange the chosen elements.
Formal:
Given an array powers[] of n integers, find the maximum subsequence length m such that the chosen elements can be rearranged into a circular array a where:
abs(a[i] - a[i+1]) ≤ 1for all validi, andabs(a[m-1] - a[0]) ≤ 1wheremis the length of the subsequence.
Function
maxServers(powers: int[]) → intExamples
Example 1
powers = [4, 3, 5, 1, 2, 1]return = 3Choose the two servers with power 1 and the server with power 2, and place them in a circle as [1, 2, 1]. Each pair of neighbors differs by at most 1, including the last and first servers (1 and 1). That is 3 servers.
No choice of 4 servers works. For example, [1, 2, 3] goes up from 1 to 3, and the circle needs a second 2 to come back down, but there is only one 2. Choices such as [3, 4] or [4, 5] have only 2 servers.
Constraints
1 ≤ powers.length ≤ 2 * 10^51 ≤ powers[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 Distinct Prefix CostChubb · OAChubb interview questions
- Minimum Distinct Prefix CostGoldman Sachs · OAGoldman Sachs interview questions
- Rearrange Songs by AuthorZomato / Eternal · OAZomato / Eternal interview questions
- Maximize Palindromic WordsSquarepoint Capital · OASquarepoint Capital interview questions
- Find Max Distinct Items 🍏IBM · OAIBM interview questions
- Nickname-Constrained GroupingZoox · ONSITE INTERVIEW
- Partition Into K-Size Consecutive GroupsDream11 · ONSITE INTERVIEWDream11 interview questions
- Find the Original Array From a Doubled ArrayGoogle · PHONE SCREENGoogle interview questions
- Task Management SystemAirbnb · OAAirbnb interview questions
- Power Cell BankOptiver · OAOptiver interview questions