Interview Question Software Engineer / Developers

  • -
    0
    of 0 votes
    18
    Answers

    Given an array, print combinations of the array elements such that it is printed only once and the order is not important between the elements. Eg. array = [a,b,c,d]
    o/p should be "", a,b,c,d,ab,ac,ad,bc,bd,cd,abc,abd,acd,bcd, abcd.. so it should not repeat abc in the form cab or bca etc..

    Output number wil always be 2^n and do this in O(1) space.

    - sylarific on July 02, 2012 in United States Report Duplicate | Flag
    Software Engineer / Developer Algorithm

Country: United States
Interview Type: In-Person


Comment hidden because of low score. Click to expand.
3
of 3 vote

private static String input;

private static void generateCombinations(String string) {
input = string;
_generateCombinations("", 0, true);
}

private static void _generateCombinations(String currentString,
int currentIndex, boolean print){
if(currentIndex >= input.length()){
if(print)
System.out.println(currentString);
return;
}
if(print)
System.out.println(currentString);
_generateCombinations(currentString + input.charAt(currentIndex), currentIndex + 1, true);
_generateCombinations(currentString, currentIndex + 1, false);
}

- Siva on July 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

by far this is the simplest solution - no external storage is required at all

- ram on July 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

great solution

- pfma129 on July 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

#include <stdio.h>

int A[5]= {0};
char B[5]={'V','A','B','C','D'};

void print2(int A[], int N){
    int sum =0;
    for (int i =1; i <=N; i++){
        if(A[i] ==1){
            printf("%c",B[i]);
            sum++;
        }
        
    }
    if(sum==0)
        printf("null set");
        printf("\n");     
}


void print(int A[], int N){

    for (int i =1; i <=N; i++){
            printf("%d ",A[i]);
    }
        printf("\n");     
}
/*
void combination(int A[], int k, int N) {
    printf("k=%d\n",k);
    if (k==N) {
        A[k]=0;
        print(A,N);
        A[k]=1;
        print(A,N); 
        return;         
              
    }
    
    for ( int i=k; i <=N ; i++) {
        A[i]=0;
        combination(A,i+1,N);
        A[i]=1;
        combination(A,i+1,N);
    }     
     
     
}
*/


void combination(int A[], int k, int N) {
    //printf("k=%d\n",k);
    if (k==N) {
        A[k]=0;
        print2(A,N);
        A[k]=1;
        print2(A,N); 
        return;         
              
    }
    
    
        A[k]=0;
        combination(A,k+1,N);
        A[k]=1;
        combination(A,k+1,N);
         
     
     
}

int main(){
 combination(A,1,4);   
 getchar();   
}

codepad.org/s17SqRQn

- Anonymous on July 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can learn and understand how to print all possible combination of a string at
youtu.be/p8SDPaX1wgw

- Anonymous on July 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

It is nothing but to write all the subsets of a given set except the empty set.

1. Find the number 2^n -1.
2. Starting from one, write all the numbers till 2^n -1 in binary form.
3. The places where '1' occur, replace them with the corresponding index in array.

Ex: {a,b,c}

Soln: n=3
N = 2^3-1 = 7

001 - c
010 - b
011 - b,c
100 - a
101 - a,c
110 - a,b
111 - a,b,c

Clear, comprehensible and crisp. :)

- Piyush on July 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

one possible approach using backtracking.
Total no of string would be 2^N-1.

#include <stdio.h>
#include <string.h>
void combination(char *string, char *temp, int start, int depth, int length)
{
int i;
if( start <= length && start != 0)
{
temp[depth+1] = '\0';
printf("%s\n ", temp);
}
for(i=start; i<length; i++)
{
temp[depth] = string[i];
combination(string, temp, i+1, depth, length);
temp[depth] = string[i];
depth++;
}
}

int main()
{
char string[]="abcd";
char temp[strlen(string)+1];
combination(string, temp, 0, 0, strlen(string));
return 0;
}

- Aalok on July 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice approach..i used recursive approach but got stuck in the middle :)

- sylarific on July 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

gr8....:)

- Raj Naik on July 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

And I thought we had to do it in constant space.. 0-0

- Shark on July 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void getCombinations(String str) {
System.out.println(str.length());
for ( int i =0 ; i < str.length();i++) {
for ( int j=i+1;j<=str.length();j++) {
System.out.println(str.substring(i,j));
}
}


}
This is working for me..any thoughts?

- ragavenderan on July 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

if the input is abcd .. abd doesn't get printed

- ram on July 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

An approach without backtracking with O(1) space.

#include <stdio.h>
#include <string.h>
#include <math.h>
 
void comb(char *str)
{
        int n,i,j,top,wt;
        n=strlen(str);
        n=pow(2,n);
 
        for(i=1;i<n;i++)
        {
                for(j=i,wt=1,top=0;j>0;j>>=1,top++)
                {
                        if(j&wt)
                                printf("%c",str[top]);
                }
                printf("\n");
        }
}
 
int main()
{
        char str[]="ABCD";
        comb(str);
        return 0;
}

ideone.com/A5Ucq

- Aashish on July 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public ArrayList getCombinations(String str) {
ArrayList<String> a = new ArrayList<String>();
// System.out.println(a.size());
// a.add("xx");
for ( int i =0 ; i < str.length();i++) {

int k=a.size();
for ( int j=0;j<k;j++)
{
System.out.println(a.get(j)+str.charAt(i));
a.add(a.get(j)+str.charAt(i));
}
a.add(str.charAt(i)+"");
// System.out.println(a.get(0));
}

return a;
}

This should work

- ragavenderan on July 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Take number 0 and increment it upto 2^n-1.
When its zero,get all its set bits and use them as index into the array for printing hence ""
for 1, output d
for 2,output c
for 3, output cd
for 4, output b
and so on....

- Luv on July 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Luv what if the value of n>10^32

- hubulu on July 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

not n>10^32

it will not work for n>32 or 64 (Size of POD).

But you can create an array of ints and carry over the bit to the next one.

- nerd on July 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@hubulu yes it will work for for n<=2^32 if we take int, but you can use arrays also.
Hope it's clear to u.

- Luv on July 02, 2012 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More