Facebook Interview Question
SDE1sCountry: United States
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));
}
}
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));
}
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));
}
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;
}
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;
}
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);
}
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))
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;
- SK May 01, 2017