Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
this problem can be solved with recursion. here are the codes
import java.util.ArrayList;
import java.util.Arrays;
public class Test {
public static void main(String[] args){
int[] theArray={1,2,4,5,6,1,2,4,3,5,7,2,1};
ArrayList<ArrayList<Integer>> allpairs=getPairs(theArray,0,4);
System.out.println(allpairs.size());
for(ArrayList<Integer> pair:allpairs){
System.out.println(Arrays.toString(pair.toArray()));
}
}
public static ArrayList<ArrayList<Integer>> getPairs(int[] theArray, int start, int sum){
if(sum==0){
ArrayList<ArrayList<Integer>> pairs=new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> pair=new ArrayList<Integer>();
pairs.add(pair);
return pairs;
}
if(start>=theArray.length){
return null;
}
ArrayList<ArrayList<Integer>> pairs=new ArrayList<ArrayList<Integer>>();
//situation 1 include the start element;
ArrayList<ArrayList<Integer>> subpairs=getPairs(theArray,start+1,sum-theArray[start]);
if(subpairs!=null){
for(ArrayList<Integer> subpair:subpairs){
ArrayList<Integer> pair=new ArrayList<Integer>();
if(pair!=null){
pair.add(theArray[start]);
pair.addAll(subpair);
pairs.add(pair);
}
}
}
//situation 2 do not include the start element;
ArrayList<ArrayList<Integer>> otherpairs=getPairs(theArray,start+1,sum);
if(otherpairs!=null){
for(ArrayList<Integer> otherpair:otherpairs){
pairs.add(otherpair);
}
}
return pairs;
}
}
A "Pair" always contain 2 elements. I am not sure whether you want the set of all pairs (pairs of 2 elements ofcourse) or you want the set of sets (may contain 2 or more elements). Because the solution of first case i.e., finding pairs that sum up to a certain value is trivial and this problem can be solved in O(n^2). In fact it can be solved in O(n) using hash table.
Yes. Any pair.
- It's standard sub set sum problem. You can find in google. but I need software implementation.
@Suman: Use elements in the array as keys. In first pass, for all the keys, set value = 1 (or you may increment this value if you encounter the same no. again in the array). In the second pass for each element 'elt' in array check whether there exists a value for key = (sum-elt). If there is one value then output 'elt' and "sum-elt" else move ahead. A little care must be taken in case of duplicates, still the logic remains the same. However, as I have mentioned above, this solution is good only if we want pairs of 2 elements. If we want a subset whose sum is equal to given value, we'll have to use dynamic programming.
hey..i can tell u the logic that works out for o(n) complexity..
and also assumption here is that pair of 2 elements((1,2)(0,3)..) is the output and input array is sorted
-->take two pointers where one starts from the beginning and other starts from the last element of the array
--> check sum of first and last pointers pointing elements sum if it is equal then print pair of element
--> else move the first pointer to next element and repeat the second statement
and here if u find the sum in the second statement then move the last pointer towards the first pointer and repeat the logic
hope this helps and this algorithm complexity is o(n)
if in output looking more than 2 elements(sets) then
- create a[2][3] array
- scan the integer array (only one pass is required) to get all 1,2 and 3 in integer array(input array). Set a[0][1],a[1][1] and a[2][1] to respective number of 1, 2 and 3 in input array.
- Do while loop for a[2][3] array.
if (a[2][1]>0 && a[0][1] >0) /* To print {3,1}*/
{
print(3,1);
--a[2][1];
--a[0][1];
}
if (a[1][1]>0 && a[0][1] >0) /* To print {1,2,1}*/
{
print(1,2,1);
--a[1][1];
a[0][1] = a[0][1] -2;
}
if (a[1][1]>1 ) /* To print {2,2}*/
{
print(2,2);
a[1][1] = a[1][1] -2;
}
if (a[0][1]>1 ) /* To print {1,1,1,1}*/
{
print(1,1,1,1);
a[0][1] = a[0][1] -4;
}
This will fail if input is {1,2,4,5,6,2,2,4,3,5,7,2,2} ie 1,2,1 case is still printed while it is not possible. BUG! You should rather compare the number of occurences of the numbers. I have tried to correct it somewhat.
Also, you always use a[][1] so i guess you dont need a 2d array!
Further, you dont need to decrement the a[].
I believe it should be:
int num[] = {1,2,4,5,6,2,2,4,3,5,7,2,2};
int a[3]={0,0,0};
int i;
for(i=0; i<13; i++) {
if(num[i]<4 && num[i]>0)
a[num[i]-1]=a[num[i]-1]+1;
if (a[2] >0 && a[0] >0) /* To print {3,1}*/
printf("\n3,1");
if (a[1] >0 && a[0] >1) /* To print {1,2,1}*/
printf("\n1,2,1");
if (a [1]>1 ) /* To print {2,2}*/
printf("\n2,2");
if (a[0] >3 ) /* To print {1,1,1,1}*/
printf("\n1,1,1,1");
this answer doesn't match the expectation of this program well. This is a N-Subset problem, the number can be used repeatedly in different sub-sets.
Say,
input : {1,2,4,5,6,1,2,4,3,5,7,2,1} only three '2'
output : {1,1,2}, {2,2}, {3,1}, {1,2,1}... with four '2'.
I have a stupid solution, just calculate all the possible combinations first, then just track each possibility if this combination can be fulfilled.
As far as I know, this problem is one of the well known NP-Complete problems named "Subset-Sum", how can you solve it in O(NlgN). Note that the question does not only ask about tuples, it is a different problem which can be solved using the binary search logic.
Below is a program, I have written in C# that will solve this in exponential time (brute force through recursion). It would be helpful, if someone could think of how to memonize it:
// Wrapper around SubsetSum method
public static void SubsetSum(int[] arr, int sum)
{
SubsetSum(arr, 0, 0, sum, new Stack<int>());
}
private static void SubsetSum(int[] arr, int i, int sumSoFar, int sum, Stack<int> parts)
{
if (sumSoFar == sum)
{
while (parts.Count > 0)
Console.Write(parts.Pop().ToString() + ", ");
Console.WriteLine();
return;
}
if (i >= arr.Length) return;
Stack<int> allParts = new Stack<int>(parts);
allParts.Push(arr[i]);
SubsetSum(arr, i + 1, sumSoFar + arr[i], sum, allParts);
if (allParts.Count > 0) allParts.Pop();
SubsetSum(arr, i + 1, sumSoFar, sum, allParts);
}
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#incluce <vector>
int* sequence;
bool* flag;
int n;
void getPermutaion(vector<int> & array, int sum, int part_sum, int d)
{
if (part_sum> sum)
return;
if (part_sum ==sum)
{
if (d==0)
return;
printf("{");
for (int i=0;i<d-1;i++)
{
printf("%d,"sequence[i]);
}
printf("%d}\n", sequence[d-1]);
return;
}
for (int i=0;i<n;i++)
{
if (!flag[i])
{
flag[i] =true;
sequence[d] =array[i]
getPermutaion(sum, part_sum + array[i], d+1);
flag[i] =false;
}
}
}
void solve(vector<int> & array, int sum)
{
sequence =new int[array.size()];
n =array.size();
free(sequence);
}
function subset_sum($input, $sum, $included=array()) {
if (count($input) == 0) {
return ($sum == 0) ?
array("{" . implode(",", $included) . "}") :
array();
} else {
$elem = array_pop($input);
$solutions_without_elem = subset_sum($input, $sum, $included);
array_push($included, $elem);
$solutions_with_elem = subset_sum($input, $sum - $elem, $included);
return array_merge($solutions_with_elem, $solutions_without_elem);
}
}
print implode(", ", subset_sum(array(1,2,4,5,6,1,2,4,3,5,7,2,1), 4)) . "\n";
<?php
$want = 7;
$arr = array (
1,
2,
4,
5,
6,
1,
2,
4,
3,
5,
7,
2,
1
);
sort ( $arr );
$result = array ();
for($j = 0; $j < count ( $arr ); $j ++)
for($n = 0; $n < count ( $arr ); $n ++) {
$part = array_slice ( $arr, $j, $n + 1 );
// var_dump($part);echo '<br>';
$sum = array_sum ( $part );
// echo $sum.'<br>';
if (in_array ( $want - $sum, $arr ) && in_array ( $want - $sum, array_diff_assoc ( $arr, $part ) )) {
array_push ( $part, ($want - $sum) );
sort ( $part );
$result [] = implode ( ',', $part );
}
}
foreach ( array_unique ( $result ) as $value ) {
echo $value . '<br>';
}
public static int LSBFibbonacci(int n){
if(n <= 1)
return n;
int a1 = 1;
int a2 = 1;
int res = 1;
for(int i=3;i<=n;i++){
res = (a1 + a2)%1000000;
a1 = a2 % 1000000;
a2 = res % 1000000;
}
return res;
}
import java.util.ArrayList;
import java.util.Arrays;
public class Test {
public static void main(String[] args){
int[] theArray={1,2,4,5,6,1,2,4,3,5,7,2,1};
ArrayList<ArrayList<Integer>> allpairs=getPairs(theArray,0,4);
System.out.println(allpairs.size());
for(ArrayList<Integer> pair:allpairs){
System.out.println(Arrays.toString(pair.toArray()));
}
}
public static ArrayList<ArrayList<Integer>> getPairs(int[] theArray, int start, int sum){
if(sum==0){
ArrayList<ArrayList<Integer>> pairs=new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> pair=new ArrayList<Integer>();
pairs.add(pair);
return pairs;
}
if(start>=theArray.length){
return null;
}
ArrayList<ArrayList<Integer>> pairs=new ArrayList<ArrayList<Integer>>();
//situation 1 include the start element;
ArrayList<ArrayList<Integer>> subpairs=getPairs(theArray,start+1,sum-theArray[start]);
if(subpairs!=null){
for(ArrayList<Integer> subpair:subpairs){
ArrayList<Integer> pair=new ArrayList<Integer>();
if(pair!=null){
pair.add(theArray[start]);
pair.addAll(subpair);
pairs.add(pair);
}
}
}
//situation 2 do not include the start element;
ArrayList<ArrayList<Integer>> otherpairs=getPairs(theArray,start+1,sum);
if(otherpairs!=null){
for(ArrayList<Integer> otherpair:otherpairs){
pairs.add(otherpair);
}
}
return pairs;
}
}
public static HashSet<ArrayList<Integer>> getSumPairs(int [] arr, int num) {
HashSet<ArrayList<Integer>> combination = new HashSet<ArrayList<Integer>>();
for (int i = 0; i < arr.length; ++i) {
ArrayList<Integer> combo = new ArrayList<Integer>();
int sum = arr[i];
combo.add(arr[i]);
for (int j = 0; j < arr.length; ++j) {
if (i == j) {
continue;
}
int localSum = sum + arr[j];
if (localSum < num) {
combo.add(arr[j]);
sum = localSum;
} else if (localSum == num) {
combo.add(arr[j]);
combination.add(combo);
combo = new ArrayList<Integer>();
combo.add(arr[i]);
sum = arr[i];
}
}
}
return combination;
}
Refer: Subset_sum_problem on wiki
- ashwanilabs January 03, 2012