## Google Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
5
of 9 vote

Each time, you combine two sticks of min length, you have (N-2) + 1 (the new stick) = N-1 left in system. So now you re-calculate and choose 2 min sticks and combine those and continue.

Implementation:
Use a min-heap, remove min and next min = combine, insert the new length into the heap.
worst case Per operation runtime: 2*log (N) (remove 2 mins) + log (N) (insert new value)

Operation repeated N times = 3N*log(N) = O(N log(N))

However, if you notice, the height of min-heap goes on decreasing in each step and a more tighter analysis would yield a log(N!) worst case complexity (which ofcourse is O(N*log(N))

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

it looks correct, but idk. I up-vote yours for people to look at it.

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

Huffman / MinHeap .... ok. But where is the proof or reasoning for correctness?

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

Take example 1,9,6,2,5
If Cost in given input order is : 10+16+18+23 = 67
If cost is sorted then : 3+8+14+23 = 48
minHeap is : 3+9+14+23 = 49
1
/ \
2 6
/\
9 5

So min heap wont give the least result sorting will.Please correct me if I am wrong

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

Sorting won't work. If you look at 4, 5, 6, 7
Sorting will give you a cost of 9 + 15 + 22 = 46
Huffman/minheap above will give you a cost of 9 + 13 + 22 =44

In the example 1,9,6,2,5, the minheap algorithm will do the following steps:
1 with 2, cost 3
3 with 5, cost 8
6 with 8, cost 14
9 with 14, cost 23
which is 48 overall.

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

EDITED: there is flaw in my post! The order of sticks matters!

Re-formulate the problem:

Given n sticks of length L_1, L_2, ..., L_n, with total length of L.
Only combination of two sticks into one is allowed each time. Every combination costs the sum of the two sticks.

Calculate the minimum cost to combine all n sticks into a stick of length L.

This can be solved by recursive/DP as following.

Let C(u,v) be the minimum cost to join sticks from number u to number v.
The recursive formula will be:

``C(u,v) = min { C(u,k) + C(k+1,v) }, for k = u+1 to v-1;``

My pseudo code implementation using recursive with memoization:

``````joinSticks(u,v):

if (u == v) return L[u];
if (Mem[pair(u,v)] != 0 ) return Mem[pair(u,v)];

minCost = maxInt;
for k = u to v-1
minCost = min { minCost, joinSticks(u,k) + joinSticks(k+1,v) };

Mem[pair(u,v)] = minCost;

return minCost;``````

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

My solution may work for the constraint that:
"Only combination of two CONSECUTIVE sticks is allowed"

Sorry!

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

Yes. good interpretation.

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

@ninhnnsoc : Your approach will fail for the following scenario
Consider Lengths as {1,4, 2}. According to your approach, it will consider the following cases
Case 1 : minCost(1) + minCost(4,2)
minCost(4,2) is 6 and joining it with 1 will cost 7 so total is 13
Case 2: minCost(1,4) + minCost(2)
minCost(1,4) will be 5 and joining with 2 will be 7 so total will be 12

But the optimal solution is MinCost(1,2) and Join with 4
Total Cost = 3 + 7 = 10

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

@nomad_coder: thanks! My solution is wrong for the original problem.

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

Recursively pick the two sticks of minimum length, merge it (e.g. sum value) and add it back to the collection.

The reason why you should always pick the minimum 2 length is:

1, suppose you have two sticks, a1 and a2
the cost is a1 + a2

2, suppose you have three sticks, a1 < a2 < a3
the answer is you pick a1, a2 first, the cost is 2*(a1 + a2) + a3
why if you choose a3 first? the cost would be higher than above by:
2 * (a3 - a2) - (a3 - a2) = a3 - a2, which is a positive value.

So you should always pick the minimum 2 sticks.

1, Sort the array
2, pick the first two
3, insert the sum of first two to the sorted array (log n)

repeat that steps until done
total cost is nlogn

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

I think the problem can be better explained with an example as many people are thinking that the total cost will be sum of all the lengths. Suppose there are 3 sticks of length 1, 2, 4

You can do the combination in this way,

Step 1: 1+2 (cost=3) Now we have two sticks of length 3 and 4
Step 2: 3+4(cost=7) Now we have one stick of length 7
Total cost 7+3=10

But if you do it in this way,
Step 1: 4+2 (cost=6) Now we have two sticks of length 6 and 1
Step 2: 6+1 (cost=7) Now we have one stick of length 7
Total cost 6+7=13

So we can see that if we add the smaller ones first, we will minimize the cost. We can solve it with a min heap. We will add all the lengths in the min heap. We will pop two from the min heap and add them and put them back in the heap. We will continue this process till there is no more stick.

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

There are two interpretations to this problem.

I suggest the OP edit the question.

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

I don't see reasoning of correctness in this greedy method?

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

I think the key is:
1. sort the sticks in ascent order, L1 <= L2 <= L3 <=...Ln
2. each time when combined 2 sticks, then put it back to the pool, and sort it again as 1)
3. we can see if the each time combination is smallest, the summary of all costs number is smallest.

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

sorry, my answer is just same as guest.guest. I should read it first.

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

As there is no restrictions on the order of sticks mentioned so perhaps sorting them in ascending order and start combining from the least one will give the minimum cost.
suppose the length of sticks are x1,x2,x3,x4.........,xn then the total cost will be given by (x1 + x2) + (x1+x2+x3) + (x1+x2+x3+x4)+...........+(x1+x2+x3+..........+xn)
So to have the minimum value x1,x2,x3......,xn must be in increasing order.

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

``````#include <stdio.h>
#include <stdlib.h>
#define INF (~0)

/* This can be optimized by caching */
unsigned int stick_length(int sticks[], int s, int e)
{
unsigned int i, ans = 0;

for (i = s; i <= e; i++) {
ans += sticks[i];
}

return ans;
}

unsigned int join_sticks(int sticks[], int s, int e, unsigned int **cache)
{
int k, p1, p2, tmp;

if (s > e) return INF;
if (s == e) return sticks[s];

if (cache[s][e] != INF) {
return cache[s][e];
}

for (k = s; k < e; k++) {
p1 = join_sticks(sticks, s, k, cache);
p2 = join_sticks(sticks, k+1, e, cache);

/* adding stick lengths, not same as making cost */
tmp = stick_length(sticks, s, k) + stick_length(sticks, k+1, e);

if (k > s) tmp += p1;
if (k+1 < e) tmp += p2;

if (tmp < cache[s][e]) {
cache[s][e] = tmp;
}
}

return cache[s][e];
}

int main()
{
int i, j;
int sticks[] = {24, 25, 28, 4, 6, 10, 9};
// int sticks[] = {2, 3, 4, 6};
// int sticks[] = {2, 3, 4, 6, 7};
// int sticks[] = {13, 4, 6};
int n = sizeof(sticks)/sizeof(sticks);
unsigned int ans;

unsigned int **cache;
cache = (unsigned int **)calloc(n, sizeof(int *));
for (i = 0; i < n; i++) {
cache[i] = (unsigned int *)malloc(n*sizeof(int));
}
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
cache[i][j] = INF;
}
}

ans = join_sticks(sticks, 0, n-1, cache);
printf("ans: %u\n", ans);

return 0;
}``````

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

I can come up with a NlogN complexity algo if lengths given are in random order.
Incase the lengths are sorted then complextity would be O(N)

``````Lengths = Array.Sort(Lengths)
int [] IncrementalLength = new int[Lengths.length + 1]
for(int i=1;i<=Lengths.length;i++)
incrementalLength[i] = incrementalLength[i-1] + Lengths[i-1]

TotalSum = SumArray(incrementalLength)

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

Solve it with a greedy algorithm similar to algorithm for Huffman tree.

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

Dude, thx for your solution, do you mind to explain why it is the minimum cost solution?

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

Does not work.

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

See this previous question: 14485666 as to why this does not work.

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

oops. wrong id.

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

What does this have to do with Huffman encoding?

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

The "Huffman coding" solution is the same as the one by anshul14ranjan above. The common point between Huffman coding and this problem is that in Huffman, you always start by combining the two characters with the smallest frequency, and you repeat that same step until you build the whole tree, which is very similar to anshul14ranjan 's solution

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

Yes.

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

Suppose there are n(>0) sticks of length {L1, L2, ... , Ln}, where L1<=L2<=...<=Ln, I think the answer is:
cost =
(1) 0, if n=1;
(2) L1+L2, if n=2;
(3) L1 + 2 * (L2 + L3 +...+Ln-1) + Ln, if n>2;
Prove:
Each time we combine 2 sticks to 1, there remains n-1 sticks, until there is only 1 stick. So we need to combine n-1 times. To minimize each combine cost, we should choose the shortest 2 sticks all the time.
So, the 1st combine cost is L1+L2, left n-1 sticks of lenght {L2, L3, ... , Ln};
the 2nd combine cost is L2+L3, left {L3, L4, ..., Ln};
the 3rd combine cost is L3+L4, left {L4, L5, ..., Ln};
...
the total cost is L1+2*(L2 + L3 +...+Ln-1)+Ln.

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

If you take the long stick and start to devide it to parts and pay every time the stick length, the best way to do it, it to devide to two equal parts every time.

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

Dupe: 14485666

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

oops wrong id.

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

I don't get it?
The answer is always sum of overall stick
It's independent of choices leading to the final sum.
It's not even a minimization problem.

for loop in any order over the sticks, and return the accumulated sum.

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

no its not.
ie. you have sticks length 1,2,3
case 1:
you put 1 and 2 together first, cost1 = 1+2 = 3, and you have sticks length 3,3
then you put 3 in, cost2 = 3+3=6;
so the total cost = cost1+cost2 = 3+6 = 9;

case 2"
you put 2 and 3 together first, cost1 = 2+3 =5, and you have sticks length 1,5
then you put 1 in, cost2 = 1+5=6;
so the total cost =cost1+cost2 = 5+6 = 11;

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

People, I got this from glassdoor. It is not from an interview I did!

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

Well don't post it in the interview questions section then!

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

Ridiculous. At least try the problem first. It has an obvious solution! There was a similar question, search for it. The answer there was dynamic programming.

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

The correct answer is the one by anshul14ranjan. Note that the algorithm is essentially equivalent to Huffman's coding algorithm

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

Sort the array and then calculate the cost adding element starting from the lowest length.

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

You have an array of stick lengths,
sLen = {1, 4, 6, 10, 11 }.
((1 + 4) + (6 + 10) + 11) == ((1 + 4) + (6 + (10 + 11)). The minimum cost is the same no matter how you do it. Unless you multiply two lengths that make up one piece and add the cost of each piece. Only in the latter case the answer will be different.

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

The final cost it's always the same (sum of lengths) regardless of the order segments are put together.

Let's say we have 3 segments

``x < y < z``

. The cost is

``x + y + z``

and you can compute it in several ways:

``````(x + y) + z = x + y + z
x + (y + z) = x + y + z
y + (x + z) = x + y + z``````

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

I think,

finally for it to become a stick we have to combine all of them,
hence there is no minimum/maximum,
the cost will be the sum of all the elements(length of sticks).

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

Suppose L1,L2,...Ln are length of the sticks with L1 <= L2 <= L3 <= ... <=Ln.
No matter how you form the final stick, each stick is used twice except for the outer ones, which are used only once. Hence, any combination which puts the largest two sticks at the left & right ends will be an optimal one.

Minimal cost = 2*[ L1 + L2 + ... + L(n-2)] + L(n-1) + Ln

An arrangement having this cost: Ln,L1,L2,L3,...L(n-1)

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.