Facebook Interview Question for SDE1s


Country: United States




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

Possible solution with O(N) time complexity (where N - number of bits) and O(N) memory complexity:
- Calculate how many flips of '0' need to be done when you move from left to right to have all '1' in bits
- Calculate how many flips of '1' need to be done when you move from right to left to have all '0' in bits
- Walk through all positions between bits and find minimal sum of '0'-flips+'1'-flips from both arrays:

private static int minimalFilps(String bits) {
    int flipsFromLeft[] = new int[bits.length()];
    int flipsFromRight[]= new int[bits.length()];
    
    int flips=0;
    for(int i=0;i<bits.length();i++) {
      if(bits.charAt(i)=='0') {
        flips++;
      }
      flipsFromLeft[i]=flips;
    }
    
    flips=0;
    for(int i=bits.length()-1;i>=0;i--) {
      if(bits.charAt(i)=='1') {
        flips++;
      }
      flipsFromRight[i]=flips;
    }
    
    int minFlips=Integer.MAX_VALUE;
    for(int i=1;i<bits.length();i++) {
      if(flipsFromLeft[i-1]+flipsFromRight[i] < minFlips)
        minFlips=flipsFromLeft[i-1]+flipsFromRight[i];
    }

    return minFlips;
  }  

  private static void doTest(String bits, int expectedFlips) {
    int minFlips = minimalFilps(bits);
    System.out.println(String.format("%s\t%d\t%d",bits, expectedFlips, minFlips));
  }
  
  private static void bulkTest() {
    Map<String, Integer> tests = new LinkedHashMap<String, Integer>() {{
      put("1000",0);
      put("0001",2);
      put("1001",1);
      put("1011001",2);
      put("10110000",1);
    }};
    
    System.out.println("Bits\tExpected\tActual");
    for(Map.Entry<String, Integer> test : tests.entrySet()) 
      doTest(test.getKey(), test.getValue());
  }                     
                       
  public static void main(String[] args) {
    bulkTest();
  }

- Matviy Ilyashenko November 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Could be solved using dynamic programming. Here's a quick Python example:

def minflip(b, index=0, all_flips=None, num_flips=0):
	# Lazy init all_flips to keep track of possible flip solutions
	if all_flips == None:
		all_flips = {} # dict { num_flips: binary_array }

	for i in range(index, len(b)):
		if i == 0 and b[0] == 0: # make sure first bit is always 1
			b[0] = 1
		else:
			# break if there's only zeros to the right
			terminate = True
			for j in range(i, len(b)):
				if b[j] == 1:
					terminate = False
			if terminate:
				break

			# Try solution without flip recursively
			minflip(b[:], i+1, all_flips, num_flips)

			# Flip bit no matter what
			b[i] = 1 if b[i] == 0 else 0

		num_flips += 1

	# Discard solution if the 1s on the left, 0s on the right constraint does not hold
	discard = False
	for i in range(1, len(b)):
		if b[i-1] == 0 and b[i] == 1:
			discard = True
	if b[-1] == 1: # Discard if last bit is 1
		discard = True
	if not discard:
		all_flips[num_flips] = b
	if len(all_flips) > 0:
		min_flips = min(all_flips.keys())
		return all_flips[min_flips], min_flips # Return the minimum flip solution
	return None

print(minflip([0,0,0,0,1]))
print(minflip([1,0,1,1,1,0,0,0]))

Time complexity should be O(n^2).

- Tobi November 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) + k soln. -

public static void main(String[] args){
    int[] nums = {0,0,0,0,1};
  	int n = findMiniFlip(nums);
    System.out.println(n);
  }
  
  //1011000; 00001
  public static int findMiniFlip(int[] nums) {
	
     int n = nums.length;
     String s = "";
     for(int i = 0; i < n; i++)
       s += nums[i];
     
     long num = Integer.parseInt(s, 2);
     
     int minXor = n;
     long mask = (1<<(n-1));
     
     while(n-1 > 0){
       long temp = (num ^ mask);
       minXor = Math.min(minXor, countones(temp));
       n--;
       mask = (mask | (1<<n));
     }
     return minXor;
  }
  
  public static int countones(long n){
  	
    int c = 0;
    while(n > 0){
    	n = n & (n-1);
        c++;
    }
    return c;
  }

- sudip.innovates November 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Dumb way

package fb;

public class Flips {

	public static void main(String[] args) {
		int[] input = {0,0,0,0,0,1};
		int n = findMinimumFlips(input);
		System.out.println(n);
	}

	private static int findMinimumFlips(int[] input) {
		int rightflips = 0;
		for (int i = 1; i < input.length; i++) {
			rightflips = rightflips + input[i];
		}
		int leftflips = 1-input[0];
		int flips = rightflips+leftflips;
		for (int i = 1; i < input.length-1; i++) {
			if (input[i] == 1) {
				rightflips -=1;
			} else {
				leftflips+=1;
			}
			if (flips>rightflips+leftflips) {
				flips = rightflips+leftflips;
			}
		}
		return flips;
	}
}

- den.zvon November 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) time and space.

#include<iostream>
#include<unordered_map>
#include<vector>

using namespace std;

int MinFlipsCount(uint8_t const *a, int size, unordered_map<uint64_t, int> &memo, int prev = 1, int idx = 0)
{
	if (idx < 0 ||
		idx > size)
	{
		return -1;
	}
	if (idx == size) {
		return 0;
	}

	uint64_t memo_key = (static_cast<uint64_t>(idx) << 32) | prev;
	auto it = memo.find(memo_key);
	if (it != memo.end()) {
		return it->second;
	}

	int bit = ((a[idx >> 3] & (1 << (7 - (idx % 8)))) == 0) ? 0 : 1;

	int flip_to_zero_count = numeric_limits<int>::max();
	int flip_to_one_count = numeric_limits<int>::max();
	if (idx != 0) {
		flip_to_zero_count = (bit == 0 ? 0 : 1) + MinFlipsCount(a, size, memo, 0, idx + 1);
	}
	if (idx != size - 1 &&
		prev == 1)
	{
		flip_to_one_count = (bit == 1 ? 0 : 1) + MinFlipsCount(a, size, memo, 1, idx + 1);
	}

	memo[memo_key] = min(flip_to_zero_count, flip_to_one_count);
	return memo[memo_key];
}


int main () {
	vector<pair<uint8_t, int>> bit_arrays = {
		{0b10110000, 7},
		{0b10110000, 7},
		{0b00001000, 5},
		{0b10101010, 8},
		{0b00001111, 8},
		{0b10011100, 8},
		{0b10111111, 8},
	};
	for (auto el : bit_arrays) {
		unordered_map<uint64_t, int> memo;
		cout << MinFlipsCount(&el.first, el.second, memo) << "\n";
	}
	return 0;
}

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

@Alex can you please explain your logic here ?

- Anonymous November 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

var num = "1011000";
findMiniFlip(num);

function findMiniFlip(num) {
var arr = num.split("");
arr = arr.map(item => {
return new Number(item);
});

var flips = 0;
if(arr[0] != 1){
arr[0] = 1;
flips ++;
}

if(arr[arr.length - 1] != 0){
arr[arr.length - 1] = 0;
flips ++;
}
var indexFlip = [];

arr.forEach((item, index) => {

if(index != 0 && index != arr.length - 1 &&
!indexFlip.find(item => { return item == index})){

if(item == 1 && arr[index - 1] == 0){
indexFlip.push(index - 1);
flips ++;
}
else if (item == 0 && arr[index + 1] == 1) {
indexFlip.push(index + 1);
flips ++;
}
}

});
console.log(flips);
}

- Larissa November 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) Have two pointers left = 0 and right = str.length -1
2) left searches for zero and right searches for one
3) if (left < right) swap/switch and increment counter by 2
4) repeat 2-3 until left < right and return counter

- Phoenix November 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Anonymous. At each position, we just try to flip to 0 and see how many flips are needed for the rest of the bits. And at the same position we also try to flip to 1 and see how many flips are needed for the rest of the bits. And we choose minimum from the two flip counts. Also, we use memoization to optimize time.

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

@Phoenix. We don't have to keep constant number of zeros and ones in the bit array. So, we have more freedom in making less flips. E.g. for the example of this task:
1011000 -> 1111000,
your algorithm would produce 2 flips.

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

It is not just:
-- Count the number of '1' --> numberOf1s
-- Count the numbers of 1' in array[numberOf1s, array.length-numberOf1s] --> flipCount
-- return 2*flipCount ( for every 1 we flip, we need to flip a 0 )

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

int findMinFlip(vector<int>& binary)
{
	size_t count = 0, last_left = -1, last_right = -1;
	size_t left = 0, right = binary.size() - 1;
	for (; left < right; ) {
		if (binary[left] == 0)
			last_left = left;
		else if (last_left != -1 && last_left != left) {
			count += left - last_left;
			last_left = -1;
		}
		if (binary[right] == 1)
			last_right = right;
		else if (last_right != -1 && last_right != right) {
			count += last_right - right;
			last_right = -1;
		}
		left++;
		right--;
	}
	if (last_left != -1 && last_left != left) {
		count += left - last_left;
		last_left = left;
	}
	if (last_right != -1 && last_right != right) {
		count += last_right - right;
		last_right = right;
	}
	return count;
}

- funcoolgeek November 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

'''
F(i) =
  if A[i] == 0:
    min(1 + F(i + 1), N1[i + 1])
  else:
    min(1 + N0[i + 1], F(i + 1))

F(n - 1) = 0
N0[i]: number of 0's in A[i:]
N1[i]: number of 1's in A[i:]

Bottom-up DP complexity:
Time: O(n)
Space: O(1)
'''
from itertools import accumulate, islice

def solution(binary_array):
  n = len(binary_array)
  if n <= 1:
    return 0

  N0 = accumulate([1 - bit for bit in binary_array[::-1]])
  N1 = accumulate(binary_array[::-1])
  f = 0
  for n0, n1, i in zip(N0, N1, range(n - 1, -1, -1)):
    bit = binary_array[i]
    if bit == 0:
      f = min(1 + f, n1)
    else:
      f = min(1 + n0, f)

  return f


A = [1, 1, 0, 1, 0, 0, 0, 1, 0]
attempt = solution(A)
print(attempt)
assert attempt == 2

A = [0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1]
attempt = solution(A)
print(attempt)
assert attempt == 5

A = [1, 0, 1, 1, 0, 0, 0]
attempt = solution(A)
print(attempt)
assert attempt == 1

- vlchen91 November 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.


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