Facebook Interview Question for SDE1s


Country: United States




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

public static int solve(int zeros, int ones) {
        return solve(zeros, ones, false);
    }

    private static int solve(int zeros, int ones, boolean prevOne) {
        if (zeros == 0 && ones == 0) {
            return 1;
        }
        int result = 0;
        if (!prevOne && ones > 0) {
            result += solve(zeros, ones - 1, true);
        }
        if (zeros > 0) {
            result += solve(zeros - 1, ones, false);
        }
        return result;
    }

//And with DP

public class AdjacentOnes {

    public static long solve(int zeros, int ones) {
        Map<String, Long> dp = new HashMap<>();
        return solve(zeros, ones, false, dp);
    }

    private static long solve(int zeros, int ones, boolean prevOne, Map<String, Long> dp) {
        String key = "z" + zeros + "o" + ones + "p" + prevOne;
        if (dp.get(key) != null) {
            return dp.get(key);
        }
        if (zeros == 0 && ones == 0) {
            return 1;
        }
        long result = 0;
        if (!prevOne && ones > 0) {
            result += solve(zeros, ones - 1, true, dp);
        }
        if (zeros > 0) {
            result += solve(zeros - 1, ones, false, dp);
        }
        dp.put(key, result);
        return result;
    }

    public static void main(String[] args) {
        System.out.println(solve(150, 90));
        System.out.println(solve(0, 0));
        System.out.println(solve(0, 1));
        System.out.println(solve(1, 3));
        System.out.println(solve(1, 1));
    }
}

- b001 April 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

int solve(int m, int n){
	if (n-1>m) return 0;
	int k = m-n+1;
	vector<int> dp(k+1, 0);
	for (int j=0; j<=n; j++){
		vector<int> cur(k+1, 1);
		for (int i=1; i<=k; i++){
			cur[i] = dp[i] + cur[i-1];
		}
		dp = cur;
	}
	return dp[k];
}

- waterbucket May 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
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) )

- NoOne April 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
}

- Sbdul April 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));

}

- Sbdul April 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int x

- Sbdul April 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));}

- Sbdul April 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Anon April 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int ones_zeros(int m, int n){
	if (n-1>m) return 0;
	int k = m-n+1;
	vector<int> dp(k+1, 0);
	for (int j=0; j<=n; j++){
		vector<int> cur(k+1, 1);
		for (int i=1; i<=k; i++){
			cur[i] = dp[i] + cur[i-1];
		}
		dp = cur;
	}
	return dp[k];
}

- bucket May 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- ysalary May 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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) :)

- dmn May 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
}

- Alex May 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
* 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
*/

- Eitan BA June 12, 2018 | 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