## Interview Question

Country: United States
Interview Type: Phone Interview

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

``````public static int getDiffPair(int a[] , int diff){
HashMap<Integer,Integer> hashMap = new HashMap<Integer,Integer>();

int count = 1;
for(int i = 0;i<a.length;i++){
if(hashMap.containsKey(a[i])){
count = hashMap.get(a[i]);
hashMap.put(a[i], ++count);
}else{
hashMap.put(a[i], 1);
}
}
count = 0;
for(int j = 0;j<a.length;j++){
if(hashMap.containsKey(a[j]+diff)){
count+=hashMap.get(a[j]+diff);
}
}
return count;
}``````

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

It covers the [x, x, .... ], K>0 case

but I think it misses the [x, x, ... ], K=0 case.

Maybe this:

``````public static int getDiffPair(int a[] , int diff){
HashMap<Integer,Integer> hashMap = new HashMap<Integer,Integer>();

int count = 1;
for(int i = 0;i<a.length;i++){
if(hashMap.containsKey(a[i])){
count = hashMap.get(a[i]);
hashMap.put(a[i], ++count);
}else{
hashMap.put(a[i], 1);
}
}
count = 0;
for(int j = 0;j<a.length;j++){
if(hashMap.containsKey(a[j]+diff)){
count+=hashMap.get(a[j]+diff) - (!diff ?1:0); //changed
}
}
return count;
}``````

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

First of all, what I would do, was to use a

``HashMap<Integer, LinkedList<Integer>> hashMap;``

So that I could also store the location of other index. If you just need the count, then use hashMap.get(i).size(). This way you can also identify the pairs, as well as the number of repetitions.

However, the array in your example is sorted. In such a case, you can actually solve it in O(1) space and O(N + M) time where "N" is the length of input, and "M" is the number of pairs of indices with a difference equal to "K". I used the idea from a O(1) space solution for 3-sum problem (google it).

Keep two pointers pos_1 <= pos_2. If array is sorted ascendingly, then array[pos_2] >= array[pos_1].

1- Check cmp = array[pos_2] - array[pos_1].
2- If "cmp" is smaller than "k", the desired difference, increase pos_2 to obtain a larger difference. Else, decrease pos_1.
3- If cmp == 0, then you already found a pair [pos_1, pos_2]. All you need to do is to resolve the repeated element case. For that, increase pos_1 until the value changes. Do the same for pos_2. Then generate all the possible tuples (pos_1, pos_2) for the ranges you found.

Here is the java code.

``````public static void main(String[] args) {
int[] arr = {1, 1, 5, 5, 5, 6, 9, 16, 27};
listKdiff(arr, 4);
}

public static void listKdiff(int[] arr, int k) {
int pos_1 = 0;
int pos_2 = 0;
while(pos_2 < arr.length) {
int cmp = arr[pos_2] - arr[pos_1];
if (cmp < k) {
pos_2++;
}
else if (cmp > k) {
pos_1++;
}
else {
// length of the subarrays of equal values starting from    pos_1 and pos_2

int len1 = 0, len2 = 0;
while (arr[pos_1 + len1] == arr[pos_1]) {
len1++;
}
while (arr[pos_2 + len2] == arr[pos_2]) {
len2++;
if (len2 + pos_2 == arr.length - 1) {
break;
}
}
// print all pairs of duplicates
for (int i = 0; i < len1; i++) {
int a = pos_1 + i;
for (int j = 0; j < len2; j++) {
int b = pos_2 + j;
System.out.println("[" + a + ", " + b + "]");
}
}
pos_1 = pos_1 + len1;
pos_2 = pos_2 + len2;
}
}
}``````

This is the output I got. The first 6 pairs corresponds to combinations of (1, 5) and the last three are combinations of (5, 9) (I printed the indices):

``````[0, 2]
[0, 3]
[0, 4]
[1, 2]
[1, 3]
[1, 4]
[2, 6]
[3, 6]
[4, 6]``````

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

We all spend time working on these types of problems. The reason is to learn and give feedback. While everyone is entitled to down/up voting whatever they want, it is best if a feedback is provided. How on earth would you downvote a correct solution? Unless you found and error and would like to share, in such a case, your efforts would be much appreciated.

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

1) Format your code correctly
2) Name your variables properly
3) Comment your code unless it's obvious what you are doing
4) Explain your code (you talk briefly of how you would solve it for unsorted arrays, but then you put code for sorted arrays without any explanation)
5) Explain runtime of your code
6) Generally, save the time of readers (don't worry about your time)

And it wasn't me who downvoted you.

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

Fair enough. I will add explanations.

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

The problem only required you to find how many pairs there were (i.e. a count) so no need to print out pairs :)

Some people are being rough on here on my question. It's not so difficult I think as I already got an O(2n) solution which is fine for interview purposes.

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

Cool idea. +1

You saved space O(1) by sacrificing time O(n^2). It is a legitimate, possible use case.

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

Thanks.

Actually, it is not O(N^2) as long as the number of pairs of indices is not O(N^2). In each iteration of the while loop, I increase either pos_1 or pos_2. So at most, there will be 2N iterations if there are no repeated elements.
It can be best said that the running time is O(N + M) where M is the number of pairs. In the example above, M = 9.

This idea is from 3-SUM problem. But only works on sorted arrays.

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

We still call it quadratic.

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

It will be O(N) if we are not asked to list the pairs of indices.

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

Prove it Ehsan. Where is the code for the O(N) nonpair version?

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

Remove the nested for loop. Instead of making all pairs, simply add the following line

``count += len1 * len2;``

In the main while loop, in every iteration either pos_1 or pos_2 or both are increased by at least "1". So it will take at most "2N" iterations.
When printing the pairs, the reason you get O(N^2) is something like this:

``int[] arr = {1, 1, 1, 1, 5, 5, 5, 5, 5, 5}``

where there are "NxM" pairs to list (N = 4 and M = 6 in this example). But we if you only need the count, then simply add "N * M" to the count and increase pos_1 by N and pos_2 by M.

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

``````public static int getDiffPair(int a[] , int diff){
HashMap<Integer,Integer> hashMap = new HashMap<Integer,Integer>();

int count = 1;
for(int i = 0;i<a.length;i++){
if(hashMap.containsKey(a[i])){
count = hashMap.get(a[i]);
hashMap.put(a[i], ++count);
}else{
hashMap.put(a[i], 1);
}
}
count = 0;
for(int j = 0;j<a.length;j++){
if(hashMap.containsKey(a[j]+diff)){
count+=hashMap.get(a[j]+diff);
hashMap.put(a[i],0);
}
}
return count;
}``````

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

Oh, I figured out how to do it in two passes, but i'm still wondering if you can do it with only one.

``````public static int arrayPairDifference(int[] a, int k)
{
HashMap<Integer, Integer> hashMap = new HashMap<>();
int count = 0;
for (int i = 0; i < a.length; i++)
{
hashMap.put(i, a[i]);
}
for (int j = 0; j < a.length; j++)
{
if (hashMap.containsValue(a[j] + k))
{
count++;
}
}
return count;
}``````

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

The issue is that the array has duplicates in it.

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

Java doesn't have a "multiset" (I don't think) like C++ does, so the standard way is to simulate it with "Map<item type, int(for counting)>"

Instead of just inserting any item, you first check if it's in the Map, and if it is, increment the value(which is the count).

Comment hidden because of low score. Click to expand.
-2
of 2 vote

with duplication, the problem became quiet tricky.
There are couples of solutions for this, it all depends if we can change the original data, if we could use extra space, etc.
1) the safest way(no extra space, and easy to code) is that we use two-layer loop.
for ith element a[i], we check how many k-a[i] in the rest of subarray. No extra space, for small array, it should be the fast way, even it's time complexity is O(n).
2) if we could change the original input array, we could first sort the array(if it's not sorted), for each element a[i], we do binary search on subarray a[i+1]...a[n-1]. we need to do this twice, since we want to find how many k-a[i] in the subarray, we use adapted binary search algorithm to find the lowest index and highest index with the value of k-a[i], the time complexity will be O(nlg(n)), but it's error-prone. For example: a=[2 6 6 6 9], run this on array a.
3) use a extra hashmap, this is very tricky if there are duplicated elements, for example, for array: a=[2 2 2 2] and K=4, the resulting number of pairs should be 6. we could create a map, with the keys be element values, and values are the number of occurrences, when we scan through the array, for element a[i], first we need to decrement the value of hashMap[a[i]] by one, and then count how many k-a[i] there. otherwise, you will get 16 instead of 6 for the input array a=[2,2,2,2] and K=4. the time complexity for this algo is O(n).

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