VMWare Inc Interview Question Software Engineer / Developers




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

This is impossible to do in O(n). Minimum is O(n^2).

Proof:

Let A be {1, 2, 4, 8, ... 2^n}

We must compute all different |A_i - A_j|. We will show that we have 1 + n(n-1)/2 such differences. First of all, because of the modulo, we can only consider |A_j - A_i| with j > i. We also have a difference of 0, from |A_i - A_i| (this is where the 1+ comes from in the formula above).

Assume that we have i1 and j1 with i1<j1 and i2 and j2 with i2<i2, for which |A_i1 - A_j1| == |A_i2 - A_j2|. We will prove that i1 == i2 and j1 == j2. Because of the ordering between i* and j*, we have A_j1 - A_i1 = A_j2 - A_i2. This is equivalent to 2^j2 - 2^i2 == 2^j1 - 2^i1, turns to 2^i2(2^(j2-i2) + 1) == 2^i1(2^(j1-i1) + 1). From this, 2^i2 has to divide 2^i1, since the parenthesis on the right (2^(j1-i1) + 1) is odd and cannot be divided by 2. In turn, 2^i1 has to divide 2^i2. Therefore i2 == i1 == i. From this, 2^(j1-i) + 1 == 2^(j2-i) + 1, which gives 2^(j1-i) == 2^(j2-i), which gives j1 == j2 == j. QED

This proves that among all pairs (i, j) with i < j, each has a unique difference |A_j - A_i|. They are n(n-1) / 2 pairs, which will take O(n^2) to even print, let alone find.

QED

- Alex on September 11, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

*Sigh* Probably yet another idiot question poster posting an inaccurate statement of the problem. The guy(s) who said you can't do better than O(n^2) are of course correct. The rest of you who gave O(n) algorithms or can't post a proper question need not apply for any software job ... please. My best guess is that the question was asking for the *sum* over all possible |ai-aj|. Now try to do O(n) for this problem.

- Bullocks on July 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sum = 0;
for(i = 1 to n)
sum += [n + 1 - 2*i] * Ai

?

- Anonymous on January 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I doubt if O(n) is possible. It seems that if this problem could be solved in O(n) sorting could be done in O(n) as well.

- anonymous on May 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Pls ignore the comment. It says "sorted array".

- oops on May 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If I'm allowed to used extra space,

I would construct an array such that S[i] = Sum(A[0..i]). Takes O(n).

1, 2, 4, 6, 7, 9, 20

|S[i]-S[j]| is the Sum(A[i+1..j]).
|S[i-1]-S[j-1]| is the Sum(A[i..j-1])

i.e,
|S[i]-S[j]| = a[i]+a[i+1]+a[i+2]..+a[j]
|S[i-1]-S[j-1]| = a[i-1]+a[i]+a[i+1]+..+a[j-1]
So,
|S[i]-S[j]| + |S[i-1]-S[j-1]| = |a[i]-a[j]|

Correct me if it's wrong...

-Hari.

- Hari Prasad Perabattula on May 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How do you do it in o(N) time, not space..

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

It does happen in O(n) time . It takes O(n) Space too .

- pup on May 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

|ai-aj| is absolute value

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

@pup: i doubt if you understand the problem itself. Tell me how can you generate O(n^2) numbers less than O(n^2) time? You can't do it in deterministic Turing machine.

- lol on May 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

there will be n^2 |ai-aj| pairs...wont we need at least n^2 operations to fill those n^2 values in an array.,...i doubt if it could be done in O(n)...

- camSun on May 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

As given array is sorted( assuming descending order) , lets say size of array is 10, a[0,...9]. and the |ai - aj| = x.
Assuming that all numbers are unique in the array ( if they are not this algo can be easily modified). Now define two indexes such that i = 0 and j=1, find the first aj such that either |a0 -aj| = x or |a0 - aj| < x .
Now we have two indexes such that i=0 and j. if |ai - aj| = x then ++j else if |ai-aj|< x then ++i. Follow this procedure and we will get the pairs.

Complexity: O(n)

- Tito on May 11, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I'm not convinced. Let input is {1,4,10,20}. Possible diff values are:

3, 9, 19
   6, 14
      10

All diffs are unique. Possible set of diff values have size O(n^2). How your algorithm works her?. Show stepwise progress. Thanks.

- lol on May 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The solution space is O(n^2), so there is no way to to solve it in O(n).

- lol on May 12, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

After yahoo VMWare is also asking for rocket science :P

- baghel on May 12, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

the minimum time complexity is O(n^2), here is the obvious reason:
say, the array is 1, 2, 3, 4
so all pairs are (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (2, 4),
total number of pairs in this type of input array is !(n-1) = O(n^2)

- Vinod Patankar on May 12, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I could only think of the below given sol. to reduce the matrix into half. Is there a better way to solve the above problem?

for(i=0 to n)
{
j=0;
while((ai-aj)!=0)
{
find(ai-aj);
j++;
}
}

- Rajiv on May 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Don't need to process a array location n1 if current array location n2 is greater than n1.

void printDiff(int a[], size_t size)
{
for (unsigned int i = 0; i < size; ++i)
{
for (unsigned int j = i+1; j < size; ++j)
{
cout << i << " , " << j << " = " << abs(a[i] - a[j]) << endl;
}
}
}

- Nathan on May 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This sounds like the best i can do, i dint understand anything faster, and i doubt if O(n) is possible

- raped on July 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Well...if a parallel/vector operations are allowed ... :)
Then, in cycle i=0->N subtract the element i from the rest i+1..N elements - as a one operation - and save results for each step...
Other ideas?

- celicom on May 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(nlogn) ??
traverse i till n
find binsearch(|ai-aj|) in rest of the array..
for element 0 u have 10 -10
for element 1 u have 9
for -11 you have 1(this comes before 0)

- laterGator on October 01, 2012 | Flag Reply


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