Interview Question






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

#include <stdio.h>

void wild(char*,int);

int main ()
{
	char arr[] = "0?1?";
	wild(arr,0);
	return 0;


}


void wild(char * arr,int i)
{
	while(arr[i] != '\0' && arr[i] != '?')
	{
		i++;
	}
	if(arr[i] == '\0')
	{
		printf("%s\n",arr);
		return;
	}
	if(arr[i] == '?')
	{
		arr[i] = '0';
		wild(arr,i);
		arr[i] = '1';
		wild(arr,i);
		arr[i] = '?';

	}
}

- Amit Dey December 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

plz help mee,,
why
arr[i] = '?';
in last used;


!!!!!!!!!!

- Anonymous August 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

plzzz help me
why arr[i] = '?'

- ankit August 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

package textSol;

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

public class textSol {
	private List<String> sol;
	private String input;
	public textSol(String i)
	{
		input = i;
		Vector <String> v = new Vector<>();
		sol = new ArrayList<>();
		for (int j = 0; j < input.length(); j++) {
			if(input.charAt(j) == '?')
			{
				if(v.size() == 0)
				{
					v.add(cutString(input, j, '0'));
					v.add(cutString(input, j, '1'));
				}
				else
				{
					int length = v.size();
					for (int z = 0; z <length; z++) {						
						String s = v.get(0);
						v.remove(0);
						v.add(cutString(s, j, '0'));
						v.add(cutString(s, j, '1'));
					}
				}
			}
		}
		for (int t = 0; t < v.size(); t++) {
			sol.add(v.get(t));
		}		
	}
	public List<String> getSol(){
		return sol;
	}
	private String cutString(String s, int index,char fillChar)
	{
		if(index < s.length()-1)
		{
			return s.substring(0, index) + fillChar + s.substring(index+1);
		}
		else
		{
			return s.substring(0, index) + fillChar ;
		}
	}
	public static void main(String[] args) {
		textSol s = new textSol(args[0]);
		List<String> sol = s.getSol();
		for (String string : sol) {
			System.out.println(string);
		}
	}
}

- chen December 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This does not use recursion. The problem says to use recursion.

- gargayushi19 December 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

this mine without recursion and going over the string once

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

Recently found that Prof Skiena has a nice Java Class for any backtracking problem. Here is my attempt at doing this: All of you have to do overwrite a few methods and you are good with any backtracking problem.. For more info on this, check youtube "skiena backtracking"

class  BackTracking {
	static boolean finished = false;
	static final int MAXCANDIDATES = 100;
	static final int NMAX = 100;


	static void backtrack(char a[], int k, int input) {
		char c[] = new char[MAXCANDIDATES];
		int ncandidates, i;
		if (is_a_solution(a, k, input))
			process_solution(a, k, input);
		else {
			k++;
			ncandidates = construct_candidates(a, k, input, c);
			for (i = 0; i < ncandidates; i++) {
				a[k] = c[i];
				make_move(a, k, input);
				backtrack(a, k, input);
				if (finished)
					return;
				unmake_move(a, k, input);
			}
			if(ncandidates > 1) a[k] = '?';
		}
	}

	static void make_move(char a[], int k, int n) {
	}

	static void unmake_move(char a[], int k, int n) {
	}

	static void process_solution(char a[], int k, int n) {
		System.out.println(new String(a));
	}

	static boolean is_a_solution(char a[], int k, int n) {
		return k == n;
	}

	static int construct_candidates(char a[], int k, int n, char c[]) {
		if(a[k] == '?') {
			c[0] = '0';
			c[1] = '1';
			return 2;
		}
		c[0] = a[k];
		return 1;
		
	}

	static public void main(String[] args) {
		char a[] = "0?1?".toCharArray();
		backtrack(a, 0, a.length-1);
	}
}

Ok for design purists, this class can be declared abstract and all methods can be designed as generic but more starters, this is good enough..

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

I'm sure my solution could be optimized but the basic idea seems to me like this:

class Program
    {
        static List<string> result = new List<string>();
        static int steps;
        static List<int> positions = new List<int>();
        static char[] inputchar = { '0', '?', '1', '?' };

        static void Main(string[] args)
        {
            
            int j = 0;
            for (int i = 0; i < inputchar.Length;i++ )
                if (inputchar[i]=='?')
                {
                    positions.Add(i);
                    steps++;
                }

            char[] tempchar = replaceWildCard(inputchar, (int)Math.Pow(2,steps)-1);

            foreach (string item in result)
            {
                Console.WriteLine(item);
            }
            Console.ReadLine();
        }

        static char[] replaceWildCard(char[] input, int i)
        {
            if (i == -1) return input;
            string bin = Convert.ToString(i, 2).PadLeft(positions.Count(), '0');
            for (int j = 0; j < positions.Count(); j++) input[positions[j]] = bin[j];
            result.Add(new string(input));
           
            return replaceWildCard(inputchar, i - 1);
        }
    }

Output is:
0111
0110
0011
0010

Also tested this code with more input chars. Works fine.

- Eugene Mmmmm December 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If it has to be recursive one simple idea seems to be to split input into already visited part (xs) and part to be visited (ys). The solution is in Scala but can be easily adopted to Java:

def replaceWildcards(s: String) : List[String] = {
    def replaceRecursive(xs: String, ys: String) : List[String] = {
      if (ys.isEmpty()) List(xs)
      else ys(0) match {
        case '?' => replaceRecursive(xs+'0', ys.drop(1)) ::: replaceRecursive(xs+'1', ys.drop(1))
        case a:Char => replaceRecursive(xs + a, ys.drop(1))
      }
    }

    replaceRecursive("", s)
  }

- Tomek Łasica December 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void fill(String input, int position) {
		int nextposition = input.indexOf('?', position);
		if(nextposition == -1) {
			System.out.println(input);
			return;
		}
		String input1 = input.substring(0, nextposition) + "0" + input.substring(nextposition+1, input.length());
		fill(input1, nextposition+1);
		String input2 = input1.substring(0, nextposition) + "1" + input1.substring(nextposition+1, input1.length());
		fill(input2, nextposition+1);
	}public static void main(String[] args) {
		// TODO Auto-generated method stub
		fill("?0?1",0);

}

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

def replaceWildcards(string: String) : Set[String] = {
if(!string.contains("?")) Set(string)
else replaceWildcards(string.replaceFirst("\\?", "0")) ++ replaceWildcards(string.replaceFirst("\\?", "1"))
}

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

def replaceWildcards(string: String) : Set[String] = {
    if(!string.contains("?")) Set(string)
    else
      replaceWildcards(string.replaceFirst("\\?", "0")) ++
      replaceWildcards(string.replaceFirst("\\?", "1"))
  }

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

//using the example, the inputs should be 
// input == the input string
// alphabet = char[]{ '0', '1' }
public static ArrayList<String> getPerms(String input, char[] alphabet){
	Worker worker = new Worker(input, alphabet){
	worker.execute();
	return worker.getResults();
}

static class Worker{
	char[] origChars;
	char[] working;
	char[] alphabet;
	ArrayList<String> results;
	
	Worker(String origString, char[] alphabet){
		this.origChars = origString.getCharArray();
		this.alphabet = alphabet;
		this.working = new char[this.origChars.length];
		this.results = new ArrayList<String>();
	}

	void execute(){
		this.execute(0);
	}
	
	void execute(int index){
		if(index == this.working.length){
			this.results.add(new String(this.working));
			return;
		}
		if(this.origChars == '?'){
			int nextIndex = index + 1;
			for(char c : this.alphabet){	
				this.working[index] = c;
				this.execute(nextIndex);
			}
		}
		else{
			this.working[index] = this.origChars[index];
			this.execute(nextIndex+1);
		}
	}

	ArrayList<String> getResults(){
		return this.results;
	}
}

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

public static void main(String[] args)
  {
    String s1 = "AB=C=";
    printCombs(s1.indexOf('='), s1);
  }

  public static void printCombs(int start, String str)
  {
    if (start == -1)
    {
      System.out.println(str);
      return;
    }
    String str1 = str.replaceFirst("=", "0");
    printCombs(str1.indexOf('='), str1);
    String str2 = str.replaceFirst("=", "1");
    printCombs(str2.indexOf('='), str2);
  }

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

This was somehow more difficult than I expected and the recursion I came up with isn't very clean, but I think I managed to get it correct

def replaceWildcards(s):
	if len(s) == 1:
		return [s[0]] if s[0] != "?" else ["0", "1"]
	res = replaceWildcards(s[1:])
	if s[0] == "?":
		return map(lambda x: "0" + x, res) + map(lambda x: "1" + x, res)
	return map(lambda x: s[0] + x, res)

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

import java.util.*;

public class main {
public static ArrayList<String> permutations=new ArrayList<String>();

public static void main(String[] args) {

System.out.println("Enter binary number with wildcard ?, print all permutations, ie 101? ");
Scanner numString=new Scanner(System.in)
String binaryNum=numString.nextLine();

getPermutations(binaryNum,0);
for(String num:permutations)
System.out.println("Permutation: "+num);
}
private static void getPermutations(String binaryNum, int index) {
if(index==binaryNum.length()){
permutations.add(binaryNum);

}
else {
if(binaryNum.charAt(index)!='?')
getPermutations(binaryNum, index+1);
else{
String string1=binaryNum.substring(0, index)+'0'+binaryNum.substring(index+1);
getPermutations(string1, index+1);
String string2=binaryNum.substring(0, index)+'1'+binaryNum.substring(index+1);
getPermutations(string2, index+1);
}
}

}

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

public static void replaceWildCardWithZeroOrOne(String input, int start) {
        for (int index = start; index < input.length(); index++) {
            if (input.charAt(index) == '?') {
                final String firstSub = input.substring(0, index);
                final String secondSub = input.substring(index + 1, input.length());
                replaceWildCardWithZeroOrOne(firstSub + "0" + secondSub, index + 1);
                replaceWildCardWithZeroOrOne(firstSub + "1" + secondSub, index + 1);
                return;
            }
        }
        System.out.println(input);
    }

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

c# version
        private static void WildCardsCombo(char[] str, int i, ref List<string> list)
        {
            string s = ""; 

            while (i < str.Count() && str[i] != '?')
            {
                i++;
            }
            if (i == str.Count())
            {
                foreach (char c in str)
                    s += string.Concat(c.ToString()); 
                
                list.Add(s);
                Console.WriteLine("{0}", s);
                return; //list;
            }
            if (str[i] == '?')
            {
                str[i] = '0';
                WildCardsCombo(str, i, ref list);
                str[i] = '1';
                WildCardsCombo(str, i, ref list);
                str[i] = '?';
            }

            return;
        }

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

private List<String> list = new ArrayList<String>();

    private void replaceAllWildCharacters(String str, int i) {
        if (!str.contains("?")) {
            list.add(str);
        } else {
            StringBuilder sb = new StringBuilder(str);
            for (; i <= str.indexOf('?'); i++) {
                if (str.charAt(i) == '?') {
                    char[] possibilities = new char[]{'0', '1'};
                    for (char ch : possibilities) {
                        sb.setCharAt(i, ch);
                        replaceAllWildCharacters(sb.toString(), i + 1);
                    }
                }
            }
        }

}

- Madhur Mehta May 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void stringCheck(char[] val,int i,int n) {
if (i == n) {
System.out.println(val);

} else if (val[i] == '?') {
val[i] = '1';
stringCheck(val, i + 1, n);
val[i] = '0';
stringCheck(val, i + 1, n);
val[i] = '?';
} else {
stringCheck(val, i + 1, n);
}
}

publlic void print() {
Scanner scan = new Scanner(System.in);
String s = scan.next();
stringCheck(s.toCharArray(),0,s.length);
}

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

/** js /
var str = '010?111?010011?011?1010?';

function loop_through_str(arg_str){
if(arg_str.indexOf('?') !== -1){
var new_str_1 = arg_str.replace('?', '1'),
new_str_0 = arg_str.replace('?', '0');
loop_through_str(new_str_0);
loop_through_str(new_str_1);
}else{
console.log(arg_str);
}
}

loop_through_str(str);

- invisble September 02, 2016 | 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