## Adobe Interview Question for Software Development Managers

• 0

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)

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.

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.

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

And the increment L and R has been reversed.

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.

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

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.

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

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!

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

@Freebird is absolutely right

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

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

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

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

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)

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

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)

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.

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

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

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

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

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

O(n)

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

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.

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.

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

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

LOL.

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.

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