Python Interview with a Netflix engineer

Watch someone solve the binary array partition problem in an interview with a Netflix engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Binary array partition

Interview question

If it is possible, return any [i, j], such that * Z[0], Z[1], ..., Z[i] is the first part; * Z[i+1], Z[i+2], ..., Z[j-1] is the second part, and * Z[j], Z[j+1], ..., Z[Z.length - 1] is the third part. * All three parts have equal binary value.

Interview Feedback

Feedback about Orange Storm (the interviewee)

Advance this person to the next round?

How were their technical skills?

2/4

How was their problem solving ability?

2/4

What about their communication ability?

2/4

1. Take more examples to find patterns and identify relevances of input values. 2. Focussing on patterns through examples should be the first step to solve a problem, than trying to optimize the brute force (code). 3. You might not get these many hints in an actual interview, so pro-actively think out aloud and propose solutions so that interviewer might be tempted to help you where you falter. Good luck!

Feedback about Heuristic Panda (the interviewer)

Would you want to work with this person?

Yes

How excited would you be to work with them?

4/4

How good were the questions?

4/4

How helpful was your interviewer in guiding you to the solution(s)?

4/4

The question an interesting new question to me, and I started by exploring the brute force solutions, then gradually realized the properties of binary integers by the very helpful hints from the interviewer. Thanks so much for your time, the hints, and feedback! I'll practice more and also think more about how to approach the problem(s)!

Interview Transcript

Orange Storm: Hi.

Heuristic Panda: Hi are you able to hear me?

Orange Storm: Yeah I can hear you.

Heuristic Panda: Great, okay yeah I can hear you too. So welcome to this interview, um mock interview. So let me just get started with a brief introduction about myself. I have 10 plus years of experience working in the industry of which past six years have been in the Bay Area and before that I was in India. Currently, I'm working for a media company in the Bay Area and I've been a backend engineer throughout working on Java and related technologies. Yeah that's about me why don't you tell me a bit about yourself.

Orange Storm: Sure, sure. I've been working the tech industry for just past my year and joined the company after school and I've been working on the those DevOps automations so using Python and to automate the tasks so that we can reduce the human errors and also just save some time.

Heuristic Panda: Gotcha, sounds good sounds good. Great so the way the code work is we would dig deeper into this coding question and typically I will allocate 45 minutes around performance for the question and beyond that we'll stop and we'll go through the feedback if any. I'll also be documenting some of this feedback so that should be available to you on the portal of interviewing.io. And in between if we just if we have some audio issues then I think we can jump on to a phone call. I think they give us an option to connect with a pin code so we'll look out for that in case we run into that because I've run into in the previous interview at all done sometimes. So yeah, just giving you a heads up so that we know what to do when we run into that. Okay and so great uh any questions so far?

Orange Storm: No that's about it yeah.

Heuristic Panda: Okay so uh have you worked on this environment before, the interviewing.io coding environment?

Orange Storm: Yeah I've done a couple of them.

Heuristic Panda: Oh okay, okay so pick a language of your choice.

Orange Storm: Tonight is Python.

Heuristic Panda: Yeah sure, feel free to use any language.

Orange Storm: Okay I will switch to Python 3 right now.

Heuristic Panda: Yeah sure, so I will just type in the question. Sure yeah so this is the question for you. I think three quotes is comment right?

Orange Storm: I'm sorry, what's that?

Heuristic Panda: Is this a comment I mean is this comments in Python, the three quotes?

Orange Storm: Yeah three quotes is a multi line comments, yeah it's good.

Heuristic Panda: Right yeah okay, I forget I didn't remember that yeah okay.

Orange Storm: Yeah it's like in Java is doing like this, but similar.

Heuristic Panda: I know yes yes exactly exactly.

Orange Storm: I see, cool. Okay I see so it's done, it's an array with only 0 and 1. Okay I see, so let me just get the functions footprint here, def divide_array(input). okay the input will be like an array of zero and one. Output... So basically output is going to be the index, right? Indexes of the...

Heuristic Panda: Yes.

Orange Storm: So is it possible like the array is actually less than length of three? So it's like zero and one, so we couldn't find any and we should...

Heuristic Panda: Yeah those edge cases. You can right now assume that it will be more than three or more three or more, the length we will be three or more, yep.

Orange Storm: Okay, I see, more so for example like example one [1, 0, 1, 0, 1] and we can split at zero. Zero should be inclusive. Okay it's going to be from zero to one, one two three. Okay I see, so it's actually found each one equal to one. I see, yeah I think just like thinking out loud we can just have like a one-point, right? it's going to be two indexes so we have two pointers like first one will be the starting point the second one will be like maybe the end point. I haven't decided yet, but it's going to be like it's going to be after the first one. We can like swipe the... check each starting point like for example, the first one so it's going to be I and J. For [1, 0, 1, 0, 1] and in first like i will be here and then in each a inclusive so I will set j here. So the first one is1, the second one right now is 0, and the third one is 101. Okay we can do something like for each i we can check the rest of the j and if like the value of i is equal to j, we can continue... We can like check if the j like the rest of the body are actually...

Heuristic Panda: Okay the third part is the same or not.

Orange Storm: Right, something like that.

Heuristic Panda: Okay, okay. So what would be the time complexity in this case?

Orange Storm: It's gonna be like one, two... Assuming we have n of elements and for each one we're going to swipe n times and we're going to check each j, we're going to check n like n - 1 basically so it's n^2. j is like a swiping...Yeah but we have to calculate the value so it's going to be like swipes the rest of the array as well. So I think it's ,I mean it could be cubed?

Heuristic Panda: It could be n^3.

Orange Storm: Like for i we are swiping from 0 to all the way to like n - 2 and for j we are swiping on like 1 to n - 1. And for each j, we are actually checking the rest of the value and I mean assuming like there is no patterns in this array and we're checking one by one, like worst case it's going to be, I think it's going to be... Because for checking the third value going to be you have to loop through the rest of the array and you are actually doing multiple times. So I think it's worst case will be n^2. I'm sorry, n^3, yeah.

Heuristic Panda: Okay, okay.

Orange Storm: Um so I'm just thinking out loud right now, because I'm kind of seeing like multiple duplicate calculations, right? Because you are calculating [0, 1, 0, 1] and then you are calculating [1, 0, 1]. You just keep doing the same calculation multiple times. Maybe we can do some pre-processing, so that we don't need to calculate all the time. And yeah that's what I'm thinking right now. So basically for pre-processing... Pre-processing... So we'll have like I maybe I will say nums that is in front... Something like I'm checking from the front, and sonums_front[i] means from 0 to i. Like equals to the integer of its representation of like it's array input high. So it's going to be like [1] or [1, 0], so it's going to be like 3 basically. So we're going to calculate each one and yeah, I mean during the past pre-processing we can optimize that by like times 2 and plus the like the digits, because we are moving one digit further.

Heuristic Panda: Okay, okay, okay. What would be the value add to your complexity?

Orange Storm: So I think it's going to be reduced to until because for each time we are checking i and j, it's like a indexing so we can call this not in front to get from 0 to iLike how many like integer of the representation of...

Heuristic Panda: So how much would it be?

Orange Storm: Like swiping n plus you can check each one, so I think it can be reduced to n^3.

Heuristic Panda: But you did mention that initially it was n^3, right?

Orange Storm: No, I'm sorry ,I mean initially it was n^3, but right now we're trying to reduce to n^2, so n^2.

Heuristic Panda: Okay okay, that's fine. Now let's get back to the examples right? Before we jump into this like optimization with the pre-processing. What do you observe about the zeros and the ones in each partition, the number of zeros, the elements of the number of ones in each partition and how about the zeros to the left or the right in each partition.

Orange Storm: In each partition? Oh sorry I'm trying to understand your question.

Heuristic Panda: So in the example one, can you write me the three partitions?

Orange Storm: In example one, right?

Heuristic Panda: Yeah.

Orange Storm: Okay yeah so it will be 0 to 0, so this is one. And it's going to be 1 to 3, so it's [0, 1], and then it's going to be 3 to the end, so it's going to do 0 and 1, that's going to be the partition. And yeah, I think that's the partition.

Heuristic Panda: Ok so what do you see about what... right. So what do you see about in this particular example, what do you see about the relevance of number of ones in each partition?

Orange Storm: Oh I see, it's actually each partition has only one 1.

Heuristic Panda: Okay and what about zeros, like the relevance? Is there a relevance of number of zeros and, if so does it matter if it is on the left of the leftmost 1 or the right of the rightmost 1?

Orange Storm: It doesn't matter on the leftmost, but it does matter on the right side because that's going to advance one more digit so for that one time, it will be actually be 3. Oh, I'm sorry, one time is actually 2. Right so if you look to the power of 1 and the plus 0 times.

Heuristic Panda: Yeah so if your example was this, each of the partition would be [1, 0] and [0, 1, 0]. Right? And also can you... so using all these observations, can you figure out what the partition should look like, what the rough indices of the i and j would be?

Orange Storm: Oh okay, I see what you're saying. Oh, you mean i and j, so what's the partition of the i and j? So I start from here and... Okay from here... Okay so are we trying to like optimize the process of calculating each integers?

Heuristic Panda: Yeah I want you to think... Right now what you have done is you have jumped into a solution, you are trying to optimize the solution that you initially proposed. I want you to see look at the problem and think in a different direction, so that you come up with an even better algorithm.

Orange Storm: Oh okay, so right now we are like based on the pre-processing approach and we are trying to get each...

Heuristic Panda: Yeah, I want you to come out of that. So so we'll get into it if if time if we are running short on time, let's spend the next probably five more minutes into thinking whether we can optimize on looking at the examples right? What do the examples tell you about? What are the relevance of 1's and 0's. And can you figure out in linear time a solution?

Orange Storm: Okay I see. Yeah I think it's actually... So if you move like from i to j, the j if the j is moving like to the right, it's actually getting bigger.

Heuristic Panda: Now I don't want you to worry about, so that is your initial solution right? I don't want you to think about it. I want you to come out of it and think about what is the relevance of zeros and ones. Leading zeros, trailing zeros, the number of ones? Can you find out i and j without doing the iteration at all? Based on the number of 1's. Can you find the i and j? Directly? Without going through two loops, nested loops. no going nuts i

Orange Storm: Okay, so for eachi, and we have some value, then we just need to find... Okay, so for example if i is actually stop at the second position, like [1, 0], so we know i is actually j. We can starting from the next one, and then we can count. Okay count how early many... So am I getting close? Like if it's [1, 0] and for j we can just get the next one because the middle part doesn't matter that's, actually the trailing, like the starting zeros. So for i it's actually the same because like thei has to be start from zero otherwise it like it doesn't doesn't matter, it's going to be zero. So i starting from one.

Heuristic Panda: So what are your big points for your i and j right now? Like how many 1's should each of this partition's have? Can they have different number of 1's?

Orange Storm: No they can't, they have to have the same ones and..

Heuristic Panda: Right so till when would you go to find i and j.

Orange Storm: For example, for i, I have [1, 0].

Heuristic Panda: Make a complex example, take a complex example wherein there are a lot more ones and zeros because you are stuck to this basic example and you're not able to think beyond that.

Orange Storm: Oh we can get another example. Like this and so starting from I'm here so, i equals to one, and j is actually one, so right now i and j...

Heuristic Panda: No, forget that yeah... Forget about i and j right now. How many ones are there? How many ones are there in your example?

Orange Storm: Right now it's a six.

Heuristic Panda: So how many per partition?

Orange Storm: Okay so I have to make sure like... Oh I see you're saying finally. Yeah so I have six ones, so each one has to have two.

Heuristic Panda: And how many zeros to the right of the rightmost one?

Orange Storm: To the right of the most one? Four zeros. Oh you mean in this list?

Heuristic Panda: In this partition.

Orange Storm: In this partition there is only one. I mean the last ones are after the last one.

Heuristic Panda: Exactly so you can deterministically find out how many zeros to the right of the rightmost one are required from the last partition right?

Orange Storm: From the last... Yeah right, okay.So now you're not rid of this zero.

Heuristic Panda: Exactly so now you can find i and j. You have all the information that you need to find i and j now.

Orange Storm: Okay I think what you are saying is actually, so from the left we have to check the first one and the from the right we have to check the like zeroes, because those are the things we cannot get rid of. Like neither starting from one end all the way, so no matter where is j, it has to be end with zero. Okay, so basically. Okay so we can count how many ones we have and so if it's... so if it's like an odd number of like if there are seven of ones and you cannot evenly split those seven ones to three partitions we can return [-1, -1], right? Because they couldn't be equal.

Heuristic Panda: That's right. So what if there are 6 and what do you do if there are 6?

Orange Storm: So I mean so basically we just check how many ones like and check ones and see if it equals to 0. If it's not, just return [-1, -1] because they couldn't get anything. So once and we can then flip them to each one. Each one has like a for example six, each one has two of ones and then we can starting from the left. Starting from left, get two one and like so and we... It's possible that we can stop until next one. And then starting from right, get two ones, and we can actually stop until next one so that we don't take effect over. Okay so basically, so it's going to be... We can check for each side how many different combinations we have but I think that part. Okay the only thing so from this last part it's actually only affecting the left value. Like a different i, because until we see the next one it's going to affect our affecting our left value but doesn't affect our middle value, because the middle is treating zero will be like... it doesn't matter. And from right, all right we're going to see... Okay, and we're gonna shrink from both sides and check that. Okay I see. So like let me figure out what the stop condition is... because at some point we need to return the indexes.

Heuristic Panda: So but where are the zeros coming into picture here?

Orange Storm: Oh where does the zeros?

Heuristic Panda: You are you are not taking into consideration zeros right?

Orange Storm: No I mean like I have, for the step three I'm stopping until I see the next 1, so like this could be zero... Like it could be multiple zeros in the middle and that's going to be like the loop like how many zero I can have and it's going to be affecting my...

Heuristic Panda: Okay, okay, okay so I think you'll need some more time to discuss on this further, so in the interest of time why don't we go ahead and implement the the earlier algorithm that you proposed, wherein you have the pre-processing and you find out all the permutations because this will take some more time and I want you to code something for me.

Orange Storm: Okay, yes.

Heuristic Panda: Yeah, yeah, makes sense? Because this is yeah... you're missing out a few points over here and you know we might spend another 5-10 minutes on it, I don't want that to happen and you running short of time to implement something right? So let's do the initial?

Orange Storm: Okay I think like are we getting close? Because I think the idea, you're like recommendation is very good. I mean we're actually... it's obvious.

Heuristic Panda: But like you are not actually taking into consideration the zeros to the right of zero and utilizing that to make information in the loop itself. Right now you have you will be generating more permutations. You'll have to check like how many zeros to the right of the rightmost 1 in each partition, which will be adding and then check for the values.

Orange Storm: Okay so for 6, like step 3 & 4 those are multiple zeros, so we're going to loop.

Heuristic Panda: Yeah so you shouldn't be doing... I mean that's not required basically. Because you are not utilizing on some of the observations that you pointed out.

Orange Storm: Okay.

Heuristic Panda: So well okay so I'll leave the decision to you. Do you want to continue analyzing this further or do you want to code? It's up to you.

Orange Storm: Maybe yeah maybe we can quickly discuss this because we're getting close right, makes sense to me. It's a really nice approach.

Heuristic Panda: Okay so you mentioned that the right, but the third partition. From the the third partition you can figure out how many zeros to the right of the rightmost one are required, right? How are you using that information?

Orange Storm: Are required? Oh okay I see I see what you're saying. Oh okay, so I can actually check the left one, the left partition because it can't be less than that, and it has to be more than more than... actually I think it has to be equal to the number of zeros creating the left partition. So for example here we have one zero in the last, we have only one zero. So from the left partition I have to starting from [1, 1, 0], because I have to have one zero, because the third partition is going to have one zero anyway. I mean it's going to have one zero and so we will start from the one 0. So basically we are reducing some like some permutations. Like we are trying decided to end of the left partition so though it has the same trailing zeros as the last partition. Am I understand correctly? For the line 28, it's [1, 1, 0]. It couldn't be [1, 1] because the last one I have one, I have the one 0 at the end so the third partition is going to have a one trailing, so I need to make sure...

Heuristic Panda: How about the second partition?

Orange Storm: The second partition will starting from the first one is... so, I think we can just like check in the middle and what to value. So to say we want to make sure that left and right they are actually equal.

Heuristic Panda: So do you think checking on the equality is a good thing to do you think... So first thing is finding the i and j. So can they do multiple solutions to this? Let's try to answer that.

Orange Storm: Can we have a bunch of solutions to this? I think we are splitting different... so in the event one we know for sure and we just little check how many trailing zeros each one have. I think it should... I couldn't think of multiple solution. Right now I will say it's like one solution.

Heuristic Panda: Okay okay, so assuming that that there's only one solution right... now just a minute it, hold on. Yeah, so assuming that there is only one solution, right? So uh can you find out the i and j in that case and then we do the quality check later okay. Finding the partition is one thing and then checking if all the partitions are same is the second problem.

Orange Storm: Okay yeah.

Heuristic Panda: So that way you don't need to complicate your code.

Orange Storm: Okay so like find the i and j. Then check quality. Okay yeah so find i and j, I think we were pretty much almost there because we check how many ones we have and so that's going to give us the exactly i and so we're from right you can check how many ones we have and that's going to give us how many zero is required. So that I can move my i. If I can move my i without like I mean like if I can have my i satisfy this requires zero then I can compare. If I cannot it's going to return like minus one minus one.

Heuristic Panda: Okay okay that is the first partition, how about the second partition?

Orange Storm: The second partition is the middle partition right?

Heuristic Panda: Yeah.

Orange Storm: So the middle partition... since we already decided how many ones for each partitions we have. We will check from the the end of the second partition, which is j and we can see if it's actually can be have the required zero. Like same as the i and j. For example the the line 28 there is only one and we're going to check if it's possible to have the last one. I'm sorry last two, only one zero,the just the rightmost one. And if it, has then we can continue check for each like check the equality.

Heuristic Panda: Okay okay okay, so does that... yeah I mean I think that might work. It depends on how you are coding for these things. But what is the time complexity now?

Orange Storm: The time complexity will... okay I think it's going to be O(n), linear, because at most we're going to check only like each one is going to check once.

Heuristic Panda: Okay okay, so let's get started with the coding. We have 20 minutes so let's see how much we can progress, yeah.

Orange Storm: Sure sure. Let's try it in code now. Okay so first one that we will find how many ones. What like edge cases. We can check from the right like like check j first. I set up some pointers... I think it's in the middle pair there's going to be an n, but we can decide later so let's say required... In Python it's actually boolean so we forget J. So what if 1 equals review now could be no ones. Okay that's actually a kind of a special case because if there is no one we can actually return anything was zero to return zero. This case is actually it could be multiple solutions because it's not always true and that's kind of an edge case

Heuristic Panda: That's an edge case, yeah. You can be done any random thing, that's fine.

Orange Storm: Okay okay yeah I see. I can return zero and one. Let's think, I think it's going to be finding the one anyway it's not going to fail because we already count how many ones and it should find the last point like require one position. Okay. Okay so I think this one right now we have j. Oh we have to count how many required zeros. Oh I need to like stop it. Okay so if like ones equals to zero. Let's see I'm checking ones and if it's one I'm going to plus one. If it is not one, so it is zero and right now we don't have any ones. We're going to say require zeros is actually plus one so that we can also get the required zeros. Let's see all right so now we have j and we also have required zeros. I think the better name it will be required ones but it's less than that... what if it's actually equal so it's going to break off condition. If it cannot found we should just return -1. How do I decide that? So i is less than j I think that's gonna be for sure. Okay that's actually equal. We should check ones only we don't need to check the... So I'm checking ones only I don't want to check zeros. I need to find an i. Okay so when our ones it's actually I can check how many zeros should I can get. So I keep looking that if it is not equal to zero actually I should break. Okay I think it's just a break the loop because I already found enough their exteriors one zero and it's gonna break and that's actually... I'm going to return such cases because I couldn't find any required zeros. It's not going to be equal so... Right now I have my i actually equals to should be i minus one if it's inclusive. Okay so we now I can check equality right because I only find an i and j. So far are we still good? I think we are running out of time but...

Heuristic Panda: Yeah I'm just looking at this... so you have found i and j right? Okay why don't you think so before going to equality why don't you run this to print i and j. Let's do that right, and we can... yeah because I think i is going to be the previous one because you actually found... it's going to be maybe like this you know because i is actually starting point of the middle part. So let's say middle-high... something like this. So the middle starting point will be i so that way... Let's take another example, add a little journey...

Orange Storm: And that's one and that's a three. So it's going to be a zero, one okay.

Heuristic Panda: Let's start with a break, right?

Orange Storm: What do you mean first one will be a break?

Heuristic Panda: This one will break right? The first example would break. If you'll try to fix it that. Anyway we are just left with five minutes so I think we should stop here because the the real interview we would stop five minutes before this right? So I think so you are on the right path but I think you need to... somewhere in the whole logic you're missing out things we'll have to sit and debug. We'll have to print out those values and figure out like what those values are at that point in time. But I don't think so by increasing or decreasing the the count will fix the issue. It's in the conditions when you are going through it somewhere else and the condition. Good, so let's spend the next five minutes probably go into the question and the feedback basically right? So what did you think about the question?

Orange Storm: Oh you mean this question?

Heuristic Panda: Yeah.

Orange Storm: I think it's a really good question. I've never seen this before, but it's really a good question to me.Because I can literally see how much time I can save by actually like analyze the like a characteristics of zeros and ones, like a binary...

Heuristic Panda: Exactly so that was a very good point. Exactly so that was the biggest flaw in this whole question, this whole interview for you. So the thing is, there are other ways to approach your problem right? So one is trying to understand what the question is about, what are the different examples, what are the relevance of the values given in this examples right? And especially when you are when you are cornered with array or a kind of example with limited set of or type of values, you shouldn't focus definitely focus on what are the relevance of these parts in the example or in the question right? So that is one way to spin one approach to solve the problem. The other approach is of course our time to optimize your code right? You came up with a brute-force algorithm. You are trying to put in dynamic programming, pre-processing logic and you know trying to optimize your code actually. So what I feel is like generally many candidates do this mistake, like they instead of looking at the problem... like it's always good to start looking at the problem and then trying to solve for the kind of peculiar cases that may exist in the problem and then moving on to your code optimization because that that's like after you code you optimize the code. Try to perform to work more so commenting. So I think that this question is a mix of both so once you figure out the relevance of zeros and ones, then it comes down to how you are coding. That's why I mentioned when you were about to code that it depends on how you are expressing your conditions. Like it's all about like finding the number of zeros that are required in each partition at the right, then finding out the number of ones that are required in each partition, and trying to adjust the i and j based on the number of ones and the zeros to the right. This will give you the three partitions and next once you get the i and j, you get out of the loop and the you do an equality quality check right? So this would be the sort of pseudocode or algorithm basically for solving this problem. Now it depends on how you are putting your conditions, where you're conditions, and you know finding that i and j. So that is the crux of the problem, finding i and j. Then equality check is like easy part to do right? So yeah, so spend more time into understanding what the question is about and how you can utilize the nuances in the question like the differences with using different examples. You were reluctant to take examples, that that was another thing right? I think you were stuck with a given example, you're stuck with the when I'm when I'm giving you hints saying that what does the relevant or what is the relative number of ones, you should immediately have gone to like it should be multiple of three. It has to be multiple of three basically right? So if it's not a multiple of three, you cannot split into three partitions right? And if it is a multiple of three, then whatever the quotient is, like if it is 2, then it is 2 partition. So can I stop there, can I can I just point my i and j to where I encounter 2 ones. Answer would be no because zeros have a relevance. The leading zeros which is the leftmost zeros, which don't have any relevance. The rightmost zeros have relevance. How would you handle that with i and j. So if you are... so the thing is if the more I think the more problems you solve the more, you will think in this manner right? So this is a smooth transition of thought process right, one over the other. So I think it just is just a matter of practice and it's just a matter of you know due diligence, like whenever you come across a question instead of trying to come up with a brute force and trying to optimize that brute force, try to think more about the problem, like words, so that the interviewer also you know might give you more hints etcetera, and you might be more successful in solving the problem in that case.

Orange Storm: Ok yeah thank you so much for your hints and also and these feedback, this is really helpful.

Heuristic Panda: Sure definitely and I have you I have added a few annotations in the whole interview, I think will be visible to you, but I think these were few things that I noted and I hope that you know it helps you in something.

Orange Storm: Okay, thank you so much, yeah I would take a look at this and I will solve this problem later after we were done this you know.

Heuristic Panda: Sounds good yeah, I wish you all the best.

Orange Storm: Thank you so much for your time.

Heuristic Panda: Sure, bye.

Orange Storm: Bye.