Tomorrow we should be able to learn about the possible fraud in the 2020 United States presidential election. Hopefully the discussions and events will be peaceful from both sides. It will be interesting to learn what went on and how is it going to be addressed.
Yesterday evening for the first time my wife and I watched a president Trump rally. This one was in an airport in Georgia. Interesting facts were presented. What called my attention was a comment made by the president regarding how some election officials use what was labeled as “intent by the voter” to decide if the ballot was for Biden or Trump. The officials inspect the ballot and they decide on what was the “intent” of the voter was, and they assign the vote to the “intended” candidate. WHAT??? If the voter filled in the slot for Biden, then the vote goes to Biden, if the slot for Trump was filled in, then the vote goes to Trump. Finally if both slots were left empty, the vote does not count. THIS IS THE BEGINING AND END OF THE STORY. There is NO INTENT. A seven year old understand this. Try explaining the rules to your kid and they will understand there is NO NEED to determine THE INTENT OF THE VOTER!
You may laugh at this, but a few governor elections back in the state of Minnesota, the vote counts were very close (about 2,000 apart if I am not mistaken). The same INTENT OF THE VOTER scam was used. The democratic candidate was declared the governor!!!
I cannot believe how elections that are one of the pillars of Democracy have been attacked slowly for about the past two decades. Americans and the world at large will be watching closely at what the courts in the USA do to fix the results, make provisions so this does not ever happen again, and make the perpetrators accountable for their actions. We shall see what we shall see.
Sorry about me ranting all over. I am not interested in politics but I do care for democracy and justice.
OK, let’s get down to the main topic for this post. I took a look at the practice question Magical Candy Bags from Facebook. I was trying to see if I could find a similar problem from HackerRank or LeetCode. The reason is that both sites provide extensive testing on the code presented for approval. The Facebook site only provides a couple of test cases.
I found a similar problem named Monk and the Magical Candy Bags but the associated code was huge and in C. In other words I did not find a place to perform extensive testing on my solution.
You have N bags of candy. The ith bag contains arr[i] pieces of candy, and each of the bags is magical! It takes you 1 minute to eat all of the pieces of candy in a bag (irrespective of how many pieces of candy are inside), and as soon as you finish, the bag mysteriously refills. If there were x pieces of candy in the bag at the beginning of the minute, then after you've finished you'll find that floor(x/2) pieces are now inside. You have k minutes to eat as much candy as possible. How many pieces of candy can you eat? Input: 1 ≤ N ≤ 10,000 1 ≤ k ≤ 10,000 1 ≤ arr[i] ≤ 1,000,000,000 Output: A single integer, the maximum number of candies you can eat in k minutes.
Apparently we are given a number of bags. Each bag has a random number of candy pieces. The idea is that the bags in question are MAGICAL. You can eat all the candy from a bag in less than a minute, but in the next minute some pieces will appear. The challenge for us is to figure out how much candy we can eat in the specified time.
int maxCandies(int[] arr, int K)
The signature for the function / method we need to implement indicates that we are given an array of numbers that represent the number of candy pieces per bag and the number of minutes that we have to consume as much candy as possible.
I will be solving the problem using the Java programming language, in a Windows 10 machine using the VSCode IDE. When I feel comfortable with the implementation of the function of interest, I will copy it to the Facebook site and run the unit test.
Because of the approach I am using, I need to generate some test code. The test scaffolding that I generated IS NOT PART OF THE SOLUTION. As a matter of fact, if you are interested in applying to a technical position at Facebook, I would recommend for you to develop a solution directly on the IDE provided.
2,1,7,4,2 3 main <<< arr: [2, 1, 7, 4, 2] main <<< K: 3 main <<< output: 14 output = 14
The first line contains the numbers of candy pieces per magic bag. In our case we have five bags. The second line indicates the number of minutes we have to eat candy. In this case we have three minutes to consume as much candy as possible.
It seems that our test code reads the first line and populates an integer array with the specified values. It also reads the number of minutes and displays it. So far all is well. We just need to call the function we need to develop and display the results. Hopefully we will get the expected result which the Facebook site describes in detail.
/**
* Test scaffolding
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read array of integers ****
String[] strArr = br.readLine().trim().split(",");
// **** read number of minutes ****
int K = Integer.parseInt(br.readLine().trim());
// **** close buffered reader ****
br.close();
// **** generate array of int ****
int[] arr = Arrays.stream(strArr).mapToInt(Integer::parseInt).toArray();
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
System.out.println("main <<< K: " + K);
// **** max number of candies one can eat in the specified time ****
System.out.println("main <<< output: " + maxCandies(arr, K));
}
Not much to add to the test scaffolding code. We read the two input lines, populate the proper data structures, make a call to the function in questions and display the results.
We can use a priority queue or heap. We keep the bag with most pieces on the top of the heap. At the start of each minute we consume all the candy and compute what will happen with that bag in the next minute. The rest of the bags are of no interest. When we put the updated bag in the heap it should re arrange the bags to keep the one with the most pieces on the top. The process repeats for as many minutes as we are required.
Note that if the top of the heap gets to 0 we could exit because the total amount of candy will not magically increase. This is not shown in the code. I will leave it as an exercise.
/**
* You have k minutes to eat as much candy as possible.
* How many pieces of candy can you eat?
* O(n)
*/
static int maxCandies(int[] arr, int k) {
// **** initialization ****
int candies = 0;
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new Comparator<Integer>() {
public int compare (Integer i0, Integer i1) {
if (i1 > i0)
return 1;
else if (i0 == i1)
return 0;
else
return -1;
}
});
// **** populate priority queue O(n)****
for (int a : arr)
pq.add(a);
// **** loop eating candies O(k) ****
for (int m = 0; m < k; m++) {
// **** eat all candies from head bag ****
int pieces = pq.remove();
// **** count number of candies eaten ****
candies += pieces;
// **** compute pieces for next minute ****
pieces = Math.floorDiv(pieces, 2);
// **** add pieces for next minute ****
pq.add(pieces);
}
// **** max number of candies ****
return candies;
}
We first perform some initialization. The candies we consume are initialized to 0. The priority queue is used in Java as a heap. We need to make sure that the bag with the largest amount of candy is on the top. For that we need to specify a comparator. That said we could remove the last bag if we do not have the priority queue in descending order. This could be an exercise.
We then populate the priority queue.
The last this is to emulate the specified number of minutes. We remove the bag with the most candy pieces and add the count to the sum of pieces we have consumed. We generate the number of pieces that will appear in this bag in the next loop. We add the replenished bag to the priority queue.
The process repeats until we ran out of time. After we exit the loop we return the number of candy pieces we ate.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset.
One last thing, many thanks to all 5,433 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.
Regards;
John
john.canessa@gmail.com