Directi Interview Question Software Engineer / Developers

  • directi-interview-questions
    0
    of 0 votes
    10
    Answers

    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.

    - game on January 07, 2010 Report Duplicate | Flag
    Directi Software Engineer / Developer



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.

- DashDash on October 05, 2010 | Flag Reply
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))

- Anonymous on January 14, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- sangeet on June 22, 2010 | Flag
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)

- pavan gupta on February 03, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- sangeet on June 22, 2010 | Flag
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

- Anup S M on August 19, 2010 | Flag Reply
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.

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

whats the use of a incomplete answer?

- kcaj on July 05, 2011 | Flag
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.

- Ashish on July 28, 2011 | Flag Reply
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;

- jackass on October 27, 2011 | 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