CGI-AMS Interview Question
Senior Software Development EngineersCountry: United States
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
#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;
}
#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;
}
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++;
}
}
}
}
}
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++;
}
}
}
}
}
/** * 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--; } } }
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--; } } }
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.
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 ? .
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
};
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);
}
}
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--;
}
}
}
- Anonymous October 14, 2013