Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

Try this out...

int start=0, end=0;

for(i=0; i<arrary.lenght; i++)
{
	for(j=i+1; i<arrary.lenght; j++)

	{
		if (a[i]+a[j] = number)
		{
			if (a[i] > a[j])
			{
				if (a[j] - a[i]) > (end -start)
				{
					start = a[i]
					end = a[j]
				} 		
			}
			Else
			{		
				if (a[i] - a[j]) > (end -start)
				{
					start = a[j]
					end = a[i]
				} 		
			}	
			
		}
	}

}

CWL("Pair is {{0}, {1}}" , start, end) ;

- Jai December 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

def Find(List, sum):
    l = len(List)
    for d in range(1,l):
        for i in range(l-d):
            if(List[i]+List[i+d]==sum):
                print List[i],List[i+d]
                return

- Aerofoil.kite December 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static Tuple<int, int> FindPair(int[] int_array, int num)
        {
            int first = -1, second = -1;
            int pair_diff = int_array.Count() + 1;
            for (int i = 0; i < int_array.Count(); i++)
            {
                for (int j = i + 1; j < int_array.Count(); j++)
                {
                    if ((int_array[i] + int_array[j]) == num)
                    {
                        if ((j - i) < pair_diff)
                        {
                            first = int_array[i];
                            second = int_array[j];

                            pair_diff = j - i;
                        }
                    }
                }
            }

            Tuple<int, int> pair = Tuple.Create(first, second);

            return pair;

        }

- Sohaib December 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You solution have problem, in Best case scenario, also run all possible combination. Because you have just try to find all solutions. Best way to go greedy approach and just check distance 1 options first and if find any combination with distance 1 than stop further process and print answer. If not than go for distance 2 options. This way, your complexity will be low in best case scenario and worst case, it will run all pairs.

My Solution:

public static void FindPair(int[] input, int num)
        {
            int distance = 1;
            bool isFound = false;
            // Check all options with distance 1 and go further
            for (distance = 1; distance < input.Length; distance++)
            {
                for (int i = 0; i < input.Length; i++)
                {
                    if (i + distance < input.Length)
                    {
                        if (input[i] + input[i + distance] == 10)
                        {
                            isFound = true;
                            Console.WriteLine(string.Format("({0},{1})", input[i], input[i + distance]));
                            break;
                        }
                    }
                }
                if (isFound)
                    break;
            }
        }

- Rajesh Kumar December 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a hashtable to store the index of each element. As we iterate through the array, check if the target (10 - current element) is already in the hashtable. If so, we get the value (target's position) and store this pair as the potential result if its distance is shorter than the existing pair (if any). Note that we want to overwrite any existing value with the newer index.

class ClosestPair {

	static int[] closestPair(int[] arr, int n) {
		int[] closest = new int[] {0, Integer.MAX_VALUE};
		HashMap<Integer, Integer> seen = new HashMap<Integer, Integer>();
		for(int i=0; i<arr.length; i++) {
			int target = n - arr[i];
			if(seen.containsKey(target)) {
				int pos = seen.get(target);
				if(i-pos < closest[1]-closest[0]) {
					closest[1] = i;
					closest[0] = pos;
				}
			}
			seen.put(arr[i], i);
		}
		return closest;
	}

	public static void main(String[] args) {
		int[] arr = new int[args.length];
		for(int i=0; i<args.length; i++) {
			arr[i] = Integer.parseInt(args[i]);
		}
		int[] pair = closestPair(arr, 10);
		if(pair[1] == Integer.MAX_VALUE)
			System.out.println("No such pair");
		else System.out.println("" + arr[pair[0]] + " " + arr[pair[1]]);
	}
}

- Sunny December 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Same idea in Python. Feels much cleaner.

def closest_pair(arr, n):
	closest = None
	seen = dict()
	for index, value in enumerate(arr):
		target = n - value
		if target in seen:
			pos = seen[target]
			if(closest == None or index-pos < closest[1]-closest[0]):
				closest = (pos, index)
		seen[value] = index;
	return None if closest == None else (arr[closest[0]], arr[closest[1]])

print closest_pair([1, 7, 5, 3, 9], 10)

- Sunny December 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can do O(n^2) with iterating two loops or O(n) with a hash

O(n^2)
public static Pair<int, int> ClosestPair(int[] input, int num) {
if(input.length < 2) return null;

int firstIndex = -1, secondIndex = - 1, closest_distance = Integer.MAX_VALUE;
for(int i = 0; i < input.length - 1; i++) {
for(int j = i+1; j < input.length; j++) {
int distance = j-i;
if(input[i] + input[j] == num && distance < closest_distance) {
firstIndex = i;
secondIndex = j;
closest_distance = distance;
}
}
}

if(firstIndex == -1 || secondIndex == -1)
return null;

return new Pair(input[firstIndex], input[secondIndex]);
}

O(n)
public static Pair<int, int> ClosestPair(int[] input, int num) {
if(input.length < 2) return null;

//Key is an integer in input. Its value is its index
HashMap<Integer, Integer> inputIndexMap = new HashMap<Integer, Integer>();

int firstIndex = -1, secondIndex = -1, closest_distance = Integer.MAX_VALUE;

for(int i = 0; i < input.length; i++) {
int correspondingIndex = inputIndexMap.get(num - input[i]);
if(correspondingIndex != null && i - correspondingIndex < closest_distance) {
firstIndex = i;
secondIndex = correspondingIndex;
closestDistance = i - correspondingIndex;
}

//We only put after the check because perhaps duplicate values is
//our solution so we don't want to overwrite too soon.
//ex. input[i] == input[j] and input[i] + input[j] == num
HashMap.put(input[i], i);
}

if(firstIndex == -1 || secondIndex == -1)
return null;

return new Pair(input[firstIndex], input[secondIndex]);
}

- rheaka December 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The key thing is the 'CLOSEST' pair consideration which I've taken to mean the pair with a sum that is numerically closest to the desired value. A hash table does not make it so easy to find the closest pair since it looks for exact values. Arcane Java constructs could possibly be used like NavigableMap constructs, but those will take more space to fully compute.

If you sort the array ( O(n log n) ), then you should be able to iterate through with runners from the front and the back in (O(n) ). Therefore, you should be able to solve with O(n log n) with no extra space.

public static int[] getClosestSumPair(int[] arr, int k){
	if(arr == null){
		throw new NullPointerException();
	}
	if(arr.length < 2){
		throw new IllegalArgumentException();
	}

	//sort the array
	Arrays.sort(arr);

	int lo = 0;
	int hi = arr.length -1;
	int[] best = new int[]{arr[lo], arr[hi]};
	int actualSum = best[lo] + best[hi];
	int actualSumDistance = Math.abs(k - actualSum );
	int bestSumDist = actualSumDistance;
	while(lo < hi - 1){
		if(actualSum > k){
			hi--;
		}
		else if(actualSum < k){
			lo++;
		}
		else{
			return best;
		}
		actualSum = arr[lo] + arr[hi];
		actualSumDistance = Math.abs(k -actualSum);
		if(actualSumDistance < bestSumDist){
			best[0] = arr[lo];
			best[hi] = arr[hi];
			bestSumDist= actualSumDistance ;
		}
	}
	return best;
}

//tests
public static void test_getClosestSumPair_null(){
	boolean foundException = false;
	try{
		getClosestSumPair(null, 0);
	}
	catch(Exception e){
		foundException = e instanceof NullPointerException;
	}

	assert(foundException);
}

public static void test_getClosestSumPair_1elmt(){
	boolean foundException = false;
	try{
		getClosestSumPair(new int[]{ 1 }, 0){
	}
	catch(Exception e){
		foundException = e instanceof IllegalArgumentException;
	}
	
	assert(foundException);
}

public static void test_getClosestSumPair_exact(){
	int[] pair = getClosestSumPair(new int[]{1, 7, 5, 3, 9}, 10);
	assert(pair != null);
	assert(pair[0] = 1);
	assert(pair[1] = 9);
}

- zortlord December 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a different solution than my first. This one interprets 'closest' to mean the pair with the closest proximity within the array. It operates in worst case O(n^2) but it's actual performance is significantly faster in most cases with O(n) memory using a HashMap:

public static int[] getClosestSumPair(int[] arr, int k){
	//map the val to positions within the array for all values
	HashMap<Integer, Collection<Integer>> valToIndexMap = new HashMap<Integer, Collection<Integer>>();
	for(int i = 0; i < arr.length; i++){
		int val = arr[i];
		Collection<Integer> col : valToIndexMap.get(val);
		if(col == null){
			col = new ArrayList<Integer>();
			valToIndexMap.put(val, col);
		}
		col.add(i);
	}

	//now construct viable pairs
	int bestDist = Integer.MAX_VALUE;
	int[] bestPair = null;
	for(int i1 = 0; i1 < arr.length; i1++){
		int val1 = arr[i1];
		//find what the other value needs to be for k = val1 + val2
		int val2 = k - val1;
		Collection<Integer> col : valToIndexMap.get(val1);
		//if the other value exists, then check it
		if(col != null){
			//for every location at which this value exists in the array
			for(Integer i2: col){
				//don't consider cases where the same value might be used twice
				if(i1 == i2){
					continue;
				}
				//if the distance between these two indices is the new best, capture it
				int dist = Math.abs(i1 - i2);
				if(dist < bestDist){
					bestDist = dist;
					bestPair = new int[]{val1, val2};
				}
			}
		}
	}
	return bestPair;
}

- zortlord December 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Objective C solution
    int sumToBeFound = 10;
    NSArray *numbersArrayGiven = @[@(1),@(7),@(5),@(3),@(9)];
    NSMutableDictionary *finalPair = [NSMutableDictionary new];
    [numbersArrayGiven enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
        for (NSUInteger k = idx+1; k<numbersArrayGiven.count; k++) {
            if ([obj integerValue]+[numbersArrayGiven[k] integerValue] == sumToBeFound) {
                NSMutableArray *pairOfNumbers = [NSMutableArray new];
                [pairOfNumbers addObject:obj];
                [pairOfNumbers addObject:numbersArrayGiven[k]];
                finalPair[@(k-idx)] = pairOfNumbers;
            }
        }
    }];
    NSInteger leastDistance = sumToBeFound;
    for (int i = 0; i<finalPair.allKeys.count; i++) {
        if ([finalPair.allKeys[i] integerValue]<leastDistance) {
            leastDistance = [finalPair.allKeys[i] integerValue];
        }
    }
    NSArray *leastArray = finalPair[@(leastDistance)];
    NSLog(@"leastArray :%@",leastArray.description);

- deepak.hebbar December 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public String findClosestPair(int[] numArray,int number){
		int minDiff=-1;
		boolean pairFlag=false;
		String closestPossiblePair="";
		for(int i=0;i<numArray.length-1;i++){
			for(int j=i+1;j<numArray.length;j++){
				if(numArray[i]+numArray[j]==number){
					pairFlag=true;
					int k=numArray[i]-numArray[j];
					if(k < 0){k=-(k);}
					if(k<minDiff||minDiff==-1){
						minDiff=k;
						closestPossiblePair=numArray[i]+","+numArray[j];
					}
					
				}
			}
		}
		if(pairFlag==false){closestPossiblePair="no pairs are there";}
		return closestPossiblePair;
	}

- gsrinivas10 December 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution O(nlogn)

void findClosestPair() {
    int N = 50;
    int arr[] = {4,4,22,6,32,8,2,12};
    
    list<int>::iterator it;
    list<int>::reverse_iterator rit;
    list<int> l (arr, arr + sizeof(arr)/sizeof(int));
    l.sort();
    it = l.begin();
    rit = l.rbegin();
    unsigned int diff = abs(*it + *rit - N);
    int l1,l2;
    for(;it!=l.end(),rit!=l.rend();) {
        cout << "Iteration: " << *it << " " << *rit << " Diff: " << diff << endl;
        if(*it>=*rit) {
            cout << "Result: " << l1 << " " << l2 << endl;
            return;
        }
            
        unsigned int d;
        if(*it+*rit == N) {
            cout << "Result: " << *it  << " " << *rit << endl;
            return;
        } else if (*it+*rit < N) {
            d= abs(*rit + *it - N);
            if(d>diff) {
                cout << "Result: " << l1 << " " << l2 << endl;
                return;
            }
            l1=*it;
            l2=*rit;
            it++;
        } else {
            d = abs(*rit + *it - N);
            if(d>diff) {
                cout << "Result: " << l1 << " " << l2 << endl;
                return;
            }
            l1=*it;
            l2=*rit;
            rit++;
        }
        diff = d;        
    }
}

- D December 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This solution is clean and simple.

public static int[] solve(int[] array, int size, int num) throws Exception {
	for (int distance = 1; distance < size; distance++) {
		for (int j = 0; j < size - distance; j++) {
			if (array[j] + array[j + distance] == num) {
				int[] pair = {array[j], array[j + distance]};
				return pair;
			}
		}
	}
	throw new Exception("No pairs have that sum.");
}

- avigailf December 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

if (array[j] + array[j + distance] == num)

You might want to check the question again. We are trying to find closest sum here. Exact sum is great but if you cannot find exact sum pair, return the closest sum pair.

- XiaoPiGu December 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks for the feedback. How do you know that from the question? If that was what the question intended, wouldn't it have specified?

- avigailf December 09, 2014 | Flag


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