Infosys-SP-Coding-Questions

Question	Description	Code
1.	Minimum Coins Required Given an array coins[] of size N and a target value V, where coins[i] represents the coins of different denominations. You have an infinite supply of each of coins. The task is to find minimum number of coins required to make the given value V. If it’s not possible to make a change, print -1. Examples: Input: coins[] = {25, 10, 5}, V = 30 Output: Minimum 2 coins required. We can use one coin of 25 cents and one of 5 cents. Input: coins[] = {9, 6, 5, 1}, V = 11 Output: Minimum 2 coins required. We can use one coin of 6 cents and one coin of 5 cents.	Click here to see the code
2.	Subset Sum Given a set of non-negative integers and a value sum, the task is to check if there is a subset of the given set whose sum is equal to the given sum. Examples: Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 9 Output: True Explanation: There is a subset (4, 5) with sum 9. Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 30 Output: False Explanation: There is no subset that adds up to 30.	Click here to see the code
3.	Largest Number Given an array of strings arr[] of length n representing non-negative integers, arrange them in a manner, such that, after concatenating them in order, it results in the largest possible number. Since the result may be very large, return it as a string. Examples: Input: n = 5, arr[] = {"3", "30", "34", "5", "9"} Output: "9534330" Explanation: Given numbers are {"3", "30", "34", "5", "9"}, the arrangement "9534330" gives the largest value. Input: n = 4, arr[] = {"54", "546", "548", "60"} Output: "6054854654" Explanation: Given numbers are {"54", "546", "548", "60"}, the arrangement "6054854654" gives the largest value.	Click here to see the code
4.	Wine Bottle Transport Given an array Arr[] of size N representing N houses built along a straight line with equal distance between adjacent houses. Each house has a certain number of wine and they want to buy/sell those wines to other houses. Transporting one bottle of wine from one house to an adjacent house results in one unit of work. The task is to find the minimum number of work is required to fulfill all the demands of those N houses. Examples: Input: N = 5, Arr[] = {5, -4, 1, -3, 1} Output: 9 Explanation: 1th house can sell 4 wine bottles to 0th house, total work needed 4*(1-0) = 4, new Arr[] = 1,0,1,-3,1. Now, 3rd house can sell wine to 0th, 2th and 4th. So total work needed = 1*(3-0)+1*(3-2)+1*(4-3) = 5. Total work will be 4+5 = 9. Input: N = 6, Arr[]={-1000, -1000, -1000, 1000, 1000, 1000} Output: 9000 Explanation: 0th house sells 1000 wine bottles to 3rd house, total work needed 1000*(3-0) = 3000. 1st house sells 1000 wine bottles to 4th house, total work needed 3000 + 1000*(3-0) = 6000. 2nd house sells 1000 wine bottles to 5th house, total work needed 6000 + 1000*(3-0) = 9000. So total work will be 9000 units.	Click here to see the code
5.	Minimum Platforms Required Given the arrival and departure times of all trains that reach a railway station, the task is to find the minimum number of platforms required for the railway station so that no train waits. We are given two arrays that represent the arrival and departure times of trains that stop. Examples: Input: arr[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}, dep[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00} Output: 3 Explanation: There are at-most three trains at a time (time between 9:40 to 12:00) Input: arr[] = {9:00, 9:40}, dep[] = {9:10, 12:00} Output: 1 Explanation: Only one platform is needed.	Click here to see the code