Adobe Interview Question
Computer ScientistsCountry: India
Interview Type: In-Person
int compareInts (const void * a, const void * b)
{
if ( *(int*)a < *(int*)b ) return -1;
if ( *(int*)a == *(int*)b ) return 0;
if ( *(int*)a > *(int*)b ) return 1;
}
void print (int* elem, int n)
{
for (int i=0;i<n;++i)
cout << elem[i] << " ";
cout << endl;
}
void findallsubsets (int sum, vector<int> prefix, int* a, int k, int n)
{
if (k > n || sum < 0)
return;
if (sum == 0)
{
print (&prefix[0], prefix.size());
return;
}
prefix.push_back (a[k]);
findallsubsets (sum-a[k], prefix, a, k+1,n);
prefix.pop_back ();
findallsubsets (sum, prefix, a, k+1,n);
}
void findallsubsets (int sum, int* elem, int n)
{
qsort (elem, n, sizeof (int), compareInts);
int* l = std::unique (elem, elem+n);
cout << "Sorted:" << endl;
print (elem,l-elem);
cout << "Subsets:" << endl;
vector<int> v;
findallsubsets (sum, v, elem, 0, l-elem);
}
void print(int *arr,int n)
{
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
cout<<endl;
}
int printAllSubsets(int *arr,int n,int last_selected,int pos,int *ele,int sum)
{
//arr is the main array
//n is the size of the array
//last_selected is the last selected element of the arr array
//pos is the current postion in ele array
//sum is the sum to be found
//cout<<"Current Sum :- "<<sum<<endl;
if(last_selected==n)
return 1;
if(sum<0)
{
return -1;
}
if(sum==0)
{
print(ele,pos);
return 0;
}
int check=1;
int flag=0;
for(int i=last_selected+1;i<n;i++)
{
ele[pos]=arr[i];
check=printAllSubsets(arr,n,i,pos+1,ele,sum-arr[i]);
if(check==0)
{
flag=1;
int j=i+1;
while(j<n && arr[j]==arr[i])
j++;
i=j-1;
}
}
if(flag==1)
return 0;
else return 1;
}
int partition(int *arr,int low,int high)
{
int left=low+1;
int right=high;
int pivot=arr[low];
while(left<=right)
{
if(arr[left]<=pivot)
left++;
if(arr[right]>=pivot)
right--;
if(left<right)
{
int temp=arr[left];
arr[left]=arr[right];
arr[right]=temp;
}
}
int temp=arr[low];
arr[low]=arr[right];
arr[right]=temp;
return right;
}
void quick_sort(int *arr,int low,int high)
{
if(low<high)
{
int pos=partition(arr,low,high);
quick_sort(arr,low,pos-1);
quick_sort(arr,pos+1,high);
}
}
int main()
{
/*int arr[]={1,2,3,4,5,6,7,8};
int size=sizeof(arr)/sizeof(arr[0]);
printArray(arr,size);
swapArray(arr,0,size-1);
printArray(arr,size);
getchar();*/
/*int arr[]={1,2,3,4,5,6,7,8,9,10};
Tree t;
for(int i=0;i<=9;i++)
t.insert(arr[i]);
cout<<t.findMax()<<endl;*/
//PrintOneToN<100> b;
int arr[]={2,3,4,1,3,2,6,-1};
int n=(sizeof(arr))/sizeof(arr[0]);
quick_sort(arr,0,n-1);
//int *l=unique(arr,arr+n);
//n=l-arr;
int *ele=new int[n];
printAllSubsets(arr,n,-1,0,ele,5);
getchar();
}
package questions;
public class Sort {
public static void main(String[] args){
int[] sample={1,3,5,-4,-5,9};
int sum=8;
int tempSum=0;
for(int i=0;i<sample.length;i++){
tempSum=sample[i];
for(int j=i+1;j<sample.length;j++){
tempSum=tempSum+sample[j];
if(tempSum==sum){
for(int a=i;a<=j;a++){
System.out.print(sample[a]+" ");
}
System.out.println("\n");
}
}
}
}
}
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
int n;
std::vector<int> in;
void printSubset(std::vector<int> &partialSubset)
{
for (int i = 0; i < partialSubset.size(); ++i)
{
cout<<partialSubset[i]<<",";
}
cout<<endl;
}
void findSubSet(int pos, int sum, std::vector<int> &partialSubset)
{
if(sum == 0)
{
printSubset(partialSubset);
return;
}
if(pos >= n) return;
if(in[pos] > sum) return;
do {
partialSubset.push_back(in[pos]);
findSubSet(pos+1, sum - in[pos], partialSubset);
partialSubset.pop_back();
do{
pos++;
}while(pos<n && in[pos-1]==in[pos]);
} while(pos < n);
}
int main(int argc, char const *argv[])
{
int temp,sum;
cin>>n;
for (int i = 0; i < n; ++i)
{
cin>>temp;
in.push_back(temp);
}
cin>>sum;
sort(in.begin(), in.end());
int i=0;
while(i<n)
{
std::vector<int> partialSubset(1,in[i]);
findSubSet(i+1,sum-in[i], partialSubset);
do {
i++;
}while(i<n && in[i-1]==in[i]);
}
return 0;
}
This code prints subset of answer... but not all answers
package codeforce;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Setsofk {
public static void main(String [] args)
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
List<Integer> li = new ArrayList<>();
Map<Integer, List<Integer>> m = new HashMap<>();
List<Integer> set=new ArrayList<>();
try {
int k=Integer.parseInt(br.readLine());
String[] array=br.readLine().split(",");
for(int i=0; i<array.length; i++)
{
li.add(Integer.parseInt(array[i]));
}
System.out.println(li);
Collections.sort(li);
System.out.println(li);
int key=0;
for(int i=0; i<li.size(); i++)
{
int sum=li.get(i);
set.clear();
set.add(li.get(i));
for(int j=i+1; j<li.size(); j++)
{
sum=li.get(i);
int l=j;
while(l<li.size())
{
sum+=li.get(l);
if(sum<k)
{
set.add(li.get(l));
}
else if(sum==k)
{
set.add(li.get(l));
if(m.containsValue(set))
{
continue;
}
else
{
m.put(key, new ArrayList<Integer>(set));
key++;
break;
}
}
else if(sum>k)
{
break;
}
l++;
}
set.clear();
set.add(li.get(i));
}
}
System.out.println(m);
} catch (NumberFormatException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
}
}
this is the perfect solution in c++. My previous solution was not giving all outputs...
- sudeep91soni January 15, 2015