## Google Interview Question for SDE-2s

Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
2
of 4 vote

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.

The 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.

Comment hidden because of low score. Click to expand.
0

---

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@guilhebl, you cannot do one by one after the first day. They would just not be used if there are no more of them than the number of days that passed.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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] -- ;

}
}``````

Comment hidden because of low score. Click to expand.
2

instead of sorting in every iteration, you can use a min - heap.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

You can use heap for that

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0

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).

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

Your time complexity is not accurate. Each loop you have to go through candles and decrease value by one, so in worst case you have to perform O(k) operation in the loop. As as result your time complexity is O(k n log(n)) and because k is bound above by n, O(n^2 log(n)).

Comment hidden because of low score. Click to expand.
0
of 2 vote

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}

>> How can you light candles 2 and 3 when they are already lit? Question is very ambiguous.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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}));

}
}``````

Comment hidden because of low score. Click to expand.
0

looks like a series problem s = n(n+1)/2

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

should this work ?

``````S = Sum(CandleLengths)
let n=number of days
solve the equation n(n+1)/2 = S``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Sum = 7, count 3
N * (N + 1)/2 = 7
N = 3
so ur answer is 3, but that is not possible

start -> 1,1,5
1st day -> 1,1,4
2nd day-> 1,0,3
3rd day-> not possible since only 2 candles are left

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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 }
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);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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 }
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;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

{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}

Comment hidden because of low score. Click to expand.
0
of 0 vote

{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}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````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) );
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.