## Interview Question Software Engineer / Developers

• 0

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.

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);
}

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

great solution

Comment hidden because of low score. Click to expand.
0

``````#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();
}``````

Comment hidden because of low score. Click to expand.
0

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

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. :)

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;
}

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

gr8....:)

Comment hidden because of low score. Click to expand.
0

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

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?

Comment hidden because of low score. Click to expand.
0

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

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

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());
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));
}
// System.out.println(a.get(0));
}

return a;
}

This should work

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....

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@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.

Name:

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

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

### 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.