An Interview with a Google engineer

Watch someone solve the defeat the enemy problem in an interview with a Google engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Defeat the enemy

Interview question

1) Based off the game Core Wars, how would you defeat the enemy? 2) What's the probability of you winning?

Interview Feedback

Feedback about Iron Gyroscope (the interviewee)

Advance this person to the next round?

How were their technical skills?

4/4

How was their problem solving ability?

1/4

What about their communication ability?

4/4

I threw you a curve ball with a problem not usually seen in interviews (programming in assembly) and you picked it up right away. It was clear that you followed the logic of everything with very little guidance. Excellent job.

Feedback about Intergalactic Avenger (the interviewer)

Would you want to work with this person?

How excited would you be to work with them?

1/4

How good were the questions?

4/4

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

3/4

Fun concept! I like that it's not something that most people would have seen and the game-like nature of it. It's less obvious how to figure out whether someone is a thematic fit for a position, but I guess you can do that with other questions. I also really like that the game-like nature of the question helps the interviewer and the interviewee warm up towards each other - much more fun than reciting some random code :).

Interview Transcript

Iron Gyroscope: Hello?

Intergalactic Avenger: Hello.

Iron Gyroscope: Hi, how are you?

Intergalactic Avenger: I'm pretty good, and yourself?

Iron Gyroscope: Doing great!

Intergalactic Avenger: Alright, you ready for a little interview question?

Iron Gyroscope: Yes, sounds good.

Intergalactic Avenger: Okay, so... I think today we're going something just a little bit different than the usual like, you know algorithms and data structures, and we're going to do this session in assembly language. Now, don't don't be too... I know no one programmed in assembly language ever, but this is actually based on a game. I don't know if you've ever heard of it, it's called Core Wars, that was popular I guess back in the 80s or something where you would program a warrior against other warriors and battle each other out in assembly language. It's kind of fun and I think I've got a couple questions that take advantage of this. So if you're up for it, let's give it a try. Can you see what I'm typing here on the screen?

Iron Gyroscope: Yes.

Intergalactic Avenger: Okay, perfect. Okay so, essentially what's happening here is that we're going to be writing a program in a very simplistic language that's called Redcode, and if you really want to look it up, you can just look up Core Wars on Google and it'll give you a little bit of introduction, but I'll give you everything that you need here, you don't actually have to look at it. So we'll just start off with the situation that we're going to want a little program that that counts to three over and over again, and I'll show you how to do that and then once you get an example of what this language looks like, then I'll ask you to sort of change it and that kind of thing. So the way this programming language works is that you just have some memory, some RAM, and you write instructions directly into the RAM and you'll have a program counter that will read the instructions and recorded the instructions and that's all it does. There's no files, there's no disk, there's no network, there's no anything, it's just a bit of RAM. So the RAM is going to be sort of numbered in terms of slots, like memory locations, and I'll just go out to 16 locations now just to give you an idea. And at every one of these locations, you will put in a... or however many blocks you'll have... you put in the instructions for your program. So one of the instructions is called move, and I'll explain a little bit more about what this all does, but in any event the way that the execution of the program is going to work is that you'll have an instruction pointer which will start at the start of your program, it will execute that one command, and then move on to the next one. And what this does...

Iron Gyroscope: By next one you mean the next part in the RAM?

Intergalactic Avenger: Yeah, so this one's number two and then the next one it will do number three. So what this one will do... so the arguments to move are basically the origin and the destination of which pieces of Ram you want to move to where, and so what what the number five is saying is that at five address spaces from now, you will copy that and you will write it to the destination, which is 6. So after this instruction pointer finishes, then you will see that same instruction written once, so it's actually more of like a copy than a move okay? And then the instruction pointer will move on to the next one, so I will show you what I'm going to put here, is going to be add and one and five. One thing to notice is that the addresses are relative, so you see that I used five. It didn't write it to actual address number five, it just went five ahead and you're going to see that this is also true of all of the address spaces, all the addressing. So add(1, 5), so add the the parameters are the amount and destination, so this will take the instruction that's five ahead and it will add one to it. So the instruction pointer moved to here and then it will move and make the next one. So then I'm just going to repeat this a couple times.

Iron Gyroscope: I'm sorry, what is number one?

Intergalactic Avenger: So number one is the the amount to add to the thing. So after instruction number four, if we're here, then this will turn into two, and after we execute this one, this will turn into three, because you're adding this number one each. And this is the address of where it's being written to. Okay and if we go and try to execute one of these data blocks, that actually is a segmentation fault and the program exits. So you want to avoid that, so in order to not go into a just end the program, you will then say we're going to do a jump to minus four, which is just the destination of where you want the instruction pointer to go to next. Instead of just increasing it by one, it will in this case jump back four, so that your instruction pointer will be pointing back here, and so what this will then do is it will start the whole thing over again. It copies this to here, and then adds up there. Okay so here's the very first program, and it would basically start looking like this, and that would be the program that you will have had written and it will behave... and the starting point will be here... and it will behave as I just showed you, that it will count to three, and then start back over in this infinite loop. So does that make basically make sense in terms of what's going on?

Iron Gyroscope: Yup, I'm good.

Intergalactic Avenger: So, all right... now this is all fine and good and you're happy in the land of of your memory and then the real challenge comes that another program jumps into your address space and starts using your CPU and he is your enemy. So here... oh one last thing to mention, so I was talking about how all the addresses are relative, so you see that this five isn't going to the number 5, this is going 5 ahead. So one of the elements about this memory is that it loops around, so that if you were down here and you said like move 1 2, then this would go and impact that up there, so it kind of loop around a little bit. Ok, so here we are. Your enemy, should you choose to fight him, has written this program here. So now, what he is trying to do is destroy you, he's trying to... or basically he is in there and I'd like you to tell me what's going to happen after... once he starts running in your address space and with your CPU, and what I mean by your CPU is that you guys will alternate the instructions, so that you will run with one instruction and then he will run one instruction and you and then he.

Iron Gyroscope: And I guess zero through seven, he gets 8 through 15?

Intergalactic Avenger: No, so you're in the same exact same address space, you both get 0 through 15.

Iron Gyroscope: Okay, but so I'll start at 2 and he'll start at 11?

Intergalactic Avenger: Yeah in this case. So do you understand the question?

Iron Gyroscope: Yes... well...

Intergalactic Avenger: I guess the first step is explain what is going to happen, like with him sort of... so once you start the CPU running, what's going to happen?

Iron Gyroscope: So his MOV(0, 1) is going to start to descending until eventually it starts hitting my instructions.

Intergalactic Avenger: Right, and then what's going to happen once he loops back around.

Iron Gyroscope: So we're going to get something like... So I'll get to run six or seven steps and then we'll get something like this, which will then move itself on to this block number two.

Intergalactic Avenger: Okay, so he will basically start to overwrite your program.

Iron Gyroscope: Yes.

Intergalactic Avenger: Okay, and then what will you do.

Iron Gyroscope: So when this happens, I will be at let's see... one two three four five six seven, so on the seventh step, he will have... on the sixth step, he will have moved zero one, and by then I'll have done six steps, so one two three four five six... oh wait no, I've done the jump, my sixth step is again move five six, so this will be at zero. I've counted once, I am back to here, now I'm doing the seventh step, so I... hold up... one two one two three four five six... okay, so I've done that step, I will be here, when he is here. So I will get to keep on counting this time, I move next, so this will become one and I move here and now it's my enemy's turn, and he is going to do this...

Intergalactic Avenger: So it's actually the old instructions sticks around, it doesn't get erased, but it's just a minor...

Iron Gyroscope: Oh yeah sorry.

Intergalactic Avenger: It's just a minor thing, but no, you're exactly right.

Iron Gyroscope: Okay, so uh now, I will keep on counting... uh two and he is going to keep overriding my instructions... and since these are all copies, they're all over the place.

Intergalactic Avenger: Yeah, you're yeah, so we can we can just imagine that they're all there, that's fine.

Iron Gyroscope: So what it looks like will happen is that I will get to count to three, and I will not get to get any further, because all the instructions will be starting MOV(0,1).

Intergalactic Avenger: Right, well so what happens once you jump?

Iron Gyroscope: I will jump to the MOV(0,1), so I will start reading the same instructions.

Intergalactic Avenger: Okay, so it's kind of like a zombie and that he will have sort of have taken your life from you and and then you just kind of plot on. Okay perfect, now let's say that you know that this is the type of enemy that you are going to be facing. I'm going to go and and put back the original thing. So then the question is, what can you do the stop it? And in general, I guess we can start with him being at number eleven now, but in general the way this game is played, you write a program and your opponent writes a program and they're actually randomly placed in the in the address space, but let's just say if you want to start with this just starting at 11, yeah that's fine, or...

Iron Gyroscope: So I guess if I know my enemy is doing this, one thing I could try to do is to keep a copy of my instruction somewhere. Am I allowed to do more than one comment for register?

Intergalactic Avenger: No, so each memory block is one single instruction, and another thing to keep in mind is you don't necessarily, at this point, have to be adding numbers to three anymore, so when you were alone by yourself, you were plenty happy to just add numbers and that was all that you needed, but we can say that now you're in fighting mode and you don't have to be in counting mode, so the counting thing was just sort of expository about how the mechanics work, so you don't have to worry about adding numbers anymore.

Iron Gyroscope: Okay I... so I just want some command that prevents it from being a burden?

Intergalactic Avenger: Yeah, so basically you're just fighting him, you're fighting him off in some way, shape, or form. And the the way that you stop him is you get him to read a non... like one of these data instructions.

Iron Gyroscope: Hmm, looks like a...

Intergalactic Avenger: Yeah, this is the... this is the tricky part.

Iron Gyroscope: Okay so I want to overwrite an instruction after he's done, the MOVE(0, 1), I want to put something in that place. So for example, I can do a... so I moved first, so I'm going to need to pass one turn, so I'm just gonna do zero... I don't want to do that.

Intergalactic Avenger: There's the no op if you want, that's fine.

Iron Gyroscope: And the next thing I'm going to do is copy, or move, I guess it's four, two, one, two three four five six seven eight nine. So this is going to copy that number zero after my enemy moves. Does that make sense?

Intergalactic Avenger: Alright, so let's see. So you've got... so he's gonna first that, you moved first, you're gonna go in his place and then you get him. Okay, perfect. And that will stop him and then you can write the rest of your program would be for counting numbers or whatever. Okay. Now let's say you don't know where he is going to be. He's going to be randomly placed somewhere in the address space along with you. And the only thing that you can be sure of is that the two programs won't overlap, that it will be in some relation of behind or ahead of you.

Iron Gyroscope: Okay so when I write the program, do I just write one line?

Intergalactic Avenger: No, you write all the lines of the program and then...

Iron Gyroscope: But I know that he is not going to overlap with my lines?

Intergalactic Avenger: Yeah, that's the only thing that you know. So you will write all the lines, but it's like six or seven or whatever.

Iron Gyroscope: Well then the trick answer is that I'm going to write 15 lines.

Intergalactic Avenger: Right, good point good point. I think in the way that the the actual game works is that there's a limit, there's a hardcore limit to how long the program can be, I think it's like 30, and the the address space is usually about 8,000, but no, that's a very good point if you had 15, then that would guarantee that you would be able to do it.

Iron Gyroscope: So one thing I can do is to make a little bot that instead of counting to three is just going to place these ... all over the place. This is not very efficient at all, yes. One second. I guess I want to play something behind me to protect myself also so that I can actually move.

Intergalactic Avenger: A very interesting point is that... so you put that in front of you.

Iron Gyroscope: Yeah I'm just gonna put it behind me. Yes that's pretty silly, unless he starts like two spots behind. It would have saved me if he starts like right in front of me, but that's a waste of time.

Intergalactic Avenger: Eventually he'll make it behind you anyway.

Iron Gyroscope: Yep, so the simple solution is probably something like this. Oops. Yep does that make sense?

Intergalactic Avenger: Okay, that does make sense.

Iron Gyroscope: It breaks if he starts one behind me.

Intergalactic Avenger: And when else does it break?

Iron Gyroscope: Actually, no it does not break if he starts one behind me because I move first. Uh so I do the copy into his spot first. When does it break, let me think. Uh, this might actually be fine.

Intergalactic Avenger: So what if he started two behind you.

Iron Gyroscope: Oh yeah sorry, I see. That's unfortunate. Uh yep, uh...

Intergalactic Avenger: Well I did not mean to discourage you, this is actually... this is great. And it does kill him under a lot of circumstances, but let's just flesh out what are the conditions in which he wins and and what are the conditions what you win. Or I guess he doesn't really win, he just zombifies you.

Iron Gyroscope: So the problem is that he is going to overwrite the move I have in front of him because if he starts on even squares. So I can make a slightly more efficient version which is still not great, which is... something like this.

Intergalactic Avenger: Okay, so how... what's the difference now, like...

Iron Gyroscope: The difference is that I am taking three moves and I'm filling up two of his spots. So then I'm going to win two-thirds of the time instead of half the time.

Intergalactic Avenger: Okay perfect. Yeah and actually and you've already sort of jumped ahead and the way that the tournaments like this work is that because there is a random element to where they start, they actually just do like a thousand runs and take the average of you know... so then if you knew that you had a maximum of say eight, like that was the maximum size of your program, then what would be optimal look like? You don't even have to write it out, but just sort of explain.

Iron Gyroscope: Yeah 6/7 because I need one spot for the dash and one for the jump.

Intergalactic Avenger: And then the rest are these moves? Perfect. Nice, that's excellent, that's excellent. Yeah no, you did great. That's all I got. I mean actually if you're interested, if you think this kind of stuff is fun, then I would just look up Core Wars on Google this is... these are actually the real instructions and how it works. It's a lot more like involved than just this step, but no you did fantastic, like you picked up on it right away, all these different things, like how to optimize it. Yeah so, it was just a great job.

Iron Gyroscope: Thanks, that was actually a lot of fun, I don't know that I learned anything very practical, but it was fun to do.

Intergalactic Avenger: Very good, well sometimes that's all you can expect out of an interview question. So all right,

Iron Gyroscope: Do you want feedback?

Intergalactic Avenger: Oh yeah, sure.

Iron Gyroscope: I guess the hard things that I would...I would have a hard time adopting this because I don't know... I'm spending the first 15 minutes without really getting any input about the candidate. So like I wonder how I would adapt it to get feedback sooner, enough in terms of knowing what were to go.

Intergalactic Avenger: Right. I see what you are saying. Yeah, I mean my my basic sort of thought is um you know, like adapting to a new type of domain that you haven't seen before. I guess one problem that you see when you've interviewed a lot of people or more like when people have done a lot of interviewing is that they hear the same questions over and over again really kind of answering by rote and sometimes someone who can like really program their way through a red-black tree like with their hands tied behind the back actually can't like adapt that like logical thinking to another thing. I mean there's obviously pros and cons you know, I didn't test whether you could like create a for loop, but I don't know I feel like you should get the concepts behind like what's all going on here and you can sort of move into that logical space that I think that the other like parts of programming shouldn't be too big of a deal. That's a good piece of feedback, it is like quite abstract and sometimes the world doesn't necessarily need more abstraction.

Iron Gyroscope: Also maybe you want to change the move function to a copy function.

Intergalactic Avenger: Yeah, I know it is... I kept it as move because that's what the original is, but yeah it is... it's kind of a weird... it takes a little while to get used to that nomenclature.

Iron Gyroscope: Okay, that's about it. Thank you, thank you very much. I had a lot of fun.

Intergalactic Avenger: Alright, great. Thank you very much.

Iron Gyroscope: Take care.