Twitter Interview Question
Software Engineer / DevelopersCountry: United States
In the 3rd step, replace all 1s with * in binary presentation is enough, why bother do the same thing for all 0s?
public static void tupleSubstitute(List<Character> tuple, char arr[], int idx) {
if(idx == tuple.size()){
System.out.print("(");
for(char ch: arr)
System.out.print(ch + ",");
System.out.println(")");
}
else{
arr[idx] = '*';
tupleSubstitute(tuple, arr, idx+1);
arr[idx] = tuple.get(idx);
tupleSubstitute(tuple, arr, idx+1);
}
}
I write my code by using your idea
m = ('a','b','c','d','e')
n = 1
while(n<2**len(m)):
count = 0
print "%s" % bin(n)[2:].zfill(len(m))
for cc in bin(n)[2:].zfill(len(m)):
if int(cc) == 0:
print '*'
elif int(cc) == 1:
print m[count]
count+= 1
n+=1
#include <iostream>
#include <vector>
using namespace std;
void Generate(string s)
{ int64_t all=(1LL<<s.size()),i,j;
for(i=0;i<all;i++)
{ printf("(");
for(j=0;j<s.size();j++)
{ if((1LL<<j)&i) printf("%c,",s[j]);
else printf("%c,",'*');
}
printf("\b)\n");
}
}
main()
{
string s="abcd";
Generate(s);
system("pause");
return 0;
}
public static void tupleSubstitute(List<Character> tuple, char arr[], int idx) {
if(idx == tuple.size()){
System.out.print("(");
for(char ch: arr)
System.out.print(ch + ",");
System.out.println(")");
}
else{
arr[idx] = '*';
tupleSubstitute(tuple, arr, idx+1);
arr[idx] = tuple.get(idx);
tupleSubstitute(tuple, arr, idx+1);
}
}
calculate combinations for 1-element selections directly. For every k-element combinations, do the following :
- for every element, E, in the set S, form a new set by joining the element with all the combinations in (k-1)-combinations set, combi[k-1], where the elements in combi[k-1] start with elements which occur after the element, E, in order in set S
pseudo code :
Set S;
combi[n][n];
//calculate 1-element combinations
for(int i=1; i<= S.length; i++)
{
combi[1][i] = new set(S[i]);
}
for(int i=2; i<=length; i++) //loop for calculating i-element combinations
{
//loop for calculating i-element combinations for a particular element
for(int j=1; j<= (length-(i-1)); j++)
{
combi_set = new set();
for(int k=j+1; k<=(length-(i-2));k++)
{
combi_set.add(multiply_set(S[j], combi[i-1][k]));
}
combi[i][j] = combi_set;
}
}
package strings;
import java.util.ArrayList;
public class tupleSubstitute {
public tupleSubstitute() {
String tuple = "(a,b,c,d)";
ArrayList<String> out = new ArrayList<String>();
out.add("(*,*,*,*)");
String tmp;
int i =1;
int n =tuple.length() -2;
while(i<16)
{
for(int j =0; j< i; j++)
{
tmp = out.get(j);
tmp = tmp.substring(0,n) + tuple.charAt(n) + tmp.substring(n+1);
out.add(tmp);
}
i = out.size();
n -=2;
}
}
}
<code><pre class="language-java">
public static void printAllSets(char[] arr) {
int counts = (int)Math.pow(2, arr.length);
for (int i = 0; i < counts; i++) {
int t = i;
System.out.print("(");
for (int j = 0; j < arr.length - 1; j++) {
if ((t & 1) == 1) {
System.out.print(arr[j]);
} else {
System.out.print("*");
}
System.out.print(",");
t = t >> 1;
}
if ((t & 1) == 1) {
System.out.print(arr[arr.length - 1]);
} else {
System.out.print("*");
}
System.out.println(")");
}
}
public static void main(String[] args) {
printAllSets3(new char[]{'a', 'b', 'c'});
}
</pre></code>
public void printtuple(ArrayList<char> tuple)
{
int l = size(tuple);
dfs(tuple, new char[l], 0, l);
}
public void dfs(ArrayList<char> tuple, char[] arr, int dep, int len)
{
if(del == len){
System.out.print('(')
for(int i=0; i<len; i++){
System.out.print(arr[i] + ", ");
}
System.out.print(") \n");
return;
}
char c = tuple.get(dep);
arr[dep] = c;
dfs(tuple, arr, dep+1, len);
arr[dep] = '*';
dfs(tuple, arr, dep+1, len);
}
#include<stdio.h>
void bin(int i,int temp[])
{
int k,j=2;
while(i!=0)
{
temp[j--]=i%2;
i=i/2;
}
}
int main()
{
int i,j,k;
for(i=0;i<=7;i++)
{
int temp[3]={0};
bin(i,temp);//in reverse order
printf("(");
for(j=0;j<3;j++)
{
if(temp[j]==1)
printf("%c",97+j);
else if(temp[j]==0)
printf("*");
if(j==2)
printf(")");
else
printf(", ");
}
}
}
/**
* Given a Tuple for eg. (a, b, c)..
* Output : (*, *, *), (*, *, c), (*, b, *), (*, b, c), (a, *, *), (a, *, c), (a, b, *), (a, b, c)
*/
public static void buildTuple(String[] tuple) {
for (int i=0; i<powerN(2,tuple.length); i++) {
String b = toBinary(i, tuple.length);
System.out.print("(");
for (int j=0; j<b.length(); j++) {
if (b.substring(j,j+1).equals("1"))System.out.print(" "+tuple[j]+" ");
else System.out.print(" * ");
}
System.out.print(") ");
}
}
private static String toBinary(int base, int length) {
String b = Integer.toBinaryString(base);
for (int i = b.length(); i < length; i++) {
b = "0"+b;
}
return b;
}
private static int powerN(int base, int n) {
int result = 1;
for (int i = 0; i < n; i++) {
result *= base;
}
return result;
}
char[] tuple = {'a', 'b', 'c'};
double permutations = Math.Pow(2, tuple.Length);
for (int n = 0; n < permutations; n++)
{
if (n > 0) Console.Write(", ");
Console.Write('(');
int pos = 0;
for (int i = tuple.Length-1; i >= 0; i--)
{
Console.Write((n & (1 << i)) != 0 ? tuple[pos] : '*');
if (i > 0) Console.Write(",");
pos++;
}
Console.Write(')');
}
#include<iostream>
using namespace std;
void printstr(char set[], int index, string str, int setlength){
if(index == setlength)
cout<<str<<endl;
else{
printstr(set, index+1, str + '*', setlength);
printstr(set, index+1, str + set[index], setlength);
}
}
int main(){
char set[]={'a', 'b', 'c'};
string str;
printstr(set, 0, str, 3);
return 0;
}
public static List<string> StarredCombinations(string str)
{
List<string> starredCombinations = new List<string>();
if (str.Length == 1)
{
starredCombinations.Add(str);
starredCombinations.Add("*");
}
else
{
List<string> subStarredCombinations = StarredCombinations(str.Substring(1));
foreach(string subStarCombination in subStarredCombinations)
{
starredCombinations.Add("*" + subStarCombination);
starredCombinations.Add(str[0] + subStarCombination);
}
}
return starredCombinations;
}
Simple recursion:
def pattern(prefix, input, len)
if (prefix.length == len)
puts prefix
return
end
pattern(prefix+input[0], input[1..-1], len)
pattern(prefix+'*', input[1..-1], len)
end
input = "ab"
pattern("", input, input.length)
simple recursion
static List<List<String>>main=new ArrayList<List<String>>();
public static void helper(String s[],int size,int index) {
if(index==s.length){
List<String>ls=new ArrayList<String>();
for (String string : s) {
ls.add(string);
}
main.add(ls);
return;
}
helper(s,0,index+1);
String temp=s[index];
s[index]="*";
helper(s,0,index+1);
s[index]=temp;
}
1. Count the number of arguments in the tuple. Lets say it is 'R'
- Learner January 10, 20132. Run a loop from 0 to (2^R)-1.
3. In any iteration i, for its binary represent, print * for 0, and for 1, print that position's character (prior to this step, we should assign an enumerator for individual characters)