IBM Interview Question
Software Engineer / DevelopersWe can optimize this by dividing the line into segment of nearly equal length. Seems like a simple binary search over the position array will do. Time complexity: O(nlogn).
It clearly need dynamic programming. I can think of O(n3) DP solution. Anyone can do O(n2)?
O(n^3) [where n is the length of position array]
let's modify the cut array in example to have 0 and 100 as
cut[6] = {0,5,20,50,98,100}
dp function f(i,j) which will be passed the values f(0,n-1) //n is 6 here
//Let len[i][j] store the length from cut i to cut j
int f(i,j)
{
if(i>=j)return 0;
int ret=INF;
for(int t=i+1;t<j;t++){
ret=(int)min(ret,f(i,t) + f(t,j) + len[i][j]);
}
return ret;
}
//len[i][j] can be calculated in O(n^2)
// or u can modify it to len[j] // where len[j] stores the length upto j from 0
// This can be calculated in O(n)
// Then,in the function replace the len[i][j] with len[j]-len[i]
For example
- Anonymous August 24, 2010Segment length=100;
Cut at positions: {5,20,50,98}