FastPrep
Problem · Dynamic Programming

Find Machine Count

Learn this problem
● HardCiscoFULLTIMEINTERNOA
See Cisco hiring insights

Problem statement

There are n regions where servers are hosted. The number of machines in the i-th region is given by machineCount[i], where 0 <= i < n. Managing all these regions can be challenging, so the team decided to move some machines to exactly 3 regions. The number of machines in the i-th of these 3 target regions is given by finalMachineCount[i], where 0 <= i < 3.

There are two operations that can be performed:

  • Add or Remove Machines: Add or remove a machine from any existing region. The number of machines in that server should be non-zero before and after the operation. This operation costs 1 unit.
  • Move All Machines: Move all machines from one region to another existing region at a cost of shiftingCost units. The now-empty region is destroyed in this operation.

    • Objective: Find the minimum cost to shift the machines so that any 3 regions have the counts required in finalMachineCount.

    Note: It is possible that there are additional machines left at the end apart from the ones placed in the final 3 regions.

    Function

    getMinimumCost(machineCount: int[], finalMachineCount: int[], shiftingCost: int) → int

    Complete the function getMinimumCost in the editor.

    getMinimumCost has the following parameters:

    1. int machineCount[]: The initial number of machines in the regions.
    2. int finalMachineCount[]: The final number of machines required in the 3 regions.
    3. int shiftingCost: The cost to move all machines from one region to another.

    Returns

    int: The minimum cost to move machines into 3 regions.

    Examples

    Example 1

    machineCount = [2, 3, 5, 7]finalMachineCount = [5, 10, 5]shiftingCost = 2return = 5

    1. Increase the number of machines in the 1st and 2nd regions by 1 and 2 machines respectively. The new machineCount = [3, 5, 5, 7]. Total cost for these operations is 1 + 2 = 3.

    2. Move all the machines from the 4th region to the 1st region, which takes shiftingCost = 2. The new machineCount = [10, 5, 5]. The cost of this operation is 2.

    Total Cost = 3 + 2 = 5

    Example 2

    machineCount = [2, 4, 5, 3]finalMachineCount = [4, 4, 4]shiftingCost = 5return = 2

    Increase the number of machines in the 4th region by 1 and decrease the number of machines in the 3rd region by 1. The new machineCount = [2, 4, 4, 4]. Total cost for these operations is 1 + 1 = 2. Use the 2nd, 3rd, and 4th regions as the required servers, leaving behind the 1st region.

    Example 3

    machineCount = [5, 10, 15, 20, 25]finalMachineCount = [20, 20, 20]shiftingCost = 3return = 8

    On increasing the number of machines of the 5th region by 5, the new machineCount = [5, 10, 15, 20, 20]. Total cost required for these operations = 5.

    Now, moving all the machines from the 3rd region to the 1st region, which takes shiftingCost(3) dollars, the new machineCount = [20, 10, 20, 20]. Total cost required for these operations = 3.

    Use the 1st, 3rd, and 4th regions as required regions, leaving behind the 2nd region. The total cost = 5 + 3 = 8.

    Constraints

    • 3 <= n <= 10^8
    • 1 <= machineCount[i], finalMachineCount[i] <= 10^6
    • 1 <= shiftingCost <= 10^6

    More Cisco problems

    drafts saved locally
    public int getMinimumCost(int[] machineCount, int[] finalMachineCount, int shiftingCost) {
  // write your code here
}
    machineCount[2, 3, 5, 7]
    finalMachineCount[5, 10, 5]
    shiftingCost2
    expected5
    checking account