IBM Interview Question for Software Engineer / Developers






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

For example

Segment length=100;
Cut at positions: {5,20,50,98}

- Anonymous August 24, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Hinax August 24, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Hinex , I don't think u can solve this problem using ur algorithm . Come up with ur exact algorithm and I will try to find a counterexample .

- Frodo Baggins August 25, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

even i agree to u Hinax.. make the cuts on the positions which are nearest to the mid of that section of block and continue doin the same. it a sort of binary appraoch as u can say ..

- saumils1987 August 25, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It clearly need dynamic programming. I can think of O(n3) DP solution. Anyone can do O(n2)?

- Anonymous August 25, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is your O(n^3) solution?

- The Red Baron August 25, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Its similar to matrix chain multiplication and its clear again that the number of cuts to make is n. Thus, say

a[1, m] = min (k) (a[1,k] + a[k, m] + m);

Solve it using DP

- Anonymous September 24, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]

- rockaustin2k6 August 25, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Isn't ur solution O(n!) where n is the maximum length ?

- aditya3889 September 07, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is making recursive calls to f(). Instead, for dynamic programming, create a matrix that stores the result of f(i,j) as and when they are computed. These will be referred later instead of making recursive call.

- Aswin March 15, 2012 | Flag


Add a Comment
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.

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