Facebook Interview Question
SDE1sCountry: United States
/*
Imagine the problem as finding all integers with
n 1s and m 0 s such that in the binary representation
There is no '*11*'. And we are good. So....
*/
def do_garbled(m,n){
range = [0 : 2 ** ( m + n )]
count = 0
for ( x : range ){
s = str(x,2)
s = '0' ** (size(s) - m - n) + s
continue ( n != sum(s.value) -> { _'1' == $.o ? 1 : 0 } )
continue ( s =~ '.*11.*')
count += 1
}
}
// now in full ZoomBA mode, we can write this:
m = 2
n = 2
res = from ( [0 : 2 ** ( m + n )] , set() ) as {
s = str($.o,2)
s = '0' ** (size(s) - m - n) + s
} where {
n == sum($.o.value ) as { _'1' == $.o ? 1 : 0 } } where {
$.o !~ '.*11.*'
}
println ( res )
println ( size(res) )
static long [][][]dpp;
public static long solve(int n, int m){
if(n == 0)return m == 1 ? 1 : 0;
if(m == 0)return 1;
dpp[0][0][0] = 0;
dpp[0][0][1] = 0;
dpp[0][1][1] = 1;
dpp[0][1][0] = 0;
for(int i = 2; i <= m; i++){
dpp[0][i][0] = 0;
dpp[0][i][1] = 0;
}
for(int i = 1; i <= n; i++){
dpp[i][0][0] = 1;
dpp[i][0][1] = 0;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
dpp[i][j][0] = dpp[i - 1][j][0] + dpp[i - 1][j][1];
dpp[i][j][1] = dpp[i][j - 1][0];
}
}
return dpp[n - 1][m][0] + dpp[n - 1][m][1] + dpp[n][m - 1][0];
}
public static void main(String[] args) {
int n = 140;
int m = 65;
dpp = new long[n + 1][m + 1][2];
System.out.println(solve(n , m));
}
static long [][][]dpp;
public static long solve(int n, int m){
if(n == 0)return m == 1 ? 1 : 0;
if(m == 0)return 1;
dpp[0][0][0] = 0;
dpp[0][0][1] = 0;
dpp[0][1][1] = 1;
dpp[0][1][0] = 0;
for(int i = 2; i <= m; i++){
dpp[0][i][0] = 0;
dpp[0][i][1] = 0;
}
for(int i = 1; i <= n; i++){
dpp[i][0][0] = 1;
dpp[i][0][1] = 0;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
dpp[i][j][0] = dpp[i - 1][j][0] + dpp[i - 1][j][1];
dpp[i][j][1] = dpp[i][j - 1][0];
}
}
return dpp[n - 1][m][0] + dpp[n - 1][m][1] + dpp[n][m - 1][0];
}
public static void main(String[] args) {
int n = 140;
int m = 65;
dpp = new long[n + 1][m + 1][2];
System.out.println(solve(n , m));
}
static long [][][]dpp;
public static long solve(int n, int m){
if(n == 0)return m == 1 ? 1 : 0;
if(m == 0)return 1;
dpp[0][0][0] = 0;
dpp[0][0][1] = 0;
dpp[0][1][1] = 1;
dpp[0][1][0] = 0;
for(int i = 2; i <= m; i++){
dpp[0][i][0] = 0;
dpp[0][i][1] = 0;
}
for(int i = 1; i <= n; i++){
dpp[i][0][0] = 1;
dpp[i][0][1] = 0;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
dpp[i][j][0] = dpp[i - 1][j][0] + dpp[i - 1][j][1];
dpp[i][j][1] = dpp[i][j - 1][0];
}
}
return dpp[n - 1][m][0] + dpp[n - 1][m][1] + dpp[n][m - 1][0];
}
public static void main(String[] args) {
int n = 140;
int m = 65;
dpp = new long[n + 1][m + 1][2];
System.out.println(solve(n , m));}
This can be solved with Dynamic Programming.
Also remember if n - m == 1 i.e. if number of 0s is one less than that number of 1s the result is always 1.
public static int DP(int m, int n){
if(m == 0 && n == 0) return 1;
if(m == n-1) return 1;
int[][]T = new int[m+1][n+1];
for(int i = 0; i<T.length; i++){
T[i][0] = 1;
}
//T[0][1] = 1;
for(int i = 0; i < T.length; i++){
for(int j = 1; j< T[i].length; j++){
if(j == i+1){
T[i][j] = 1;
}
else if( j > i+1) break;
else if(j == i){
T[i][j] = T[i-1][j]+T[i-1][j-1];
}else{
T[i][j] = T[i][j-1]+T[i-1][j];
}
}
}
return T[m][n];
}
Time Complexity : O(M x N)
Space Complexity: O(M x N)
first you put one 0 between all ones. Then distribute the rest of the zeros between the "o + 1" buckets. if "o" is the number of ones.
auto cache = vector<int>(2, 1);
int fac(int m) {
int count = cache.size();
if(count > m) {
return cache[m];
}
int result = fac(m-1) * m;
cache.push_back(result);
return result;
}
int permutation(int n, int M) {
if(n>M) {
return 0;
}
return fac(M)/(fac(n)*fac(M-n));
}
int ones_zeros(int o, int z) {
int extraZeros = z - o + 1;
return permutation(extraZeros, extraZeros + o);
}
I think there is a combinatoric solution to this problem.
Let's say we have n position and k ones that we want to arrange. There are C(n,k) combinations to do this. from all this combinations we need to deduct those that have two adjacent once- there are (n-2)*C(n-2,k-2) of these. So result would be something like C(n,k) - (n-2)*C(n-2,k-2) :)
int Count(int ones, int zeros, unordered_map<tuple<int, int, bool>, int> &memo, bool prev_one = false)
{
if (ones == 0 &&
zeros == 0)
{
return 1;
}
if (ones < 0 ||
zeros < 0)
{
return 0;
}
tuple<int, int, bool> memo_key = make_tuple(ones, zeros, prev_one);
auto it = memo.find(memo_key);
if (it != memo.end()) {
return it->second;
}
int count = Count(ones, zeros - 1, memo, false);
if (!prev_one) {
count += Count(ones - 1, zeros, memo, true);
}
memo[memo_key] = count;
return memo[memo_key];
}
/*
* it seems that this can be solved with math - no need for code.
* we have M bits of '0'
* N bits of '1'
* we need a permutation (out of a total of 2^(N+M)) in which no '1' is adjacent to another
*
* solution
* lay down the '1' bits in a row
* next, use N-1 '0' to separate them. this make a valid permutation apart from length.
* we are now left with M-N+1 instance of 0 which we can put anywhere (between any 2 bits).
* any such selection will be valid & also different than previous, as long as we only pick between the '1' -s
* bcz if we have 3 adjacent '0' bits, we can add another '0' in 4 positions but its all the same. order of '0' bits doesnt matter
* so the remaining bits can each pick a position betwen adjacent '1' or at the ends - its N+1 options
* the same is applicable for all remaining '0' so a total of (N+1)^(M-N+1) permutations
*
* if M < (N-1) then there arent enough '0' to separate every adjacent '1', hence answer is 0.
*
* Implementation
* simple imple to verify the analysis
*/
- b001 April 29, 2017