Minimum Cost of Merging Files [Amazon Coding Test Question]

This programming challenge is asked in the Amazon coding round hosted on the Amcat platform.

There will be two coding questions to be solved in 90 minutes. So you can take 45 minutes to solve this coding challenge.

In this tutorial, I’m explaining one coding program. Another coding program, you can find here- the minimum distance required for the truck to deliver the order.

Problem Statement: Minimum Cost of Merging Files

Amazon has a cloud music application. When the user subscribes to it, music files are encoded and then transfer it to the user’s smartphone. The encoder takes each music file and merges them all into a single file. This single file will be sent to the user’s smartphone.

At a time, the encoder can only merge two files. The cost of merging two files is the same as the size of those two files. Find the minimum cost to merge all files into one.

Input format:

• numOfSubFiles- number of files to be compressed
• files- array/list which contains the size of each file

Output format:

Write a function to the return minimum cost required to compress files.

Example:

Input: [14, 25, 5, 8 ]
Output: 92

Explanation:

First, two files of size 5 and 8 will be merged. It will cost 13 (5+8). The updated files on the list are [14, 25, 13].

In the next turn, two files of size 13 and 14 will be merged. It will cost 27 (13+14). The updated files in the list are [25, 27]

Finally, 25 and 27 will merge to [52], it will cost 52.

The total cost to merge all the files is 92 (13+27+52).

Algorithm:

It has a simple solution.

• Find the two smallest integers from the list or array.
• Calculate the cost of merging by adding the size of two files.
• Merge two files into one.
• Repeat the step above steps until there is only a single file in the list.

Python Program To Calculate Minimum Cost of Merging Files

You can do with and without recursion the recursion.

Before going through the below code, I would recommend you write your own code. If you stuck anywhere, you can always refer below code.

With recursion:

def minCostToMerge(files):
    if len(files)<=1:
        return 0
    else:
        minA=min(files)
        files.remove(minA)
 
        minB=min(files)
        files.remove(minB)
 
        files.append(minA+minB)
        return minA+minB+minCostToMerge(files)
 
print(minCostToMerge([14, 25, 5, 8 ]))

Output:

92

Without recursion (using while loop):

def minCostToMerge(files):
 
    cost=0
 
    while(len(files)>1):
        minA=min(files)
        files.remove(minA)
 
        minB=min(files)
        files.remove(minB)
 
        files.append(minA+minB)
        cost= cost+minA+minB
 
    return cost
 
print(minCostToMerge([21, 17, 5, 9]))

Output:

97

To solve this kind of problem, you have to be very good at handling a Python list. You should aware of all the methods to add, delete, and update the element in the list.

Your Challenge…

Can you solve this problem to calculate the minimum cost of merging files in any other programming language like C/C++, Java…?

Please share your code with me in the comment. I will add it to this challenge.