Citigroup Interview Question
Country: United States
It will not print in the lexicographical order, but it gives nice solution.
// assuming s is limited with 64 we're going to use fancy bit solution
public void printAllSubsets(List<Integer> s) {
// get max integer number that we're going to use.
long limit = ((long) Math.pow(2, s.size()));
for (long i=0; i<limit; i ++) {
// lets print only those elements that are in the those positions of i that have non-zero bit
long j = i;
int bitNumber = 0;
while (j > 0) {
bitNumber ++;
if ((j & 1L) == 1L) {
System.out.print(s.get(bitNumber));
}
j = j >> 1;
}
System.out.println();
}
}
Following is an iterative implementation to print all the combinations.
It first prints all combinations consisting of 1 elements, then prints all combinations consisting of 2 elements and so on
#include<stdio.h>
int main()
{
int arr[] = {1,2,3};
int gap,i,j,k;
/* loop is for the length of the number of elements */
for(gap=1;gap<=sizeof(arr)/sizeof(arr[0]);gap++)
{
/* loop is to traverse the entire list, for eg. if gap is 1 (1st iteration), for above list it will print 1,2,3 */
for(i=0;i<sizeof(arr)/sizeof(arr[0])-gap+1;i++)
{
int num = 0; /* tmp variable to store the number formed*/
k = 0;
j = i;
while(k<gap)
{
num = num*10+arr[j++];
k++;
}
printf("%d\n",num);
}
}
}
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.TreeSet;
public class Comb {
TreeSet hs = new TreeSet();
public TreeSet permutation(String prefix, String str) {
int n = str.length();
if (n == 0)
{
hs.add(prefix);
//System.out.println(prefix);
}
else
{
hs.add(prefix);
//System.out.println(prefix);
}
for(int i = 0;i < n;i++)
permutation(prefix+str.charAt(i), str.substring(0, i)+str.substring(i+1, n));
return hs;
}
void print (TreeSet hs)
{
Iterator itr = hs.iterator();
while(itr.hasNext())
{
String str = (String)itr.next();
System.out.println(str);
}
}
public static void main(String[] args) {
Comb b = new Comb();
String ss = "abc";
TreeSet hss = b.permutation("", ss);
System.out.println("Printing in acsending order....................");
b.print(hss);
int i;
ArrayList al = new ArrayList();
for (i = 1;i<=ss.length() ; i++)
{
Iterator itr = hss.iterator();
while(itr.hasNext())
{
String str = (String)itr.next();
if(str.length()==i)
{
al.add(str);
}
}
}
System.out.println("Printing in acsending order and ascending length....................");
for (i=0;i<al.size(); i++)
{
System.out.println((String)al.get(i));
}
}
}
public static void arr1(int[] word, int[] letters, int wordLength, int t) {
if (t == 0) {
for (int i = 0; i < wordLength; i++) {
System.out.print(word[i]);
}
System.out.println();
} else {
for (int j = 0; j < word.length; j++) {
if (t == wordLength
|| (letters[j] != word[t] && letters[j] < word[t])) {
word[t - 1] = letters[j];
arr1(word, letters, wordLength, t - 1);
}
}
}
}
public static void main(String[] args) {
int[] letters = { 1, 2, 3 };
int[] word = new int[3];
for (int wordLength = 1; wordLength < word.length + 1; wordLength++) {
arr1(word, letters, wordLength, wordLength);
}
}
- Anonymous April 08, 2014