Amazon Interview Question SDE1s
Country: India
Interview Type: In-Person
First sort the array of colors so colors 0..99 are seen in that order.
Then there are two approaches to reach the solution.
1. While mixing, alternate between emitting minimum smoke and getting 0 as the resultant color of the mix.
2. A more elegant approach (thanks to a hint given by my friend) is to follow a greedy approach to get 0(by mixing 1 with 99 and then 2 with 98 and so on...) as the resultant color at each mixing step. This results in the jars array finally having 50 zeroes along with the color 50 in it. The 50 zero colors when mixed among themselves, vanish into a single zero color with 0 smoke. The lone zero color can then be mixed with color 50 so color 50 remains in the end.
It is quite counter-intuitive and surprising to see how achieving the objective of getting minimum color value(=0) at every step, achieves the overall objective of emitting minimum smoke.
I don't think there are any guarantees about certain values being present. The problem doesn't state that all values 0-99 will occur, just that they're the valid possible colors. Obviously, if n < 100, then they won't all occur.
For example: [ 0, 5, 99 ]. There is no way to mix any two of these colors to result in a 0 color result. Therefore I don't think your 2nd approach is viable.
However, I have yet to think of a clever way of solving this problem, just recursion/brute-force.
Do not use the jar with color 0, mix other jars in any order you want. Then use the color 0 at last step, then you will have the color with smoke 0. Am I missing something?
Instead of mixing the 'other jars' in any order, you can try to give it a some order so the objective of emitting minimum smoke is met.
@Arth my interpretation of this question is that the final smoke is the sum of all smokes produced during mixing. So though in the last step you will get color with 0 smoke it doesn't mean that the sum of previous ones is minimum.
Here is my attempt:
Lets say there is an array of n elements int[] arr = new int[n];
1) Sort array
2) For every element a[i] find its perfect matching pair. By perfect matching pairs I mean elements a[i], a[j] which sum a[i] + a[j] % 100 is the closest to 0.
2) Mix them and insert new element on its position in the original array so that it is taken in to account during the next 'search and merge' phase.
3) Repeat the process till there is only one element.
Eg.
int[] arr = {3,5,95, 99}
Starting from the first element a[i] = 3 find perfect pair:
1)
100 - a[i] = 97
- the perfect match for 3 would be 97 say X
2) Use binary search to find X. However there is no such value. But we will get next bigger element from 97 which is 99 call it Y as a result of bin search.
2) Because the perfect match was not found we have to check the following conndition
min ((a[i] + a[i+1]) % 100, (a[i] + Y) % 100)
to find a perfect match. In our example it is
min ((3+ 5) % 100, (3 + 99) % 100)
so we choose (3,99) and mix them.
3) New array is
int[] arr = {2,5,95}
, Repeat 1 and 2 to find pairs for the rest of elements.
- (5, 95), (2, 0), (2)
At the and we should get min smoke.
Yet another gem from Amazon. I have a solution for this, which I will post shortly.
- Murali Mohan January 09, 2014