Google Interview Question

  • google-interview-questions
    1
    of 1 vote
    42
    Answers

    A log of wood has n marks on it. Cost of cutting wood at a particular mark is proportional to the length of the log. The log of wood can be cut at all the marks. Find the optimal order of the marks where the log should be cut in order to minimize the total cost of cutting.

    - brahmasani99 on May 02, 2012 in India Report Duplicate | Flag
    Google Algorithm

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

- jzhu on May 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on October 20, 2014 | Flag
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.

- epsilon on May 03, 2012 | Flag Reply
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.

- prakhargoyal on May 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- jzhu on May 17, 2012 | Flag
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.

- arindam.mitra2 on June 03, 2012 | Flag Reply
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

- Anonymous on August 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Qing on May 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Prove that this is optimal.

- Anonymous on May 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Use smallest case, if there are only two marks.

- qingd7 on May 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I also want someone to prove it....

- kurskk141 on May 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on May 03, 2012 | Flag
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

- Learner on May 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Rushil on June 21, 2012 | Flag
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))

- vikas24 on May 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on May 03, 2012 | Flag
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.

- Jack Cheng on May 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous on May 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- GKalchev on May 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on May 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Dave on May 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on May 07, 2012 | Flag
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.

- Jack Cheng on May 03, 2012 | Flag Reply
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.

- Anonymous on May 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I even don't understand the question

- Please refine the question on May 04, 2012 | Flag Reply
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 ?)

- rohithindustani2004 on May 07, 2012 | Flag Reply
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 ?)

- rohithindustani2004 on May 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anonymous on May 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@anonymous : can you explain ???

- rohithindustani2004 on May 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- shashank on May 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- shashank on May 10, 2012 | Flag
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.

- Raj on May 18, 2012 | Flag Reply
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
		LogSegmentLenght.add(4);
		LogSegmentLenght.add(1);
		LogSegmentLenght.add(2);
		LogSegmentLenght.add(3);
		*/
		
		//e.g. 2
		LogSegmentLenght.add(1);
		LogSegmentLenght.add(1);
		LogSegmentLenght.add(1);
		LogSegmentLenght.add(1);
		
		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];
	}

		
}

- qingd7 on May 18, 2012 | Flag Reply
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....

- maddy on June 12, 2012 | Flag Reply
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);
}
}

- Anonymous on June 14, 2012 | Flag Reply
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...

- Dontgetit on June 15, 2012 | Flag Reply
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;
	}

- Anonymous on June 23, 2012 | Flag Reply
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

- neer300 on July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- pegasi on August 03, 2012 | Flag Reply
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

- grave on August 11, 2012 | Flag Reply
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.

- dexter999 on August 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.


Add a Comment
Name:

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

Books

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

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More