Facebook Interview Question for SDE1s


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

- SK May 01, 2017 | Flag Reply
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));
     }
}

- mtao April 30, 2017 | Flag Reply
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)

- NoOne April 30, 2017 | Flag Reply
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));
}

- Sbdul April 30, 2017 | Flag Reply
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));
	     }

- sbdul April 30, 2017 | Flag Reply
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;
		}

- Chris Judge April 30, 2017 | Flag Reply
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;
		}

- cjudge@grandecom.net April 30, 2017 | Flag Reply
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);
		}

- cjudge@grandecom.net May 01, 2017 | Flag Reply
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))

- lalat.nayak July 02, 2017 | 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