Greedy: Perform operations on a broker calculator
Problem Statement: You have a broken calculator and there is a number showing on the display. You can perform below two operations: Double: Multiply the number by 2 Decrement: Subtract the number by 1. Initially calculator is displaying number ‘x’ and you are given a number ‘y’. Return the minimum number of operations needed to […]
Greedy: Given a string, split into balanced strings.
Problem Statement: You are given a string with “R” “L” characters. You need to balance the string so that it will have same number of R and L. Return the maximum number of split balanced strings. Example Input: s = “RLRRLLRLRL” Output: 4 String can be split into “RL”, “RRLL”, “RL”, “RL” Solution We can […]
Greedy: Juice change
Problem Statement: You are selling a Juice for RS 5. Initially you will not have any change left with you. Customers can buy the juice with either “5”, “10” or “20” RS. You need to provide them with exact change, and you need to return true if you are able to provide them with exact […]
Greedy: Partition characters
Problem Statement: You are given a string with multiple characters repeating. You need to partiton the string into many parts such that each letter appears only once in any part. Example Input: asdfadaasfhjklqwertypcv Output: [8, 6, 9] We can split the string into [asdfadaa] [sfhjkl] [qwertypcv] We cannot split as “[asdfadaa] [sfhjklqwertypcv]” because it will […]
Greedy: Maximum sum of absolute difference of an array
Problem Statement: You are given an array, you need to find the maximum sun of absolute difference of any permutation in the given array. Example Input: 1, 2, 7 Output: 11 Explanation: sum = |1 – 7| + |7 – 2| = 11. So the arrangement is (1, 7, 2) Solution We can solve this […]
Greedy: Shuffle array so that one array element is greater than other array element
Problem Statement: You are given 2 array of equal size. You need to rearrange the first array in such a way that at any point of time a[i] > b[i] Example Input: A = [2,7,11,15], B = [1,10,4,11] Output: [2,11,7,15] Here a[i] is always greater than b[i] Solution First we will insert all the elements […]
Greedy: Schedule task efficiently
Problem Statement: You are given an array of CPU tasks and a cool off period between the same task “n”. You need to re-arrange the tasks such that, the time run should be minimum. Example Input: tasks = [“A”,”A”,”B”,”B”,”B”], n = 2 Output: 8 Explanation: A -> B -> idle -> A -> B -> […]
Greedy: Distribute Candy
Problem Statement: There are N children and each child is assigned a rating. You need to give candies to these children while making sure that each child should get one candy and child with higher rating should get more candies than their neighbors Example Input: [1, 2, 2] Output: 4 You can distribute as [1, […]
Greedy: Maximum meetings in one room
Problem Statement: You have one meeting room in your company. There are multiple meetings taking place. Every meeting has a start and end time along with the meeting title. You need to schedule as many meetings as possible without conflicts. Example start time = [1,4,0,6,9,10] End time = [3,5,7,8,11,12] Output: The maximum meetings that can […]
Greedy: Plant n flowers in flower bed
Problem Statement: You are given array that represents flowerbed, where some plants are placed. You are also given new flowers to be placed. You need to place the flowers in such a way that they should not be placed adjacent. You need to return true or false based on if the “n” new flowers can […]