## VMWare Inc Interview Question Software Engineer / Developers

• 0

Given a sorted array find all possible |ai - aj| where ai,aj belongs to Array A. n^2 is obvious. Find a solution in O(N).

Comment hidden because of low score. Click to expand.
1
of 1 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

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.

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

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

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.

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

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

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

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

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

|ai-aj| is absolute value

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

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

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

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)

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

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.

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

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

After yahoo VMWare is also asking for rocket science :P

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)

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++;
}
}

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;
}
}
}

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

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

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?

Comment hidden because of low score. Click to expand.
0
of 0 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.

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)

Name:

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

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

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