CGI-AMS Interview Question for Senior Software Development Engineers


Country: United States




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

public class AllPairsSum {

	public static void main(String[] s) {
		AllPairsSum run = new AllPairsSum();
		run.printAllPairs(new int[] { 6, 5, 2, 1, 3, 4 }, 7);
	}

	private void printAllPairs(int[] arr, int target) {
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

		for (int i = 0; i < arr.length; i++) {
			int diff = target - arr[i];
			if (map.containsKey(diff)) {
				System.out.println(arr[i] + " " + (target - arr[i]));
			} else {
				map.put(arr[i], diff);
			}
		}
	}
}

- Anonymous October 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This wont work for 3 integers that sum up to 7. e.g. 1,2,4

- Anonymous November 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just to clarity: Is this to determine all PAIRS that sum to K as in the output example? Or all combinations (as in the question):

If input array is {1,2,3,4,5,6} and K is 7
then O/P should be
1 6
3 4
2 5
1 2 4

- Michael.J.Keating October 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is just not the pairs. 1 2 4 should also get printed when K is 7.

- Raj October 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I've ever been asked this question at Microsoft's interview

Please note: if our target is 8, and an array with {4, 4, 4, 4, 4, 4}, what should be output, and it is a good test case for your code..

- wwwwwwking October 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#define NUM 7

int main()
{
	int a[6] = {1,2,3,4,5,6};
	int i,j;
	for(i=0;i<6;i++)
	{
		for(j=i+1;j<6;j++)
		{
			if((a[i]+a[j]) == NUM)
				printf("%d\t%d\n",a[i],a[j]);
		}
	}
    return 0;
}

- sakthivel Sethu,Software Engineer ,Bangalore October 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wont work for 3 integers that sum up to 7. eg 1,2,4

- Anonymous November 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
using namespace std;

void OutpuPair(int *src, int length, int sum)
{
    int leftStart = 0;
    int leftEnd, rightStart;
    int rightEnd = length - 1;
    while (leftStart < rightEnd)
    {
        if (src[leftStart] + src[rightEnd] > sum) rightEnd--;
        else if (src[leftStart] + src[rightEnd] < sum) leftStart++;
        else
        {
            leftEnd = leftStart;
            while (leftEnd+1<length && src[leftEnd+1] == src[leftStart]) leftEnd++;
            rightStart = rightEnd;
            while (rightStart-1>=0 && src[rightStart-1] == src[rightEnd]) rightStart--;
            for (int i = leftStart; i <= leftEnd; ++i)
            {
                for (int j = rightStart; j <= rightEnd; ++j)
                {
                    if (i < j) 
                        cout << src[i] << " " << src[j] << endl;
                }
            }
            leftStart = leftEnd+1;
            rightEnd = rightStart-1;
        }
    }
}

int main()
{
    int arr[] = {4,4,4};
    OutpuPair(arr, sizeof(arr) / sizeof(int), 8);
    return 0;
}

- wwwwwwking October 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
import javax.swing.*;

/*public static void main(String args[])throws Exception
{
List ll=new ArrayList();
Scanner sc=new Scanner(System.in);
do
{
String str=sc.next();
if(str.compareTo("ext")==0)
{
System.out.println("\t\t\t\texit");
break;
}
System.out.println(str);
ll.add(str);
}while(sc.hasNextLine());

for(int i=ll.size()-1;i>=0;i--)
{
System.out.println(ll.get(i));
}
int f1=0,t1=0;
for(int i=0;i<100;i++)
{
if(i%3==0 && i%5==0)
{
System.out.println("FB");
continue;
}
else if(i%3==0)
{
System.out.println("T");
}
else if(i%5==0)
{
System.out.println("F");
}
else
{
System.out.println(i);
}
}
int a[],b[],i=0,x;
//a=new Integer[14];
//b=new Integer[14];
a[10]=new Integer();
sc=new Scanner(System.in);
while(sc.hasNext())
{
//a[i]=new Integer();
a[i++]=sc.nextInt();
}
int c=0;
for(int j=0;j<i;j++)
{
x=a[j];
for(int k=0;k<i;k++)
{
if(a[k]==x)
{
c++;
}
}
b[j]=c;
c=0;
}
System.out.println("The Output is ");
for(int kk=0;kk<i;kk++)
{
System.out.println(a[kk]+"=============="+b[kk]);
}
}*/

class first
{
public static void main(String args[])throws Exception
{
Scanner sc=new Scanner(System.in);
System.out.println("Enter size of array");
int n=sc.nextInt();
int[] a;
a=new int[n];
System.out.println("Enter Data");
for(int i=0;i<n;i++)
{
a[i]=sc.nextInt();
}
System.out.println("Enter a no which you want as sum");
int sum=sc.nextInt();
int count=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(a[i]+a[j]==sum)
{
if(a[i]==a[j]&& i==j)
continue;

System.out.println("Combination no "+count+"\t"+a[i]+"\t"+a[j]);
count++;
}
}
}
}
}

- Code Study October 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class first
{
public static void main(String args[])throws Exception
{
Scanner sc=new Scanner(System.in);
System.out.println("Enter size of array");
int n=sc.nextInt();
int[] a;
a=new int[n];
System.out.println("Enter Data");
for(int i=0;i<n;i++)
{
a[i]=sc.nextInt();
}
System.out.println("Enter a no which you want as sum");
int sum=sc.nextInt();
int count=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(a[i]+a[j]==sum)
{
if(a[i]==a[j]&& i==j)
continue;

System.out.println("Combination no "+count+"\t"+a[i]+"\t"+a[j]);
count++;
}
}
}
}
}

- Code Study October 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for(i=0;i<n-1;i++)
 {
  for(j=i+1;j<n;j++)
  {
    if(a[i]+a[j]==k)
 printf("\n%d %d",a[i],a[j]);
     }
   }

- Anonymous October 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**  * Print the pair here such that a[i]+a[j] = sum  *   * @param array : Sorting integer array.  * @param sum : int to check possible combination of its sum.  */

public void printPair(int[] array, int sum)	{				int length = array.length;		int i = 0, j = length - 1;				while (i < j) {			int number = sum - array[i];			if (array[j] == number) {				System.out.println(array[i] + " + " + array[j] + " = " + sum);				j--;			}else if (array[j] < number) {				i++;			}else {				j--;			}		}	}

- Manoj Sharma October 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void printPair(int[] array, int sum)	{				int length = array.length;		int i = 0, j = length - 1;				while (i < j) {			int number = sum - array[i];			if (array[j] == number) {				System.out.println(array[i] + " + " + array[j] + " = " + sum);				j--;			}else if (array[j] < number) {				i++;			}else {				j--;			}		}	}

- Manoj Sharma October 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I would treat it as a knapsack problem, where every number of the array is a weight and the limitation is the sum, then every time we get the sum we print the output. Using dynamic programming the solution could be n^2.

- joe kidd October 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If the input array is {1,2,3,4) and K is 6.
Then the possible sets are
1 2 3
2 4

I tried DP and was able to build the matrix as below.
------>sum
1 2 3 4 5 6 7 8 9 10
in
dex
1 1 0 0 0 0 0 0 0 0 0

2 1 1 1 0 0 0 0 0 0 0

3 1 1 1 1 1 1 0 0 0 0

4 1 1 1 1 1 1 1 1 1 1


How can I print the possible sets using the above matrix ? .

- Raj October 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Generally the DP approach, except finding the solution step, contain also a step of building a structure of optimal solution, that is skipped sometimes.

The matrix filling in this case looks like:

M[i][j] = if Weight[i] <= W then M[i - 1][W - Weight[i]] else M[i-1][j]

So you choose or the solution (i - 1), with the value K - (current value), or you choose the previous solution. You need to remember which way you choose. Then when finding the solution you need to iterate back using previously stored steps to rebuild the structure of solution.

I propose instead of having array of int, let's say

int M[N][K];

An array of structure (or pairs)

struct Cell{
int value;
struct Cell * prevCell; // or coordinates of the previous cell in the array
};

- joe kidd October 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

knapsack is classic NP-hard. You can't solve it in O(n^2)

- naiem October 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be solved using recursion fairly easily.
Here's a solution in C#

public static void SumCombinations(int[] nums, int target)
		{
			FindCombinations(nums, target, new List<int>(), 0, 0);
		}

		private static void FindCombinations(int[] nums, int target, List<int> currentComb, int start, int sum)
		{
			for (int i = start; i < nums.Length; i++)
			{
				currentComb.Add(nums[i]);
				int currentSum = sum + nums[i];
				if (currentSum == target)
				{
					currentComb.ForEach(k => Console.Write(k+", "));
					Console.WriteLine();
				}
				else if (currentSum < target)
				{
					FindCombinations(nums, target, currentComb, i + 1, currentSum);
				}
				currentComb.RemoveAt(currentComb.Count-1);
			}
		}

- Sam October 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is O(n) solution

/**
* Print all possible pair exist in sorted array, who's addition is equal to give integer number 'sum'.
* Print the pair here such that a[i]+a[j] = sum
*
* @param array : Sorting integer array.
* @param sum : integer to check possible combination of its sum.
* @Source : Expedia
* @Efficiency : O(n)
*/

public void printPair(int[] array, int sum)
	{
		
		int length = array.length;
		int i = 0, j = length - 1;
		
		while (i < j) {
			int number = sum - array[i];
			if (array[j] == number) {
				System.out.println(array[i] + " + " + array[j] + " = " + sum);
				j--;
			}else if (array[j] < number) {
				i++;
			}else {
				j--;
			}
		}
	}

- Manoj Sharma October 16, 2013 | 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