Expedia Interview Question
Software Engineer / DevelopersAssumptions: Input is String instead of char array.
Code is in Java:
public static void printAllSubsets(String s){
int[] base=new int[s.length()];
String s1="";
while(!s1.equals(s)){
s1="";
nextCombination(base);
for(int i=0;i<base.length;i++){
if(base[i]==1){
s1=s1+s.charAt(i);
}
}
System.out.println(s1);
}
}
public static void nextCombination(int[] arr){
int i=arr.length-1;
while(i>=0){
if(arr[i]==0){
break;
}
i--;
}
if(i<0){
return;
}
arr[i++]=1;
while(i<arr.length){
arr[i++]=0;
}
}
I think one approach that may work is dynamic programming. If you do it bottom-up, you can find all combinations. However, if I'm not mistaken, DP is usually O(n^2) or worse, and doing it iteratively is a downhill compilation task.
You can represent each combination as a binary number with n bits. If the bit is on, the letter in that index is included in the combination. For a string of length n there are 2^(n+1)-1 combinations (if you include the empty set as a subset), therefore I don't think you can do it in less than 2^(n+1) time. I think that's the idea behind kg's response.
Ouput: x1...xn where xi denotes whether the i-th element of the input appears in the subset or not
#include <stdio.h>
#include <stdlib.h>
void gen(int* input, int n, int index);
int main(int argc, char* argv[])
{
int *input;
int n;
if (argc != 2) {
printf("Usage: %s <#elements>\n",argv[0]);
exit(0);
}
n = atoi(argv[1]);
input = malloc(sizeof(int)*n);
gen(input,n,0);
}
void gen(int* input, int n, int index)
{
int i;
if (index == n) {
for (i = 0; i < n; i++)
printf("%d",input[i]);
printf("\n");
return;
}
input[index] = 0;
gen(input,n,index+1);
input[index] = 1;
gen(input,n,index+1);
}
Yet another solution,
public static void combination(Queue<String> input,List<String> result ) {
if (input.Count == 0) return;
string seed = input.Dequeue();
List<String> copy = new List<string>(result);
foreach (String o in copy) {
result.Add(seed + o);
}
result.Add(seed);
combination(input, result);
}
Take each character in the input character array and put it in a Queue. Pass this queue to the above method.
#include <stdio.h>
#include <math.h>
int main() {
int a[] = {1,2,3,4,5}, size;
size = sizeof(a)/sizeof(a[0]);
for (int i = 0; i < pow(2.0, size); ++i) {
printf("{");
for (int j = 0; j < size; ++j)
if (((i >> j) & 1) == 1)
printf(" %d ", a[j]);
printf("}\n");
}
return 0;
}
"Present" string as binary. If i-th bit ON print character i.
L - length of the string;
2^(L-1) - number of combinations
- zdmytriv March 11, 2008