## CGI-AMS Interview Question for Senior Software Development Engineers

• 0

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

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

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

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

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

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

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..

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

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

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

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

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);
}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++;
}
}
}
}
}

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

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

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

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

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.

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

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 ? .

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

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

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

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

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++)
{
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);
}
}``````

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

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.