Binary array partition: Python interview with a Netflix engineer

[vnnyboy]

These mock interview videos are great, but for this particular interview .... I found the tonality of the interviewer bordering towards rude ...


Although the interviewee was not really on the right track, words like "forget about it" and "you're not able to think beyond this example" would really hamper the confidence of an already confused interviewee ..


If I may ... I believe, a good way to deal with this situation, if one is the interviewer, is to gently hint towards other examples and not use terminology like "forget about it ", which could potentially make the interviewee even more nervous, and hence unable to perform

[TOn-fxgr]

Seriously i can't understand the first question like what we have to do, i always have this problem

[Triavanicus]

Welp.... I was following this interview along, but doing it in rust. It took me 3 hours to get a linear solution, but it is still O(3n) at worst.. (once to count the total number of ones, once to move i and j, and once to test if they are the same number)... I guess I need more practice. It was a really good question though.

[garciajero]

now reading comments and reading the question again, the goal is to divide [1, 1, 0, 1, 1] for example into 3 arrays that contain the same binary value.
now nothing stops you from finding the 1s, saving the index and forgeting about the left overs, the quesiton doesn't say anything about the size of the array, only mention the binary value of them:
so for example [1, 1, 0, 1, 1] i could get 3 arrays that contain a single element and that element is a "1" only. let me know if im being to cheeky

[RaoVenu]

JS solution if anyone is interested


const assert = require('assert').strict;


/**
* O(N) solution
*
* Basic insight is sum of 1s in the array (arraySum) has be divisble by 3. If not, return [-1, -1]
* If divisible, then each section has to have total = arraySum / 3.
* Traverse from left and right of the array to find appropriate indices and return the breakpoints accordingly
* @param nums
*/
const divideArray = nums => {
// Find sum of array
const arraySum = nums.reduce((total, currVal) => total + currVal);
if (arraySum % 3 !== 0) {
return [-1, -1];
}


let lSum = 0;
let lIndex = 0;
while (lIndex < nums.length - 2 && lSum < arraySum / 3) {
lSum += nums[lIndex++];
}


let rSum = 0;
let rIndex = nums.length - 1;
while (rSum < arraySum / 3) {
rSum += nums[rIndex--];
}
return [lIndex - 1, rIndex];
};


assert.deepEqual(divideArray([1, 0, 1, 0, 1]), [0, 3]);
assert.deepEqual(divideArray([1, 1, 0, 1, 1]), [-1, -1]);
assert.deepEqual(
divideArray([1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1]),
[3, 10]
);

[lertuz]

it's hard to think of a solution while talking - more challenging for limited english speaker - i hope they let you write your solution first and talk about it after - thinking out loud is not for everyone

[digroot]

You never try to optimize your solution if you do not have solution yet.

[michaeldang]

1) Drop all 0s in front
2) Iterate through the array and count the number of 1s (Each of the 3 numbers have to contain the same number of 1s)
3) If the total number of 1s is not divisible by 3, return (nothing to do)
4) Find the position of the first 1 of the last number, then get the actual partitioned number
5) Check whether the first 2 partitioned arrays CONTAIN the same pattern as the last number, done.

[mohamedabdul]

I'm still not sure what's the question meant to do.

[benyeh]

Can you upload some system design interview examples?

[LivePython]

Pretty neat topic. Netflix are really impressive and glad they're promoting Python so much. Probably most impressed with how Netflix do failovers in 7 minutes. Nice how they normally send someone to PyCon. Can't wait to see them at 2020!

[viveksingh-dcny]

Please do a mock interview for Goldman Sachs, JP Morgan, Optiver and TowerResearch

[vadiimt]

Sure would help if the interview was in english.

[DrunkLotion]

Tell me if my method is wrong: (still new to coding);
following his if statement (Count%3==0);

1. Count all 1s in the array.
2. divide the Count/3. Assign it as "variable1". Count/3*2 will be "variable2".
3. Brute-force throught the array and find the number "variable1" st 1 in array and that would be possible i.
"variable2" nd 1 in array will be possible j. ("""if "variable1"=3. we will look for 3rd 1 in array and assign the index to i).
4.check if the boolean number from input[0] to array input[i] equals to input[i] to input[j] and input[j] to input[length-1].
('''' we can check by calculating boolean to decimal or by comparing the 1s."'')


if we do step 4 with comparing the whole number including 0. than in situation like it will fail.
@me

[digroot]

one solution would be have two pointers: i and j, one starts from first index, and one start from last index

[RaoVenu]

// JS/Node O(N) solution


const assert = require('assert');

/**
*
* Solution:
* Time complexity O(N)
* Space complexity O(1)
*
* This problem is easy to model if we assume
* O* : Zero or more optional zeroes (each occurence can have different length)
* P : pattern between first and last 1 in partition (both inclusive)
* T : Zero or more optional zeroes (all occurences have the same length)
*
* The original array pattern is
*
* 0*PT0*PT0*PT
* where leading zeroes are irrelevant but trailing zeroes contribute to necessary zeroes. for e.g., for a partition,
* [1], [0, 1], [0, 0, 0, 0, 1] are all equivalent
*
* a) So we first traverse from the back of array to figure out what P and T is. (third partition)
* b) Then when we traverse from front, we skip all zeroes till the first one 1 is. From there, we can find P and T (first partition)
* c) We repeat step (b) to find the second partition. We also find all the un-necessary trailing zeroes. These are now appended to the thrid partition
*/


const count1s = A => {
let count = 0;
for(let i = 0; i < A.length; i++) {
if (A[i] === 1) {
count++;
}
}
return count;
}


const countForward = (A, matchCount, cb, startIndex) => {
let counter = 0;
let i = startIndex;
while(A[i] === 0) {
i++;
}
let start = i;
while(counter < matchCount) {
if (A[i] === 1) {
counter++;
}
if (counter === matchCount) {
break;
}
i++;
}

if (counter !== matchCount) {
return -1;
}


let j = 0;
while(A[i + j + 1] === 0) {
j++;
}
if (j < cb.trailingZeroes) {
return -1;
}

return {
startIndex: start,
endIndex: i + cb.trailingZeroes,
extraTrailingZeroes: j - cb.trailingZeroes
};
}

/**
* Verify sub-patterns are same by checking each value in corresponding index.
* Necessary for very long arrays
* @param {} A
* @param {*} cb
* @param {*} sec
*/
const verifySamePattern = (A, cb, sec) => {
if ((cb.endIndex + cb.trailingZeroes - cb.startIndex) !== sec.endIndex - sec.startIndex) {
return false;
}

let fl = cb.startIndex;
let sl = sec.startIndex;
let length = sec.endIndex - sec.startIndex;
for(let i = 0; i <= length; i++) {
if (A[fl + i] !== A[sl + i]) {
return false;
}
}
return true;
}
const countBackward = (A, matchCount) => {
let counter = 0;
let i = A.length - 1;
let trailingZeroes = 0;
while(A[i] === 0 && i > -1) {
trailingZeroes++;
i--;
}
let start = i;
while(i > -1) {
if (A[i] === 1) {
counter++;
}
if (counter === matchCount) {
break;
}
i--;
}
return {
startIndex: i,
endIndex: start,
trailingZeroes: trailingZeroes,
}
}


const threeEqualParts = function(A) {
if (!A || A.length < 3) {
return [-1, -1];
}
const sum = count1s(A);
if (sum === 0) {
return [0, A.length - 1];
}
if (sum % 3 !== 0) {
return [-1, -1];
}
const cb = countBackward(A, sum / 3);
const cf = countForward(A, sum/3, cb, 0);
if (cf === -1) {
return [-1, -1];
}

if (!verifySamePattern(A, cb, cf)) {
return [-1, -1];
}
const middle = countForward(A, sum/3, cb, cf.endIndex + 1);
if (middle === -1) {
return [-1, -1];
}
if (!verifySamePattern(A, cb, middle)) {
return [-1, -1];
}
return [cf.endIndex, cb.startIndex - middle.extraTrailingZeroes];
};


assert.deepEqual(threeEqualParts([1, 0, 0, 0, 1, 0, 1]), [0, 5]);
assert.deepEqual(threeEqualParts([1, 0, 1, 1, 0]), [-1, -1]);
assert.deepEqual(threeEqualParts([1, 1, 0, 0, 1, 0, 1, 0, 1, 1]), [-1, -1]);
assert.deepEqual(threeEqualParts([1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1]), [4, 10]);
assert.deepEqual(threeEqualParts([1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0]), [15, 32]);

[praveenchukka]

This interviewer is so nice. He guiding so much.