## Directi Interview Question Software Engineer / Developers

• 0

Given 2 sorted arrays A and B, sorted in increasing order, find the minimum value of |A[i]-B[j]| for all i belonging to A and all j belonging to B. Preffered order O(M+n) in the worst case. m being size of array A and n being size of array B.

Then he extended the same question to n sorted arrays with k elements each. I was required to find the minimum range in which the values fall.

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

take 2 pointers both pointing to the starting of the array A and B respectively
Now find the difference.
Move the pointer pointing to the lesser of the 2 ahead
Let say
A = 3,10,20
B = 2,5,15

first step 3-2 = 1
Now move pointer B to 5
5-3 = 2.
Now move pointer A to 10 and so on...

The idea is move that pointer which is pointing to the lesser value of the 2 so as to reduce the diff between numbers.

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

For the first part, find the min of A and max of A, and similarly min B and max B. Answer would be min(abs(minA-maxB),abs(maxA-minB))

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

You did not cover the full problem.
You solution is right only when the arrays do not overlap on the number line. If they do, you are busted.
try with this A={1,3,4,5} and B={-10, 3,10} . Getting me ? you can choose to add logic in overlap case.

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

do merge both array then find minimum consecutive difference in that merge array having time complexity 2*(m+n) or o(m+n)

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

Wrong algo . Thing again buddy .
I give you input like A={1,3,5} and B={8,9,10}.
How can you assume that consecutive elements in the final merged array will be from A and B, they can be from A only or B only.

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

min <- A[0]-B[0] // Assuming non negative number in the array
i,j <- start of array
while not end of array
do
temp <- A[i]-B[j]
if (temp < min)
min <- temp
if temp < 0
i++
else
j++
end while

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

Merge both the arrays O(m+n)

Differ 2 consecutive numbers(Keep checking both do not belong to same array). Track minimum.

We can use different Data Structure to capture array information.

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

whats the use of a incomplete answer?

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

Can somebody explain the remaining question :
Then he extended the same question to n sorted arrays with k elements each. I was required to find the minimum range in which the values fall.

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

Do something similar to merge operation :

For ex:
A = [1, 3, 5]
B = [8, 9, 10]

i = 0
j = 0

mindiff = INT_MAX;
while(i < m && j < n)
{

if(mindiff > |a[i] - b[j]|)
mindiff = |a[i] - b[j]|;

if(a[i] < b[j])
i++;
else
j++;
}

print mindiff;

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.