• 1
of 1 vote

Country: India
Interview Type: Phone Interview

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

Use dynamic programming.
1) Add two auxilary marks on each end of the log (totally n+2 marks)
2) min_cost[i][j]=minimum{min_cost[i][k] + min_cost[k][j] + length[i][j]}, where k=i+1 to j-1
3) min_cost[i][i+1]=0
4) min_cost[i][i+2]=length[i][i+2]
Find min_cost[0][n+1].

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

what's the time complexity of this problem with this logic, O(n^3)??

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

Giving you two extreme cases:
consider a log of length 8
1 strategy: cut smallest possible part, so we cut at mark 1,2,3,4,5,6,7 in that order
so cost would be 8,7,6,5,4,3,2

2 strategy: cut as evenly as possible, so we cut at mark 4,2,6,1,3,5,7
so cost would be 8,4,4,2,2,2,2

the difference would be more prominent with bigger log.

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

what is the meaning of "proportional to the length of the log"?
does it mean that if i cut at say second mark and there are total 10 marks, then cost is just 2.

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

Use dynamic programming.
1) Add two auxilary marks on each end of the log (totally n+2 marks)
2) min_cost[i][j]=minimum{min_cost[i][k] + min_cost[k][j] + length[i][j]}, where k=i+1 to j-1
3) min_cost[i][i+1]=0
4) min_cost[i][i+2]=length[i][i+2]
Find min_cost[0][n+1].

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

i think there are two sub cases :
case 1:cost is linearly proportional to the the length of the log ,in which case,irrespective of the positions of cuts,we have to spent money equal to some constant times of total length of the rod.
case 2 :is when cost of cutting is not linearly proportional ,then we have to minimize sum of k terms ,each representing cost of a particular cut.keeping in mind that (a+b+c..)^n>a^n +b^n +...we should try to keep the size of the log as small as possible i.e k=n.

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

Go binary on the log... nlogn

first n/2
then part one... (n/2)/2...
part two... (n/2)/2...
11
5 6
3 2 3 3
2 1 1 1 1 2 1 2
1 1 1 1 1 1

cost: 6+3+3+2+1+2+2+1+1+1 => 22

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

Greedy algorithm, always divide the log as evenly as possible.

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

Prove that this is optimal.

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

Use smallest case, if there are only two marks.

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

I also want someone to prove it....

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

See post by Jack Cheng, where he gives a counterexample.

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

Is there any numbering of marks? Say, if n=10, and I make a cut at mark 2, it also means that I have made a cut at mark 8 from other end, making the overall sum constant.
By sum, I mean the cost of cutting log w.r.t one end and the other end.

Please let me know if I am overthinking this :P

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

You are.
the cost doesn't depend on where you cut the log but on what the length of the log was when you cut it.
For example, no matter where you cut a log of length 10, you pay \$10. :)

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

assuming the n marks are equally spread across the entire log, Cut the log at n/2th mark, splitting it into two half, and keep repeating the process. the size of the log will be half its size with each cut, we'll make log(n) cuts cozt would be O(nlog(n))

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

Do you really think you are allowed to make such trivial assumptions in a Google Interview?

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

Cutting evenly doesn't work. For example, look at 4,1,2,3. If you cut evenly, the cost is 2. But in fact you can do it with cost 1.9 (I leave this as an exercise :)

You need some sort of Huufman coding scheme where the order of the leaves are preserved.

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

Exactly right. Lookup Optimal Alphabetic search tree. I believe that applies here.

Hu Tucker algorithm: www cs ust hk/mjg_lib/bibs/DPSu/DPSu.Files/jstor_514.pdf
which is O(n^2) time.

A straighforward dynamic programming approach can also be used, which gives a cubic algorithm.

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

I am not sure what are the numbers you have added. I assume these are the possible cuts. So what is the length of the log? Can you explain in more details what you mean.

How I see it for example the Len of the log is lets say 5 and I keep your cuts in 1,2,3,4. So still the greedy approach works - always cut middle(closest to middle) so that we get lowest price:

cut-point | price (len)
2 | 5
1 | 2
3 | 3
4 | 2
Total Price 12.

Can you give me a better one?

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

@gk.

The length of the log is 10 cm: 4 + 1 + 2 + 3.

The first mark is after 4cm from left. The second mark is 1 cm to the right after that etc.

The cost is length/10.

In greedy approach first cut [4,1] CUT [2, 3] Cost 1.
Second cut [4] CUT [1] Cost 0.5,
THird cut [2] CUT [3] Cost 0.5.

TOtal cost 2.

Better solution
[4] CUT [1,2,3] Cost 1.
[1,2] CUT [3] Cost 0.6
[1] CUT [2] COST 0.3

Total 1.9.

Greedy does not work always.

And go take a course in logic. Giving an example to show greedy approach works is pointless and does not prove that the greed approach _always_ works.

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

The problem is equivalent if you consider the log already chopped, and you want to put it back together. The cost of putting two pieces together is proportional to the length of the resulting piece.

In this case, does the greedy algorithm (always perform the cheaper available junction) work?
If yes, reverse the order of the junctions and you have the order of cuts for the original problem.

E.g. with 4,1,2,3:

1. 4 (1 2) 3 -> cost 3
2. 4 (1 2 3) -> cost 6
3. (4 1 2 3) -> cost 10

If you read it upside-down, they're the cuts of the previous comment.

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

@Dave: THe optimal alphabetic trees probably does something similar, but is more complicated than what you have. I suggest you read the paper linked.

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

Cutting evenly doesn't work. For example, look at 4,1,2,3. If you cut evenly, the cost is 2. But in fact you can do it with cost 1.9 (I leave this as an exercise :)

You need some sort of Huufman coding scheme where the order of the leaves are preserved.

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

I will give a try.
We have n distinct marks.
We can create all permutations of using these n marks.
Then we can find the cost of each permutation to find the one with the minimum.
We can do one optimization like cutting at 1 or cutting at n will amount the same. So we can cut down on the permutations this way.

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

I even don't understand the question

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

Why don't we put all the n marks at one end , so that the first cut will be proportional to the total length and rest all the n-1 cuts will be free of cost (negligible).
Please let me know your views (and did I understood the question correctly ?)

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

Why don't we put all the n marks at one end , so that the first cut will be proportional to the total length and rest all the n-1 cuts will be free of cost (negligible).
Please let me know your views (and did I understood the question correctly ?)

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

I dont think this will work.. Read the question again..

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

@anonymous : can you explain ???

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

Question doesn't allow you to decide the placement of marks I guess.

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

Question doesn't allow you to decide the placement of marks I guess.

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

This is a variation of String Breaking problem in section 15.9 of "Algorithms by Cormen" text. It needs to be solved by D.P. If you can solve knapsack or similar problems, this is quite similar to that for solving it using D.P.

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

Can somebody check if this code is correct?

import java.util.ArrayList;

public class LogWoodCutting {

public static void main(String args[])
{
ArrayList<Integer> LogSegmentLenght = new ArrayList<Integer>();
/*
* e.g. 1
*/

//e.g. 2

System.out.println(LogWoodCutting.minimumPrice(LogSegmentLenght));
}

private static int minimumPrice(ArrayList<Integer> logSegmentLenght) {
int n = logSegmentLenght.size();
int[][] length = new int[n+1][n+1];
int[][] minCost = new int[n+1][n+1];
int[][] preCut = new int[n+1][n+1];
int i,k;

for(i=0;i<n;i++)
length[i][i+1]=logSegmentLenght.get(i);

for (k = 2; k <= n; k++)
for (i = 0; i < n; i++) {
if (i + k <= n)
length[i][i + k] = length[i][i + k - 1] + length[i + k - 1][i + k];
}

for(i=0;i<n-1;i++)
minCost[i][i+2]=length[i][i+2];

for(i=0;i<n-1;i++)
preCut[i][i+2]=i+1;

for (k = 3; k <= n; k++)
for (i = 0; i < n; i++) {
if (i + k <= n)
minCost[i][i + k] = findMin(i, i+k, minCost, length, preCut);

}

System.out.print("Cutting sequence:");
printCut(0,n, preCut);
System.out.println();

return minCost[0][n];
}

private static void printCut(int i, int j, int[][] preCut) {
if(preCut[i][j]==0) return;
System.out.print(preCut[i][j] + " ");
int cut = preCut[i][j];
printCut(i,cut,preCut);
printCut(cut,j,preCut);

}

private static int findMin(int i, int j, int[][] minCost, int[][] length, int[][] preCut) {
int value = minCost[i][i+1]+minCost[i+1][j];
preCut[i][j]=i+1;
int k=2;
while(i+k<j)
{
if((minCost[i][i+k]+minCost[i+k][j])<=value)
{
value = (minCost[i][i+k]+minCost[i+k][j]);
preCut[i][j]=i+k;
}
k++;
}
return value + length[i][j];
}

}

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

Think of this problem in terms of graph. lets say the "n" marks where we have to make a cut are "n" vertices and the cost of moving the ace from vertex V1 to V2 the length of log form V1 to V2.... now we have to cover all vertices while minimizing the cost...

thus this can be reduced to spanning tree problem and our goal is to find minimum spanning tree.... there are 2 algorithms for this... Prims and Kruskal.. they each have pros and cons... but any of them will solve the problem....

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

Hope this will work -
# include <stdio.h>

#define PRICE_PER_UNIT xx
#define MAX_SEGEMENT yy

int wood_segment[MAX_SEGMENT] = { 4,5,1,2,1,...};
typedef struct result_segment {
int left_seg;
int right_seg;
struct result_seg *next
}result_seg;

void free_ptr(result_seg *ptr)
{
if (ptr != NULL)
free_ptr(ptr->next);
free(ptr);
}

int cost_of(int first_seg_idx, int last_seg_idx)
{
int len = 0;
for(int i = first_idx, i <= last_seg_idx; i++)
len += wood_segment[i];
return (len * PRICE_PER_UNIT);
}

result_seg *calc_cost(int *total_cost, int first_seg_idx, int last_seg_idx)
{
int ct_cost, least_cost = 0, initial_cost;
result_seg *least_cost_seg, *left_cost_seg, *right_cost_seg;

initial_cost = *total_cost;
for(i = first_seg_idx; i < last_seg_idx; i++) {
*total_cost = initial_cost;
left_cost_seg = right_cost_seg = NULL;
if((ct_cost_seg = (result_seg) malloc(sizeof(result_seg))) == NULL){
printf("malloc failed \n");
exit(-1);
}
ct_cost_seg->left_seg = first_seg_idx+1; //(1,2) (1,3) (1,4) (1,5) - In case of 5 segments.
ct_cost_seg->right_seg = (last_seg_idx+1) - (last_seg_idx - i - 1);

*total_cost += cost_of(first_seg_idx, i);
*total_cost += cost_of(i+1, last_seg_idx);
if((left_seg - first_seg_idx) > 1) {
left_cost_seg = calc_cost(total_cost, first_seg_idx, i);
}
if((last_seg_idx - i) > 1) {
right_cost_seg = calc_cost(total_cost, i+1, last_seg_idx);
}
if(left_cost_seg == NULL && right_cost_seg == NULL){
return ct_cost_seg; // only two segments left.
}
if (left_cost_seg == NULL) {
ct_cost_seg->next = right_cost_seg;
} else {
ct_cost_seg->next = left_cost_seg;
if(right_cost_seg != NULL) {
for(result_seg *ct_seg = left_cost_seg; ct_seg->next != NULL; ct_seg = ct_seg->next);
ct_seg->next = right_cost_seg;
}
}
if(least_cost = 0 || least_cost > *total_cost) {
if(least_cost != 0)
free_ptr(least_cost_seg);
least_cost = *total_cost;
least_cost_seg = ct_cost_seg;
} else {
free_ptr(ct_cost_seg);
}
}
*total_cost = least_cost;
return ct_cost_seg;
}

main()
{
int least_cost = 0;
result_seg *least_cost_seg;

least_cost_seg = calc_cost(&least_cost, 0 , MAX_SEGMENT-1);
print("Minimal Cost = %d\n Minimal Cost Cuts are -", *least_cost);
for(; least_cost_seg != NULL; least_cost_seg = leg_cost_seg->next) {
printf("Left segments = %d Right segments %d\n", least_cost_sega>-left_seg, least_cost_seg->right_seg);
}
}

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

Sorry, what is the "goal"? Cutting at all the marks?

Otherwise, the minimum is 0, don't cut anything at all...

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

int CutWoodDP(vector<int>& w, map<pair<int, int>, int>& p, int start, int end, int length)
{
if (start >= end)
{
return 0;
}

if (p.find(pair<int, int>(start, end)) != p.end())
{
return p[pair<int, int>(start, end)];
}

int sumUpToi = 0;
int minSum = numeric_limits<int>::max();

for(int i=start; i<end; ++i)
{
sumUpToi += w[i];
int sum = CutWoodDP(w, p, start, i, sumUpToi) + CutWoodDP(w, p, i+1, end, length - sumUpToi) + length;

if (sum < minSum)
{
minSum = sum;
}
}

p[pair<int, int>(start, end)] = minSum;

return minSum;
}

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

Cut at every half - 8 + (4+4) + (2 + 2 + 2 + 2) = 8log8

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

Recursion or dynamic programming. DP seems hard to work out.

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

I think,the cuts should happen where the 2 parts has the minimum difference in length.
log length is 10.marks at 2 ,4,6 ,8
4 and 6 cost 10
4- at 2 cost 4
6- (2,4) cost 6
(2,4) divide 4 cost 4 total cost -10+6+4+4=24

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

This is a variation of binary search. Cut the log in 2 halves each time and we would get the minimum cost.

Comment hidden because of low score. Click to expand.

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.