Interview Questions

  • View all algorithm tutorials
  • 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 ? 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
  • +
  • 3
  • -
  • 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;
  • +
  • 1
  • -
  • 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?');
  • +
  • 1
  • -
  • public class CombinationsZeroOneWildCard { public static void main(String[] args) { char[] input = new char[]{'1', '?', '1', '1', '?'}; printOutput(input, "", 0, input.length); } private static void printOutput(char[] input, String c, int pos, int t) { if (c.length() == t) System.out.println(String.valueOf(c)); if (pos < t && input[pos] == '?') { printOutput(input, c.concat("0"), pos + 1, t); printOutput(input, c.concat("1"), pos + 1, t); } else if (pos < t) { printOutput(input, c.concat(String.valueOf(input[pos])), pos + 1, t); } } }
  • +
  • 1
  • -
  • 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; }
  • +
  • 1
  • -
  • Simpler in Haskell allCombinations :: String -> [String] allCombinations [] = [[]] allCombinations (x:xs) | x == '?' = map ('1':) (allCombinations xs) ++ map ('0':) (allCombinations xs) | otherwise = map (x:) (allCombinations xs) λ allCombinations "10?0" ["1010","1000"] λ allCombinations "10?0?001?" ["101010011","101010010","101000011","101000010","100010011","100010010","100000011","100000010"]
  • +
  • 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?');
    Log in to submit a comment.