## Facebook Interview Question for SDE1s

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 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;
}
}``````

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

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

Hi Matviy, can u please explain in the below line of code:
if(flipsFromLeft[i-1]+flipsFromRight[i] < minFlips)
why are you considering flipsFromLeft[i-1] ?? instead of flipsFromLeft[i]

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
for i in range(1, len(b)):
if b[i-1] == 0 and b[i] == 1:
if b[-1] == 1: # Discard if last bit is 1
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).

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;

while(n-1 > 0){
long temp = (num ^ mask);
minXor = Math.min(minXor, countones(temp));
n--;
}
return minXor;
}

public static int countones(long n){

int c = 0;
while(n > 0){
n = n & (n-1);
c++;
}
return c;
}``````

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

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

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

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

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.

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.

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 )

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

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

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

Its a bit unclear, why would 00001 --> 10000 require 2 flips? Is 00000 (1 flip) not an acceptable answer? The question doesn't require you the preserve number of 1s. It just asks for min flips.

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

@dora. Yes, the description looks a bit inconsistent. E.g. in Example 1 the amount of ones is not preserved: 1011000 -> 1111000 only need one flip 0 -> 1.

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

Find the position for the last 1 with min number of flips required by counting the 0s from the left and 1s from the right. Return the smallest sum of the two

``````object FindMinFlip extends App {
println(flips("0000001"))
println(flips("1010001111010"))

def flips(in: String): Int = {
val count = Array.fill(in.length)(0)
var i = 0
var zerosToLeft = 0
while (i < in.length) {
if (in(i) == '0') {
zerosToLeft += 1
}
count(i) = zerosToLeft
i += 1
}

var onesToRight = 0
i = in.length - 1
while (i > 0) {
i -= 1
if (in(i + 1) == '1') {
onesToRight += 1
}
count(i) += onesToRight
}
count.min
}

}``````

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

``````public class NumberOfFlips {

public static void main(String[] args) {
System.out.println(findFlipCount("1000")==0);
System.out.println(findFlipCount("00001")==2);
System.out.println(findFlipCount("1011000")==1);
System.out.println(findFlipCount("1011001")==2);
}

public static int findFlipCount(String input){
int numOfOne = 0;
int numOfZero = 0;

int flips= 0;
for(int i=0;i<input.length();i++){
if(input.charAt(i) == '1'){
numOfOne++;
}else{
numOfZero++;
}
}
if(numOfOne == input.length()|| numOfZero == input.length()){
return 0;
}
for(int k=1;k<=numOfOne;k++){
if(input.charAt(k-1) == '0'){
flips++;
numOfZero--;
}
}
for(int k=1;k<=numOfZero;k++){
if(input.charAt(input.length()-k) == '1'){
flips++;
}
}
return flips;
}
}``````

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

``````public static void main(String[] args) {
System.out.println(findFlipCount("1000")==0);
System.out.println(findFlipCount("00001")==2);
System.out.println(findFlipCount("1011000")==1);
System.out.println(findFlipCount("1011001")==2);
}

public static int findFlipCount(String input){
int numOfOne = 0;
int numOfZero = 0;

int flips= 0;
for(int i=0;i<input.length();i++){
if(input.charAt(i) == '1'){
numOfOne++;
}else{
numOfZero++;
}
}
if(numOfOne == input.length()|| numOfZero == input.length()){
return 0;
}
for(int k=1;k<=numOfOne;k++){
if(input.charAt(k-1) == '0'){
flips++;
numOfZero--;
}
}
for(int k=1;k<=numOfZero;k++){
if(input.charAt(input.length()-k) == '1'){
flips++;
}
}
return flips;
}``````

Comment hidden because of low score. Click to expand.

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.