Adobe Interview Question for Software Development Managers


Country: India




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

Step 1: Sort the array O(nlogn)
Step 2: For each element x in the sorted array, find the complement element x+d using binary search. Before attempting step 2, ensure that the in sorted array last element value - first element value >= d.
For step 2, the worst case would be O(nlogn)

- to_google. April 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

You don't need to do binary search.

Once the array is sorted. You can have two pointers L and R.

Initially L is pointing to the smallest element, and R to the second smallest.

If A[R] - A[L] < d, increment L.
If A[R] - A[L] > d, increment R.
if A[R] - A[L] = d, found one pair, output it and increment both L and R.

- Anonymous April 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Note: The last step assumes integers are distinct.

If they are not, when you find a pair, you need to increment L till A[L] changes and R till A[R] changes, outputting all the pairs till then.

- Anonymous April 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

And the increment L and R has been reversed.

- Anonymous April 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

We can do this in O(n) time using a Hash Map. Iterate through the array and add it to hash map. Take the first number substract d from it and search the remaining number in the HashMap do the same for all elements in the HashMap.

- Free Bird April 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In the worst case that is Omega(n^2), but it is on average O(n).

If using only comparisons, taking d = 0, makes it equivalent to Element Distinctness Problem which has known Omega(n log n) lower bounds.

- Anonymous April 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Proposed hash map solution is innovative. Thanks!
The O(N^2) is also very interesting....did not get this initially but realized that this happens in the case where all the "n" elements hash onto the same index. Thanks as well!

- Anonymous April 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How can the worst case be O(n^2). You iterate once to put the array elements in HashMap which is of O(n). For the second time when we iterate through the array once again this time the only difference is that each time we are at the ith element we substract the d from ith element and search it in HashMap which is a O(1) operation. Also this second iteration takes O(n). So in worst case it is O(n)+O(n) = 2O(n)=O(n). I hope this helps. :)

- Free Bird April 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@free bird, remember one thing with Hashing technique.

most of the problems we can solve in O(n) with Hashing , this only in best case situation( I/P size almost equal to Hashmap size, and input elements are distinct).

in worst case ( hash map size is much smaller than I/P size), hash does not help much , it gives O(n2).

in this problem, assume i/p size is 1000 elements and hash map size is 10 . then Hash map does not solve the problem in O(n).

- siva.sai.2020 April 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

LOL @ freebird with the "I hope this helps" comment.

- Anonymous April 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are right @sai. But what you are talking theoritical. Normally in interview questions we do not assume worst case for HashMaps that is the reason we are able to do questions like find two numbers in an unsorted array that sum to k in O(n) time else again it would be O(n^2). So assuming this i gave the logic for the above question.

- Free Bird April 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

LOL @FreeBird again. O(nlogn) is possible to find two numbers that sum to k.

- Anonymous April 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I know but as far as i kno O(n) faster than O(nlogn). LOL.

- Free Bird April 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

LOL @freebird: "Without hashing it would be O(n^2)".

Second, not really. O(n) is not always preferred, practically speaking, Classic example: selection.

- Anonymous April 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Freebird is absolutely right

- lazywiz April 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Bit.Varun. Sorry. The first comment by Anonymous is absolutely right. Worst case Omega(n^2), Average case O(n) and a mention of Element Distinctness problem for a known lower bound in case only comparisons are used.

The subsequent comments by FreeBird only show his ignorance, and you have now added yours to the mix.

FreeBird was making wrong comments and misguiding people and being condescending: "I hope that helps". He deserves the LOL comments that try to correct his mistakes.

btw, It should not matter who is making those comments. Judge the comments on their own merits.

If you find some disagreement, take it as an opportunity to learn. Rather than attacking the person, try to attack the comments with logical arguments.

- iit.Tarun April 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@FreeBird: There is one problem in your algo, it will report each pair twice, for e.g

int a[] = {1, 2, 3, 4} and d = 5

It will report (1, 4) and (4, 1) both and similarly (2, 3) and (3, 2)

- ravigupta May 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

If you want to find X and Y s.t. X-Y = 3, => X = Y+3
Simply hash numbers in the array and look for a number that's 3 more than itself. Solved O(n)

- Ashish Kaila April 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes. Let 'd' is the difference.
Insert the first element in the array.
Then for all the elements, y, check whether (y+d) is present in the array. If yes print (x,y)
and also search for abs(y-3) in the hash, if present print (x,y)

- Psycho September 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I love the 'd' since I have no idea what it is.

- Leon April 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Isn't it obvious? d is an input, along with the array.

- Anonymous April 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void main()
{
int arr[10]= {1,2,4,5,7,6,3,8,9,0}, z=9;
int hash[10]= {0,0,0,0,0,0,0,0,0,0};
while(z>=0)
{
hash[arr[z]]= arr[z];
z--;
}

for(z=0;z<=9;z++)
{
if (arr[z]+3 == hash[arr[z]+3])
printf("(%d,%d)\n",arr[z],hash[arr[z]+3]);

}

return;
}

- Anonymous April 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming d=3

void main()
{
int arr[10]= {1,2,4,5,7,6,3,8,9,0}, z=9;
int hash[10]= {0,0,0,0,0,0,0,0,0,0};
while(z>=0)
{
hash[arr[z]]= arr[z];
z--;
}

for(z=0;z<=9;z++)
{
if (arr[z]+3 == hash[arr[z]+3])
printf("(%d,%d)\n",arr[z],hash[arr[z]+3]);

}

return;
}

- Anonymous April 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(n)

- Anonymous April 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashMap;

public class target 
{
    public static void hash(int []a,int sum)
    {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

        int i;

        for (i = 0; i < a.length; ++i) 
            map.put(a[i], sum-a[i]);

        for (i = 0; i < a.length; ++i) 
            if(map.containsValue(a[i]) && map.get(a[i])!=null)
             {
                System.out.println("("+a[i]+","+map.get(a[i])+")");
                map.remove(a[i]);
             }
    }

public static void main(String[] args)
{
    int []a={1, 2, 13, 34, 9, 3, 23, 45, 8, 7, 8, 3, 2};
    hash(a,11);
}
}

- @ingenious April 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use hashing: O(n) time and in single iteration - Take the first number from the array, subtract d from it and search the remaining number in the hash table, if found, we got a pair otherwise store the element a[i] in the hash table. Do this for all the elements in the array.

- ravigupta May 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In these types of questions you are explicitly asked not to use any complex inbuilt data structure. Hence do not use HashSet/HashMap.

Also, these questions require some limited amount of extra memory usage.

The best answer i thought has already been given by 'to google' as first reply.

- rai.kaushal May 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple O(n) Solution .

// Type your C++ code and click the "Run Code" button!
// Your code output will be shown on the left.
// Click on the "Show input" button to enter input data to be read (from stdin).

#include <iostream.h>

void find(int a[], int size, int d) {
int n =0;
for(int i=0;i<size;i++) {
n |= 1<< a[i]-1;
}

for(int i =0;i<size;i++) {
if (n & (1<<(a[i]-d-1))) {
cout << "a= " << a[i] << "b= " <<a[i]-d << endl;;
}
}
}


int main() {
int a[] = {4,6,1,3};
find(a, sizeof(a)/sizeof(a[0]), 2);
return 0;
}

- Nishant Pandey August 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

LOL.

- Anonymous August 26, 2013 | Flag


Add a Comment
Name:

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

Books

is a comprehensive book on 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