## Facebook Interview Question for SDE1s

• 0

Country: United States

Comment hidden because of low score. Click to expand.
3
of 5 vote

Let's look at the pattern of binary representations of consecutive ones vs. non-consecutive ones. Let's shift the number over by 1 bit (on the bottom):

01001
10010

01101
11010

011001
110010

We see that if we AND the numbers, consecutive-one numbers produce non-zero values, so our check if the binary representation has consecutive ones is this;

``````bool consecutiveOnes(int n) {

return ((n << 1 & n) != 0);
}``````

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

``````import java.lang.*;

class Main {

public static int getNum(String prefix, int numBits, int max) {
if (numBits ==0) {
if (Integer.parseInt(prefix, 2) <= max) {
//System.out.println(prefix);
return 1;
}
return 0;
}

int cnt = getNum(prefix+"0", numBits -1, max);
if (!prefix.endsWith("1")) {
cnt += getNum(prefix+"1", numBits - 1, max);
}
return cnt;
}

public static void main(String[] args) {
int max = 10;
int numBits = Integer.toBinaryString(max).length();
System.out.println(getNum("", numBits, max));
}
}``````

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

``````n = 8
t = sum ( [0:n+1] ) -> {
x = \$.o
m = 3 // 11
found = false
// 11, 110, 1100, ...
while ( m < x ){
break( (m & x) != 0 ){ found = true }
m *= 2
}
(found ? 0 : 1)
}
println(t)``````

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

Turning mtao's solution to a Dynamic programming solution.

``````static long [][]DP = new long [64][2];
public static long count(String prefix,String max ,int rem, int prevOne){
if(prefix.compareTo(max) > 0)return 0;
if(rem == 0){
return 1;
}
if(DP[rem][prevOne] != -1)return DP[rem][prevOne];
long ret = 0;
ret += count(prefix + "0", max,rem - 1, 0);
if(prevOne != 1){
ret += count(prefix +"1", max,rem - 1,1);
}
return DP[rem][prevOne] = ret;
}

public static void main(String[] args) {
for(int i = 0; i < 64; i++){
DP[i][0] = -1;
DP[i][1] = -1;
}
long max = Long.MAX_VALUE;
int num = Long.toBinaryString(max).length();
System.out.println(count("", Long.toBinaryString(max), num,0));
}``````

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

Turning mtao solution to a dynamic programming.

``````static long [][]DP = new long [66][2];
public static long count1(String prefix,String max ,int rem, int prevOne){
if(prefix.compareTo(max) > 0)return 0;
if(rem == 0){
return 1;
}
if(DP[rem][prevOne] != -1)return DP[rem][prevOne];
long ret = 0;
ret += count1(prefix + "0", max,rem - 1, 0);
if(prevOne != 1){
ret += count1(prefix +"1", max,rem - 1,1);
}
return DP[rem][prevOne] = ret;
}

public static void main(String[] args) {
for(int i = 0; i < 65; i++){
DP[i][0] = -1;
DP[i][1] = -1;
}
long max = Integer.MAX_VALUE;
int num = Long.toBinaryString(max).length();
System.out.println(num);
System.out.println(count1("", Long.toBinaryString(max), num,0));
}``````

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

A bit more complex, but for large n, this is orders of magnitude faster:

``````public static long count_SumOfSeries(long n) {
if (n == 0)
return 1;

if (n == 1)
return 2;

if (n < 4)
return 3;

long sum = 2;
long a = 0;
long b = 1;
long pOf2 = 4;
while (true) {
if (pOf2 <= n) {
long c = a + b;
sum += c;
a = b;
b = c;
pOf2 <<= 1;
}
else {
pOf2 >>= 1;
n &= ~pOf2;
pOf2 >>= 1;
if (n >= pOf2){
// don't count anything above the midpoint - they all start with 11
n = pOf2 - 1;
}
sum += count_SumOfSeries (n);
break;
}
}

return sum;
}``````

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

A bit more complex (punny!), but orders of magnitude faster for large n:

``````public static long count_SumOfSeries(long n) {
if (n == 0)
return 1;

if (n == 1)
return 2;

if (n < 4)
return 3;

long sum = 2;
long a = 0;
long b = 1;
long pOf2 = 4;
while (true) {
if (pOf2 <= n) {
long c = a + b;
sum += c;
a = b;
b = c;
pOf2 <<= 1;
}
else {
pOf2 >>= 1;
n &= ~pOf2;
pOf2 >>= 1;
if (n >= pOf2){
// don't count anything above the midpoint - they all start with 11
n = pOf2 - 1;
}
sum += count_SumOfSeries (n);
break;
}
}

return sum;
}``````

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

Here's a table lookup that - with 10 million iterations of calculating the count for n = 10,000,000,000,000,000 - shaves about 20% off of my previous algorithm:

``````// fib starting at 2
static long[] counts = {
2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,
196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,
63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,
4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,
225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,
6557470319842,10610209857723,17167680177565,27777890035288
};

public static long count_TableLookup(long n) {
if (n < 2)
return n + 1;

int e = -1;
int p = 2;
while (p <= n) {
e++;
p <<= 1;
}

long sum = counts [e];

p >>= 1;
n &= ~p;
p >>= 1;
if (n >= p) {
// don't count anything above the midpoint - they all start with 11
n = p - 1;
}

return sum + count_TableLookup (n);
}``````

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

``````import math

def get_all(n):
result = []
if n <= 3:
result = [i for i in range(n)]
else:
k = math.floor(math.log(n, 2)) + 1
nxt = pow(2, k-2) + 1
seqs = get_all(nxt)
result.extend(seqs)
m = max(seqs)
i = 0
temp = 0
while i < len(seqs) and temp <= n:
temp = try_append_one_to_left(seqs[i], k-1)
if temp and n >= temp > m:
result.append(temp)
i += 1
return result

def try_append_one_to_left(n, k):
if not n & (1 << (k-1)):
return (1 << k) | n
else:
return None

print(get_all(17))``````

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.