Google Interview Question SDE-2s
Country: India
Interview Type: Written Test
EDIT: Added working solution
---
Ok, now I have a prof it is not going to work:
Let's say we have n candles and perfect n(n+1)/2 combined length. and the first candle is n(n+1)/2 - (n-1) and the rest of candles are 1.
The candles that are taller than possible amount of days can never be fully utilized.
Please, don't down-vote because I can just remove this but I do not remove because I think this thoughts can help in discussion.
The idea is to keep using candles until all of them reach size 1, then you're left with the only option of extinguishing one by one.
The upper bound for maximum days is Number of candles
Use greedy approach:
int numDays = 0;
while(true)
{
numDays += 1;
sort candles by descending length of candle
for(int i =0; i< numDays; ++i)
{
if(candleLength[i] == 0)
{
return numberOfDays;
}
candleLength[i] -- ;
}
}
You sort the candles in descending order, take the tallest one(s), burn an inch off, rearrange the candles, take again the tallest ones, burn an inch off etc.
The complexity is i think n^2 unless you use some data structure which allows sublinear sorting of partially sorted array
Solution using:
1. sorting - tallest candles will be last
2. decrease sequentially the candles according to each days number.
approach, time: O(N*log(K)) where K is the number of days per cycle, space O(1):
public static int daysFromCandles(int[] a, int daysMax) {
if(a == null || a.length == 0) {
// Error
return -1;
}
int limit = daysMax;
int candles = 0;
int days = 0;
Arrays.sort(a);
int currentIndex = a.length-1;
boolean stillCandles = true;
while (stillCandles) {
// day cycle
for (int i = 0; i < limit && stillCandles; i++) {
candles = i + 1;
// starting lit from highest
int j = currentIndex;
for (;candles>0 && j>0 && stillCandles; j--,candles--) {
if (a[j] > 0) {
a[j]--;
}
if (j == 0) {
if (a[j] > 0) {
currentIndex--;
} else if (a[j] == 0) {
stillCandles = false;
}
}
}
currentIndex = j;
if (currentIndex == 0) {
int top = a.length-1;
while (a[top] == 0 && top > 0) {
top--;
}
if (top == 0) {
stillCandles = false;
}
currentIndex = top;
}
days++;
}
}
return days;
}
Not sure that your time complexity is correct. As for me your solution takes in worst case O(N * K) where N - number of days and K number of candles, because you have while loop which always has N iteration and internal for loop which should go on the last step through all candles in worst case (when all candles are equal and have numbers equal to number of days).
Let n be the candle count
Maximum number of days should be <= n
sort the height of candles in descending order
maintain day count which contains the maximum number of days.
loop through the height
reduce height of one candle by 1 in first iteration
reduce height of one additional candle (by 1) for each iteration
increment the day count for each iteration
iterate till day count <= n and any of the candle height shouldn't be zero
Greedy approach: always light the tallest candles and extinguish the lowest one
Can use a min heap for lit candles and max heap for unlit candles which offer lgn insert/delete/update runtimes.
Runtime: O(klgn) where k is the number of rounds and n is the number of candles.
Pseudocode:
int countRounds(litCandles, unlitCandles, round) {
// Decrease height of all lit candles by 1
// Remove all lit candles whose height becomes 0
// If no lit candles remain and no unlit candles remain, return 1
// Based on the round, light "round" number of unlit candles, moving them from unlit to lit heap
// If not enough candles exist, return 1
// Unlight the lowest lit candle, moving it from lit to unlit heap
// Recurse with set of candles for next round
return 1 + countRounds(litCandles, unlitCandles, round + 1);
}
public class FindMaxDays{
public int findDays(int candleNum, int maxDays, int level) {
if(maxDays*(1 + maxDays) >= 2*candleNum || level == 0) {
return maxDays;
}
else
return findDays(candleNum, maxDays + 1, level -1);
}
public int findMaxDays(int [] array) {
int sum = 0;
for(int count=0; count<array.length; count++) {
sum+=array[count];
}
return findDays(sum, 0, array.length);
}
public static void main(String [] args) {
System.out.println(new FindMaxDays().findMaxDays(new int[]{4,4,4}));
}
}
We use greedy approach: each turn we try to decrease candles with max values by one. If there is not enough candles or we exhaust the length of a next candle, we done. Instead to use max_heap for supporting turn-number max values we can use count sort.
Thus the time complexity is O(N * K), where N is number of turns and K is number of candles. Because number of turns is bounded above of number of candles we can replace N with K, so we have O(K^2). Memory complexity is O(K).
/**
* Created by Igor_Sokolov on 3/12/2015.
*/
public class CarrerCup_5196482787409920 {
public static int candleTurns(int[] candles) {
if (candles.length == 0) {
return 0;
}
countSort(candles);
int turn = 0;
while (true) {
for (int i = 0; i < turn + 1; i++) {
if (--candles[i] < 0) {
return turn;
}
}
turn++;
if (turn >= candles.length) {
return turn;
}
countSort(candles);
}
}
private static void countSort(int[] candles) {
int[] counts = new int[candles.length];
int last = 0;
for (int i = 0; i < candles.length; i++) {
int candle = candles[i];
if (candle >= counts.length) {
swap(candles, last++, i);
} else {
counts[candle]++;
}
}
for (int i = counts.length - 1; i >= 0; i--) {
int count = counts[i];
if (count != 0) {
for (int j = 0; j < count; j++) {
candles[last++] = i;
}
}
}
}
private static void swap(int[] candles, int i, int j) {
int t = candles[i];
candles[i] = candles[j];
candles[j] = t;
}
public static void main(String[] args) {
int[] test1 = {};
System.out.println(candleTurns(test1)); // 0
int[] test2 = {1};
System.out.println(candleTurns(test2)); // 1
int[] test3 = {10};
System.out.println(candleTurns(test3)); // 1
int[] test4 = {2, 2, 2};
System.out.println(candleTurns(test4)); // 3
int[] test5 = {1, 2, 2};
System.out.println(candleTurns(test5)); // 2
int[] test6 = {1, 2, 3};
System.out.println(candleTurns(test6)); // 3
int[] test7 = {1, 2, 3, 4};
System.out.println(candleTurns(test7)); // 4
int[] test8 = {1, 2, 3, 3};
System.out.println(candleTurns(test8)); // 3
int[] test9 = {3, 3, 3, 3};
System.out.println(candleTurns(test9)); // 4
}
}
I think its a simple math problem. Just use quadratic equation and you are done.
Lets take an example :
[2, 3, 5, 3, 1, 1, 1]
Total number of candles are 7 so count is 7
Also take the sum of all the candles height in this case sum is 16
Now since the problem says 1st day 1, 2nd day 2, 3rd day 3 and so on
So its
N * (N+1)/2 = sum
well we know the sum as 16
N * (N+1)/2 = 16
N2 + N = 32
N2 + N - 32 = 0
= -1 +- SQRT(1 - 4 x 1 x (-32))/2
= -1 +- SQRT(1 - (-128))/2
= -1 +- SQRT(129)/2
SQRT(129) floored to 11
= -1 +- 11/2
= -1 + 11/2
= 10/2 = 5 days
Lets solve it manually
Problem: [2, 3, 5, 3, 1, 1, 1]
Sort DESC Order: [5, 3, 3, 2, 1, 1, 1]
[4, 3, 3, 2, 1, 1, 1] // 1st day
[3, 3, 2, 2, 1, 1, 1] // 2nd day
[2, 2, 2, 1, 1, 1, 1] // 3rd day
[1, 1, 1, 1, 1, 1, 0] // 4th day
[0, 0, 0, 0, 0, 1, 0] // 5th day
Missed to add this :
after getting the result from quadratic equation just do a diff with the count. which ever is less is the answer.
Lets take an example
[5, 5, 5]
count = 3
sum = 15
N * (N + 1)/2 = 15
N2 + N = 30
N2 + N - 30 = 0
= -1 +- SQRT(1 - 4 x 1 x (-30))/2
= -1 +- SQRT(1 - (-120))/2
= -1 +- SQRT(121)/2
= -1 +- 11/2
= -1 + 11/2
= 10/2
= 5
so in this case answer will be 3 since the count is lesser than the answer 5.
package careercup;
/*
* You are given heights of n candles .
First day you lit one candle
second day you need to lit two candles
Third day you need to lit three candles
..........
........
till possible.
After lighting candles the height of candles deduced by 1 each day.You can also extinguish any candle you want but only at the end of day.
So you need to tell the maximum number number of days , you can carry on lighting the candles.
Example : there are three candles of heights {2 , 2 ,2 }
Answer : 3
1.You light first candle on day one. heights -> {1,2,2}
2.You light second and third and extinguish first one . heights ->{1, 1,1}
3.You light all the candles. heights -{0,0,0}
*/
public class MaxCandles {
public static void main(String[] args) {
// TODO Auto-generated method stub
int heights[]={9,4,3,2,2,2,2,2,2,2,2};
int used=0;
int numdays=0;
int heightSum=0;
for(int i=0 ; i<heights.length&&used<=heightSum;i++)
{
used+=++numdays;
heightSum+=heights[i];
System.out.println(used+" "+heightSum);
}
System.out.println(numdays);
int moreDays=heights.length-numdays;
while(moreDays>numdays)
{
numdays++;
moreDays-=numdays;
}
System.out.println("Max No of days:"+numdays);
}
}
package careercup;
import java.util.Arrays;
/*
* You are given heights of n candles .
First day you lit one candle
second day you need to lit two candles
Third day you need to lit three candles
..........
........
till possible.
After lighting candles the height of candles deduced by 1 each day.You can also extinguish any candle you want but only at the end of day.
So you need to tell the maximum number number of days , you can carry on lighting the candles.
Example : there are three candles of heights {2 , 2 ,2 }
Answer : 3
1.You light first candle on day one. heights -> {1,2,2}
2.You light second and third and extinguish first one . heights ->{1, 1,1}
3.You light all the candles. heights -{0,0,0}
*/
public class MaxCandles {
public static void main(String[] args) {
// TODO Auto-generated method stub
int heights[]={9,2,2,4,3,2,2,2,2,2,2};
maxNoOfDays(heights);
}
public static int maxNoOfDays(int heights[])
{
if(null==heights||heights.length==0)
return 0;
Arrays.sort(heights);//ascending order
int used=0;
int numdays=0;
int heightSum=0;
for(int i=heights.length-1 ; i>=0&&used<=heightSum;i--)
{
used+=++numdays;
heightSum+=heights[i];
System.out.println(used+" "+heightSum);
}
System.out.println(numdays);
int moreDays=heights.length-numdays;
while(moreDays>numdays)
{
numdays++;
moreDays-=numdays;
}
System.out.println("Max No of days:"+numdays);
return numdays;
}
}
This is a weird question, and a detail that I think a lot of posters here are missing is that on day N you must have N candles lit.
I guess you'd just have a priority queue with the candles. On day 1, grab the tallest candle. On day 2, extinguish the candle, put it back into the queue with reduced height, grab the two tallest candles and light them. On day 3, extinguish those, put them back in the queue, grab the three tallest candles and light them. Keep going.
Because N candles must be lit on day N, obviously you can't do this for more days than there are candles. So for N candles the absolute max is N days.
This is a simple Greedy approach.
Sort the array. Start from the maximum, each day we add an element and subtract the number of candles needed. So given
2 2 2
Day 1: 2 - 1 = 1
Day 2: 1 + 2 - 2 = 1
Day 3: 1 + 2 - 3 = 0
public static int maxDays(int[] candles){
if(candles == null || candles.length == 0)
return 0;
Arrays.sort(candles);
int lit = candles[candles.length - 1] - 1;
int count = 1;
for(int i = candles.length - 2; i >= 0; i--){
if(lit + (candles[i] - (count + 1)) < 0)
break;
lit += candles[i] - (++count);
}
return count;
}
Algo: another variant of puzzle-solving problem
n candles with heights>0, for goal of lighting m candles out of n, find all possible combinations C(n,m)
for each combination, reduce the m selected candles' heights by 1, and check if a solution is found
if the number of candles with heights>0, let's say, n' < (m+1), a solution to the puzzle is found (i.e. base case, no
further lit):
check if either it is the first solution found or its lit days > the longest lit days, update longest record
else //longer lit days are possible(i.e. n'>=m+1), make recursive call to find a solution, all candles become available
again for selection (i.e. new temp target of lighting m+1 candles), back to the algo beginning (n', m+1)
return the selected m candles back to the set G, and check the next combination
Algo: another variant of puzzle-solving problem
n candles with heights>0, for goal of lighting m candles out of n, find all possible combinations C(n,m)
for each combination, reduce the m selected candles' heights by 1, and check if a solution is found
if the number of candles with heights>0, let's say, n' < (m+1), a solution to the puzzle is found (i.e. base case, no
further lit):
check if either it is the first solution found or its lit days > the longest lit days, update longest record
else //longer lit days are possible(i.e. n'>=m+1), make recursive call to find a solution, all candles become available
again for selection (i.e. new temp target of lighting m+1 candles), back to the algo beginning (n', m+1)
return the selected m candles back to the set G, and check the next combination
Algo: another variant of puzzle-solving problem
n candles with heights>0, for goal of lighting m candles out of n, find all possible combinations C(n,m)
for each combination, reduce the m selected candles' heights by 1, and check if a solution is found
if the number of candles with heights>0, let's say, n' < (m+1), a solution to the puzzle is found (i.e. base case, no
further lit):
check if either it is the first solution found or its lit days > the longest lit days, update longest record
else //longer lit days are possible(i.e. n'>=m+1), make recursive call to find a solution, all candles become available
again for selection (i.e. new temp target of lighting m+1 candles), back to the algo beginning (n', m+1)
return the selected m candles back to the set G, and check the next combination
Algo: another variant of puzzle-solving problem
n candles with heights>0, for goal of lighting m candles out of n, find all possible combinations C(n,m)
for each combination, reduce the m selected candles' heights by 1, and check if a solution is found
if the number of candles with heights>0, let's say, n' < (m+1), a solution to the puzzle is found (i.e. base case, no
further lit):
check if either it is the first solution found or its lit days > the longest lit days, update longest record
else //longer lit days are possible(i.e. n'>=m+1), make recursive call to find a solution, all candles become available
again for selection (i.e. new temp target of lighting m+1 candles), back to the algo beginning (n', m+1)
return the selected m candles back to the set G, and check the next combination
{Algo: another variant of puzzle-solving problem
n candles with heights>0, for goal of lighting m candles out of n, find all possible combinations C(n,m)
for each combination, reduce the m selected candles' heights by 1, and check if a solution is found
if the number of candles with heights>0, let's say, n' < (m+1), a solution to the puzzle is found (i.e. base case, no
further lit):
check if either it is the first solution found or its lit days > the longest lit days, update longest record
else //longer lit days are possible(i.e. n'>=m+1), make recursive call to find a solution, all candles become available
again for selection (i.e. new temp target of lighting m+1 candles), back to the algo beginning (n', m+1)
return the selected m candles back to the set G, and check the next combination}
{Algo: another variant of puzzle-solving problem
n candles with heights>0, for goal of lighting m candles out of n, find all possible combinations C(n,m)
for each combination, reduce the m selected candles' heights by 1, and check if a solution is found
if the number of candles with heights>0, let's say, n' < (m+1), a solution to the puzzle is found (i.e. base case, no
further lit):
check if either it is the first solution found or its lit days > the longest lit days, update longest record
else //longer lit days are possible(i.e. n'>=m+1), make recursive call to find a solution, all candles become available
again for selection (i.e. new temp target of lighting m+1 candles), back to the algo beginning (n', m+1)
return the selected m candles back to the set G, and check the next combination}
Algo: another variant of puzzle-solving problem
n candles with heights>0, for goal of lighting m candles out of n, find all possible combinations C(n,m)
for each combination, reduce the m selected candles' heights by 1, and check if a solution is found
if the number of candles with heights>0, let's say, n' < (m+1), a solution to the puzzle is found (i.e. base case, no further lit):
check if either it is the first solution found or its lit days > the longest lit days, update longest record
else //longer lit days are possible(i.e. n'>=m+1), make recursive call to find a solution, all candles become available again for selection (i.e. new temp target of lighting m+1 candles), back to the algo beginning (n', m+1)
return the selected m candles back to the set G, and check the next combination
Algo: another variant of puzzle-solving problem
n candles with heights>0, for goal of lighting m candles out of n, find all possible combinations C(n,m)
for each combination, reduce the m selected candles' heights by 1, and check if a solution is found
if the number of candles with heights>0, let's say, n' < (m+1), a solution to the puzzle is found (i.e. base case, no further lit):
check if either it is the first solution found or its lit days > the longest lit days, update longest record
else //longer lit days are possible(i.e. n'>=m+1), make recursive call to find a solution, all candles become available again for selection (i.e. new temp target of lighting m+1 candles), back to the algo beginning (n', m+1)
return the selected m candles back to the set G, and check the next combination
public static void main(String args[]) {
for(String arg : args) {
int num = Integer.parseInt(arg);
int places = (int)((float) Math.log10(num+1)/Math.log10(2));
int highest = (int)Math.pow(2, places) - 1;
char output[] = new char[places];
int itr = places-1;
int diff = num - highest;
while(diff != 0) {
int bal = diff%2 ;
diff /= 2 ;
if(bal == 1)
output[itr--] = 'B';
else
output[itr--] = 'A' ;
}
while(itr >= 0)
output[itr--] = 'A';
System.out.println( arg + " --- " + disp(output) );
}
EDIT: This is working solution and it is still O(n) because while loop will have very small amount of iterations. It is based on the thinking I posted (below the solution) - it was not 100% correct, but it is now corrected:
static public int solveIgnoringUnusableWax ( int[] candles ) { int totalLength = 0; for ( int c : candles ) { totalLength += c; } return Math.min( candles.length, //inverse of n(n+1)/2 (int)Math.floor((Math.sqrt(8*totalLength+1)-1)/2) ); } static public boolean cutUnusableWax( int[] candles, int currentSolution ) { boolean cut = false; for ( int i = 0; i < candles.length; i ++ ) { if ( candles[i] > currentSolution ) { candles[i] = currentSolution; cut = true; } } return cut; } static public int solve( int[] candles ) { int currentSolution; do { currentSolution = solveIgnoringUnusableWax ( candles ); } while ( cutUnusableWax(candles, currentSolution) ); return currentSolution; }Find biggest integer n(n+1)/2 that is smaller or equal than combined length of all candles. Answer is minimum between n and number of candles. Time complexity O(n) for summing up step.
- CT March 11, 2015The strategy for choosing candles is always peek tallest.
Scetch of Proof.
in case n is less than number of candles
Let's say you can no longer peek candles. It means you have all left candles size 1. Why. Because in previous steps you burned the candles that you need now and they were size 1. Since we peek allays tallest, we would prefer size 2. Meaning there could not be size 2 candles left. You can make the same argument about burning size 2 candles and so on.
If all left candles are size 1, the combined length of all candles can be used optimally.