Facebook Interview Question
SDE1sCountry: United States
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();
}
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).
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;
}
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;
}
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);
}
@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.
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;
}
'''
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
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
}
}
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;
}
}
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;
}
Dumb way
- den.zvon November 09, 2017