Interview Questions

  • View all interview questions
  • blank
  • Find all string combinations consisting only of 0, 1 and ?
    For this popular algorithm interview question, the input will be a string consisting only of the characters 0, 1 and ?, where the ? acts as a wildcard that can be either a 0 or 1, and your goal is to print all possible combinations of the string. For example, if the string is "011?0" then your program should output a set of all strings, which are: ["01100", "01110"].

    Algorithm

    The general algorithm we will write a solution for is: (1) Call the function with the string and an empty set where we begin pushing 0 and 1's. (2) Once we reach a ?, then make a copy of each string set, and for half append a 0 and for the other half append a 1. (3) Recursively call the function with a smaller string until the string is empty.

    Example

    Assume the input string is "10??" Initial set = [] 1st character = 1 set = [1] 2nd character = 0 set = [1, 0] 3rd character = ? First we make a copy of each string set and then we add a 0 to half of the sets and 1 to the other half. set = [[1, 0, 0], [1, 0, 1]] 4th characer = ? Same procedure as the previous step. set = [[1, 0, 0, 0], [1, 0, 1, 0], [1, 0, 0, 1], [1, 0, 1, 1]]

    Code

    function patterns(str, all) {
      
      // if the string is empty, return all the string sets
      if (str.length === 0) { return all; }
      
      // if character is 0 or 1 then add the character to each
      // string set we currently have so far
      if (str[0] === '0' || str[0] === '1') {
        for (var i = 0; i < all.length; i++) {
          all[i].push(str[0]);  
        }
      }
      
      // for a wildcard, we make a copy of each string set
      // and for half of them we append a 0 to the string 
      // and for the other half we append a 1 to the string
      if (str[0] === '?') {
        var len = all.length;
        for (var i = 0; i < len; i++) {
          var temp = all[i].slice(0);
          all.push(temp);
        }
        for (var i = 0; i < all.length; i++) {
          (i < all.length/2) ? all[i].push('0') : all[i].push('1');  
        }
      }
      
      // recursively calculate all string sets
      return patterns(str.substring(1), all);
      
    }
    
    patterns('10?1?', [[]]);
    
    def patterns(str, all):
      
      # if the string is empty, return all the string sets
      if len(str) == 0:
        return all
      
      # if character is 0 or 1 then add the character to each
      # string set we currently have so far
      if str[0] == '0' or str[0] == '1':
        for i in range(0, len(all)):
          all[i].append(str[0])
          
      # for a wildcard, we make a copy of each string set
      # and for half of them we append a 0 to the string 
      # and for the other half we append a 1 to the string
      if str[0] == '?':
        le = len(all)
        for i in range(0, le):
          temp = list(all[i])
          all.append(temp)
        for i in range(0, len(all)):
          if i < len(all)/2:
            all[i].append('0')
          else:
            all[i].append('1')
            
      # recursively calculate all string sets
      return patterns(str[1:], all)
      
    print patterns('10?1?', [[]]) 
    
    Run Code
    Run Code

    Running time

    This algorithm runs in O(2n) time where n is equal to the number of wildcards because there are 2n possible sets for all wildcards in the string. The algorithm must perform this many steps to calculate all the sets. [1] If there are no wildcards in the string, then the algorithm runs in linear time, O(n), because it will simply append each character to a string.

    Sources

    http://www.careercup.com/question?id=20308668 http://www.glassdoor.com/Interview/Phone-interview-question-Given-a-string-pattern-of-0s-1s-and-s-wildcards-generate-...
    mrdaniel published this on 11/24/15 | array, math, combination, Google
    Comments
  • +
  • 1
  • -
  • What's wrong with this way?
    /*
        All string combos of 1, 0 and ?
        11?1 => [1101, 1111]
        10?? => [1000, 1010, 1011, 1001]
    */
    
    
    var all = [];
    
    function allCombos(str) {
        let idx = str.indexOf('?');
        
        if (idx < 0) {
            all.push(str);
            return;
        }
    
        var splitStr = str.split('');
        var addZero = splitStr.slice();
        var addOne = splitStr.slice();
    
        addZero.splice(idx, 1, '0');
        addOne.splice(idx, 1, '1');
    
        allCombos(addZero.join(''));
        allCombos(addOne.join(''));
    }
    
    allCombos('10??');
    
    all;
    
  • +
  • 0
  • -
  • Mine was this
    function combination(arr) {
      let elems = [];
      var fn = function(newElem, index) {
        if (newElem.length == arr.length && newElem.indexOf('?') == -1) {
          elems.push(newElem);
        }
        let position = newElem.indexOf('?');
        if (position > 0) {
          let stringElement = newElem.substring(0, position);
          fn(stringElement + '0' + newElem.substring(position + 1, newElem.length), position + 1);
          fn(stringElement + '1' + newElem.substring(position + 1, newElem.length), position + 1);
        }
      };
      fn(arr, -1);
      return elems;
    }
  • +
  • 0
  • -
  • I tried this way..
    function power(arrayStart,iStart,strEnd,arrayRes){
    	for(var i=iStart;i<arrayStart.length;i++){
      	if(arrayStart[i]==='?'){
        	power(arrayStart,i+1,strEnd+'0',arrayRes);
          power(arrayStart,i+1,strEnd+'1',arrayRes);
          return;
        }else{
        	strEnd+= arrayStart[i];
        }
      }
      arrayRes.push(strEnd);
    }
    
    function wild(str){
    	var arrayRes= [];
    	power(str.split(''),0,'',arrayRes);
      
            return arrayRes;
    }
    
    wild('10?1?');
    
  • +
  • 0
  • -
  • Without recursion...
    function wildCard(str) {
      var list = [];
      var wild = [];
    
      if (str.match(/\?/)) wild.push(str);
    
      while (wild.length) {
        var wildStr = wild.pop();
    
        for (var i = 0; i < 2; i++) {
          var aux = wildStr.replace(/\?/, i);
          if (aux.match(/\?/)) wild.push(aux);
          else list.push(aux);
        }
      }
    
      return list;
    }
    
    wildCard('10?1?');
    
    Login to submit a comment