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

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

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

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

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

}

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

``int x``

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

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)

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

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

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

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

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

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.

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.