## Adobe Interview Question for Developer Program Engineers

Country: United States

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

``````#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <iterator>

using namespace std;

int main ()
{
vector<int> A = { 1,5, 3, 4, 2, 9, 7 };

int K = 2;

sort(A.begin(), A.end());

int count = 0;
auto i = A.begin();
auto j = next(i, 1);

while(j != A.end()) {
int n = *i + K;

auto r = equal_range (j, A.end(), n);

j = r.first;

while (r.first != r.second) {
cout << "(" << *i << ", " << *r.first << ")" << endl;
count++;
r.first++;
}

++i;
}
cout << "total pairs = " << count << endl;
return 0;
}
/***********************************************************
output:

(1, 3)
(2, 4)
(3, 5)
(5, 7)
(7, 9)
total pairs = 5
***********************************************************/``````

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

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!

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

haha, if all numbers are distinct, then ...

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

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:

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.

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

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

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

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;
i=0
while(i<n) {
i++;
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``````

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

``````/**
*
*/
package com.practice;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;

/**
*
*/
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<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);

}

}``````

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

This can be solved in O(n) by using a hash map.
Hash function = (value - k)
each hash bucket maintains 2 things:
1. flag = weather a number is found whose value is same as bucket value
2. list of numbers hashed in that bucket

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

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

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

hackerrank.com/challenges/pairs

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

hackerrank.com/challenges/pairs

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

Order n Solution :
Store the numbers in hash.
Then if (k+n) exists in Hash then count++

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

Why is the binary search approach not suggested? Anything wrong with it?
1. Sort the elements.
2. Iterate through the sorted list.
3. For each number "num", binary search for num+K.

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.