given the output from the first question write a algorithm to calculate how many possible inputs could have created that output. for example.

"1211" could be interpreted as one two and one one || one hundred and twenty one ones.

Question

given the output from the first question write a algorithm to calculate how many possible inputs could have created that output. for example.

"1211" could be interpreted as one two and one one || one hundred and twenty one ones.

Claxon · Accepted Answer

Consider number 1345792

Start from the reverse:  
When at digit 2: Given 2 there are 0 ways to interpret this.
When at 9 :  Just one way that is nine - two possible
When at 7:   We could either add 7 to all possibilities starting with 9 .. i.e it becomes 79 times 2 or we could do 7 times 9 followed by what we see by starting at 2.

Thus the recurrence relation for digits at index 0 to digits at len-3 (we fill in last two digits manually) is this:
f(i) = f(i+1) + f(i+2)

This forms a Fibonacci sequence somehow.  This for the example the output will be this:
index   0   1   2   3   4   5   6
digit     1   3   3   5   7   9   2
f(i)        8   5   3   2   1   1   0 (Fill this from reverse)

Thus when we start at digit 1 or index 0, we have 8 different ways to interpret this

Sigiloso · Answer

#include 
#include 

int count(const std::string &input, int last_cut);

int calcPossibilities(const std::string &input) {
    return count(input, 0);
}

int count(const std::string &input, int last_cut) {
    if (input.size() - last_cut > input;
    std::cout << calcPossibilities(input) << std::endl;
}

Kenneth · Answer

#include 
#include 

int count(const std::string &input, int last_cut);

int calcPossibilities(const std::string &input) {
    return count(input, 0);
}

int count(const std::string &input, int last_cut) {
    int result = 1;
    for (int i = last_cut + 2; i > input;
    std::cout << calcPossibilities(input) << std::endl;
}

Karan · Answer

Wouldn't it just be equal to 2^(n-1) where n is the length of the number.

There is only 1 possibility for a single digit.
For two digits, its' twice of the first one
... 
and so on

J · Answer

In PHP:

echo getNumberOfPossibleInputs("1211");

function getNumberOfPossibleInputs($output) {
  return sizeof(getUniquePermutations($output)) + 1;
}

function getUniquePermutations($output, $prefix="", $suffix="") {
  $len = strlen($output);
  $perms = array();

  $prefix .= " ";
  $suffix = " " . $suffix;
    
  for ($i = 1; $i  2) {
      $perms = array_merge($perms, getUniquePermutations($part1, trim($prefix), trim($part2.$suffix)));
    }
    
    if ($p2Len > 2) {
      $perms = array_merge($perms, getUniquePermutations($part2, trim($prefix.$part1), trim($suffix)));
    }
  }
  
  return $perms;
}

light · Answer

the question just asks us to give the number and not to list all possibilites, hence it is relatively much easier to solve

you can reformulate the question this way:
how many numbers of size n of the form ((1)+0)+ exist
this is a regular expression and what it means is streak of 1s followed by a zero and this pattern repeats.

for example if n=4
you have the following possibilities:
1010
1110

for n=5 you have
11010, 10110
11110
etc.

now how does this relate to the question in hand?
note that it is a very easy translation for example, take n=4 and 1211
1010 ==one 2 one 1
1110==one two one 1

we can easily find this number using a simple combinatorial equation
for a given n number of 0's is at most floor(n/2), and each 0 is prepended with a 1 this we just have to allot the remaining 1's 

let i=number of zeros
thus number of ones = n-i
each zero is prepended to a 1 this n-2*i 1's have to be alloted to i slots (the position before 10 is called as a slot)
this can be done in (n-i-1)C(i-1) ways
thus the answer is

summation [(n-i-1)C(i-1)] for i = [1,floor(n/2)]
we can use a dp to calculate this, which would require o(n) time

light · Answer

sorry, i posted o(n) as complexity while it is o(n^2) using dp.

Dropbox

Pergunta de entrevista da empresa Dropbox

Respostas da entrevista

Empresas seguidas

Buscas de vagas