## Directi Interview Question Software Engineer / Developers

- 0of 0 votes
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.

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

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

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.

take 2 pointers both pointing to the starting of the array A and B respectively

- DashDash on October 05, 2010 Edit | Flag ReplyNow 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.