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

- Westlake February 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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!

- entri February 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- entri February 21, 2014 | Flag
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:
	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.

- s.shrinidhi February 21, 2014 | Flag Reply
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;
	}
	return total;
}

- uuuouou February 21, 2014 | Flag Reply
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;
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

- asdf February 23, 2014 | Flag Reply
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;

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

	}

}

- Sunny Yadav February 26, 2014 | Flag Reply
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

- nuaavaa February 28, 2014 | Flag Reply
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

- Satish Kumar March 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

hackerrank.com/challenges/pairs

- Anonymous June 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

hackerrank.com/challenges/pairs

- Anonymous June 10, 2014 | Flag Reply
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++

- Registered June 23, 2014 | Flag Reply
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.

- rohitjv July 26, 2014 | Flag Reply


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