## Adobe Interview Question

Developer Program Engineers**Country:**United States

Nice code!

Your algo is O(nlogn) time complexity: sorting O(nlogn) + O(n) lookups for "equal-range" * O(logn) for each lookup.

However, to print out all pairs, it may take O(n^2). For example: K = 20, A ={10,10,10,...10, 30,30,...30) with half of numbers are all 10, other half are all 30.

Cheers!

1. Take the set of numbers which are all unique, duplicate the set

2. From the duplicated list subtract the difference value (2) from each element

You get: 1 5 3 4 2 and -1 3 1 2 0

3. Do a set intersection of the original set and duplicated set

4. The count of elements in the intersection gives you the list of numbers where the difference between the 2 numbers == to the difference value you set

```
from sets import Set
listOfNumbers = Set([1, 5, 3, 4, 2, 7, 8, 100, 6])
duplicateSet = Set([])
difference = 2
for num in listOfNumbers:
duplicateSet.add(num - difference)
print len(listOfNumbers.intersection(duplicateSet))
```

Going through the list is O(n) and set intersection is

Average - O(min(len(s), len(t))

Worst - O(len(s) * len(t))

If they specify only positive integers you can skip inserting any number where number - difference < 0 and that will reduce the size of the duplicate set and make your intersection go a little faster.

Because K != 0 and all numbers are distinct, which means all (num - K) are different, we may use hashtable to fix the problem in nearly O(n) time.

Following is C++ code:

```
int howmanyPairWithDifference(vector<int>& v, int K)
{
unordered_set<int> hash;
int i, n = v.size(), total = 0;
for(i = 0; i < n; ++i) hash.insert(v[i] - K);
for(i = 0; i < n; ++i){
if(hash.count(v[i])) ++total;
}
return total;
}
```

The problem states that the solution has to read from stdin, so, I will use this to my advantage and do something like this

```
set<long>looking_for; /*set doesn't allow duplicates*/
List<Pair(long, llong) op;
n<-read_from_stdin();
k<-read_from_stdin();
i=0
while(i<n) {
i++;
num<-read_from_stdin();
p1=num+k;
p2=num-k;
if(!looking_for.insert(p1)) {
/*insert fails when we've found p1*/
looking_for.remove(p1);
op.insert(Pair(num, p1);
}
if(!looking_for.insert(p2)) {
/*insert fails when we've found p1*/
looking_for.remove(p2);
op.insert(Pair(p2,num);
}
}
/*here, we've finished reading input and
also found the output*/
print the long, long pairs in the op list
```

```
/**
*
*/
package com.practice;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
/**
* @author Sunny Yadav
*
*/
public class Solution {
/**
* @param args
*/
public static void main(String[] args) {
int n;
int k;
int count = 0;
@SuppressWarnings("resource")
Scanner in = new Scanner(System.in);
n = in.nextInt();
k = in.nextInt();
HashSet<Integer> list = new HashSet<>();
for(int i = 0; i < n ; i++) {
list.add(in.nextInt());
}
List<Integer> sortList = new ArrayList<Integer>(list);
for(int j = 0; j < sortList.size(); j++) {
for(int p = 1; p < sortList.size(); p++) {
if((sortList.get(p) - sortList.get(j)) == k) {
count++;
}
}
}
System.out.println(count);
}
}
```

Also the issue can be solve by using an extra space complexity of 0(N) and running time algorithm of 0(N) .

Use an array of size N-aN, traverse through the given array of elements and increment the no of occurences of each element in the list ,in the array aN.

Now traverse through the array aN, for every i th element find the i + k th element and calculate the no of pairs accordingly

- Westlake February 21, 2014