Adobe Interview Question Java Developers
Country: India
Interview Type: In-Person
void printsubset(int a[],int size)
{ for(int i=0;i<size;i++)
cout<<a[i]<<" ";
cout<<"\n";
}
void subset(int s[],int t[],int ssize,int tsize,int sum,int ite,int const targetsum)
{ if(targetsum==sum)
{ printsubset(t,tsize);
subset(s,t,ssize,tsize-1,sum-s[ite],ite+1,targetsum);
return
}
else
{ for(int i=ite;i<ssize;i++)
{ t[tsize]=s[i];
subset(s,t,ssize,tsize+1,sum+s[i],i+1,targetsum);
}
}
}
I assumed that initially ite=0; t[] is empty, sum=0 ; tsise=0 targetsum isgiven sum;
import java.io.IOException;
public class FindingCombination {
public static void main(String[] args) throws IOException{
int[] arr = {1,3,23,76,908,34,256,12,43,11,2,-10};
System.out.println(combination(arr,13));
}
public static String combination(int[] arr, int data){
String comb = "";
for(int i=0;i<arr.length;i++){
int temp = data - arr[i];
for(int j=0;j<arr.length;j++){
if(temp == arr[j]){
comb = comb + " ("+arr[j]+","+arr[i]+")";
}
}
}
return comb;
}
}
import java.io.IOException;
public class FindingCombination {
public static void main(String[] args) throws IOException{
int[] arr = {1,3,23,76,908,34,256,12,43,11,2,-10};
System.out.println(combination(arr,13));
}
public static String combination(int[] arr, int data){
String comb = "";
for(int i=0;i<arr.length;i++){
int temp = data - arr[i];
for(int j=0;j<arr.length;j++){
if(temp == arr[j]){
comb = comb + " ("+arr[j]+","+arr[i]+")";
}
}
}
return comb;
}
}
import java.io.IOException;
public class FindingCombination {
public static void main(String[] args) throws IOException{
int[] arr = {1,3,23,76,908,34,256,12,43,11,2,-10};
System.out.println(combination(arr,13));
}
public static String combination(int[] arr, int data){
String comb = "";
for(int i=0;i<arr.length;i++){
int temp = data - arr[i];
for(int j=0;j<arr.length;j++){
if(temp == arr[j]){
comb = comb + " ("+arr[j]+","+arr[i]+")";
}
}
}
return comb;
}
}
import java.io.IOException;
public class FindingCombination {
public static void main(String[] args) throws IOException{
int[] arr = {1,3,23,76,908,34,256,12,43,11,2,-10};
System.out.println(combination(arr,13));
}
public static String combination(int[] arr, int data){
String comb = "";
for(int i=0;i<arr.length;i++){
int temp = data - arr[i];
for(int j=0;j<arr.length;j++){
if(temp == arr[j]){
comb = comb + " ("+arr[j]+","+arr[i]+")";
}
}
}
return comb;
}
} }}}
import java.io.IOException;
public class FindingCombination {
public static void main(String[] args) throws IOException{
int[] arr = {1,3,23,76,908,34,256,12,43,11,2,-10};
System.out.println(combination(arr,13));
}
public static String combination(int[] arr, int data){
String comb = "";
for(int i=0;i<arr.length;i++){
int temp = data - arr[i];
for(int j=0;j<arr.length;j++){
if(temp == arr[j]){
comb = comb + " ("+arr[j]+","+arr[i]+")";
}
}
}
return comb;
}
}
It can be done as follows.
1. Sort the list in ascending order (takes O(nlgn))
2. Read the list from begining
3. For each element read search (13 - element read) value from the list.
Seaching in list takes lgn and in worst case the time complexity will be O(nlgn)
This way it will be O(n^2). Do this :
1) Sort- o(nlogn)(say increasing sorted)
2) int i=0, j=n-1;
3) while(i<j) if ( a[i]+a[j]==13) print i,j;
else if (a[i]+a[j] <13 ) i++ else j--;
Second approach do hash. and when inserting any new element just check if 13-element is already in hash. This will be O(n)
Sort it in nLogn and then it can be found in )(n). So the total is )(nlogn).... Can we do better?I dont think so
Subset sum problem.
- Anonymous July 12, 2012