Amazon Interview Question SDE1s
0of 0 votesWrite code to Print the power set of given string
Country: United States
Interview Type: In-Person
#include <stdio.h>
#include <string.h>
int main()
{
//assuming the string has distinct characters... (or else one can also pick out the distinct chars ..)
char str[20];
strcpy(str, "abcdef");
int len = strlen(str);
int start_val=(1<<len)-1;
char subset[20];
int itr1, itr2;
while(start_val >=0)
{
int tmp=start_val;
itr1=itr2=0;
while(itr2!=len)
{
if(tmp&1)
subset[itr1++] = str[itr2];
tmp >>=1;
itr2++;
}
subset[itr1]='\0';
printf("%s\n", subset);
start_val--;
}
return 0;
}
This code will print all possible subsets of the given string.
You can ignore that. I think it was generated by the editor(coz i m unable to remove it.)... assume there isn't a ';' there.. :)
@ashish In order to improve it, i guess we need to find a faster way of finding the positions of set bits...it is as follows:
For each number 'p' that we convert into binary .. do as follows:
int itr2=0;
while(p>0)
{
int tmp=p;
p = p&(p-1);
tmp-=p;
int pos = log2(tmp);
subset[itr2++]=str[pos];
}
subset[itr2]='\0';
The time complexity now will be:
total number of set bits from 0 to 2^n-1 = n*2^(n-1) = O(n*2^n).
But the advantage is that running time is reduced to nearly half of the previous algorithm.
I guess this can't still be reduced.. :) :)
dude are u sure this printing all subsets...doesn't seem so.. see the outer loop is running for 32 times then what is the inner loop for?
public class PowerSet
{
public static String[] generate(char[] array){
int n = 1 << (array.length); // calculate 2 ^ n
int [] validator = new int[array.length];
for(int k=0; k<array.length; k++){
validator[k]=1<<k;
}
ArrayList<String> strArray = new ArrayList<String>();
for(int i=0; i<n; i++){;
StringBuffer buf = new StringBuffer();
buf.append( '{' );
for(int j=0; j<array.length; j++){
if((i & validator[j])>0){
buf.append( array[j] );
}
}
buf.append( '}' );
strArray.add( buf.toString() );
}
return strArray.toArray( new String[strArray.size()]);
}
public static String[] generate(String input){
return generate(input.toCharArray());
}
public static void main( String[] args )
{
String input = "abc";
String[] set = generate( input );
printArray( set );
}
public static void printArray(String... array){
for ( String str : array )
{
System.out.println(str);
}
}
}
public class PowerSet
{
public static String[] generate(char[] array){
int n = 1 << (array.length); // calculate 2 ^ n
int [] validator = new int[array.length];
for(int k=0; k<array.length; k++){
validator[k]=1<<k;
}
ArrayList<String> strArray = new ArrayList<String>();
for(int i=0; i<n; i++){;
StringBuffer buf = new StringBuffer();
buf.append( '{' );
for(int j=0; j<array.length; j++){
if((i & validator[j])>0){
buf.append( array[j] );
}
}
buf.append( '}' );
strArray.add( buf.toString() );
}
return strArray.toArray( new String[strArray.size()]);
}
public static String[] generate(String input){
return generate(input.toCharArray());
}
public static void main( String[] args )
{
String input = "abc";
String[] set = generate( input );
printArray( set );
}
public static void printArray(String... array){
for ( String str : array )
{
System.out.println(str);
}
}
}
void printPowerSet(char *set, int set_size)
{
/*set_size of power set of a set with set_size
n is (2**n -1)*/
unsigned int pow_set_size = pow(2, set_size);
int counter, j;
/*Run from counter 000..0 to 111..1*/
for(counter = 0; counter < pow_set_size; counter++)
{
for(j = 0; j < set_size; j++)
{
/* Check if jth bit in the counter is set
If set then pront jth element from set */
if(counter & (1<<j))
printf("%c", set[j]);
}
printf("\n");
}
}
#include<cstdio>
#include<string.h>
using namespace std;
void fun(char* str,bool* status,int n,int size,int index,int length_upto){
if(index==n)
return;
fun(str,status,n,size,index+1,length_upto);
status[index]=true;
length_upto++;
if(length_upto==size){
for(int i=0;i<n;i++){
if(status[i]==true){
printf("%c",str[i]);
}
}
printf(" ");
status[index]=false;
return;
}
else{
fun(str,status,n,size,index+1,length_upto);
status[index]=false;
}
}
int main(){
char str[100];
int n;
bool* status;
scanf("%s",str);
n=strlen(str);
status=new bool[n];
for(int i=0;i<n;i++){
status[i]=false;
}
for(int i=1;i<=n;i++){
printf("Length %d---->>>>\n",i);
fun(str,status,n,i,0,0);
printf("\n");
}
return 0;
}
Recursive solution, looks elegant, and you wont run the risk of making boundary errors.
public void powerSet(String s) {
System.out.println("{}");
powerSet(s, new StringBuilder());
}
private void powerSet(String s, Stringbuilder out) {
if(s.length() == 1) {
out.append(s.charAt(0));
System.out.println("{" + out.toString() + "}");
out.deleteCharAt(out.length() - 1);
return;
}
for(int i = 0; i < s.length(); i++) {
out.append(s.charAt(i));
System.out.println("{" + out.toString() + "}");
powerSet(s.substring(i, s.length()), out);
out.deleteCharAt(out.length() - 1);
}
}
Naive implementation using recursive invocations.
Idea: consider a generation of a string as being done for a particular number of characters, for example, string for "abc" generate strings with 1 char, 2 chars and 3 chars.
Let's call them levels. A string at a level is formed from a current char + all combinations for the substring starting with the next character at level - 1.
For example, "abc" for level = 2 and char "a" has to be considered a substring "bc" at level = 1 (which are "b" and "c")
import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.Matchers.arrayContainingInAnyOrder;
import static com.google.common.collect.Sets.newHashSet;
import java.util.Set;
public class PrintPowerSetOfAString {
public static Set<String> superSet(final String s) {
final Set<String> result = newHashSet("");
if (s == null || s.length() == 0) {
return result;
}
/*
* Level is the number of characters + 1 that have to be taken from the string, for example,
* string: "abc"
* level 0: "a", "b", "c"
* level 1: "ab", "ac", "bc"
* level 2: "abc"
*/
for (int lvl = 0; lvl < s.length(); lvl++) {
result.addAll(get(s.toCharArray(), 0, lvl));
}
return result;
}
/**
* Returns combination of strings for a substring starting with {@code start} with number of characters
* {@code lvl + 1}.
*/
public static Set<String> get(final char[] a, final int start, final int lvl) {
final Set<String> result = newHashSet();
if (start >= a.length) {
return result;
}
if (lvl < 0) {
return result;
}
for (int i = start; i < a.length; i++) {
// get combinations of the substring starting from the next char with lvl number of chars
Set<String> set = get(a, i + 1, lvl - 1);
if (!set.isEmpty()) {
for (String s : set) {
result.add(a[i] + s);
}
} else {
if (lvl + 1 == 1) {
result.add(String.valueOf(a[i]));
}
}
}
return result;
}
public static void main(final String[] args) {
assertThat("", superSet("a").toArray(new String[0]), arrayContainingInAnyOrder("", "a"));
assertThat("", superSet("abc").toArray(new String[0]),
arrayContainingInAnyOrder("", "a", "b", "c", "ab", "ac", "bc", "abc"));
assertThat("", superSet("abcde").toArray(new String[0]),
arrayContainingInAnyOrder("", "a", "b", "c", "d", "e", "ab", "ac", "ad", "ae", "bc", "bd", "be", "cd", "ce",
"de", "abc", "abd", "abe", "acd", "ace", "ade", "bcd", "bce", "bde", "cde", "abcd", "abce", "abde",
"acde", "bcde", "abcde"));
}
}
import java.io.*;
import java.lang.String;
class powerset
{
static int l;
static String str="abc";
public static void main(String args[])throws IOException
{
String str1="";
l= str.length();
print_word(str1,0);
}
static void print_word(String str1,int i)
{
if(i>(l-1))
{
System.out.println(str1);
System.out.println("\n");
return;
}
char ch=str.charAt(i);
print_word(str1 + ch,i+1 );
print_word(str1,i+1 );
}
}
Similar solution to as posted above just with easier code
private static String printSubset(int s, String str)
{
StringBuilder b = new StringBuilder();
for (int i = 0; i < str.length(); i++)
{
if (((s >> i) & 0x1) == 1)
b.append(str.charAt(i));
}
return b.toString();
}
public static void printPowerSet(String str)
{
int n = 1 << str.length();
for (int i = 0; i < n; i++)
System.out.println(printSubset(i, str));
}
public static void main(String[] args) {
String s = "tony";
printPowerSet(s);
}
output:
t
o
to
n
tn
on
ton
y
ty
oy
toy
ny
tny
ony
tony
You have 2^n sets to generate (including the empty set). You can loop for each integer value 'i' from 0 to 2^n and for each binary representation of 'i', print characters of string that corresponding to 1s in the binary representation. For example, a s = "123" and i="101" then you have set "13".
- ahmad.m.bakr June 03, 2013public static void printPowerSet(String s){ char [] array = s.toCharArray(); for(int i=0; i< Math.pow(2, array.length); i++){ char [] values = Integer.toBinaryString(i).toCharArray(); StringBuffer buffer = new StringBuffer(); int index=0; for(int j=values.length-1; j>=0;j--){ if(values[j]=='1') buffer.append(array[index]); index++; } System.out.println(buffer.toString()); } }