Adobe Interview Question
Software Development ManagersCountry: India
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.
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.
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.
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.
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!
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, 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).
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.
LOL @freebird: "Without hashing it would be O(n^2)".
Second, not really. O(n) is not always preferred, practically speaking, Classic example: selection.
@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.
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)
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;
}
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);
}
}
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;
}
Step 1: Sort the array O(nlogn)
- to_google. April 23, 2012Step 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)