Katkat
Back

Split Modules Across Three Servers to Maximize the Minimum Deployment Difficulty

J.P. MorganSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

Assign modules with given difficulty values to three non-empty servers so that the smallest value of |d1 - d2| + |d2 - d3|, over one module picked from each server, is as large as possible. Tests max-min reasoning over partitions, the role of the middle server, and handling of duplicates and large values.

You are given an integer array difficulty of length n, where difficulty[i] is the difficulty of the i-th software module. Assign the modules to three servers, Server 1, Server 2 and Server 3, so that:

  1. every server receives at least one module, and
  2. every module is assigned to exactly one server.

After the assignment, pick one module from each server and call their difficulties d1 (from Server 1), d2 (from Server 2) and d3 (from Server 3). The deployment difficulty of that pick is |d1 - d2| + |d2 - d3|.

The minimum deployment difficulty of an assignment is the smallest deployment difficulty over all possible picks. Find the assignment that makes this minimum as large as possible, and return that largest possible minimum.

Function Signature

def max_min_deployment_difficulty(difficulty: list[int]) -> int:

Rules

  • The servers are labeled, and the labels matter only through the formula: the module picked from Server 2 is the middle term, compared with both of the others.
  • Modules with equal difficulty are still different modules and may go to different servers.
  • The result is a single integer, so it is unique even when several assignments achieve it.

Constraints

The reported statement gives no input bounds; these are added so the problem is fully specified.

  • 3 <= n <= 10^5
  • 1 <= difficulty[i] <= 10^9
  • The answer can approach 2 * 10^9, which exceeds 2^31 - 1; use 64-bit integers in typed languages.

Examples

Example 1

Input: difficulty = [1, 5, 9]
Output: 12

Each server gets exactly one module. Putting 1 on Server 2, 5 on Server 1 and 9 on Server 3 gives |5 - 1| + |1 - 9| = 12. Putting 9 on Server 2 also gives 12, while putting 5 there gives only 8.

Example 2

Input: difficulty = [100, 1, 3, 2]
Output: 196

Server 1 = {2, 3}, Server 2 = {100}, Server 3 = {1}. The cheapest pick takes d1 = 3, so the minimum is |3 - 100| + |100 - 1| = 196.

Example 3

Input: difficulty = [3, 7, 1, 3]
Output: 10

Server 1 = {3, 3} (the two modules of difficulty 3), Server 2 = {7}, Server 3 = {1}. Every pick gives |3 - 7| + |7 - 1| = 10.