Java Interview with a Facebook engineer

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

Interview Summary

Problem type

Infinite binary print

Interview question

Print out all numbers in binary, preserving leading zeros.

Interview Feedback

Feedback about Purple Hurricane (the interviewee)

Advance this person to the next round?

How were their technical skills?

3/4

How was their problem solving ability?

3/4

What about their communication ability?

3/4

Hey! These are the notes I wrote during the interview and would be roughly what I would pass to the hiring committee if this were a real interview. Overall pretty solid. - Came up with a queue based solution relatively quickly and demonstrated it working by simulating the algorithm. This is good and shows solid communication skills. - Implemented the queue based solution pretty quickly. Solid coding though the code war relatively simple. - Asked about space complexity. Said space usage grows exponentially. There was some mention of heaps but I wasn't sure how it was related. I suggested we talk about space usage more abstractly. Overall showed good understanding of space usage of the program. - Asked about time complexity next and average number of operations per string output. Discussed the append operation on the string. Eventually landed on O(n) because of the cost to copy the string and then append one character at the end. - I then asked about improving space usage. Candidate came up with a solution using integers to represent the string and converting the integer to a binary string and incrementing them to go from one string to the next. After a small hint to fix a simple bug got the program working. - Asked about space usage. Candidate said space complexity is O(n). - Asked if something could go wrong if we let the program run for a while. Candidate first said OOM but eventually with some hints landed on integer overflow. - Asked for a solution, candidate suggested using int64 or BigInteger. Initially suggested implementing the big int class using a string in base 10. I hinted that we can just store in base 2 so we will not need to convert to binary string and candidate agreed. We ran out of time at this point.

Feedback about Stateless Samurai (the interviewer)

Would you want to work with this person?

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

I think the question was really good and explained really well. Thanks for your valuable time.

Interview Transcript

Stateless Samurai: Hello? Hello? I don't hear anything.

Purple Hurricane: Hello.

Stateless Samurai: Hey.

Purple Hurricane: Hello. Yeah, hi, can you hear me?

Stateless Samurai: Yeah, you're a little quiet, but yes, I can hear you now.

Purple Hurricane: I'm going to be using Java today.

Stateless Samurai: Sounds good. Perfect. Yeah, sorry I'm a few minutes late. The website wasn't loading. I'm not sure what was going on with it. I don't know if it was my internet or the website was actually down for a few minutes, no idea. Anyways, let's get started. So, interviewing.io was mentioning that you're... are you in university now or new grad or..?

Purple Hurricane: Okay, so actually I have four years of experience back in India and after 4 years of experience, I moved to the US for my master's. Currently I'm pursuing my master's in computer science.

Stateless Samurai: Cool, you're doing a master's. Great, sounds good. Let's get started. So I'm going to type some stuff in the comments section here. So the problem today is to write a program. But when you run it, we'd like it to output the following. So the is output just the string 0, then 1, 00, 01, 10, 11, three 0's, and so on. So basically what we want it to do is basically at some point any binary string should be theoretically printed, like at some point it should print that and so on. And so there's no input to the program, as soon as you run it it starts printing these strings out and it will keep running until it gets interrupted. Make sense?

Purple Hurricane: Yes. Okay, so this is what I have to print. Okay, so it's not like I have to print any particular number, I have to print all of them. So, here looking at this, I can see a pattern that the first two numbers are nothing but all the numbers placed in two.

Stateless Samurai: Yeah, it's all binary strings, like all strings consisting of zero and one. That's the goal.

Purple Hurricane: Yeah, so basically. If I have to print something like this, what I can do is like for i is less than... let's say I have a variable i, which is start with 0. And every time it's less than let's say less than two, so I print variable j, which is again start with 0. So 0 and 1, it will be distinct and next time, when I want to print the next variable, so, I again set my i to 0, and then... This is just one approach. But maybe a recursion or... I just think one minute for a better approach. Okay, so even a recursive solutions... Okay, so in this case, if I use a queue, let's say if I use a queue... So in my queue I can insert 0 and 1. And then I pop this 0 out and print it and add 0 and 1 to the back of this string, So then I can insert back into the queue. So, let's say once I pop 0 out and put 0 0 and 0 1 into the queue and now I have an output 0 on my screen. Then I pop this 1 out and I'll print it out on my screen, so 1. And then I can put 1 0 and 1 1 on in the queue. Then I can pop this 00, it will print 00 and I can put 000 into queue and 001 into queue and then I can pop 01 out and I can print this here. And then I can put this into a queue and I can add 0 here. And then I can add 1 here. So if I go by this way, then now I have 10 out here, so I can include to 100 and then 101. So if I use a queue, I can generate this pattern.

Stateless Samurai: Alright.

Purple Hurricane: So should I implement it?

Stateless Samurai: Sorry?

Purple Hurricane: Like if I use a queue and I just put 0 and 1, so I will be able to implement this feature.

Stateless Samurai: Okay, sure.

Purple Hurricane: So I'll just implement this. So I'll create a function. It will not return anything, so I can... And this will not take anything. But it in case if we want to generate just n numbers, we could have passed n in. So queue of strings... So if I do while true, it will go into an infinte loop, so maybe I can limit it to some limited number? Should I or should I run it for an infinite loop?

Stateless Samurai: So the program wants an infinite loop, but because we're going to run it in the browser, I'm not really sure what happens... I haven't tried it yet, if you run an infinite loop from the browser, so let's yeah, I think let's limit it for now to the first hundred or so.

Purple Hurricane: Okay. And what this will do is it will first get the string, p is equal to queue.front. So it will remove the first element from the queue and it will print the first element. Yeah, so this should actually give me one warning because I'm not using... So this will now get a hundred values, one in each line. Just try them on this. Yeah, so the output is zero, one, two.

Stateless Samurai: Alright. Let's talk about space usage for a minute. Ao as this program keeps running, how much space is it using?

Purple Hurricane: So actually it will start growing exponentially. So for each pattern it will add two, so yep, so it will keep on going exponentially.

Stateless Samurai: Yeah, so roughly what? Like if you're printing a string of length n, roughly what is the size of the queue?

Purple Hurricane: If I've been doing this... So basically it depends on the heap that I allocated because all these strings will be going to the heap. So I guess... This program can print up to 10 to the power of 4 rows at max.

Stateless Samurai: Where's that coming from? That's a constant by the way, 10,000.

Purple Hurricane: If it's on the basic machine like if the heap is allocated like 4gb, we can certainly allocate more space, and on linux we can allocate more space but for a normal window system like it would be 8 to 16gb.

Stateless Samurai: Sorry, I'm not really sure why we're talking about the heap at all. So let's just let's just talk about the algorithm itself independent of specific system. There's a certain number of elements in the queue at any moment, right? The queue has a size. Sorry?

Purple Hurricane: That's two to power of n.

Stateless Samurai: Yeah, roughly 2^n, that was the question. Yeah okay. So sounds good. So space usage grows exponentially. What about time wise? So obviously the theoretical version of this... or not theoretical but the real version of this program would run infinitely, so time complexity doesn't make sense as a whole because it just keeps going forever, but it is interesting to see how many operations take place her string on average right? So how much work are you doing to create each string, what do you think that is?

Purple Hurricane: So for each string I'm doing one plus operation and since it's a queue, so I'm just removing the peak, so it's O(1), so basically just one operation is used to generate any one particular row in the pattern. Yeah, so just one. So any of the peak plus zero will generate one pattern at any time. Plus one will generate one pattern.

Stateless Samurai: Okay and how much work is that? What is the time complexity of the operation you're using to create each string?

Purple Hurricane: Okay, so it's plus so... It will append at the last, so and if we're not taking the string full into consideration, it is O(1). Because internally string is also added, so it will create an array. I mean, because I'm not using any builder or something so okay, let's not talk about heap so... I have a string here so basically make a copy of the existing existing string. Append a 0 to it, and then it will put into the memory so the time it takes to copy the existing queue element and append it... so the copy amounts let's say the size of peak is n, so it will just add one, so it depends on the size of the peak element.

Stateless Samurai: Yeah, so as a function of the values of the string you're printing, the length of the string you're printing, what is it?

Purple Hurricane: Yeah, so the length of string I'm printing at any time is so... it could be at max... So it will be on average O(log n) I guess. Overall, it will be... I did get that like what is the length?

Stateless Samurai: So the string you're printing, so like if you're printing like... let's look at the example, like here n is the number of elements here, so it's four plus five, so n is nine here. So in terms of like the number of characters in the string you're printing, or the number of bits in the binary string you're printing, if we consider that to be the variable, then how much work is done to create that string?

Purple Hurricane: Actually O(n).

Stateless Samurai: Right. Why?

Purple Hurricane: It's because the particular copy the n elements, it will create a character array, and then it will put that in and add an extra element to that array, so the copying operation itself will be O(n).

Stateless Samurai: Yeah, cool. Sounds good. So we got exponential space growth and then for each string we're doing a linear number of operations. That was good. So can we make that better? Especially the space, the space usage is pretty concerning because it grows exponentially. You'll run out of memory pretty quickly.

Purple Hurricane: Yeah, so the one of the approaches I can think of is like the first one of this series. I can start with zero and one. If I see a pattern, this number says nothing but less than two. Then when I generate zero, one, two, three. And which is less than four. And similarly it goes on until the next one is seven, which is less than eight. So when I start doing like this, so it's all about... If we want to save the memory, I have to use this feature and generate the binary representation of this number. And the length of each pattern should be nothing but whatever the power of two it is. So let's say in this case, in the first case, it is two to the power one. So the length has to be one. So I'll generate zero and one of length one. Then I generate zero, one, two, three of length two. And similarly I can generate for length of 3. In that way, I can save the extra space in the queue, but then I have to again create a string, so the creation will take memory and the O(n) time.

Stateless Samurai: Alright.

Purple Hurricane: Yeah, so should I go ahead with the implementation.

Stateless Samurai: Sure.

Purple Hurricane: Okay sure. And let's say my int start equals to two and it's power is one. So I have to generate 100 elements. So I can write count is equal to a hundred. So while count is greater than zero.

Stateless Samurai: You probably want to subtract here, not add to i.

Purple Hurricane: I mean I'm using i to generate the pattern, so I think plus plus.

Stateless Samurai: Oh sorry, yeah.

Purple Hurricane: And here I can do count minus, so that's how I implement it and now here I can actually generate my string, so let's say string current equal to integer dot to binary string. Yeah, so here I can pass my i. And now I have my current and it will first check if my i is 0 and if it is not equal to start, so it will come and it will try to generate... convert i to binary string, so it will convert 0 to a binary string and now I have to see while current dot length is less than power.... So in this case, it is equal to power, it will not do anything. Otherwise it will keep appending current. So basically I can use this string builder for this. But for the time being I'm just using string. So I can add a 0 and then I can append my i after that. So once it becomes power... yeah, so and now I have my current element and I can print this. And then my current element. Yeah, so now I have this and it again goes to the loop. It means I also want one and it is not equal to start, so it will convert one to a binary string. Length is power, so it next time it goes, i is equal to 2. So now i is equal to start, so it will make 0. Yeah, so this one is... so yeah this one should be the difference. Okay, yeah. Should I run this?

Stateless Samurai: Sure.

Purple Hurricane: For the program using too much memory... How come it's taking so much memory just for four lines.

Stateless Samurai: Why are you adding i to current?

Purple Hurricane: Okay, so. Just i is nothing but it's...

Stateless Samurai: Yeah, in this while loop, what are you trying to do?

Purple Hurricane: Okay, so I started i equal to... so as I explained my algorithm on line twenty seven, so basically I start with i equal to zero on line twenty seven and my start is two. So I check whether i is less than two or not, so since i is zero.

Stateless Samurai: I know what you're trying to do, I just don't understand why you're adding i to it. Why are you prepending zero to i? i is an integer, like it could be like, I don't know... There you go. Yeah, I think that's what you wanted to do. I don't know if that was actually causing the memory issue, but that's something.

Purple Hurricane: Oh.

Stateless Samurai: I don't know why that was causing too much memory, that's weird. Honestly I don't even know what Java does when you add a string to an integer. That's pretty messed up that you even can do that.

Purple Hurricane: Actually, when we add anything to a string, it uses the string method which is defined in a class, so that's if it is a object class, okay, so it's using dot toString of the integer class.

Stateless Samurai: So then why why were we getting too much memory usage? To me it seemed like it was doing an infinite loop here somehow. Oh. Yeah, no actually I don't know. I don't know what was happening.

Purple Hurricane: Even I'm confused because it should append on character and the power values stayed so not sure. Okay, I mean, I can have a look at that later.

Stateless Samurai: That's an interesting puzzle to solve, yeah. I can't think of why that would be doing that. Cool alright so... What are we looking at in terms of space usage now?

Purple Hurricane: Okay, so now when you see this, the space complexity would be... currently I'm just using strings everywhere, so instead of using... So this complex should only be the number of distinct strings that got created during the process because all the strings live in the heap. So let's not talk about that. So space complexity will be O(n).

Stateless Samurai: Yeah, yeah. Yeah so just a random suggestion. This is not something I would say during an actual interview, but like a quick thing as first feedback goes, generally when you're talking about space on time complexity of an algorithm, you generally want to talk about it in a way that's independent of the exact implementation. It's not always true, like sometimes an interview might specifically ask you like, you know, how does Java handle this or how does Java do this or whatever language you're using, in which case you want to get into like heaps and you know, whatever, but in general like, you know, like this could be pseudo code and it you can talk about it's it's memory usage, it doesn't really matter what language it's in. So just a random note. Cool okay, so linear space, but here you're using an integer. So one natural question is if this was to run forever... not forever, but like if you remove the limit of a hundred strings from it, do you see something that could go wrong? Eventually.

Purple Hurricane: Yeah, so if I remove count, it will be an infinite loop. So if it is on a server, definitely it will crash, because of the memory so... and if it is a browser, maybe a...

Stateless Samurai: Sorry, why would it crash because of memory?

Purple Hurricane: So, actually, so talking in context of Java...

Stateless Samurai: Sure, but even more generally, I don't know... I mean, you're right, it's using linear amounts of memory, right, which means that eventually it will crash, but I think it will crash much sooner than it will crash from... actually, I don't know if it will necessarily crash, it will just have wrong outputs.

Purple Hurricane: So there are two things, if it's also a language dependency and so in case of Java it will crash before, but in case of Python, it will take or some time to crash. So it's because for a server, there is a limited memory. So when we are generating a string, in case of Java, it will all go to the heap.

Stateless Samurai: So I think... I'm trying to lead you towards a different problem which happens far before memory becomes an issue, can you see what it could be?

Purple Hurricane: Okay.

Stateless Samurai: Like let's not deal with memory, because memory will not be a problem. Something else will go wrong way before that becomes an issue.

Purple Hurricane: Yeah, so there is one thing like since we are trying to ...or I'm using an integer variable, so after some time, the integer will overflow, so the binary representatives won't be the same.

Stateless Samurai: Yeah exactly, and that will happen way before the memory becomes a problem because you're only using like four bytes of memory type then. That's not much memory at all.

Purple Hurricane: Yeah.

Stateless Samurai: All right, so yeah... so when will that happen?

Purple Hurricane: Okay, so... the maximum integer value is represented using two different 32 bits. So it will be good for 32. So once my integer value which is true about 32 bits. So I have created a pattern. In this case, it will be an allotment pattern, because I am using the chunks of two. So it will be like two plus two power one plus two the power two, so two plus thirty one pattern. So it will be GP sum of two to the power of thirty one. So once I print those patterns, then the value of two will overflow and then the binary will representation of a one will be seen.

Stateless Samurai: Exactly. So what can we do about?

Purple Hurricane: Okay, so if we want to use even longer, in that case, the first thing is if we just want to... one thing is from integer, I can convert it to long. So that will be 2 to the power of 64 and in case if we want even more, there is for Java we have big integer classes, so that will again allow us to generate longer strings. These are really long long extension so... Yeah, but comparatively it will slower or we can implement our own class instead of using integer like for a big number who can use string representation itself and for all the operations will use the system. Let's say I am using integer to binary string. Instead of converting this integer if I somehow... I don't want to use memory. So, for very long, I have to generate... So I need to use a string class itself and... Very long. Okay, so in that case, let's say... I have a variable 7. So I should pass... I can't use 7 directly. So somehow I have to pass it by the same and then do a character-wise operation to convert the 7 into a binary string so my integer will not overflow. So my first two approaches will definitely be long or limited if I have something inbuilt and then big integer will work for anything. And then comes a manual approach like where I have to implement something of my own integer type of class. So in that case, I have to pass a string and then I can use all the operations supported by big integer class. It means I have to write my own operations similar to big integer class and perform those mathematical operations on each string.

Stateless Samurai: So wait, how many operations do you need?

Purple Hurricane: Yeah in this case, I just need a convert to binary string. So for that I need a division operation.

Stateless Samurai: Sorry, isn't it already a string? I thought you're using a string to implement it.

Purple Hurricane: Yeah, I mean, I'm passing this i as an integer here and then I'm using a string. So I'm using a string, but answer instead of i, which is an integer, I can also do this by passing two here. And let's say once it reaches the max val of integer, two one one one, and then I try to add one. Then instead of representing it as a normal integer value, I can do string sum operation on this, so I can add the last two values, one and one, and that becomes two and this will be my next carry. I will not be using i anymore, not any integer anymore. So everything will be a string and my conversion logic will again be a string.

Stateless Samurai: Wait so everything will be a string? So you're talking with implementing the big integer class yourself right? That's what you're getting at? So what is the underlying data type for your big integer class?

Purple Hurricane: Okay, so when you pass anything into a big integer, it's string inside and then it strings look...

Stateless Samurai: What space are you using to store the number?

Purple Hurricane: It's normal addition.

Stateless Samurai: Sorry?

Purple Hurricane: It's decimal, it's a 0 to 9.

Stateless Samurai: Why would you use 0 to 9? Isn't there a base much better suited for the problem we're looking at?

Purple Hurricane: Yeah, in this case we can use base two.

Stateless Samurai: Yeah because when we don't have to convert it to binary, it's already binary. And then what operations do we need to implement if we do that?

Purple Hurricane: Yeah, so if I'm going that, there will be an addiction operation because we are trying to iterate from zero, one, two, three, so first the zero and then just add one to it in a binary, so this will give me one, and then I can add one to it, and then this will give me one zero, and then I can add one to the that.

Stateless Samurai: So how many operations do you need to implement in that case?

Purple Hurricane: In that case, I have to do one is this addition. And then I have to also append number of zeros in front, which will be out of this class, but yeah, I have to maintain the number of leading zeros, that will be one more operation.

Stateless Samurai: Okay great. In terms of mathematical operations, you only really need to be able to increment by one, right?

Purple Hurricane: Yeah.

Stateless Samurai: Cool, alright. We are basically out of time at this point, so if this were a real interview, yeah I think later about now we would be out of time and then you know, in a... Sorry I'm actually not sure, have you've done any phone interviews or anything with like the big tech companies? I don't know if that's where you're interested in sort of like learning about or I'm not sure what your goals are basically. What would you like to get out of this session? Are you are you preparing to interview.

Purple Hurricane: I have even a few more interviews after this. I keep on practicing every now and then.

Stateless Samurai: No, no, I understand. I'm just trying to to see what kind of feedback I should provide. Are you preparing for interviewing with with the bigger tech companies?

Purple Hurricane: Actually, I interviewed with Amazon, but the position got filled. I'm not getting any calls from the big tech companies. Apart from that, I have... because of the multiple platforms like, Triplebyte, interviewing.io, I not gotten in person from interviewing.io but from people Triplebyte, I have a few calls for startups in the end.

Stateless Samurai: Okay, well, basically what I was going to say is in terms of... so I've been doing the interviewing.io for a bit now, and what I usually do is simulate a phone interview, like I would do when I was at one of the bigger companies. Like I worked at Google for a few years and I did a bunch of interviews there, so that's basically more or less what I simulate. And yes, so basically if this were real interview, it would be, you know, five minutes of warm up at the beginning, then about thirty five minutes of coding, and then another five minutes towards the end where you would ask the candidate to ask you questions if they have any questions or working at the company, or generally any questions about what you do and all of that. Yeah so anyways, I'll give you some quick feedback and I'll write some some down as well, but basically I think you did a pretty solid job. Yeah, it was pretty collaborative. You came up with working code pretty quickly, you picked up my hints pretty quickly. Yeah, the only main feedback that I had, which I already kind of mentioned, was that generally when you do like time and space complexity, you want to focus on the algorithm part of it more. Unless the interviewer asked to be specific. But again, even that kind of depends on the company and the interviewer, so it's not necessary true. Yeah, anyway, I hope that helps. And yeah, oh I wrote some notes during the interview as well, so I'll send that along as well. So, hopefully it'll be useful.

Purple Hurricane: Yeah, sure. Thanks. Thanks a lot. That will be helpful for me.

Stateless Samurai: Okay, great. Yeah, sounds good. Good luck with everything.

Purple Hurricane: Thanks for your time. Have a good day.

Stateless Samurai: Yup, you too, bye.