• Home
  • Subscribe
  • Contribute Us
    • Share Your Interview Experience
  • Contact Us
  • About
    • About CSEstack
    • Campus Ambassador
  • Forum & Discus
  • Tools for Geek
  • LeaderBoard
CSEstack

What do you want to Learn Today?

  • Programming
    • Tutorial- C/C++
    • Tutorial- Django
    • Tutorial- Git
    • Tutorial- HTML & CSS
    • Tutorial- Java
    • Tutorial- MySQL
    • Tutorial- Python
    • Competitive Coding Challenges
  • CSE Subject
    • (CD) Compiler Design
    • (CN) Computer Network
    • (COA) Computer Organization & Architecture
    • (DBMS) Database Management System
    • (DS) Data Structure
    • (OS) Operating System
    • (ToA) Theory of Automata
    • (WT) Web Technology
  • Interview Questions
    • Interview Questions- Company Wise
    • Interview Questions- Coding Round
    • Interview Questions- Python
    • Interview Questions- REST API
    • Interview Questions- Web Scraping
    • Interview Questions- HR Round
    • Aptitude Preparation Guide
  • GATE 2021
  • Linux
  • Trend
    • Full Stack Development
    • Artificial Intelligence (AI)
    • BigData
    • Cloud Computing
    • Machine Learning (ML)
  • Write for Us
    • Submit Article
    • Submit Source Code or Program
    • Share Your Interview Experience
  • Tools

Minimum Cost of Merging Files [Amazon Coding Test Question]

Aniruddha Chaudhari/7023/2
Code
YouTube CSEstack

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.

Python Interview Questions eBook

amazoncoding challenge
Aniruddha Chaudhari
I am complete Python Nut, love Linux and vim as an editor. I hold a Master of Computer Science from NIT Trichy. I dabble in C/C++, Java too. I keep sharing my coding knowledge and my own experience on CSEstack.org portal.

Your name can also be listed here. Got a tip? Submit it here to become an CSEstack author.

Comments

  • Reply
    Moksha Jain
    May 10, 2020 at 8:37 pm

    Sir, there is a minute correction in this code inside condition of loop…

    while(len(files) > 1):

    Thanks

    • Reply
      Aniruddha Chaudhari
      May 12, 2020 at 12:07 pm

      Thanks for the correction, Moksha! Fixed it.

Leave a Reply Cancel reply

Why?

Why Competitive Programming Important?

Coding Challenges for Practice

  1. Count Common Factor
  2. Does it Divide
  3. Sum of Sub Arrays
  4. Pair of Desired Sum
  5. Remove Duplicate Char from String
  6. Sort String by Char Freq (Python)
  7. Sort String by Char Freq (Java)
  8. Split Array into Equal Sum Subarray
  9. Validate IP Address
  10. Validate PAN Card Number
  11. Sort Circular Rotated Array
  12. Min Arrow to Burst Bubbles
  13. HourGlass with Largest Sum
  14. Max Profit by Buying/Selling Stocks
  15. Hailstone Sequence
  16. Reverse String without affecting Special Characters
  17. Secure Conversation by Encry/Decry
  18. Special Elements in Matrix
  19. Next Greater No with Same set of Digits
  20. Smallest Subarray with Sum Greater than Given Number
  21. Group Anagrams
  22. Find Duplicates in Array in O(n)
  23. Find Two Unique Numbers from Array in O(n)
  24. Number Patterns & Finding Smallest Number
  25. Minimum Cost of Merging Files [Amazon]
  26. Minimum Distance for Truck to Deliver Order [Amazon]
  27. Minimum Coins Required
  28. Max Sum Subarray
  29. Merge Overlapping Intervals
  30. Longest Balanced Subarray
  31. Longest Path in a Weighted Tree
  32. Generate Balanced Parentheses
  33. PostOrder Traversal Without Recursion

© 2021 – CSEstack.org. All Rights Reserved.

  • Home
  • Subscribe
  • Contribute Us
    • Share Your Interview Experience
  • Contact Us
  • About
    • About CSEstack
    • Campus Ambassador
  • Forum & Discus
  • Tools for Geek
  • LeaderBoard