Google Interview Question for Developer Program Engineers


Country: United States
Interview Type: In-Person




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

No Recursion needed.

Complexity: O(n) * no of combinations

The simplest way to solve this is to consider the number of diff combinations (num_of_comb) and representing that in binary starting from 0 to (num_of_comb - 1).

Ex a?b?c? has 8 comb. i.e 2^3 . i.e. 2 power no of '?'s. Obviously the possible combinations are 000, 001, 010, ..... 110, 111.

Complexity: O(n) * no of combinations.
O(n) to find no of '?'s.

Down below is the complete working code with minor description along. Comment if you can improvise further.

#include <iostream>
#include <cmath>
using namespace std;


void stringReplace ( char *str )
{
  char *temp = str;
  int count = 0, num_of_comb = 0, value = 0;

  while ( *temp ) {
    if ( *temp == '?' )
      count++;
    temp++;
  }
  temp = str;

  num_of_comb = pow(2,count);       // count the num of combinations
  cout << "There are " << num_of_comb << " different possible combinations";

  while ( value < num_of_comb ) {
    cout << endl;
    int calc = value;

    /* use the standard Math to convert num to its binary form, modify its output to the present context" */
    while ( *temp ) {
      if ( *temp == '?' ) {
        char ch = ( calc % 2 ) ? '1' : '0';
        calc /= 2;
        cout << ch << flush;  // do use 'flush' instead of unwanted 'newline' on Linux console to flush the buffer
      }

      else cout << *temp << flush;

      temp++;
    }

    temp = str;
    value++;
  }
}


int main ()
{
  char A[] = "????";      // makes it easy to see the combinations. You could obviously add letters
  stringReplace(A);
  while (1);
}

- Orion arm, Laniakea September 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How is this O(n) + k ? Its more like O(k.N)

- Anonymous September 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

My bad, thanks noted and edited.

- Orion arm, Laniakea September 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your code doesn't work when count of '?' exceeds 31. In general, we could use big integers to represent current values. (Not sure if it's possible to use GMP on interview).

- manykey March 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The only problem that I see here is that you have to recompute the String every single time and you don't save any results between. This may be a problem, because you are doing it (2^n) times where n is the number of '?'.
I think this can be improved a little bit and done in a simpler way by storing last permutation of the string and remembering which '?' we are dealing with now. You only need O(n) memory to memoize the '?' positions in the array to speed it up, but you may save time (not complexity, it's 2^n still). I will write my own answer with my solution, maybe somebody will be interested.

- mbriskar June 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 4 vote

public static void replace(String str, int pos) {
		if (pos == str.length()) {
			System.out.println(str);
		}
		else if (str.charAt(pos) != '?'){
			replace(str, pos+1);
		}
		else {
			String prefix = str.substring(0, pos);
			String suffix = str.substring(pos+1);
			replace(prefix + "0" + suffix, pos+1);
			replace(prefix + "1" + suffix, pos+1);
		}
	}
	
	public static void replace(String str) {
		replace(str, 0);
	}

- valakaka May 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

Why did this get downvoted? It's correct.

- Anonymous May 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Too much unnecessary recursion I guess. You can actually skip some recursions by directly copying those letters before next "?" prefix.

- jonoson August 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 4 vote

import java.util.ArrayList;


public class ReplaceQuestionMark {
    public ArrayList<String> replace(String target){
        return replaceHelper(target, target.length()-1);
    }

    public ArrayList<String> replaceHelper(String target, int to){
        char c = target.charAt(to);
        if (to == 0){
            ArrayList<String> res = new ArrayList<String>();
            if (c == '?'){
                res.add("0");
                res.add("1");
            }
            else{
                res.add(c+"");
            }
            return res;
        }
        ArrayList<String> res = new ArrayList<String>();
        ArrayList<String> preRes = replaceHelper(target, to-1);
        if (c == '?'){
            for (String token: preRes){
                res.add(token + "0");
                res.add(token + "1");
            }
        }
        else{
            for (String token: preRes){
                res.add(token + c);
            }
        }
        return res;
    }

    public static void main(String[] args){
        ReplaceQuestionMark rqm = new ReplaceQuestionMark();
        ArrayList<String> res = rqm.replace("a?b?c?");
        for (String s: res){
            System.out.println(s);
        }
    }
}

- Anonymous May 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

When I saw this question, the first way I can think of is to use recursion. It's good that you remind me that I could also choose not to use recursion.

- ravio June 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Recursion is not so good if you'll try to find all combinations for a long string like "a?b?c?d?a?b?c?da?b?c?da?b?c?da?b?c?da?b?c?da?b?c?da?b?c?da?b?c?d". You'll probably get an "out of memory".

- maks1m June 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@ravio : This code is using recursion. The helper function replaceHelper is actually called recursively!

- Nomad June 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If the string is "a?b?c", then this code will return : "a01b01c" instead of all the possible combinations. Looks incorrect to me

- UV March 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If the string is "a?b?c", then this code will return : "a01b01c" instead of all the possible combinations. Looks incorrect to me

- UV March 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

function doReplace(str) {
    if(str.indexOf('?') === -1) {
        return [str];
    } else {
        return []
            .concat(doReplace(str.replace(/(\?)/, '0')))
            .concat(doReplace(str.replace(/(\?)/, '1')));
    }
}

- Anonymous May 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

void Print(char p[], size_t len)
{
	for (int i = 0; i < len; ++i)
	{
		cout << p[i];
	}
	cout << endl;
}

bool Replace(char p[], size_t cur, char ch, size_t len)
{
	size_t pos = cur;
	for (; pos < len; ++pos)
	{
		if (p[pos] == '?')
		{
			break;
		}
	}
	if (pos < len)
	{
		p[pos] = ch;
		if (Replace(p, pos + 1, '0', len))
		{
			Replace(p, pos + 1, '1', len);
		}
		p[pos] = '?';
		return true;
	}
	else
	{
		Print(p, len);
		return false;
	}
}
void Replace(char p[], size_t len)
{
	if (Replace(p, 0, '0', len))
	{
		Replace(p, 0, '1', len);
	}

}

- Anonymous May 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Tail recursive version in Scala:

import scala.util.matching.Regex._

val pattern = """([^?]*)\?""".r

def generate(text: String): List[String] = {
  val tokens = pattern.findAllMatchIn(text).toList.reverse
  if (tokens.isEmpty) {
    List(text)
  } else {
    val tail = text.drop(tokens.head.end)
    def helper(tokens: List[Match], acc: List[List[String]]): List[List[String]] = tokens match {
      case Nil => acc
      case token :: tail =>
        val text = token.group(1)
        helper(tail, (for (str <- acc) yield {
          List(text :: "0" :: str, text :: "1" :: str)
        }).flatten)
    }
    for (prefix <- helper(tokens, List(List("")))) yield {
      (prefix.iterator ++ tail).mkString("")
    }
  }
}

for (text <- List("aa?bb?cc", "aa?", "?aa", "aa", "?", "??", ""))
{
  println("Text: " + text)
  println(generate(text))
  println()
}

- Oleg June 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

well you can try something like this....

String str = "a?b?c?";
 char[] arr = str.toCharArray();
 int occurrence = 0;
 List<Integer> index = new ArrayList<>();
 for (int i = 0; i < arr.length; i++) {
   if ('?' == arr[i]) {
       occurrence++;
       index.add(i);
      }
   }
 double twosPow = Math.pow(2, occurrence);
 List<String> list = new ArrayList<>();
 for (double i = 0; i < twosPow; i++) {
    int k = (int) i;
    String val = String.format("%" + occurrence + "s",
                              Integer.toBinaryString(k)).replace(" ", "0");
            list.add("" + val); // take binary
    }
 String replace = null;
 StringBuilder sb = null;
 List<String> result=new ArrayList<>();
 for (String i : list) {
     sb=new StringBuilder();
     sb.append(str);
     int p = 0;
     for (Integer k : index) {
          sb.replace(k, k+1, "" + i.charAt(p));
          p++;
         }              
          result.add(sb.toString());
        }
  System.out.println(result);

and the out put would be as..

[a0b0c0, a0b0c1, a0b1c0, a0b1c1, a1b0c0, a1b0c1, a1b1c0, a1b1c1]

- Anonymous September 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

public static void doReplace(String data){
long x = 0;
while(data.indexOf('?')>-1){
data = data.replaceFirst("\\?", "%s");
x++;
}

long max = (long)Math.pow(2, x);
if(max>1){
for(int i=0; i<max; i++){

String[] items = String.format("%"+x+"s",Integer.toBinaryString(i))
.replace(" ", "0")
.split("");

System.out.println(
String.format(data,
Arrays.copyOfRange(items,1,items.length)
)
);
}
}else{
System.out.println(data);
}

}

- Anonymous May 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes
Very nice idea with format. And code is so laconic. But you should use "{{{", without it code is not highlighted and its hard to read. - maks1m June 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

And i tried to run it and get an error then i replaced Arrays.copyOfRange(items,1,items.length) with items and everything works fine.

- maks1m June 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

My algorithm is similar to yours but i use explicit bitwise operations and on big data my algo is about 30 times faster.

- maks1m June 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the recursive approach:

void removeQm(char *s,int ind,int len)
{
	if(ind==len)
		return;
	if(s[ind]!='0'||s[ind]!='1')
	{
		ind=ind+1;
		removeQm(s,ind,len);
	}
	if(s[ind]=='0')
	{
		s[ind]='1';
		for(int i=0;i<len;i++)
			printf("%c",s[i]);
		printf("\n");	
		ind=ind+1;
		removeQm(s,ind,len);
	}
	if(s[ind]=='1')
	{
		s[ind]='0';
		for(int i=0;i<len;i++)
			printf("%c",s[i]);
		printf("\n");	
		ind=ind+1;
		removeQm(s,ind,len);
	}
		
}
int main()
{
	char s[]="a?b?c?d?";
	int len=strlen(s);
	for(int i=0;i<len;i++)
	{
		if(s[i]=='?')
			s[i]='0';
	}
	for(int i=0;i<len;i++)
		printf("%c",s[i]);
	printf("\n");
	removeQm(s,0,len);
}

- vgeek May 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void Print(char p[], size_t len)
{
for (int i = 0; i < len; ++i)
{
cout << p[i];
}
cout << endl;
}

bool Replace(char p[], size_t cur, char ch, size_t len)
{
size_t pos = cur;
for (; pos < len; ++pos)
{
if (p[pos] == '?')
{
break;
}
}
if (pos < len)
{
p[pos] = ch;
if (Replace(p, pos + 1, '0', len))
{
Replace(p, pos + 1, '1', len);
}
p[pos] = '?';
return true;
}
else
{
Print(p, len);
return false;
}
}
void Replace(char p[], size_t len)
{
if (Replace(p, 0, '0', len))
{
Replace(p, 0, '1', len);
}
}

- Anonymous May 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

One way of doing this is to generate the bits in-place and print the string once all the ‘?’ are replaced appropriately.

public static void printString (StringBuilder s, ArrayList<Integer> spots, int j){

	if (j==spots.size()){
		System.out.println(s.toString());
		return;
	}
	
	StringBuilder t = new StringBuilder ();
	char c=’0’;

	for (int i=0;i<2;i++){
		t.append(s.substring(0,spots.get(j)));
		t.append(c);
		t.append(s.substring(spots.get(j)+1));
		printString (t, spots, j+1);
		t.delete(0,t.length());
		c = ‘1’;
	}

}

public static void printString (StringBuilder s){
	ArrayList<Integer> spots = new ArrayList<Integer>();
	StringBuilder gen = new StringBuilder ();
	
	for (int i=0;i<s.length();i++)
		if (s.charAt(i) == ‘?’)
			spots.add(i);

	printString (s, spots, 0);
}

- Bhaskar May 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Below is java code:

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

public class StringReplace {
	
	public void replace(String string){
		
		List<Integer> questionMarkIndexList=new ArrayList<Integer>();
		for(int i=0;i<string.length();i++){
			if(string.charAt(i)=='?'){
				questionMarkIndexList.add(i);
			}
		}
		
		StringBuffer sb=new StringBuffer(string);
		
		doReplace(sb,questionMarkIndexList,0);
	}
	
	private void doReplace(StringBuffer sb,List<Integer> questionMarkIndexList ,int index){
		if(index>=questionMarkIndexList.size()){
			System.out.println(sb);
			return;
		}
		
		int questionMarkIndex=questionMarkIndexList.get(index);
		
		sb.setCharAt(questionMarkIndex, '0');
		doReplace(sb,questionMarkIndexList,index+1);
		
		sb.setCharAt(questionMarkIndex, '1');
		doReplace(sb,questionMarkIndexList,index+1);
		
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String s="a?b?c?";
		
		StringReplace sr=new StringReplace();
		sr.replace(s);

	}

}

- xiaofan May 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is simple combinatorial algo

Print(string s)
{
       
       int ind = s.IndexOf('?');
       if(ind < 0)
        { 
           System.Out.Print(s);
	   return;
         }
       Print(s.Replateat(ind, '0');
  
       Print(s.Replaceat(ind, '1');
       
}

- vikas May 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static List<string> Replace (string s)
        {
            var result = new List<string>(); 

            if (s == null)
                throw new ArgumentNullException();

            if (s.Length == 0)
                return result; 

            if (s.Length == 1)
            {
                if (s[0] == '?')
                    return new List<string> { "0", "1" };
                else
                    return new List<string> { s }; 
            }

            var items = s.Substring(1).Contains("?") ? Replace(s.Substring(1)) : new List<string> { s } ;
            foreach (var item in items)
            {
                if (s[0] == '?')
                {
                    result.Add(item.Insert(0, "0"));
                    result.Add(item.Insert(0, "1"));
                }
                else
                    result.Add(item.Insert(0, s[0].ToString()));
            }

            return result;
        }

- Anonymous June 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import itertools,re

def generate_possible_strings(s, c):
    """
    :param s: input string
    :param c: matching character in our scenario ?
    returns : iterator by generating all possible results yields or None :
    """
    if re.search(c,s) == None:
        return
    rr = list(s)
    l_index, index_map = find_qm(s,c)
    # the possible combinations are all the subsets from 0 to 2**n-1
    for r in range(2**l_index):
        q = bin(r)[2:].zfill(l_index)
        for i, x in enumerate(q):
            rr[index_map[i]] = x
        yield ''.join(rr)

def find_qm(s,c):
    """
    :param s: input string
    :param c: matching character
    :return: a dictionary with the indexes for c in the string
    """
    index_map = {}
    for i, x in enumerate([m.start() for m in re.finditer(c, s)]):
        index_map[i] = x
    return len(index_map), index_map


if __name__ =='__main__':
    for r in generate_possible_strings(' a?b?c?tt?uu?','\?'):
        print r,

- jk June 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class TestBuildGivenString {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		char a[] = "a?bc?def?g".toCharArray();
		printAllString(a, 0);
	}

	public static void printAllString(char[]a,int start)
	{
		int end = a.length-1;
		if(start >= end)
		{
			printArray(a);
			return;
		}
		
		for(int i=start;i<=end;i++)
		{
			if(a[i] == '?')
			{
				for(int j=0;j<=1;j++)
				{
					
						a[i] = (j+"").toCharArray()[0];
						printAllString(a, i+1);
						if(a[i] == '0' || a[i] == '1')
							a[i] = '?';
					
				}
				break;
			}
		
		}
	}
	
	public static int getLastIndex(char[]a,char c)
	{
		for(int i = a.length-1;i>=0;i--)
		{
			if(a[i] == c)
			{
				return i;
			}
		}
		
		return -1;
	}
	
	public static void printArray(char[]a)
	{
		StringBuffer buffer =  new StringBuffer();
		
		for(char c:a)
		{
			buffer.append(c);
		}
		System.out.println(buffer.toString());
		
	}
}

- yuwenbao June 01, 2014 | 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 Replaceby0and1 {

public static void main(String[] args) {
String test = "a?b?ab?";
List<String> replacedStrings = replace(test);
for (String temp : replacedStrings) {
System.out.println(temp);
}

}

private static List<String> replace(String test) {

List<String> replacedStrings = new ArrayList<>();

if (test.indexOf('?') == -1) {
replacedStrings.add(test);
return replacedStrings;
} else {

if (test.length() == 0) {
replacedStrings.add(test);
return replacedStrings;
} else if (test.length() == 1) {
if (test.equals("?")) {
replacedStrings.add("0");
replacedStrings.add("1");

} else {
replacedStrings.add(test);
}
return replacedStrings;
} else {

List<String> replacedSubStrings = new ArrayList<>();
replacedSubStrings = replace(test.substring(1, test.length()));
if (test.charAt(0) == '?') {
for (String temp : replacedSubStrings) {
replacedStrings.add('0' + temp);
replacedStrings.add('1' + temp);
}

} else {
for (String temp : replacedSubStrings) {
replacedStrings.add(test.charAt(0) + temp);

}
}

return replacedStrings;
}

}
}

}

- Bhagrav June 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void replaceChars(String s)
	{
		if((s==null)||(s.length()==0))
		{
			return;
		}
		int count=0;
		for(int i=0;i<s.length();i++)
		{
			if(s.charAt(i)=='?')
			{
				count++;
			}
		}
		if(count>0)
		{
			replaceWithPermutations(s,count,0);
		}
	}
	
	public static void replaceWithPermutations(String str, int count, int i)
	{
		if(count==0)
		{
			System.out.println(str);
		}
		else
		{
			if(str.charAt(i)=='?')
			{
				str = str.substring(0,i)+0+str.substring(i+1,str.length());
				replaceWithPermutations(str,count-1,i+1);
				str = str.substring(0,i)+1+str.substring(i+1,str.length());
				replaceWithPermutations(str,count-1,i+1);
			}
			else
			{
				replaceWithPermutations(str,count,i+1);
			}
		}

}

- GReeky June 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

char *glob_str;
void rep_qm(char *inStr, int len);

int main(int argc, char* argv[])
{
  char* inStr;

  if(argc != 2)
  {
    printf("Usage: ./replace_qm <string>\n");
    return 0;
  }

  glob_str = inStr = argv[1];

  printf("Input String: %s\n", inStr);

  printf("Output Strings are: \n");
  rep_qm(inStr, strlen(inStr));

  return 0;
}

void rep_qm(char *inStr, int len)
{
  int i;

  //printf("rep_qm: str[%s] len[%d]\n", inStr, len);
  for(i=0;i<=len;i++)
  {
    if(inStr[i] == '?')
    {
      /*Replace the '?' with 0 first and continue for the remaining substring*/
      inStr[i] = '0';
      rep_qm((char *)&inStr[i+1], (len - i - 1));

      /*Then replace it with 1 and continue with remaining substring */
      inStr[i] = '1';
      rep_qm((char *)&inStr[i+1], (len - i - 1));

      /*Once done with every thing, replace the changed character back to '?' so that the position is not missed*/
      inStr[i] = '?';
        return;
    }
  }

  printf("%s\n",glob_str);

}

- CCoder June 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void replaceMarkWith0and1(String str) {
        if (str == null) {
            throw new NullPointerException("Parameter passed is null");
        }

        if (str.isEmpty()) {
            System.out.println("String is empty");
            return;
        }

        char[] carray = str.toCharArray();
        printWithMark(carray, 0);
    }

    private void printWithMark(char[] str, int current) {
        if (str == null) {
            throw new NullPointerException("Parameter str is null");
        }

        if (current == str.length) {
            System.out.println(new String(str));
            return;
        }

        if (str[current] == '?') {
            str[current] = '0';
            printWithMark(str, current + 1);
            str[current] = '1';
            printWithMark(str, current + 1);
            str[current] = '?';
        } else {
            current++;
            printWithMark(str, current);
        }
    }

- Victor June 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive Program in Java:
public class ReplaceQuestionMark
{
public static void main(String[] args) {
String input = "a?b?c?";
replace(input.toCharArray());
}
public static void replace(char[] input) {
boolean found = false;
for(int i=0;i<2;i++) {
int foundAt = 0;
for(int j=0;j<input.length;j++) {
if(input[j] == '?') {
foundAt = j;
found = true;
break;
}
}
if(found) {
input[foundAt] = (char)(i + 48);
replace(input);
input[foundAt] = '?';
foundAt = 0;
}
else {
System.out.println(input);
return;
}
}
}
}

- Sourabh Das June 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive program in Java:

public class ReplaceQuestionMark {
	public static void main(String[] args) {
		String input = "a?b?c?";
		replace(input.toCharArray());
	}
	public static void replace(char[] input) {
		boolean found = false;
		for(int i=0;i<2;i++) {
			int foundAt = 0;
			for(int j=0;j<input.length;j++) {
				if(input[j] == '?') {
					foundAt = j;
					found = true;
					break;
				}
			}
			if(found) {
				input[foundAt] = (char)(i + 48);
				replace(input);
				input[foundAt] = '?';
				foundAt = 0;
			}
			else {
				System.out.println(input);
				return;
			}
		}
	}
}

- Sourabh Das June 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think my code will works.

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

class Replace
{
private int[] number;
private List<Integer> indexlist;
char[] thestring;

public Replace(String s)
{
indexlist = new LinkedList<Integer>();
thestring = s.toCharArray();
int count = 0;
for(int i=0; i<thestring.length; i++)
{
if(thestring[i] == '?')
{
count++;
}
}

number = new int[count];

for(int i=0; i<count; i++)
{
number[i] = 0;
}

for(int i = 0; i<thestring.length; i++)
{
if(thestring[i] == '?')
{
indexlist.add(i);
}
}

}

public void output(char[] a)
{
System.out.println(a);
}

public void RemoveQ(int[] array, int start, int end)
{
if(start == end)
{
char[] result = new char[thestring.length];
int i = 0;
result = thestring.clone();
Iterator<Integer> iter = indexlist.iterator();
while(iter.hasNext())
{
result[iter.next()] = (char)(array[i]+48);
i++;
}

output(result);
return;
}
else
{
array[start] = 0;
RemoveQ(array, start+1, end);
array[start] = 1;
RemoveQ(array, start+1, end);
}
}


public void run()
{
int[] temp = new int[number.length];
temp = number.clone();
RemoveQ(temp, 0, temp.length);
}

}






public class Main {

public static void main(String args[])
{
Scanner in = new Scanner(System.in);
String instring = in.nextLine();
in.close();
Replace R = new Replace(instring);
R.run();
}

}

- gzyeli123 June 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think my code will works.

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

class Replace
{
private int[] number;
private List<Integer> indexlist;
char[] thestring;

public Replace(String s)
{
indexlist = new LinkedList<Integer>();
thestring = s.toCharArray();
int count = 0;
for(int i=0; i<thestring.length; i++)
{
if(thestring[i] == '?')
{
count++;
}
}

number = new int[count];

for(int i=0; i<count; i++)
{
number[i] = 0;
}

for(int i = 0; i<thestring.length; i++)
{
if(thestring[i] == '?')
{
indexlist.add(i);
}
}

}

public void output(char[] a)
{
System.out.println(a);
}

public void RemoveQ(int[] array, int start, int end)
{
if(start == end)
{
char[] result = new char[thestring.length];
int i = 0;
result = thestring.clone();
Iterator<Integer> iter = indexlist.iterator();
while(iter.hasNext())
{
result[iter.next()] = (char)(array[i]+48);
i++;
}

output(result);
return;
}
else
{
array[start] = 0;
RemoveQ(array, start+1, end);
array[start] = 1;
RemoveQ(array, start+1, end);
}
}


public void run()
{
int[] temp = new int[number.length];
temp = number.clone();
RemoveQ(temp, 0, temp.length);
}

}






public class Main {

public static void main(String args[])
{
Scanner in = new Scanner(System.in);
String instring = in.nextLine();
in.close();
Replace R = new Replace(instring);
R.run();
}

}

- gzyeli123 June 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple and concise recursive solution in Java.

public class PrintStrings {

    public static void main(String... args) {
        printStrings("a?bc?def?g");
    }

    private static void printStrings(String str) {
        printStrings(str, 0);
    }

    private static void printStrings(String str, int pos) {
        if (pos == str.length() - 1) {
            System.out.println(str);
            return;
        }

        for (; pos < str.length(); ++pos) {
            if (str.charAt(pos) == '?') {
                byte[] chars = str.getBytes();
                chars[pos] = '0';
                printStrings(new String(chars), pos + 1);
                chars[pos] = '1';
                printStrings(new String(chars), pos + 1);
                break;
            }
        }
    }
}

- Diego Giagio June 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#!/usr/bin/python 
import itertools

text = 'ab?c?d?efg?'

def char_replace(string=""):
    count = string.count('?')
    snaps =  list(itertools.product(['0','1'],repeat=count)) 
    lst =[]
    #print snaps
    for snip in snaps:
        txt = list(string)
        for c in xrange(count):
            txt[txt.index('?')]=snip[c]
        lst.append("".join(txt))
    return lst
for x in char_replace(text):
    print x

- wingles.angel4 June 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class careercup {
	private static String data = "a?bc?def?g";

	private static void get(int index, String counter) {
		if (index == data.length())
			System.out.println(counter);
		else if (data.charAt(index) == '?') {
			get(index + 1, "0" + counter);
			get(index + 1, "1" + counter);
		} else {
			get(index + 1, data.charAt(index) + counter);
		}
	}

	public static void main(String[] args) {
		get(0, "");
	}

}

- eng.mohamed.CSD2014 June 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You haven't backtracked. Will it work?

- Victor June 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here code in C using recursion.

- Sumit June 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Code in C using recursion

#include <stdio.h>
#include <stdlib.h>

static int N=0;
void generateComination( char *str ,int a[], int n){
  
     if(n ==0){ printf("%d->%s\n",++N,str);}
     else{
          str[a[n-1]]='0';
          generateComination(str,a,n-1);
          str[a[n-1]]='1';
          generateComination(str,a,n-1);
          }
          
     }
main(){
       char str[100];
       int i,j;
       int *ptr;
       int strlen=0,count=0,index=0;
       printf("Enter given string\n");
       scanf("%s",&str);
       printf("%s\n",str);
       i=0;
       while ( str[i] != '\0'){ i++; strlen++;}
       
      // printf("%d\n",strlen);
       for( i =0; i < strlen ; i++){  if(str[i] == '?')  count++; }
       //printf("%d\n",count);
       
       ptr=  (int *) malloc ( sizeof(int)* count);
       for( i =0; i < strlen ; i++){  
            if(str[i] == '?') { ptr[index++]= i;}
        }
       //for( i =0; i < index ; i++){ printf("%d",ptr[i]);}
       generateComination( str, ptr, count);
       
       int n;
       scanf("%d",&n);
}

- sumit June 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void generator(vector<string> &ret, string s, size_t cur){
	if(cur==s.size()){
		ret.push_back(s);
		return;
	}
	if(s[cur]=='?'){
		s[cur]='0';
		generator(ret, s, cur+1);
		s[cur]='1';
		generator(ret, s, cur+1);
	}
	else
		generator(ret, s, cur+1);
}
void wrapperFillQuestionMark(){
	vector<string> ret;
	generator(ret, "a?b?c?", 0);
	for(auto it = ret.begin(); it!=ret.end(); ++it)
		cout << *it << endl;
}

- Jason Ding June 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have two solutions. One with permutation and one without permutation using bitset.

#include "stdafx.h"
#include <iostream>
#include <string>
#include <set>
#include <bitset>

using namespace std;

set<string> perm;

void replace(string str, string strWith) {
int index = 0;
for(int i=0; i< str.length(); ++i) {
if(str[i] == '?') str[i] = strWith[index++];
}
cout << str << endl;
}

void parmutation(string str, string endStr) {
if(str.length() == 0) perm.insert(endStr);
for(size_t i = 0; i < str.length(); ++i) {
string StrIn = str;
string StrEnd = endStr;
StrIn.erase(i,1);
StrEnd += str.at(i);
parmutation(StrIn,StrEnd);
}
}

void replaceString(string str) {
perm.insert("0000");
parmutation("0001","");
parmutation("0011","");
parmutation("0111","");
perm.insert("1111");

for(auto it= perm.begin(); it != perm.end(); ++it) {
replace(str,*it);
}
}

void replaceWithPermutation(string str) {
for(int i=0; i< 16; ++i) {
bitset<4> bt(i);
replace(str,bt.to_string<char,string::traits_type,string::allocator_type>());
}
}

int main()
{
replaceString("a?b?c?d?");
cout << endl;
replaceWithPermutation("a?b?c?d?");
while(1) {}
return 0;
}

- vkbajoria June 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void print_str_combinatins(const char *str){
    const char *p = str;
    unsigned int c, i;
    for(c = 0; *p; p++){
        if(*p == '?')
            c = c<<1 | 1; 
    }
    for(;c != 0; c--){
        for(p = str, i=c; *p; p++){
            if(*p == '?'){
                printf("%d", (i & 1));
                i >>= 1;
            } else {
                printf("%c", *p);
            }
        }
        printf("\n");
    }
    for(p = str, i=c; *p; p++){
        printf("%c", *p=='?' ? 0x30 : *p);
    }
}

- nradsoft June 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about this code?

public class Integer2Binary {
	public static void main(String[] args) {
		String str = "a?bc?def?gh?ij";
		char[] charArr = str.toCharArray();
		int count = 0;
		for(char c : charArr) {
			if(c == '?') {
				count++;
			}
		}
		String newStr = null;
		for(int i = 0; i < Math.pow(2, count); i++) {
			String bin = Integer.toString(i, 2);
			newStr = str;
			//System.out.println(newStr);
			while(bin.length() != count) {
				bin = "0" + bin;
			}
			//System.out.println(bin);			
			//String binPart = bin.substring(bin.length() - count, bin.length());
			char[] binPartArr = bin.toCharArray();
			
			for(char c : binPartArr) {
				newStr = newStr.replaceFirst("\\?", "" + c + "");
				//System.out.println(newStr);
			}
			System.out.println(newStr);
		}
	}
}

- Ramana Reddy June 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

An iterative solution using bit manipulation (we want to replace the n ? with all the possible values of an n-bit vector).

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

void gen_replace(string s) {
    stringstream ss(s);
    vector<string> tokens;
    
    //parse input string
    string elem;
    while(!ss.eof()) {
        getline(ss, elem, '?');
        tokens.push_back(elem);
    }
    int n_gaps = tokens.size() - 1 ;
    int n_combinations = ( 1 << n_gaps ); 

    //print all combinations
    for (int i = 1; i <= n_combinations; ++i) {
        int j=0;
        for (; j < n_gaps; ++j) {
            cout << tokens[j] << ((i >> j) & 1 ); 
        }
        cout << tokens[j] << endl; //print last token
    }
}

- sylreboux June 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void ReplaceString(char* p, int index, int len)
{
    while (index < len && p[index] != '?')
        index++;

    if (index >= len)
    {
        printf("%s\n", p);
        return;
    }

    // we reached ? at index
    p[index] = '0';
    ReplaceString(p, index + 1, len);

    p[index] = '1';
    ReplaceString(p, index + 1, len);

    p[index] = '?';
}

int _tmain(int argc, _TCHAR* argv[])
{
    char s[] = "";
    ReplaceString(s, 0, strlen(s));
	return 0;
}

- m June 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static void generateValues(String s, int index) {
if (index == s.length()) {
System.out.println(s);
return;
}
for (int i= index; i < s.length(); i++) {
if (s.charAt(i) == '?') {
s = s.substring(0, i) + '0' + s.substring(i + 1);
generateValues(s, i + 1);
s = s.substring(0, i) + '1' + s.substring(i + 1);
generateValues(s, i + 1);
}
}
}

- Tyrian June 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static void generateValues(String s, int index) {
        if (index == s.length()) {
            System.out.println(s);
            return;
        }
        for (int i= index; i < s.length(); i++) {
            if (s.charAt(i) == '?') {
                s = s.substring(0, i) + '0' + s.substring(i + 1);
                generateValues(s, i + 1);
                s = s.substring(0, i) + '1' + s.substring(i + 1);
                generateValues(s, i + 1);
            }
        }
    }

- Tywin June 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<%
  # Ruby
  
  input = "a?b?c?d?e?f"
  @output = Array.new

  # replace ?'s with 0's
  input.gsub! "?", "0"
  @output << input

  # convert string to array and reverse
  @input_arr = input.chars.reverse

  # recursively iterate through array
  while idx_0 = @input_arr.index("0")
    @input_arr[idx_0] = "1"
    while idx_1 = @input_arr[0, idx_0].index("1")
      @input_arr[idx_1] = "0"
    end
    input = @input_arr.reverse.join
    @output << input
  end

  @output.join(", ")
%>

- Anonymous June 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;

public class ReplaceQuestionMarks {

	//returns null if none
	public static ArrayList<String> replace(String original)
	{
		ArrayList<String> out = new ArrayList<String>();
		replaceHelper(original, 0, out);
		return out;
	}

	private static void replaceHelper(String s, int i, ArrayList<String> out)
	{
		if (i == s.length()) {
			out.add(s);
			return;
		}
		// else
		char[] cs = s.toCharArray();
		if (cs[i] == '?') {
			cs[i] = '0';
			replaceHelper(String.valueOf(cs), i+1, out);
			cs[i] = '1';
			replaceHelper(String.valueOf(cs), i+1, out);
		}
		else {
			replaceHelper(s, i+1, out);
		}
		return;
	}

	public static void main(String[] args)
	{
		String s = new String("a?b??");
		ArrayList<String> all = replace(s);
		for (String t : all) {
			System.out.println(t);
		}
	}
}

- dblaalid June 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void replaceQnMarkByZeroOne(char *a,int i)
{
	if (a[i] == '\0')
	{
		puts(a);
		return ;
	}  
	while(a[i] != '?' )
	{
		i++;
		if(a[i] == '\0')
		 {
		 	puts(a); return;
		 } 
	
	}
	/* We get a Question Mark */
	a[i] = '0';
	replaceQnMarkByZeroOne(a, i+1);
	a[i] = '1';
	replaceQnMarkByZeroOne(a, i+1);
	
	// This is for back trace
	a[i]  = '?';
	
}

void test()
{
   char str[]="a?b?c?";
   replaceQnMarkByZeroOne(str,0);	
}

- dutta.dipankar08 June 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Code in Java

/**
 * Here is my algorithm without recursion.
 * It works faster and eats much less memory comparing to recursion.
 * The idea is that values 0 or 1 could be a bits of a number.
 * So we have to count symbol '?' and find a number of all possible combinations.
 * Combinations quantity is 2^(quantity of '?').
 * Then we make a loop and get a value of each bit for every number from loop.
 * Easy :)
 * Sorry for my english.
 */
public class Combinations {
    public static void main(String[] args) {
        String test = "a?b?c?d?";
        generator(test);
    }

    private static void generator(String str) {
        StringBuilder strB = new StringBuilder();
        boolean lastIsQMark = str.substring(str.length() - 1).equals("?");
        int bit;

        String arr[] = str.split("\\?");
        int bitsCount = arr.length - (lastIsQMark ? 0 : 1);
        int combinations = (int) Math.pow(2, arr.length - (lastIsQMark ? 0 : 1));

        for (int i = 0; i < combinations; i++) {
            for (int j = 0; j < bitsCount; j++) {
                bit = (i >> bitsCount - j - 1) & 1;
                strB.append(arr[j]);
                strB.append(bit);
            }

            if (!lastIsQMark) {
                strB.append(arr[bitsCount]);
            }

            System.out.println(strB.toString());
            strB.delete(0, strB.length());
        }
    }
}

- maks1m June 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It eats less memory. But is it faster than the recursive method? I think the recursive method is O(n) but this method is O(2^n). Please correct me if I'm wrong.

- allenylzhou June 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Both areO( 2^k.n) where k is the number of ? chars in str of length n. This approach is much faster and desirable than the recursive approach.

- im.code.warrior July 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static List<String> generateString(char[] inputString, int startIndex) {
		List<String> result = new ArrayList<String>();
		StringBuilder sb = new StringBuilder();
		boolean addlast = true;
		for (int i = startIndex; i < inputString.length; i++) {
			if (inputString[i] != '?')
				sb.append(inputString[i]);
			else {
				List<String> otherResult = generateString(inputString, i + 1);
				for (String otherStr : otherResult) {
					result.add(sb.toString() + "0" + otherStr);
					result.add(sb.toString() + "1" + otherStr);
				}
				addlast = false;
				break;
			}
		}
		if (addlast)
			result.add(sb.toString());
		return result;
	}
        public static void main(String[] args) {
		char[] test = "?a?b??".toCharArray();
		for (String str : generateString(test, 0))
			System.out.println(str);

}

- fang-l10 June 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void replaceBits(String target) {
        int count = 0;
        List<Integer> charPositionList = new ArrayList<>();
        for (int i = 0; i < target.length(); i++) {
            if (target.charAt(i) == '?') {
                count++;
                charPositionList.add(i);
            }
        }
        StringBuilder finalString = new StringBuilder(target);
        for (int i = 0; i < (Math.pow(2, count)); i++) {
            String binaryString = Integer.toBinaryString(i);
            binaryString = "0000" + binaryString;
            binaryString = binaryString.substring(binaryString.length() - 4, binaryString.length());
            for (int j = 0; j < count; j++) {

                finalString.setCharAt(charPositionList.get(j), binaryString.charAt(j));

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

- Preeti June 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ solution

void binarizeQuestionMarks(string str) {

    // find the indexes of question marks
    vector<int> stridxs;
    for (int i = 0; i < (int)str.size(); ++i) {
        if (str[i] == '?') {
            stridxs.push_back(i);
        }
    }

    // count from 0 to 2^strlen
    for (int i = 0; i < pow(2, (int)stridxs.size()); ++i) {
        // make appropriate assignment to each index
        for (int j = 0; j < (int)stridxs.size(); ++j) {
            // apply bitmask followed by bitshift to get 0 or 1
            int val = (i & (int)pow(2, j)) >> j;
            str[stridxs[j]] = '0' + val;
        }
        // output string
        cout << str << endl;
    }

}

- allenylzhou June 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ solution

void binarizeQuestionMarks(string str) {

    // find the indexes of question marks
    vector<int> stridxs;
    for (int i = 0; i < (int)str.size(); ++i) {
        if (str[i] == '?') {
            stridxs.push_back(i);
        }
    }

    // count from 0 to 2^strlen
    for (int i = 0; i < pow(2, (int)stridxs.size()); ++i) {
        // make appropriate assignment to each index
        for (int j = 0; j < (int)stridxs.size(); ++j) {
            // apply bitmask followed by bitshift to get 0 or 1
            int val = (i & (int)pow(2, j)) >> j;
            str[stridxs[j]] = '0' + val;
        }
        // output string
        cout << str << endl;
    }

}

- allenylzhou June 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
    using namespace std;
  
	int QCnt = 0;

   void ADDval(char Input[], int flag, int Count)
   {
	   int i = 0;
	   int Val = QCnt - Count;

	   while(Input[i] != '\0')
	   {
		   if(Input[i] == '?' || Input[i] == '0' || Input[i] == '1')
		   {
			   if(Val == 0)
			   {
				Input[i] = flag + '0';
				break;
			   }
			   else Val --;
		   }
		   i++;
	   }
   }

   int CountQ(char Input[])
   {
	    int i = 0;	 
		int cnt = 0;

	   while(Input[i] != '\0')
	   {
		   if(Input[i] == '?')
		   {
			   cnt++;
		   }
		   i++;
	   }
   return cnt;
   }

   void ProcessString(char Input[],int Count)
   {
	   if(Count == 0)
	   {
		   cout<<Input<<endl;
	   }
	   else if(Count > 0)
	   {
		   ADDval(Input,0,Count);
		   ProcessString(Input,Count-1);
		   ADDval(Input,1,Count);
		   ProcessString(Input,Count-1);		   
	   }
   }


    int main()
    {
	
	char Input[] = {"a?b?c?"};
	int length = sizeof(Input)/sizeof(Input[0]);
	
	QCnt = CountQ(Input);
	
	ProcessString(Input,QCnt);

	getchar();
    return 0;
    }

- deepak_gta June 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

List<string> Generate(string template) {

	var result = new List<string>();
	var current = template.ToArray();
	var index = new List<int>();
	for(int i=0; i<template.Length; i++) {
		if( template[i] == '?') {
			index.Add(i); //put index
			current[i] = '0'; //initial value
		}
	}

	result.Add( new string(current));
	var maxCount = 2 << index.Count;
	for( int n=1; n<8; n++) {
		var carry = true;
		for (var i=index.Count-1; i>=0; i--) {
			if( !carry)
				break;
			var pos = index[i];
			if( current[pos] == '1' ) { //max value
				current[pos] = '0';
				carry = true;
			}
			else { //was '0'
				current[pos] = '1';	
				carry = false;
			}
		}
		result.Add( new string(current));
	}
	return result;
}


var template = "a?bc?def?g";

Console.WriteLine(template);

var result = Generate(template);
Console.WriteLine("generated {0} strings", result.Count );
foreach (var s in result) {
    Console.WriteLine(s);
}

- nemo June 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class StringTest {
	static int row ,col,n;
	public String[][] buildGrid(String input) {
		n=0;
		String[][] matrix;
		col = input.length();
		for(int i=0; i<col; i++) {
			if(input.charAt(i)=='?')
				n++;
		}
		double m = Math.pow(2,n);
		row = (int) m;
		
		matrix = new String[row][col];
		return matrix;
	}
	
	public String[][] fillGrid(String input,String[][] Grid) {
		int d = 0;
		for(int a=0; a<col; a++){
			if(input.charAt(a)=='?'){
				d++;
				double m = Math.pow(2, d-1);
				double n = Math.pow(2, d);
				int p = (int) m;
				int q = (int) n;
				for(int i=0; i<p; i++) {		
					for(int j=(row/p*i); j<(row/q+row/p*i);j++){
						Grid[j][a] = "0";
						Grid[j+row/q][a] = "1";
					}
				}
			}
			else {
				for(int b=0; b<row; b++){
					char c = input.charAt(a);
					Grid[b][a]=String.valueOf(c);
				}
			}
		}
		return Grid;
	}
	
	public static void main(String[] args) {
		StringTest tmp = new StringTest();
		String input = "a?b?c?";
		String[][] preOutput = tmp.buildGrid(input);
		String[][] output = tmp.fillGrid(input,preOutput);
		for(int i=0; i<row; i++){
			for(int j=0; j<col; j++){
				System.out.print(output[i][j]);
			}
			System.out.println();
		}
	 }
}

- tonylibra1018 June 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class StringTest {
	static int row ,col,n;
	public String[][] buildGrid(String input) {
		n=0;
		String[][] matrix;
		col = input.length();
		for(int i=0; i<col; i++) {
			if(input.charAt(i)=='?')
				n++;
		}
		double m = Math.pow(2,n);
		row = (int) m;
		
		matrix = new String[row][col];
		return matrix;
	}
	
	public String[][] fillGrid(String input,String[][] Grid) {
		int d = 0;
		for(int a=0; a<col; a++){
			if(input.charAt(a)=='?'){
				d++;
				double m = Math.pow(2, d-1);
				double n = Math.pow(2, d);
				int p = (int) m;
				int q = (int) n;
				for(int i=0; i<p; i++) {		
					for(int j=(row/p*i); j<(row/q+row/p*i);j++){
						Grid[j][a] = "0";
						Grid[j+row/q][a] = "1";
					}
				}
			}
			else {
				for(int b=0; b<row; b++){
					char c = input.charAt(a);
					Grid[b][a]=String.valueOf(c);
				}
			}
		}
		return Grid;
	}
	
	public static void main(String[] args) {
		StringTest tmp = new StringTest();
		String input = "a?b?c?";
		String[][] preOutput = tmp.buildGrid(input);
		String[][] output = tmp.fillGrid(input,preOutput);
		for(int i=0; i<row; i++){
			for(int j=0; j<col; j++){
				System.out.print(output[i][j]);
			}
			System.out.println();
		}
	 }
}

- tonylibra1018 June 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class StringTest {
	static int row ,col,n;
	public String[][] buildGrid(String input) {
		n=0;
		String[][] matrix;
		col = input.length();
		for(int i=0; i<col; i++) {
			if(input.charAt(i)=='?')
				n++;
		}
		double m = Math.pow(2,n);
		row = (int) m;
		
		matrix = new String[row][col];
		return matrix;
	}
	
	public String[][] fillGrid(String input,String[][] Grid) {
		int d = 0;
		for(int a=0; a<col; a++){
			if(input.charAt(a)=='?'){
				d++;
				double m = Math.pow(2, d-1);
				double n = Math.pow(2, d);
				int p = (int) m;
				int q = (int) n;
				for(int i=0; i<p; i++) {		
					for(int j=(row/p*i); j<(row/q+row/p*i);j++){
						Grid[j][a] = "0";
						Grid[j+row/q][a] = "1";
					}
				}
			}
			else {
				for(int b=0; b<row; b++){
					char c = input.charAt(a);
					Grid[b][a]=String.valueOf(c);
				}
			}
		}
		return Grid;
	}
	
	public static void main(String[] args) {
		StringTest tmp = new StringTest();
		String input = "a?b?c?";
		String[][] preOutput = tmp.buildGrid(input);
		String[][] output = tmp.fillGrid(input,preOutput);
		for(int i=0; i<row; i++){
			for(int j=0; j<col; j++){
				System.out.print(output[i][j]);
			}
			System.out.println();
		}
	 }
}

- tonylibra1018 June 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class StringTest {
	static int row ,col,n;
	public String[][] buildGrid(String input) {
		n=0;
		String[][] matrix;
		col = input.length();
		for(int i=0; i<col; i++) {
			if(input.charAt(i)=='?')
				n++;
		}
		double m = Math.pow(2,n);
		row = (int) m;
		
		matrix = new String[row][col];
		return matrix;
	}
	
	public String[][] fillGrid(String input,String[][] Grid) {
		int d = 0;
		for(int a=0; a<col; a++){
			if(input.charAt(a)=='?'){
				d++;
				double m = Math.pow(2, d-1);
				double n = Math.pow(2, d);
				int p = (int) m;
				int q = (int) n;
				for(int i=0; i<p; i++) {		
					for(int j=(row/p*i); j<(row/q+row/p*i);j++){
						Grid[j][a] = "0";
						Grid[j+row/q][a] = "1";
					}
				}
			}
			else {
				for(int b=0; b<row; b++){
					char c = input.charAt(a);
					Grid[b][a]=String.valueOf(c);
				}
			}
		}
		return Grid;
	}
	
	public static void main(String[] args) {
		StringTest tmp = new StringTest();
		String input = "a?b?c?";
		String[][] preOutput = tmp.buildGrid(input);
		String[][] output = tmp.fillGrid(input,preOutput);
		for(int i=0; i<row; i++){
			for(int j=0; j<col; j++){
				System.out.print(output[i][j]);
			}
			System.out.println();
		}
	 }
}

- tonylibra1018 June 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Basically I converted the number of ? on a binary number, from there I subtracted 1 and then I produce the string:

String cad = new String("a?b?c???");
		StringBuffer cad2 = new StringBuffer(cad);
		Integer num;
		String r;
		int i=0;
		int cont=0;
		int strLength, strLength2;
		while (i<cad.length()){
			if (cad.charAt(i)=='?') cont++;
			i++;
		}
		Double j = Math.pow(2, cont);
		num = new Integer(j.intValue()-1);
		System.out.println(num);
		strLength= num.toBinaryString(num).length();
		while (num.intValue()>=0){
			r = num.toBinaryString(num);
		//	System.out.println(r);
			num = new Integer(num.intValue()-1);
			i=0;
			cont=0;
			strLength2 = r.length();
			while(i<cad.length()){
				if (cad.charAt(i)=='?'){
					if (strLength==r.length()){
						cad2.setCharAt(i,r.charAt(cont));
						cont++;
					}
					else {
						if (strLength2<strLength){
							cad2.setCharAt(i,'0');
							strLength2++;
						}
						else {
							cad2.setCharAt(i,r.charAt(cont));
							cont++;
						}
					}
				}
				else cad2.setCharAt(i, cad.charAt(i));
				i++;
			}
			System.out.println(cad2);
			
		}

- Carlos June 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
import java.lang.*;
class googleinterview
{
public static void main(String args[])
{
int count=0,r;
Scanner sc=new Scanner(System.in);
System.out.print("Enter the expression:");
String s=sc.next();
int len=s.length();
for(int i=0;i<s.length();i++)
{
if(s.charAt(i)=='?')
{
count++;
}
}
//System.out.println("Count="+count);
int power=(int)Math.pow(2,count);
//System.out.println("Power="+power);
int[][] a=new int[power][count];
int[][] b=new int[power][count];
int[] x=new int[power];
for(int i=0;i<power;i++)
{
x[i]=i;
}

for(int i=0;i<power;i++)
{
int k=0;
while(x[i]!=0)
{
r=x[i]%2;
//System.out.print(r);
a[i][k]=r;
x[i]=x[i]/2;
k++;
}

}
String s1=s;
System.out.println("**********Total possible combinations**********");
char[] ch=new char[len];
ch=s1.toCharArray();
for(int i=0;i<power;i++)
{
int k=count-1;
for(int j=0;j<len;j++)
{
if(s1.charAt(j)=='?')
{
if(k>=0)
{
System.out.print(a[i][k]);
k--;
}
else
break;
}
else
System.out.print(ch[j]);
}
System.out.println("\n");
}

}
}
/*
Output:
---------------------------------------------------
Enter the expression:?a?b?c
**********Total possible combinations**********
0a0b0c

0a0b1c

0a1b0c

0a1b1c

1a0b0c

1a0b1c

1a1b0c

1a1b1c

*/

- sai krishna June 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class CharacterReplacer {
	public static void main(String[] args) {
		String s = "a?b?c?djjjjh?";
		List<Integer> list = getNumberOfPosition(s);
		String[] str = generateCombination(s,list);
		for(String st : str){
			System.out.println(st);
		}
	}

	private static String[] generateCombination(String s, List<Integer> list) {
		String[] binaryCombination = getBinaryString(list);
		String[] allString = new String[binaryCombination.length];
		int index  = 0;
		for(String string : binaryCombination){
			StringBuffer stringBuffer = new StringBuffer(s);
			for(int k=0;k<list.size();k++){
				stringBuffer.replace(list.get(k), list.get(k)+1, string.substring(k,k+1));
			}
			allString[index++] = stringBuffer.toString();
		}
		return allString;
	}

	private static String[] getBinaryString(List<Integer> list) {
		int totalCombination = (int) Math.pow(2, list.size());
		String[] str = new String[totalCombination];
		for(int i = 0 ; i < totalCombination;i++){
			str[i] = Integer.toBinaryString(i);
			int diff = list.size() - str[i].length();
			String s = "";
			for(int j=0 ; j<diff ; j++)
				s =s + "0";
			str[i] = s + str[i];
		}
		return str;
	}

	private static List<Integer> getNumberOfPosition(String s) {
		char[] ch = s.toCharArray();
		List<Integer> list = new ArrayList<>();
		for(int i = 0;i < ch.length;i++){
			if(ch[i] == '?'){
				list.add(i);
			}
		}
		return list;
	}
}

- kmlsharma53 June 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void getAllPossible(String original_string ){
		
		
		getAllPossible(original_string , "" , 0);
	}

	
	
	public void getAllPossible(String original_string , String made_String , int index ){
		
		char two [] = {'0' , '1'};
		
		
		for(int i=index;i<original_string.length();i++){
			
			if(original_string.charAt(index)=='?'){
				
				for(char s: two){
					getAllPossible(original_string, made_String+s , index+1);
				}
			}else{
				
				made_String+=original_string.charAt(index);
			}
			
			
		}
		
		if(made_String.length()==original_string.length()){
			System.out.println(made_String);
		}
		
	}

- Aleksey June 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

vector<string> writeReplacements(const string &initialString)
{
	vector<string> allReplacements;

	const int questionCount = count(initialString.begin(), initialString.end(), '?');
	const int variantsCount = 2 << (questionCount-1);
	for (int i = 0; i < variantsCount; i++)
	{
		string str = initialString;
		int questionCounter = 0;
		for (int j = initialString.size()-1; j >= 0; j--)
		{
			if (initialString[j] == '?')
			{
				str[j] = '0' + (i >> questionCounter) % 2;
				questionCounter++;
			}
		}
		allReplacements.push_back(str);
	}

	return allReplacements;
}

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

Not the best solution, but its another one

public static void main(String[] args) {
		ArrayList<String> result = combify("a?bc?def?g");
		for (String r : result ) System.out.println(r);
	}
	
	private static ArrayList<String> combify(String string) {
		ArrayList<String> result = new ArrayList<String>();
		ArrayList<Integer> positions = new ArrayList<Integer>();
		for ( int index = 0; index < string.length(); index++ ) {
			if (string.charAt(index) == '?' )
				positions.add(index);
		}
		
		long combo = Math.round(Math.pow(2, positions.size()));
		for ( int value = 0; value < combo; value++ ) {
			String copy = string;
			for ( int times = 0; times < positions.size(); times++ ) {
				long val = 0x01 & (value >> times);
				copy = copy.replaceFirst("\\?", "" + val);
			}
			result.add(copy);
		}
		
		return result;
	}

- Vijay July 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
	 
        ArrayList<String> result = new ArrayList<String>();
        String s = "a?bc?def?g";
        replace(s,result);

        for(String ss:result){
        	System.out.println(ss);
        }			
}

public static void replace(String s,ArrayList<String> result){
		String[] sp = s.split("\\?");
		String[] set = {"0","1"};
		String res = "";
		replaceHelper(sp,0,set,res,result);
		
	}
	public static void replaceHelper(String[] s, int index,String[] set,String res,ArrayList<String> result){
		if(s.length < 1)
			return;
		
		if(index == (s.length-1)){
			result.add(res+s[index]);
			return;
		}
		
		for(int j=0;j<set.length;j++){
			String temp = res + s[index]+set[j];
			replaceHelper(s,index+1,set,temp,result);
		}
			
	}

- Anonymous July 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

int main()
{
         char str[20] = "a??b??c?";
        int i = 0, z ;
        int count  = 0 , occ = 0;
        int bit = 1, d;
        int index[10];
         while(str[i]!='\0')
        {
                 if(str[i] == '?')
                {
                        index[count] = i;
                        count++;
                }
                i++;
        }
        occ = count;
        while(count)
        {
                bit = bit * 2; //bit = 8
                 count--;
         }
         i=0;
        bit = bit - 1;
         while(i<=bit)
         {
                 d = 0;
                for (z = 1<<occ-1 ; z > 0; z >>= 1)
                {
                        if((i & z)==z)
                         {
                                str[index[d]] = '1';
                         }
                         else
                         {
                                 str[index[d]] = '0';
                         }
                        d++;
                 }
                i++;
                printf("\n String = %s\n ",str);
        }
        return 0;
}

- Jossy August 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>

using namespace std;

void generate(string& iStr , int index)
{
    if(index == iStr.size())
	{
		cout<<"\n"<<iStr;
	}
	else 
	{
		if(iStr[index] == '?')
		{
			iStr[index] = '0';
			generate(iStr , index + 1);
			iStr[index] = '1';
			generate(iStr , index + 1);
            iStr[index] = '?';
		}
		else
		{
			generate(iStr , index + 1);	
		}
	}
}

void generate(string iStr)
{
	generate(iStr , 0);
}

int main()
{
	generate("a?bc?def?g");
}

- MIG August 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class StringReplacer {

private String input;

public StringReplacer(String in) {
this.input = in != null ? in : "?";
}

public String[] replace() {
int count = 0, size = 0;

for (char c : this.input.toCharArray()) {
if (c == '?') {
size = 1<<(++count);
}
}

String[] out = new String[size];
int replacer = size;
replacer--;
for (int z=0; z<size; z++,replacer--) {
String replacerString = Integer.toBinaryString(replacer);
while (replacerString.length()<count) {
replacerString = "0"+replacerString;
}

int c=0;
char[] chars = this.input.toCharArray();
for (int p=0; p<chars.length; p++) {
if (chars[p] == '?') {
chars[p] = replacerString.charAt(c++);
}
}


out[z] = new String(chars);
}

return out;

}

public static void main(String[] args) {
StringReplacer replacer = new StringReplacer("a?b?c?");

String[] replaced = replacer.replace();

for (String s : replaced) {
System.out.println(s);
}
}

}

- PS August 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Question {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		questionReplace("a?bc?def?g");
	}
	
	public static void questionReplace(String question){
		
		int count = 0;
		for(int i = 0; i < question.length(); i++){
			if(question.charAt(i) == '?'){
				count++;
			}
		}
	
		String[] s = new String[(int)Math.pow(2,count)];
		for(int i = 0; i < s.length; i++){
			s[i] = "";
		}
		zeroOne(s);
		
		for(int i = 0; i < Math.pow(2,count); i++){
			int counter = 0;
			int subIndex = 0;
			String sub = "";
			for(int j = 0; j < question.length(); j++){
				if(question.charAt(j) == '?'){
					sub +=  question.substring(subIndex, j) + s[i].charAt(counter);
					subIndex = j + 1;
					counter++;
				}
				if(counter == Math.log(s.length) / Math.log(2)){
					sub += question.substring(subIndex, question.length());
					break;
				}
			}
			System.out.println(sub);
		}
	}
		
	public static void zeroOne(String[] a){
		
		int n = (int)( Math.log(a.length) / Math.log(2));
		int N = a.length;
		for(int i = 0; i < n; i++){
			int count = 0;
			int secCount = 0;
			for(int j = 0; j < a.length; j++){
				if(count < N/2){  
					a[j] += 0 + "";
					secCount = 0;
					count++;
				}
				else{  
					secCount++;
					a[j] += 1 + ""; 
				}
				if(secCount == N/2){
					count= 0;
				}
			} 
			N /= 2;
		}
	}
}

- Anonymous August 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Question {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		questionReplace("a?bc?def?g");
	}
	
	public static void questionReplace(String question){
		
		int count = 0;
		for(int i = 0; i < question.length(); i++){
			if(question.charAt(i) == '?'){
				count++;
			}
		}
	
		String[] s = new String[(int)Math.pow(2,count)];
		for(int i = 0; i < s.length; i++){
			s[i] = "";
		}
		zeroOne(s);
		
		for(int i = 0; i < Math.pow(2,count); i++){
			int counter = 0;
			int subIndex = 0;
			String sub = "";
			for(int j = 0; j < question.length(); j++){
				if(question.charAt(j) == '?'){
					sub +=  question.substring(subIndex, j) + s[i].charAt(counter);
					subIndex = j + 1;
					counter++;
				}
				if(counter == Math.log(s.length) / Math.log(2)){
					sub += question.substring(subIndex, question.length());
					break;
				}
			}
			System.out.println(sub);
		}
	}
		
	public static void zeroOne(String[] a){
		
		int n = (int)( Math.log(a.length) / Math.log(2));
		int N = a.length;
		for(int i = 0; i < n; i++){
			int count = 0;
			int secCount = 0;
			for(int j = 0; j < a.length; j++){
				if(count < N/2){  
					a[j] += 0 + "";
					secCount = 0;
					count++;
				}
				else{  
					secCount++;
					a[j] += 1 + ""; 
				}
				if(secCount == N/2){
					count= 0;
				}
			} 
			N /= 2;
		}
	}
}

- Will B August 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In Ruby:
Assume there are 3 question marks, use binary string from 000 to 111. Convert it to string, replace binary chars with each question marks.

# s = "a?bc?def?g", 3 question marks
def fill_qmarks_iterate( s )
  count_q = s.chars.count("?")
  n = 2 ** count_q # n = 1000 to 1111
  for x in n..n*2-1
    s2 = s.clone
    # from 000 to 111
    x.to_s(2).chars[1..s.chars.count("?")].each do |y|
      s2[ s2.index("?") ] = y # replace with first ? from left
    end
    p s2
  end
end

- jonoson August 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Backtracking in C++:

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

void generate(int depth, string gen, string &s){
    if (depth == (int)s.size()){
        cout << gen << endl;
    }
    else{
        if(s[depth] == '?'){
            generate(depth + 1, gen + '0', s);
            generate(depth + 1, gen + '1', s);
        }
        else {
            generate(depth + 1, gen + s[depth], s);
        }
    }
}

int main(){
    string s;
    cin >> s;
    generate(0, "", s);

    return 0;
}

- Inucoder August 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static List<String> combinations(String input) {
		List<String> resultSet = new ArrayList<String>();
		
		Stack<String> stack = new Stack<String>();
		stack.push(input);
		while (!stack.isEmpty()) {
			String current = stack.pop();
			if (current.indexOf("?") == -1) {
				resultSet.add(current);
			} else {
				stack.push(current.replaceFirst("\\?", "0"));
				stack.push(current.replaceFirst("\\?", "1"));
			}
		}
		
		return resultSet;
	}

- Deege August 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Sequence {

	private static void allSequence(String str, int replaced, int zeros,
			int ones) {

	

		if (replaced == 3) {
			System.out.println( str);
			return;
		}

		if (zeros > 0 && replaced < 3) {

			StringBuilder sb = new StringBuilder();
			boolean change = false;
			for (int i = 0; i < str.length(); i++) {

				if (str.charAt(i) == '$' && !change) {
					sb.append("0");
					change = true;
				} else {
					sb.append(str.charAt(i));
				}
			}

			allSequence(sb.toString(), replaced + 1, zeros - 1, ones);
		}

		if (ones > 0 && replaced < 3) {

			StringBuilder sb = new StringBuilder();
			boolean change = false;
			for (int i =0 ; i < str.length(); i++) {

				if (str.charAt(i) == '$' && !change) {
					sb.append("1");
					change = true;
				
				} else {
					sb.append(str.charAt(i));
				}
			}
			allSequence(sb.toString(), replaced + 1, zeros, ones - 1);

		}

	}

	public static void main(String[] args) {

		allSequence("a$b$c$", 0, 3, 3);

	}
}

- Anonymous August 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void interrogant_to_0_and_1(const std::string& string, int pos)
{
	if (pos >= string.size())
		std::cout << string.c_str() << std::endl;
	else if (string[pos] == '?')
	{
		std::string new_string = string;
		new_string[pos] = '0';
		interrogant_to_0_and_1(new_string, pos + 1);
		new_string[pos] = '1';
		interrogant_to_0_and_1(new_string, pos + 1);
	}
	else
		interrogant_to_0_and_1(string, pos + 1);
}

void interrogant_to_0_and_1(const std::string& string)
{
	// Recursive approach
	interrogant_to_0_and_1(string, 0);
}

- A C++ approach September 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java solution - no recursion. Memory O(n), does n * 2^n operations.

public static void main(String[] args) {
        String input = "ab?asd?asdfasdf??saf???sadf????";
        int numMarks = 0;

        for (char c : input.toCharArray()) {
            if (c == '?') {
                numMarks++;
            }
        }

        for (int i = 0; i < Math.pow(2, numMarks); i++) {
            String variant = new String(input);
            int markNumber = 0;
            for (int j = 0 ; j < input.length(); j++) {
                if (input.charAt(j) == '?') {
                    markNumber++;
                    if ((i & markNumber) > 0) {
                        variant = variant.substring(0, j) + '1' + variant.substring(j+1);
                    } else {
                        variant = variant.substring(0, j) + '0' + variant.substring(j+1);
                    }
                }
            }
            System.out.println(variant);
       }
    }

- DmitryS September 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int main(){
  string tmp;

  cin >> tmp;
  vector<int> pos;
  int found=0;
  for (int i=0; i<tmp.size();i++){
    if (tmp[i]=='?'){
     found++;
     pos.push_back(i);
    }
  }
  for (int i=0;i<(1<<found);i++){
    for (int j=0;j<pos.size();j++){
      tmp[pos[j]]=(i&(1<<j))?'1':'0';
    }
    cout <<tmp<<endl;
  }

  return 0;
}

- Jesus Federico October 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is simple readable code with working solution using recursion. Just copy paste and compile

public class aqbqcq {
public static void main(String[] args)
{
replace("a?b?c?d?");
}

public static void replace(String s)
{
char c;

for (int i = 0; i < s.length(); i++)
{
c = s.charAt(i);

if (c == '?')
{
replace(rc(s,i,'0'));
replace(rc(s,i,'1'));
return;
}
}

System.out.println(s);
}

// Replace char in string at certain index
public static String rc(String s, int index, char c)
{
return s.substring(0,index) + c + s.substring(index+1);
}
}

- Mike November 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

using System;
using System.Text;

namespace SRMs
{
    public class StringGames
    {
        public void AllStrings(string template)
        {
            int counter = 0;
            for (int i = 0; i < template.Length; i++)
            {
                if (template[i] == '?')
                {
                    counter++;
                }
            }
            
            long numberOfCombinations = 1 << counter;
            for (long i = 0; i < numberOfCombinations; i++)
            {
                var result = new StringBuilder();
                int move = 0;
                for (int j = 0; j < template.Length; j++)
                {
                    if (template[j] == '?')
                    {
                        result.Append((i & (1 << move++)) == 0
                            ? "0"
                            : "1");
                    }
                    else
                    {
                        result.Append(template[j]);
                    }
                }
                Console.WriteLine(result);
            }
        }
    }
}

Works in cases where number of '?' is less then 63.

- YourThirdLife December 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

using System;
using System.Collections.Generic;

namespace InterviewTasks
{
    internal static class QuotationMarks
    {
        public static string[] GetAllStrings(string pattern)
        {
            if (string.IsNullOrEmpty(pattern))
            {
                throw new ArgumentException("Pattern should be a non-empty string");
            }

            List<int> quotationMarks = new List<int>();
            for (int i = 0; i < pattern.Length; ++i)
            {
                if (pattern[i] == '?')
                {
                    quotationMarks.Add(i);
                }
            }

            string[] result = new string[1 << quotationMarks.Count];
            for (int i = 0; i < result.Length; ++i)
            {
                char[] chars = pattern.ToCharArray();
                for (int j = 0; j < quotationMarks.Count; ++j)
                {
                    var quotationMarkPosition = quotationMarks[j];
                    chars[quotationMarkPosition] = ((i >> j) & 1) == 1 ? '1' : '0';
                }
                result[i] = new string(chars);
            }

            return result;
        }
    }
}

- stanislav.khalash December 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

final double LOG_2 = Math.log(2);
        String a = "b????a";
        int numOfQues = 0;
        for(int i = 0; i<a.length();i++){
            if(a.charAt(i) == '?'){
                numOfQues++;
            }
        }
        ArrayList<Boolean[]> bitMasks= new ArrayList<Boolean[]>();
        for(int i = 0; i <(1<<numOfQues); i++){
            int x = i;
            Boolean bitMsk[] = new Boolean[numOfQues];
            Arrays.fill(bitMsk, false);
            while(x!=0){
                //get least significant bit
                int tar = (int) (Math.log(x & ~(x-1))/LOG_2);
                bitMsk[tar] = true;
                //remove least significant bit:
                x = x & (x-1);
            }
            bitMasks.add(bitMsk);
        }
        for(int i = 0; i<bitMasks.size(); i++){
            for(int l = 0; l< bitMasks.get(i).length; l++){
                System.out.print((bitMasks.get(i)[l] == true ? 1 : 0) + " ");
            }
            System.out.println();
        }

        for(int i = 0; i<bitMasks.size(); i++){
            int index = 0;
            for(int l = 0; l<a.length(); l++){
                if(a.charAt(l) == '?'){
                    System.out.print(bitMasks.get(i)[index++] == true ? 1 : 0);
                }else{
                    System.out.print(a.charAt(l));
                }
            }
            System.out.println();
        }

- daljeetv January 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

No recursion, extra O(n) space

public static void main(String[] args) {
        compute("a?b?c?");
    }

    public static void compute(String s)
    {
        List<Integer> questionPosition = new ArrayList<>();
        for(int i=0;i<s.length();i++) {
            char character = s.charAt(i);
            if(character == '?') {
                questionPosition.add(i);
            }
        }
        
        //for faster modification than String
        char[] inputArray = s.toCharArray();
        //to know when to end
        int numberOf1s =0;
        //which questionmark to process next
        int currentQuestion=0;

        while(numberOf1s < questionPosition.size()) {
            if(currentQuestion<questionPosition.size()) {
                char q = inputArray[questionPosition.get(currentQuestion)];
                if(q == '?') {
                    inputArray[questionPosition.get(currentQuestion)] = '0';
                    currentQuestion++;
                } else if(q=='0'){
                    inputArray[questionPosition.get(currentQuestion)] = '1';
                    numberOf1s++;
                    currentQuestion++;
                } else if(q=='1') {
                    inputArray[questionPosition.get(currentQuestion)] = '?';
                    numberOf1s--;
                    currentQuestion--;
                }
            } else {
                printArray(inputArray);
                currentQuestion--;
            }

        }
        // last 1's were not printed
        printArray(inputArray);
    }

    private static void printArray(char[] inputArray)
    {
        for(int i=0;i<inputArray.length;i++) {
            System.out.print(inputArray[i]);
        }
        System.out.println();
    }

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

import java.util.List;

/**
 * Created by tiwariaa on 7/5/15.
 */
public class StringCombination {

    public static void printStringCombincation(String arg){
        if(!arg.contains("?"))
            System.out.println(arg);
        String with1s = arg.replaceAll("\\?", "1");
        String with0s = arg.replaceAll("\\?", "0");
        for(int i=0; i<with1s.length(); i++){
           if(with1s.charAt(i) == '1'){
            System.out.println(with1s.substring(0, i) + "0" + with1s.substring(i + 1));
           }
        }

        for(int i=0; i<with0s.length(); i++){
            if(with0s.charAt(i) == '0'){
                System.out.println(with0s.substring(0, i) + "1" + with0s.substring(i + 1));
            }
        }

    }

    public static void main(String[] args){
        if(args.length == 0){
            System.out.println("Please pass right args");
            return;
        }

        printStringCombincation(args[0]);
    }
}

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

void print01Helper(char* s, int i)
{
	if (i == -1)
	{
		printf("%s\n", s);
		return;
	}

	if (s[i] == '?')
	{
		s[i] = '0';
		print01Helper(s, i - 1);
		s[i] = '1';
		print01Helper(s, i - 1);
		s[i] = '?';
	}
	else
	{
		print01Helper(s, i - 1);
	}
}

void print01(char* s)
{
	print01Helper(s, strlen(s) - 1);
}

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

void print01Helper(char* s, int i)
{
	if (i == -1)
	{
		printf("%s\n", s);
		return;
	}

	if (s[i] == '?')
	{
		s[i] = '0';
		print01Helper(s, i - 1);
		s[i] = '1';
		print01Helper(s, i - 1);
		s[i] = '?';
	}
	else
	{
		print01Helper(s, i - 1);
	}
}

void print01(char* s)
{
	print01Helper(s, strlen(s) - 1);
}

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

/*void calcPermutation(int n, vector<vector<int>> &permutationArr)
{
	if (n <= 0)
	{
		return;
	}

	//if n = 2, nTemp = 3
	//if n = 3, nTemp = 7
	//if n = 4, nTemp = 15
	//.... 

	int nTemp = (int)pow(2, n);
	
	permutationArr.resize(nTemp);
	for (int i = 0; i < nTemp; i++)
		permutationArr[i].resize(n);
	
	nTemp--;

	int p, q;

	p = 0;
	q = 0;

	for (int i = 0; i <= nTemp; i++)
	{
		for (int k = 0; k < n; k++)
		{
			if ((i >> k) & 0x1)
			{
				permutationArr[p][q] = 1;
			}
			else
			{
				permutationArr[p][q] = 0;
			}

			if (k != n - 1)
			{
				q++;
			}
		}

		p++;
		q = 0;
	}
}
*/

void calcPermutation(int n, vector<vector<int>> &permutationArr)
{
	if (n <= 0)
	{
		return;
	}

	//if n = 2, nTemp = 3
	//if n = 3, nTemp = 7
	//if n = 4, nTemp = 15
	//.... 

	int nTemp = (int)pow(2, n);

	permutationArr.resize(nTemp);
	for (int i = 0; i < nTemp; i++)
		permutationArr[i].resize(n);


	int val = 0;
	int p, q, calc;

	p = 0;
	

	while (val < nTemp)
	{
		q = 0;
		calc = val;
		while (q < n)
		{
			permutationArr[p][q] = calc % 2 ? 0 : 1;
			calc = calc/2;
			q++;
		}
		p++;
		val++;
	}

}


void replaceString(string input)
{
	int i,j;
	int len = strlen(input.c_str());
	int qCount = 0;
	int *qIndexArr = new int[len];

	j = 0;
	for (i = 0; i < len; i++)
	{
		if (input[i] == '?')
		{
			qIndexArr[j] = i;
			j++;
			qCount++;
		}
	}

	if (qCount == 0)
	{
		cout << input << endl;
		return;
	}

	vector<vector<int>> permutationArr;		
	calcPermutation(qCount, permutationArr);
	list<string> l;
	char *temp = new char;

	for (i = 0; i < permutationArr.size(); i++)
	{
		for (j = 0; j < qCount; j++)
		{
			 temp = itoa(permutationArr[i][j],temp, 10);
			input[qIndexArr[j]] = *temp;
		}
		l.push_back(input);
	}

	list<string>::iterator it;

	cout << "Answers is:";
	for (it = l.begin(); it != l.end(); ++it)
	{
		std::cout << ' ' << *it;
		std::cout << '\n';
	}
	
}


int main(int argc, char* argv[])
{
	replaceString("a?b?c?");
	return 0;
}

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

I came up with this code: I think it runs in O(N.2^K). K is number of combos. Any Suggestions?

Queue<String> q = new LinkedList<String>();
		q.add(s);
		while(!q.isEmpty())
		{
			String ns = q.poll();
			int replaceIndex = ns.indexOf('?');
			if(replaceIndex > -1)
			{
				String ss1 = ns.substring(0, replaceIndex);
				String ss2 = ns.substring(replaceIndex+1, ns.length());
				String ns1 = ss1+"0"+ss2;
				String ns2 = ss1+"1"+ss2;
				q.add(ns1);q.add(ns2);
			}
			else
				System.out.println(ns);
		}

- vikashtalanki November 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static String[] convertAll(String input) {

// Find amount of ?
int amountOfQuestionMarks = 0;
for (char c : input.toCharArray()) {
if (c == '?') amountOfQuestionMarks++;
}

// If no question marks return empty array
if (amountOfQuestionMarks == 0) return new String[]{};

int variations = (int) Math.pow(2, amountOfQuestionMarks);
String[] result = new String[variations];

for (int i = 0; i < variations; i++) {
String binaryString = Integer.toBinaryString(i);
if (binaryString.length() < amountOfQuestionMarks) {
String zeroStrings = getZeroStrings(amountOfQuestionMarks, binaryString.length());
binaryString = zeroStrings + binaryString;
}

char[] binaryChars = binaryString.toCharArray();
String modifiedInput = input;
for (char c : binaryChars) {
modifiedInput = modifiedInput.replaceFirst("\\?", Character.toString(c));
}

result[i] = modifiedInput;
}

return result;
}

private static String getZeroStrings(int shouldBe, int current) {
StringBuilder builder = new StringBuilder();
for (int i = 0; i < shouldBe - current; i++) {
builder.append('0');
}
return builder.toString();
}

- Artyom June 10, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Code in C:

#include <stdio.h>

/*
 * src is the source string which containing target to be replaced
 * offset is where to start this replace action in source string
 * target is target character to be found and replaced
 * candidate is an array of all substitutes
 * n is the size of candidate array
 */
void permutateReplace(char* src, int offset, char target,
                      const char candidate[], int n
)
{
//step 1: find the first target start from offset
    for(; src[offset]; ++offset){
        if(src[offset] == target) break;
    }
//step 2: if found, use candidate to replace it, else print the result out
    if(src[offset]){
        //try to replace target with every candidate
        int i = 0;
        for(; i < n; ++i){
            src[offset] = candidate[i];
            permutateReplace(src, offset + 1, target, candidate, n);
        }
        //restore site
        src[offset] = target;
    }
    else puts(src);
}

int main()
{
    char src[] = "a?b?c?";
    char target = '?';
    char candidate[] = {'0', '1'};
    
    permutateReplace(src, 0, target, candidate, sizeof(candidate)/sizeof(char));
    
    return 0;
}

- uuuouou May 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#!/usr/bin/env python
import string
import sys
def comb(s):
c = s.lower().count('?')
for i in range(c ** 2 -1 ):
l1 = list(bin(i)[2:].zfill(c))
s1 = s[:]
for j in range(c):
s1 = string.replace(s1,'?', l1[j], 1)
print s1

if __name__ == "__main__":
s = sys.argv[1]
comb(s)

- samsixtyone May 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

play.google.com/store/apps/details?id=com.couponkart.couponcodes

try this out . might be useful

- Anonymous June 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

play.google.com/store/apps/detai...
try it out

- Anonymous June 01, 2014 | 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