Google Interview Question for Software Engineers


Country: United States




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

public static class WildcardProblem {

        public static void getPerms(String input) {
            if (input.contains("?")) {
                getPerms(input.replaceFirst("\\?", "0"));
                getPerms(input.replaceFirst("\\?", "1"));
            }
            else {
                System.out.println(input);
            }
        }

    }

- Chris May 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Really nice solution, Chris.

- Ravi May 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

Too much of scan like contains , replaceFirst. How about this.

public class PatternProduce {

	public static void produce(char[] in, int index, String output) {
		if(index == in.length) {
			System.out.println(" " + output);
			return;
		}
		
		if(in[index] == '?') {
			produce(in, index+1, output+"0");
			produce(in, index+1, output+"1");
		} else {
			produce(in, index+1, output+in[index]);
		}
		
	}
	
	public static void main(String[] args) {
		String in = "10?";
		produce(in.toCharArray(), 0, new String());
		in = "01?0?";
		produce(in.toCharArray(), 0, new String());
	}
	
}

- Guru June 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

import java.util.Arrays;


public class WildCardsFor1Or0 {

public static void main(String[] args) {
int n=0;
String value="?1?1??";
String[] s=value.split("\\?+");
String input="";
for(int i=0;i<value.length();i++){
if(value.charAt(i)=='?'){
input+="0";
}
}
double Qcount=Math.pow(2,input.length());
System.out.println(value.replace("?", "0"));
StringBuffer temp=new StringBuffer(input);
for(int j=0;j<Qcount-1;j++){
for(int i=temp.length()-1;i>=0;i--){
if(temp.charAt(i)=='0'){
if(i==temp.length()){
temp.setCharAt(i, '1');
break;
}
else{
temp.setCharAt(i, '1');
int len=temp.length()-i;
for(int k=i+1;k<temp.length();k++){
temp.setCharAt(k, '0');
}
break;
}
}
}
String output="";
int innercount=0;
int innercount1=0;
for(int i=0;i<value.length();i++){
if(value.charAt(i)=='?'){
output+=temp.charAt(innercount);
innercount++;
}
else{
output+=value.charAt(i);
}
}
System.out.println(output);
}
}
}

- without recurssion and java collections July 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

import java.util.Arrays;


public class WildCardsFor1Or0 {

	public static void main(String[] args) {
		int n=0;
		String value="?1?1??";
		String[] s=value.split("\\?+");
		String input="";
		for(int i=0;i<value.length();i++){
			if(value.charAt(i)=='?'){
				input+="0";
			}
		}		
		double Qcount=Math.pow(2,input.length());
		System.out.println(value.replace("?", "0"));
		StringBuffer temp=new StringBuffer(input);
		for(int j=0;j<Qcount-1;j++){
			for(int i=temp.length()-1;i>=0;i--){
				if(temp.charAt(i)=='0'){
					if(i==temp.length()){
						temp.setCharAt(i, '1');
						break;
					}
					else{
						temp.setCharAt(i, '1');
						int len=temp.length()-i;
						for(int k=i+1;k<temp.length();k++){
							temp.setCharAt(k, '0');
						}
						break;
					}
				}
			}
			String output="";
			int innercount=0;
			int innercount1=0;
			for(int i=0;i<value.length();i++){
				if(value.charAt(i)=='?'){
					output+=temp.charAt(innercount);
					innercount++;
				}
				else{
					output+=value.charAt(i);
				}
			}
			System.out.println(output);
		}		
	}
}

- without recurssion and java collections July 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

import java.util.Arrays;


public class WildCardsFor1Or0 {

public static void main(String[] args) {
int n=0;
String value="?1?1??";
String[] s=value.split("\\?+");
String input="";
for(int i=0;i<value.length();i++){
if(value.charAt(i)=='?'){
input+="0";
}
}
double Qcount=Math.pow(2,input.length());
System.out.println(value.replace("?", "0"));
StringBuffer temp=new StringBuffer(input);
for(int j=0;j<Qcount-1;j++){
for(int i=temp.length()-1;i>=0;i--){
if(temp.charAt(i)=='0'){
if(i==temp.length()){
temp.setCharAt(i, '1');
break;
}
else{
temp.setCharAt(i, '1');
int len=temp.length()-i;
for(int k=i+1;k<temp.length();k++){
temp.setCharAt(k, '0');
}
break;
}
}
}
String output="";
int innercount=0;
int innercount1=0;
for(int i=0;i<value.length();i++){
if(value.charAt(i)=='?'){
output+=temp.charAt(innercount);
innercount++;
}
else{
output+=value.charAt(i);
}
}
System.out.println(output);
}
}
}

- without recurssion and java collections July 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

public static void getBitStrings(String s) {

		listPossibilities(s, "", 0);
	}

	public static void listPossibilities(String bitString, String currentString, int currentIndex) {

		int length = bitString.length();

		if (currentIndex == length) {

			System.out.println(currentString);
			return;
		}

		if (bitString.charAt(currentIndex) == '?') {

			listPossibilities(bitString, currentString + '0', currentIndex + 1);
			listPossibilities(bitString, currentString + '1', currentIndex + 1);
			return;
		} 

		listPossibilities(bitString, currentString + bitString.charAt(currentIndex), currentIndex + 1);
	}

- SK May 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

had the same solution in C#

private static void wildcardReplace(string source, string currentSource, int startIndex, ref List<string> permutation)
{
if (startIndex == source.Length)
{
permutation.Add(currentSource);
return;
}
if ('?' == source[startIndex])
{
wildcardReplace(source, currentSource + '0', startIndex + 1, ref permutation);
wildcardReplace(source, currentSource + '1', startIndex + 1, ref permutation);
return;
}
wildcardReplace(source, currentSource + source[startIndex], startIndex + 1, ref permutation);
}

- .netDecoder May 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

The wildcard positions have to be filled with all possible combination of 0 and 1. This can be done by backtracking but the best way is to check all numbers from 0 to 2^(total wildcard) - 1 and set 0 or 1 by checking its bit pattern.

Complexity is O(2^n) in worst case.

vector<string> wildcardFillUp(string bitStream) {
	vector<string> result;
	vector<int> positions;
	int cnt = 0;
	int len = bitStream.length();
	for(int i = 0; i < len; ++i) {
		if(bitStream[i] == '?') {
			positions.push_back(i);
			++cnt;
		}
	}
	int n = (1 << cnt) - 1;
	for(int i = 0; i <= n; ++i) {
		for(int idx = 0, k = cnt - 1; k >= 0; --k) {
			bool isSet = (bool) (i & (1 << k));
			bitStream[positions[idx++]] = isSet ? '1' : '0';
		}
		result.push_back(bitStream);
	}
	return result;
}

- Kaidul Islam May 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<string> produce(string p) {
    vector<string> res;
    if (p.empty()) return res;
    
    vector<int> wildcards;
    for (int i = 0; i != p.size(); ++i)
        if (p[i] == '?')
            wildcards.push_back(i);
    
    for (int i = 0; i != (1 << wildcards.size()); ++i) {
        string r(p);
        for (int j = 0; j != wildcards.size(); ++j) {
            r[wildcards[j]] = (i & (1 << j)) ? '1' : '0';
        }
        res.push_back(r);
    }
    return res;
}

int main() {
    string p;
    cout << "Enter pattern: ";
    getline (cin, p);
    vector<string> res = produce(p);
    
    for (int i = 0; i != res.size(); ++i) {
        cout << res[i] << endl;
    }
}

- Sergey May 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The question is to print all possible wild card 0/1 permutations?

- infinity May 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes

- .netDecoder May 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* modified find combination code.
concept: backtracking
call printCombination("01?1?0", new StringBuffer(),0);
*/
public static void printCombination(String str, StringBuffer buff, int index){

if(index==str.length()){
System.out.println(buff.toString());
return;
}else if(index > str.length()){
return;
}

if(str.charAt(index)=='?'){

buff.append('0');
printCombination(str,buff, index+1);
buff.setLength(buff.length()-1);

buff.append('1');
printCombination(str,buff, index+1);
buff.setLength(buff.length()-1);

}else{
buff.append(str.charAt(index));
printCombination(str,buff, index+1);
buff.setLength(buff.length()-1);
}

}

- bt May 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int main() {
	string s = "01?0?";
	vector<string> results;
	vector<int> indexes;
	results.push_back(s);
	
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '?') {
			indexes.push_back(i);
		}
	}
	wild_char_fillup(results, indexes);

	for (int i = 0; i < results.size(); i++) {
		cout << results[i] << endl;
	}
}


void wild_char_fillup(vector<string> &results, vector<int> &indexes) {
	for (int i = 0; i < indexes.size(); i++) {
		int size = results.size();
		for (int j = 0; j < size; j++) {
			string str = results[0];
			results.erase(results.begin());

			str = replace(str, indexes[i], '0');
			results.push_back(str);

			str = replace(str, indexes[i], '1');
			results.push_back(str);	
		}
	}

}

string replace(string str, int index, char c) {
	str[index] = c;
	return str;

}

- gungorbasa May 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def wildcard(wildcard_string):
    list_of_strings = []
    for c in wildcard_string:
        if not list_of_strings:
            if c == '?':
                list_of_strings.append('0')
                list_of_strings.append('1')
            else:
                list_of_strings.append(c)
        else:
            new_list_of_strings = []
            for string in list_of_strings:
                if c == '?':
                    new_list_of_strings.append(string + '0')
                    new_list_of_strings.append(string + '1')
                else:
                    new_list_of_strings.append(string + c)
                list_of_strings = new_list_of_strings
    return list_of_strings
            
print wildcard('01?0?')

- mukund1776 May 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

vector<string> wildcardMatch(string &s)
{
	int n = s.size(); vector<int> indexs; vector<string> ans;

	for (int i = 0; i < n; ++i) if (s[i] == '?') indexs.push_back(i);

	n = indexs.size();

	for (int mask = 0; mask < (1 << n); ++mask)
	{
		int tmp = mask;

		for (int i = 0; i < n; ++i, tmp >>= 1) s[indexs[i]] = (tmp & 1) ? '1' : '0';

		ans.push_back(s);
	}

	return move(ans);
}

- malinbupt May 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static List<String> produceFromWildCard(String input) {
	List<String> result = new LinkedList<String>();
	produceFromWildCard(input, result);
	return result;
}

static void produceFromWildCard(String input, List<String> result) {
	int indexWild = input.indexOf('?');
	if (indexWild < 0) {
		result.add(input);
		return;
	}
	produceFromWildCard(input.substring(0, indexWild) + "0"
					+ input.substring(indexWild + 1), result);
	produceFromWildCard(input.substring(0, indexWild) + "1"
					+ input.substring(indexWild + 1), result);
}

- mulli2 May 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void printPer(String s, int cursor) {
		if(cursor >= s.length()) {
			System.out.println(s);
			return;
		}
		
		if(s.charAt(cursor) == '?') {
			String s1 = s.substring( 0, cursor) + "1" + s.substring(cursor+1, s.length());
			String s2 = s.substring( 0, cursor) + "0" + s.substring(cursor+1, s.length());
			printPer(s1, cursor+1);
			printPer(s2, cursor+1);
		} else {
			printPer(s, cursor+1);
		}
	}
	
	public static void main(String[] args) {
		Permutation.printPer("01?0?", 0);
	}

- Minh Hoang May 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <string>
#include <iostream>

using namespace std;

void expand(std::string prefix, std::string suffix)
{
  if (suffix.length() == 0)
  {
    std::cout << prefix << std::endl;
    return;
  }
  else if (suffix[0] != '?')
    expand(prefix + suffix[0], suffix.substr(1));
  else 
  {
    expand(prefix + '1', suffix.substr(1));
    expand(prefix + '0', suffix.substr(1));
  }
}
int main() {
  string s = "01?0?";
  expand(string(""), s);
}

- murga May 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <string>
#include <iostream>

using namespace std;

void expand(std::string prefix, std::string suffix)
{
  if (suffix.length() == 0)
  {
    std::cout << prefix << std::endl;
    return;
  }
  else if (suffix[0] != '?')
    expand(prefix + suffix[0], suffix.substr(1));
  else 
  {
    expand(prefix + '1', suffix.substr(1));
    expand(prefix + '0', suffix.substr(1));
  }
}
int main() {
  string s = "01?0?";
  expand(string(""), s);
}

- murga May 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static List<string> GetBitString(string input)
{
var output = new List<string>();
var first = true;
foreach (var t in input)
{
if(first)
{
if (t == '?')
{
output.Add("1");
output.Add("0");
}
else
{
output.Add(t.ToString());
}
first = false;
continue;
}
if (t == '?')
{
var temp1 = new List<string>();
for (int i = 0; i < output.Count(); i++)
{
temp1.Add(output[i] + "1");
}
var temp2 = new List<string>();
for (int i = 0; i < output.Count(); i++)
{
temp2.Add(output[i] + "0");
}
output = temp1;
output.AddRange(temp2);
}
else
{
for (int i = 0; i < output.Count(); i++)
{
output[i] = output[i] + t;
}
}
}
return output;
}

- Omkar Panhalkar May 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static List<string> GetBitString(string input)
        {
            var output = new List<string>();
            var first = true;
            foreach (var t in input)
            {
                if(first)
                {
                    if (t == '?')
                    {
                        output.Add("1");
                        output.Add("0");
                    }
                    else
	                {
                      output.Add(t.ToString());
	                }
                    first = false;
                    continue;
                }
                if (t == '?')
                {
                    var temp1 = new List<string>();
                    for (int i = 0; i < output.Count(); i++)
                    {
                        temp1.Add(output[i] + "1");
                    }
                    var temp2 = new List<string>();
                    for (int i = 0; i < output.Count(); i++)
                    {
                        temp2.Add(output[i] + "0");
                    }
                    output = temp1;
                    output.AddRange(temp2);
                }
                else
	            {
                    for (int i = 0; i < output.Count(); i++)
			        {
			            output[i] = output[i] + t;
			        }
	            }
            }
            return output;
        }

- Omkar Panhalkar May 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <cstdlib>

using namespace std;
#include <stdio.h>
#include <string.h>

void print_wildcard(char *s, int i)
{
    if(s[i] == 0)
    {
        printf("%s\n", s);
        return;
    }
    if(s[i] == '?')
    {
        s[i] = '0';
        print_wildcard(s,i+1);
        s[i] = '1';
        print_wildcard(s,i+1);
        s[i] = '?';
    }
    else
    {
        print_wildcard(s,i+1);
    }  
}

void print_wildcard(char *in)
{
    char *temp = new char [strlen(in)+1];
    strcpy(temp,in);
    print_wildcard(temp,0);
    delete[] temp;
}

int main(int argc, char** argv) {

    print_wildcard("01?0?");
    
    return 0;
}

- Dr A.D.M. May 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def _helper(result, s, word, i, l):
	if i == l:
		result.append(word)
		return
	if s[i] == "0" or s[i] == "1":
		_helper(result, s, word+s[i], i+1, l)
	else:
		_helper(result, s, word+"0", i+1, l)
		_helper(result, s, word+"1", i+1, l)
	return result

def expand(expression):
	return _helper([], expression, "", 0, len(expression))

- zingcat May 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.List;

public class WildCardResolver {

public static List<String> resolveWildCardString(String input) {
int startFrom = 0;
int wildCardSize = 0;
List<Integer> wildCardIndexes = new ArrayList<Integer>();
List<String> output = new ArrayList<String>();
int currentIndex = -1;

while ((currentIndex = input.indexOf("?", startFrom)) != -1) {
++ wildCardSize;

wildCardIndexes.add(currentIndex);

startFrom = currentIndex + 1;
}

if (wildCardSize == 0) {
output.add(input);

return output;
}

List<String> result = new ArrayList<String>();
String temp = "";

getAllPermutations("01", wildCardSize, temp, output);

for (int i = 0; i < output.size(); ++i) {
char[] inputChars = input.toCharArray();
String possibleOutputItem = output.get(i);
char[] possibleOIChars = possibleOutputItem.toCharArray();

int possibleOICharsIndex = 0;

for (int j = 0; j < wildCardIndexes.size(); ++j) {
inputChars[wildCardIndexes.get(j)] = possibleOIChars[possibleOICharsIndex ++];
}

result.add(new String(inputChars));
}

return result;
}


public static void getAllPermutations(String input, int size, String temp, List<String> output) {
if (temp.length() >= size) {
output.add(temp);
} else {

for (int i = 0; i < input.length(); ++i) {
String newTemp = temp + input.charAt(i);

getAllPermutations(input, size, newTemp, output);
}
}
}

public static void main(String[] args) {
List<String> output = resolveWildCardString("01?0?");


for (String item : output) {
System.out.println(item);
}
}
}

- Good Maker May 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

here is a simple solution

void printPattern(const string& s, string& buf, int i){
	if (i >= s.size()){
		cout << buf << endl;
		return;
	}

	if (s[i] == '?' ){
		for (int k = 0; k <= 1; k++){
			buf[i] = '0' + k;
			printPattern(s, buf, i + 1);
		}
	}
	else{
		buf[i] = s[i];
		printPattern(s, buf, i + 1);
	}
}

void printPattern(const string& s){
	string buf;
	buf.resize(s.size());

	printPattern(s, buf, 0);
}

- LaithBasilDotNet May 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In C:

#include <stdio.h>
#include <string.h>

void wildcard(char *s, int idx)
{
    int i;
    for (i=idx; i < strlen(s); i++)
    {
        if (s[i] == '?')
        {
            s[i] = '0';
            wildcard(s, i+1);
            s[i] = '1';
            wildcard(s,i+1);
            s[i]='?';
            return;
        }
    }
    printf("\n-->%s", s);
}

int main()
{
    char s[] = "01?0?";
    printf("\n Input string: %s", s);
    wildcard(s,0);
    getchar();
    return 1;
}

- xs2xa May 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In C:

#include <stdio.h>
#include <string.h>

void wildcard(char *s, int idx)
{
    int i;
    for (i=idx; i < strlen(s); i++)
    {
        if (s[i] == '?')
        {
            s[i] = '0';
            wildcard(s, i+1);
            s[i] = '1';
            wildcard(s,i+1);
            s[i]='?';
            return;
        }
    }
    printf("\n-->%s", s);
}

int main()
{
    char s[] = "01?0?";
    printf("\n Input string: %s", s);
    wildcard(s,0);
    getchar();
    return 1;
}

- xs2xa May 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In C:

#include <stdio.h>
#include <string.h>

void wildcard(char *s, int idx)
{
    int i;
    for (i=idx; i < strlen(s); i++)
    {
        if (s[i] == '?')
        {
            s[i] = '0';
            wildcard(s, i+1);
            s[i] = '1';
            wildcard(s,i+1);
            s[i]='?';
            return;
        }
    }
    printf("\n-->%s", s);
}

int main()
{
    char s[] = "01?0?";
    printf("\n Input string: %s", s);
    wildcard(s,0);
    getchar();
    return 1;
}

- xs2xa@ymail.com May 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Has the benefit of not creating extra interim objects at every level in the function call stack. Runtime: O(n^2), memory O(n) of which is only consumed by the function call stack and only for each '?'.

public static void getPerms(String str){
    if(str == null){
        throw new NullPointerException();
    }

    Worker worker = new Worker(str);
    worker.work();
}

public static class Worker{
    private char[] arr;
    private StringBuilder line;
    private int index;
    
    public Worker(String str){
        this.arr = str.toCharArray();
        this.line = new StringBuilder();
        this.index = 0;
    }

    public void work(){
        while(this.index < this.arr.length){
            if(this.arr[this.index] == '?'){
                this.arr[this.index] = '0';
                this.index++;
                this.work();
                this.arr[this.index -1] = '1';
                this.work();
                this.index--;
                this.arr[this.index] = '?';
                return;
            }
            this.index++;
        }
        this.print();
    }

    private void print(){
        this.line.setLength(0);
        for(int i = 0; i < this.arr.length; i++){
            line.append(this.arr[i]);
        }
        java.lang.System.out.println(line.toString());
    }
}

- zortlord May 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<string>
using namespace std;
void printAll(int start,const string& st) {
static string ss;
if(start==0)
ss=st;
int l=ss.length();
int i=start;
while( (ss[i]!='?') && i<l)
i++;
if(i<l) {
ss[i]='0';
printAll(i+1,st);
ss[i]='1';
printAll(i+1,st);
ss[i]='?';
} else
cout<<ss<<endl;
}
int main() {
string str="01?0?";
printAll(0,str);
}

- montreal6 June 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void combine(String in) {
		// TODO Auto-generated method stub
		int index = in.indexOf('?');
		if(index != -1)
		{
			System.out.println(in.substring(0, index) + "1" + in.substring(index+1));
			System.out.println(in.substring(0, index) + "0" + in.substring(index+1));
			combine(in.substring(0, index) + "0" + in.substring(index+1));
			combine(in.substring(0, index) + "1" + in.substring(index+1));
		} else {
			return;
		}
	}

- udaykumarbpatel July 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I solve this problem with an odometer approach, the number of '?' determine the length of the odometer, I use an array to manage/store the odometer. A StringBuilder is used to generate the resulting strings. To modify the StringBuilder I use a second array that store the indexes to modify (C# implementation)

public List<string> ParseWildcard(string s)
{
	List<string> result = new List<string>();
	List<int> indexes = new List<int>();
	List<int> odometer = new List<int>();
	StringBuilder sb = new StringBuilder();

	for (int i = 0; i < s.Length; i++)
	{
		if (s[i] == '?')
		{
			indexes.Add(i);
			odometer.Add(0);
			sb.Append('0');
		}
		else
			sb.Append(s[i]);
	}

	if (odometer.Count == 0)
	{
		result.Add(s);
		return result;
	}

	
	bool lastChanged = false;
	int lastIndex = odometer.Count - 1;

	while (!lastChanged)
	{
		result.Add(sb.ToString());

		int i = 0;
		int j = i - 1;

		while (i != j && i <= lastIndex)
		{
			j = i;
			odometer[i] = (odometer[i] + 1) % 2;

			if (odometer[i] == 0)
			{
				lastChanged = i == lastIndex;
				i++;
			}

			sb[indexes[j]] = (char)(odometer[j] + 48);
		}
	}

	return result;
}

// Test Code

//string s = "010010";
//string s = "01?";
string s = "01?0?";
var result = ParseWildcard(s);
foreach (var item in result)
	Console.WriteLine(item);

- hnatsu July 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;


public class WildCardsFor1Or0 {

public static void main(String[] args) {
// TODO Auto-generated method stu

int n=0;

String value="?1?1??";

String[] s=value.split("\\?+");
//System.out.println(Arrays.toString(s));

String input="";
for(int i=0;i<value.length();i++){
if(value.charAt(i)=='?'){

input+="0";
}
}
double Qcount=Math.pow(2,input.length());
System.out.println(value.replace("?", "0"));
StringBuffer temp=new StringBuffer(input);

for(int j=0;j<Qcount-1;j++){


for(int i=temp.length()-1;i>=0;i--){

if(temp.charAt(i)=='0'){

if(i==temp.length()){

temp.setCharAt(i, '1');
break;
}
else{
temp.setCharAt(i, '1');
int len=temp.length()-i;
for(int k=i+1;k<temp.length();k++){

temp.setCharAt(k, '0');
}
break;
}
}


}

String output="";
int innercount=0;
int innercount1=0;

for(int i=0;i<value.length();i++){


if(value.charAt(i)=='?'){

output+=temp.charAt(innercount);
innercount++;

}
else{

output+=value.charAt(i);

}
}

System.out.println(output);

}





}


}

- Without using recursive call and collections July 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;


public class WildCardsFor1Or0 {

public static void main(String[] args) {
// TODO Auto-generated method stu

int n=0;

String value="?1?1??";

String[] s=value.split("\\?+");
//System.out.println(Arrays.toString(s));

String input="";
for(int i=0;i<value.length();i++){
if(value.charAt(i)=='?'){

input+="0";
}
}
double Qcount=Math.pow(2,input.length());
System.out.println(value.replace("?", "0"));
StringBuffer temp=new StringBuffer(input);

for(int j=0;j<Qcount-1;j++){


for(int i=temp.length()-1;i>=0;i--){

if(temp.charAt(i)=='0'){

if(i==temp.length()){

temp.setCharAt(i, '1');
break;
}
else{
temp.setCharAt(i, '1');
int len=temp.length()-i;
for(int k=i+1;k<temp.length();k++){

temp.setCharAt(k, '0');
}
break;
}
}


}

String output="";
int innercount=0;
int innercount1=0;

for(int i=0;i<value.length();i++){


if(value.charAt(i)=='?'){

output+=temp.charAt(innercount);
innercount++;

}
else{

output+=value.charAt(i);

}
}

System.out.println(output);

}





}


}

- Without using recursive call and collections July 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
// TODO Auto-generated method stu

int n=0;

String value="?1?1??";

String[] s=value.split("\\?+");
//System.out.println(Arrays.toString(s));

String input="";
for(int i=0;i<value.length();i++){
if(value.charAt(i)=='?'){

input+="0";
}
}
double Qcount=Math.pow(2,input.length());
System.out.println(value.replace("?", "0"));
StringBuffer temp=new StringBuffer(input);

for(int j=0;j<Qcount-1;j++){


for(int i=temp.length()-1;i>=0;i--){

if(temp.charAt(i)=='0'){

if(i==temp.length()){

temp.setCharAt(i, '1');
break;
}
else{
temp.setCharAt(i, '1');
int len=temp.length()-i;
for(int k=i+1;k<temp.length();k++){

temp.setCharAt(k, '0');
}
break;
}
}


}

String output="";
int innercount=0;
int innercount1=0;

for(int i=0;i<value.length();i++){


if(value.charAt(i)=='?'){

output+=temp.charAt(innercount);
innercount++;

}
else{
output+=value.charAt(i);

}
}
System.out.println(output);
}
}

- Without using recursive call and collections July 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{
int n=0;
String value="?1?1??";
String[] s=value.split("\\?+");
String input="";
for(int i=0;i<value.length();i++){
if(value.charAt(i)=='?'){
input+="0";
}
}
double Qcount=Math.pow(2,input.length());
System.out.println(value.replace("?", "0"));
StringBuffer temp=new StringBuffer(input);
for(int j=0;j<Qcount-1;j++){
for(int i=temp.length()-1;i>=0;i--){
if(temp.charAt(i)=='0'){
if(i==temp.length()){
temp.setCharAt(i, '1');
break;
}
else{
temp.setCharAt(i, '1');
int len=temp.length()-i;
for(int k=i+1;k<temp.length();k++){
temp.setCharAt(k, '0');
}
break;
}
}
}
String output="";
int innercount=0;
int innercount1=0;
for(int i=0;i<value.length();i++){
if(value.charAt(i)=='?'){
output+=temp.charAt(innercount);
innercount++;
}
else{
output+=value.charAt(i);
}
}
System.out.println(output);
}
}

- without using recurssion n java collections July 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;


public class WildCardsFor1Or0 {

public static void main(String[] args) {
int n=0;
String value="?1?1??";
String[] s=value.split("\\?+");
String input="";
for(int i=0;i<value.length();i++){
if(value.charAt(i)=='?'){
input+="0";
}
}
double Qcount=Math.pow(2,input.length());
System.out.println(value.replace("?", "0"));
StringBuffer temp=new StringBuffer(input);
for(int j=0;j<Qcount-1;j++){
for(int i=temp.length()-1;i>=0;i--){
if(temp.charAt(i)=='0'){
if(i==temp.length()){
temp.setCharAt(i, '1');
break;
}
else{
temp.setCharAt(i, '1');
int len=temp.length()-i;
for(int k=i+1;k<temp.length();k++){
temp.setCharAt(k, '0');
}
break;
}
}
}
String output="";
int innercount=0;
int innercount1=0;
for(int i=0;i<value.length();i++){
if(value.charAt(i)=='?'){
output+=temp.charAt(innercount);
innercount++;
}
else{
output+=value.charAt(i);
}
}
System.out.println(output);
}
}
}

- without using recurssion n java collections July 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

One more way

626 void print_wildcard(char *S, char *res, int i, int n) {
627 
628     if(i>n){
629         /*res[i] = S[i];*/
630         printf("%s\n", res);
631         return;
632     }
633 
634     if(S[i]!='?'){
635         res[i] = S[i];
636         print_wildcard(S, res, i+1, n);
637 
638     }else {
639         S[i] = '0';
640         res[i] = S[i];
641         print_wildcard(S, res, i+1, n);
642         S[i] = '1';
643         res[i] = S[i];
644         print_wildcard(S, res, i+1, n);
645         S[i] = '?'; //move the string back to the origial character
646     }
647

}

- vivekh September 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function binary_wildcard($s){
	$count = 0;
	for($i=0; $i<strlen($s); $i++){
		if($s[$i] == "?"){
			$count++;
		}
	}
	
	$combs = pow(2, $count);
	for($i=0; $i<$combs; $i++){
		$b = sprintf("%0" . $count . 'b', $i);
		$j=0;
		$k=0;
		$tmp = $s;
		for($j=0; $j<strlen($tmp); $j++){
			if($tmp[$j] == "?"){
				$tmp[$j] = $b[$k];
				$k++;
			}
		}
		echo $tmp . '<br/>';
	}
}

- oelsayed September 14, 2015 | Flag Reply


Add a Comment
Name:

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

Books

is a comprehensive book on 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