Interview Transcript
Stochastic Panda: Hello.
Occam's Laser: Hi.
Stochastic Panda: How's it going?
Occam's Laser: Fine, fine. How are you?
Stochastic Panda: I'm doing well, thank you for asking. So just want to start off by making sure we're on the same page here. So today we have a senior level target for mock coding round. Is that your understanding as well?
Occam's Laser: Yeah, right.
Stochastic Panda: Fantastic. Fantastic. Okay. Yeah, so we'll conduct this kind of in a standard way. So about five minutes or so for intros, then we'll make for about 40 minutes main coding challenge and then remaining time, basically remaining a recap. Yeah. So for one or two minute introductions.
Occam's Laser: Oops.
Stochastic Panda: Would you like to get us started or shall I? Keeping in mind, of course, this is anonymous platform, so sharing, comfortable with.
Occam's Laser: Yeah. Okay, I can start. Sure. I'm the web engineer, mostly web engineer for the last eight years. I started even before I went to the university. I had a passion about the web stuff. I started doing freelance stuff with creating websites and so on. And then increasingly, let's say, dig into the back end stuff. And now for the last two, I'm the lead engineer at my company. I lead few projects in the company. Yeah. And acting as a full stack as developer and tech lead of the few projects. Yeah, maybe briefly. That's it. What about you?
Stochastic Panda: Yeah, that sounds exciting. Thank you. From my side. Well, I've worked at some large tech companies and currently still do from the Pacific Northwest, although recently relocated east coast, and have been focusing a lot for sure on software engineering for the last nine years or so. In my case with a special niche or focus on machine learning ranging from computer vision and more recently some split between time series and so called language processing. At a high level, I might consider myself closer to machine learning engineer scientist, but yeah, that's my brief background there and I've had good experience on this platform for probably over a year now. Yeah, that's brief about me. Any other questions or things you want to cover before we get started?
Occam's Laser: No, we can jump in into the coding session.
Stochastic Panda: Excellent. So to begin that part, if you would like to select your preferred coding language for today?
Occam's Laser: Yeah, I would say javascript. I will select in the drop down.
Stochastic Panda: Okay, perfect. Excellent. So I will type in my question and for today it's going to be actually in two parts. So let me start by listing the first part, which we'll talk a little bit about at high level just to make sure we are on the same page. Then I'll paste in part two and we can discuss that a little bit. Then I would propose we jump into the code for part one. Does that kind of make sense?
Occam's Laser: Cool. Yeah.
Stochastic Panda: Excellent. All right, let me paste in here. All right, so here we go. Take some time to read part one. We can discuss high level for maybe up to four to five minutes, and then I'll paste in part two.
Occam's Laser: All.
Stochastic Panda: All right. Just want to make sure you're still with me.
Occam's Laser: Yeah, I'm trying to figure it out. I'm not sure that I know this game.
Stochastic Panda: Okay, perfectly fine. Perfectly fine. And always good to make sure we're on the same page about the game. Like, if someone gets tictactoe or poker or whatever else, don't want to assume that there's full knowledge of it. So let me give some examples that I think might help. So, generally, the tictactoe game will consist of two players, each taking alternating turns. And just to give you an example, so if we go to example one, where I should also say n is equal to three, we have a three by three board that initially starts off as all dots. So dot equals empty cell, x equals. Let's say it doesn't really matter too much. Player one. And let's say o is equal to player two. So they take turns and they fill in the empty cells so that we're at the current state of the three by three board from lines 36 to 38. And now in the current state, we have two free cells, right? So let's suppose for illustration, that it is now o's turn. And let's suppose that o decides to place their letter here on the bottom left. In this case, we would say that o wins on antidiagonal and game stops. So winning in general will be filling in either a contiguous column row, main diagonal, or this so called antidiagonal. So, just to give one more brief example, before I maybe get to some questions, let's suppose it was a little different, and maybe this was the state of the board on example two. And so far, the game is ongoing. There's no tie. Nobody has won yet. And let's suppose now that it is X's turn in example two, if X goes here, then we would say that X wins on the first row. And I'll pause after this one. Actually, finally, let's suppose that we have this date of the final board. In this case, we would actually say that there's a tie. And I'll give a slight hint because nobody won and all cells are used. So let me pause here and see if the examples make sense.
Occam's Laser: Yeah, sure. Now, I understand in my country, this game has a different name, but. Yeah, I know this game. Okay. Yeah, let me start from my, let's say, vision. How to do this? Yeah, I would say I would start from, of course, building the board that's like the matrix with the array of arrays. So I will have the matrix that I can fill in, fill in with the moves. So every time when the player makes a move, I mark with his idea the point he wants to mark. Then basically I will have the second method that will actually check the game status. How I will do this? First of all, I will check the diagonals. It's just a simple cycle for loop. And then check the row and columns. If some of them are true, that means this player won. By the way, I also count the moves, how many moves each player did, and if they equals to the size of the board, this means it's tied status. And the last case, if no ₩1, it is not tied that we are in ongoing status. Basically, that's it. I will explain more about how we'll check diagonals and so on while implementing it.
Stochastic Panda: Yeah, excellent. So I think this is a good initial approach. But since we want to get to a part two, if you don't mind, let me give you some hints in the form of some questions. So I got your first approach and keeping track of the entire board is one way, right? And as I kind of provided, if we do that, this would mean that we have a plus o of n square space complexity, right? And also, that's kind of related to that you mentioned when a player moves. So let's suppose we go back to example one and the player moves o here. I think you were suggesting that you would check the entire board for all possible wins once we get a new move, right?
Occam's Laser: Yeah.
Stochastic Panda: Okay, so let's talk about that a little bit. Because I think we can reduce both space and some time complexity here. So as a hint again, let's suppose we're in this current state and in example one and suddenly o moves here. My hint is that once o moves in that cell, there's actually only a few possible ways that o can win. That might reduce the amount of time we need to spend to check all possible wins on the board, if that makes sense.
Occam's Laser: So you want to. Yeah, let me think it. But I still need to it. Okay, I got you. I can store only the. For example, if I make a movie for the specific, let's say row or column only. In this case, I store the state only for this specific row and column.
Stochastic Panda: Yeah, that's along the right track. Exactly. Just to follow up. And please pause me if I'm interrupting you to follow on your idea. Right. If o moves on cell 20, this spot in line 43, then what do we need to check for a win? Well, we need to check possible win on row equals two. So we would check can o be contiguous or do we see only o's on that last row too? We also need to check possible win on column equals zero. Right. We would need to ask the question, okay, after that move is made, are there only o's in that first column? And because 20 is on antidiagonal, this implies we just need one more check whether only o is on antidiagonal.
Occam's Laser: So, yeah, so basically I can initialize counts for each row and column. Also I can initialize the count for the diagonal and anti diagonal for both diagonals. And on each move I increment or decrement discounts depending on the player.
Stochastic Panda: Exactly. Yes, and this is exactly the good approach. And my question there is, let's say we think about your approach as a second approach. What would you say in that case is the new space complexity with your new approach.
Occam's Laser: Okay, so basically we store only the counts for the rows and the data analys of n. I will have the from n. Exactly. With the row and columns trackers. Yeah. Cool.
Stochastic Panda: So I think we're at a good place to maybe start coding part one. And then after that we can move on to part two. How does that sound?
Occam's Laser: Yeah, let's jump in. Great. Okay. Yeah, sorry, let me, give me like a few minutes. I will disable Grammarly bothers me. Sometimes it just turns on.
Stochastic Panda: All good.
Occam's Laser: Turn off. Okay, I'm here. Yeah, I will start from the constructor where I will specify all the counters and all the stuff I mentioned earlier. So yeah, I will store the size just to refer it. Then as I mentioned, the first value will be the counts for the rows. I'm not sure about these syntaxes. I don't remember. This basically creates the Nt array of the size n, but. Okay. Yeah, it works. We fill it with the zeros. We do the same with the columns. Now. Yeah, I need the counter for the first diagonal which will decrement or increment based on the player, and the counter from the entity diagonal. Yeah, we need the moves count here just to check if we tied here in the tide status.
Stochastic Panda: Yes.
Occam's Laser: I do think like for now. Yeah, I will start maybe from the move method.
Stochastic Panda: Sure.
Occam's Laser: Then switch to the check status. So yeah, basically we do move for the role column and the player because we need to increment decrement. I will use the variable, additional variable as the current player, which basically will check if the player, if we play for the excess with plus and minus for the O's and. Yeah. When we make move, we actually check, not the check, but set the value. So for this, the same for the column. Okay, so we put here, we put the values for the, for the row. For the column. Yeah. If we need to check if we're on the diagonal, we also need to modify the counter for the diagonal range. And at the same time, ah, we need to modify also the antidiogonal counter. Yeah.
Stochastic Panda: That'S right. We need a condition.
Occam's Laser: Yeah, I'm trying to figure out the condition. Yeah, the condition of the antidival.
Stochastic Panda: Yeah.
Occam's Laser: So if we have the column and the row. Okay, so the row is two, two and two. Okay. Yeah, I can check it. If we have the column, I have the column basically like the ante, we take the size, for example, minus row, and to get the index to minus one. So yeah, I can check there like this. So this will be the index of our antidiagonal.
Stochastic Panda: Yeah, that's exactly right. And because we're essentially zero indexing. That's the right answer. Yes.
Occam's Laser: Great. Yeah. Okay, I scroll down to the code. So, yeah, basically put the value for the diagonals. So yeah, we put the move on the counters also. We increment the moves. Count it. It. Yeah. Now we can basically check the. Or do you want me to check this in the same method or to make the check. Okay, yeah, better to, of course, better to check the status. Check. Status method. So I could.
Stochastic Panda: Yeah, that's right. We can have a separate check status method. And it's a good question. We can always call, if we want to, the check status method inside of move. But all good. Yeah, whichever you choose actually is good.
Occam's Laser: Okay. But we need to check after the move. And I think that we need to pass down here also the current player.
Stochastic Panda: Yeah, great question. So for now, just to keep it simple, let's assume we only want to know if the game is ongoing, won or tied, and the win, for now, let's just say independent of the player, we can always come back to this small detail.
Occam's Laser: Okay. Basically, sorry I didn't tell you about the strategy here. So I can check if some of the counters here, it is equal to the size of word. Yes. If someone is, we assume that we have one of the players, one. If not, we check the moves count. And if the moves count equals to the. But, yeah, it should not be equal to the size of board. It should be the square of the size.
Stochastic Panda: Right?
Occam's Laser: Yeah. If. Yes, the status is tight and otherwise the last one is ongoing. Okay, so the check status here. We still need to pass down the row column to check if we can check the move. Okay, so yeah, let me start from there because we have the negative value there. I want to check the model of the model of this value. Yes, it. Okay, so we will check either rows, either columns, either we check the diagonal and antidonal. It doesn't help me. Okay. So if any of them. So we can. Yeah, I'm trying to think. Okay, we checked, but. Okay, so basically we need to. Okay, you know what we can do? We can store the last player. We can store the last player that made a move. Last player. It actually equals to current player. Yeah. It. And here we check if someone size is reached here we get the last player just to not pass it down yet to make this function to be independent. Yeah. So if the last player is one, that means we assumed. Okay, so that means the player won by player. Player X. Otherwise, one by player. Okay, if we skip this case. Yeah. We check the moves, how many moves we did. If our moves count equal to the size square of size. Yeah. This means we are. How is this called? Tight. Yeah.
Stochastic Panda: Tie.
Occam's Laser: Yes, tie. Okay. Tie. Otherwise we are still playing. Ongoing. Okay, so yeah, after the. Sorry. After we made the move, we check. Yeah, we need to check the status after we made the move.
Stochastic Panda: Yeah, perfect.
Occam's Laser: Okay, so let's test it out.
Stochastic Panda: Actually, let's maybe test at the end. I think from what I'm seeing, this is a correct and actually really nice solution. Before we move on to part two, which will actually use some of this from my side. I think this is a really good solution. And for example, because you pass in row and calling to check status, then exactly as you do here. Actually, one quick follow up question is what would you say is the time complexity of check status?
Occam's Laser: This is simply the check status is all from one because we just reference by row and column. We go directly to the position. That's it.
Stochastic Panda: Yes, exactly. And that was a key part that you observed that because we pass in those two variables, it's constant time and reduces the exploration. Okay, so I'm really happy with that. And now let's move on to part two, which will essentially be an extension of this. So I'm wondering, would you be comfortable if I pasted in part two above like around line 70? Or would you prefer if I paste it in part two, maybe like around 135?
Occam's Laser: Yeah, you can pass wherever you want. Yeah, we can do all just mess up all the.
Stochastic Panda: Yeah. Okay, cool. So let's move on to part two. So I'll paste in part two, take some time to read it, and if you want to ask clarifying questions, definitely feel free.
Occam's Laser: Basically, it's like tic tac toy inside the tic tac toy. Yeah.
Stochastic Panda: Yes, that's right.
Occam's Laser: Okay, so do you want me to build it up using the previous class as a foundation, or you want me to build it from the scratch?
Stochastic Panda: Good question. That's actually a really clever question. So, yeah, kind of like as a hint response to your good question. Yeah. I would propose to leverage as much as you can of your existing solution from part one and see how we can use it for part two.
Occam's Laser: Yeah, I'm trying to think, how can you reuse it? Yeah, sorry, that's why I'm keeping silent. From what I see, I definitely will need some more variable. Not variable, the property where I can store the board winners. If we have multiple boards, I need to keep track of the winner in each board, but I'm trying to think how to reuse this logic and how to maybe. Yeah, maybe I can store, make a move. Okay, what do you say about if I reuse this class.
Stochastic Panda: I will have.
Occam's Laser: The new class, but to store the winnings for each small board, I will reuse the class, the previous one like this. Sorry, I cannot explain it. I will show the server code, for example. I will have the board that will be like an array of the previous class. Yeah, something like this. And keep track of the boards. Yeah. What, what do you say?
Stochastic Panda: Yeah, definitely. And to nitpick just a little bit, I think your previous class was called Tic Tac. But yes, I think you're on the right path. Okay.
Occam's Laser: But here, actually be inside. Yeah, I'm trying to build it up altogether. I mean, even if I track each board. Yeah, I need to get easily the status of the each board and check it on the each movement, how to, how to extend it.
Stochastic Panda: Yeah, I think you're on the right path. And what I might hint at or suggest is let's see if we can first focus on implementing the move method. And what I would say is, for our first strategy, let's suppose you're given the integer n as part of your, and I'll just call this like meta. If we're given the integer n and we wanted to start maybe simply how many individual tic tac toe boards might we watch and how might we organize them?
Occam's Laser: Yeah, I think that we can store the boards as the matrix because actually each cell it's a board. Did you get Mia? Just to sort the matrix. So we will have the boards, but actually this will be it. And we fill it with an arrays which actually be our instances. Yeah. Of the, so we will have the matrix of boards and. Yeah, then we can. On the each move. Yeah, on the each move we make the move inside the board because we pass the meta and. Exactly the row and column inside board. And after we make a move, basically we return the result. Yeah. We need to return the status of the current small board and check if someone wins. We mark this displayer as a winner for now. Yeah. And then we continue the same. And the logic of checking, for example, the status will be exactly the same, but we will have accounters of the meta row and metacolum counters instead of the regular one we had previously. But the logic of the check status remains the same and we make a move inside the board. So yeah, we can reuse the logic. Yeah, sorry, I'm just speeding out and rumbling. I hope you get my idea.
Stochastic Panda: Yeah, definitely. I think it's a good approach. So basically we do need to implement I think a new move method which can definitely rely in part on the previous move method and then similarly with check gain status, just a small modification but which also can leverage your previous solution. Yeah.
Occam's Laser: Okay. Yeah. First of all, here it is, we create new arrays. But basically I need, here I need the same variables. I need to have the counters. Yeah, let me start. I need the same counters for the rows, for the columns, for the diagonals and for the moves. Yeah, basically I have the size, again, I have the meta call counter, counter. That will be, yeah, will be the same way. The empty array size m filled with zeros. We'll have the meta row counter. Meta it. Okay. And the same stuff with the moves. This moves metamones. Yeah. Let's say ss you suggested. Let's move to the movement. Basically first of all I collect the needed board. Yeah. Because we know where we are going. We go to the row first and column. So we get the board. Yeah. We make a move, we make a move for the board. So we board move. We also know the player and, but based on this move. Yeah, we need to check the current status, current status of this small board here. I scrolled up to the 111 here. We need to return the status because we don't return the status here.
Stochastic Panda: Yeah, that's it.
Occam's Laser: Yeah, we'll have the result here and I can check it. The thing that I will do here, it is not the good practice, but I don't want to spend the time writing the previous solution. I will check if we have that someone is winning the current board. I need to check which player first of all. Yeah, if it is. If it is x. We basically the same logic as from the previous solution. And we update the meta column and. Meta meta column with the value and the meta meta row. Right. Okay. Yeah. And again we check also if current row. If the meta row and the meta column, they are the same. We also mark not the mark, we increment or decrement the value here. And the same is for the. For the anti diagonal. We have. We have the meta meta row. Yeah. How. How did they do this? Okay. If we have the metal row moment. Okay, let me check. Yeah, the size. Yeah, the size metas. I had this size minus metro, minus one to get index and. Yeah, I marked the meta antidia now. Okay. Yeah. So again we made a move metamoves and then again we need to have a check the check status. Now we check the meta rows, metacolums in the same way. Yeah, I do think that we check in the same way. Let me just copy paste it. But here it is the meta rows. For example, this is meta, meta row, met column, meta row, counter column, counter anti diagonal and meta now. So yeah, we check the status the player.
Stochastic Panda: Yeah. And you could have like a bis last player somewhere in the move method. Yeah, I follow what you're doing.
Occam's Laser: Yeah, I am trying to think what to do with the player. Do I need to. Yeah, maybe, maybe the same logic. Yeah, I think to store the last players here.
Stochastic Panda: Sorry to interrupt, but just watching the time, maybe one quick follow up question here is what would you say changes or stays the same with respect to time and space complexity in the meta board versus the standard board?
Occam's Laser: Yeah, of course, the time complexity of the check status, it remains the same. But for the moment we will have the explanation because here basically we. Okay, no, let me think. We make a move. No, actually, yeah, we have the same. We have the same. Just from the complex store complexity. Now we have the boards, we have the array of arrays, we have like all and square for the space complexity. But from the time complexity, the moves and the check status, they remain the same as for the previous solution.
Stochastic Panda: Yes, that's right. Because we're essentially doing an index lookup and checking what the current counters are, just like in the previous one. Great, thank you. I think this is a good stopping point for us to recap. And what I would offer is that I think you did really well. You caught the sort of minor hints in the beginning really quickly, to go from your first initial approach of maintaining the entire board for the standard board to discovering that good efficiency of keeping the row states or row sum states and column states and diagonals, antidiagonals. So that was excellent. And also I would say, yeah, you did good code reuse in the meta tic tac toe board of, for example, online 150 of basically inheriting and using the previous tic tac class. Now, if potential nitpicks, and this is just me, but it would just depend on the interviewer, potential nitpicks would be like some of these syntax, like if we look at line 95 and we were maybe trying to debug this code, and we see rows and row, those two names are a little bit similar. They're fine, they're understandable. But another way to do it might be to say like this row sums, and then you index row from that. But that's more of a nitpick. The other kind of nitpick I had in mind was, which I think we would get to with more time if we look at your move method and check status method. Certainly to solve a problem, we can basically copy paste the code and change it. But another potential way to do it is to inherit those two methods, move and check status from the standard board. But if we do that right, then check status needs to know what it's checking the status of. So we could actually go back and if we wanted to extend it to like row sums and call sums, et cetera. Because in this case there's pros and cons. We are building essentially an extra pointer and passing things in. But it would give us the flexibility to use just one kind of check status method and do something like this is also another nitpick, like have this method be called like meta check status, and at some point calls, and I'll put in quotes directly. I forget how to do it exactly in JavaScript, but check.
Occam's Laser: Yeah, I got you. It makes sense if the move, it differs, but the check status, it remains the same, only the field names changed, right?
Stochastic Panda: Yeah, to be honest, those were my only nitpicks. I also thought you did really well on the time and space complexity analysis. And yeah, sometimes it can be tricky to think about the meta board, but one way I think about it is that the metaboard, if I kind of flatten it onto a 2d space, then it's another way to see that the time complexity would not increase. Right. And those were my main comments. So yeah, thank you. I had some other maybe fun, interesting follow ups on this that I can share, but in the last few minutes, if you had any comments or questions for me.
Occam's Laser: Yeah, basically I wanted to say that it is the good question. It is not that, let's say nerd questions about the data structures. I like this. I like the way you conducted the interview. It was polite and very helpful about the questions. Yeah. If you can share the follow up questions so I can do them as a homework, let's say, just to develop myself. Yeah, I will be happy if you could share.
Stochastic Panda: Yeah, sure. And thank you for that feedback, by the way. It was a real nice experience for me as well. So I can share some of the follow up considerations like verbally, and I'll make sure to type them in in the feedback. But something interesting to think about, which at least for me is nice practice in terms of working with some of the object oriented design, is to basically design this game that can be applied or interacted with at the command line interface level. And so what I mean by that is we made a simplifying assumption that the move method is always valid. But if we think of using basically this setup as a two player game, then eventually we probably do want something like a check valid method, which is pretty simple to implement, and we can reuse the meta board. But the advantage to that is then on the CLI interface we actually allow player one to try and move anywhere on the meta board. And one interesting thing we can also think about is, well, what should player two do, right? So in Cli we can do one player at a time and just say, okay, player one, tell me your move.
Occam's Laser: It goes.
Stochastic Panda: Player two, make your move and it goes. So that's one part, but another part that I find sort of fun that adds to some of the object oriented, or just general coding, is what if we thought about making player two a basically random computer, player two. So it just tries to pick a random cell, and if it is not a valid cell, then it randomly picks something else and just interacts. So that's like a super simple player too. And if we wanted to go even deeper, actually, if we're sort of inspired by chess, like in chess engines, you can kind of choose how sophisticated you want the computer to be that you're playing against. And there's a sort of similar thing here too, where you can say, well, player two, maybe it can be a little bit more clever than just choosing somewhere random. How would I make player two be more responsive and better equipped against player one? And there's actually some relatively simple but interesting game theory or combinatorics there to say, like, okay, what if I made a more clever player? Two, that, for example, always tries to pick the centermost positions if they're available. And what I just said starts getting a bit involved in some of the code. But there's a lot of good, I think, code reuse and sort of design or game design in that type of exercise. But, yeah, that's all I had in mind there.
Occam's Laser: Okay. Yeah, that may make sense.
Stochastic Panda: Great. All right, well, we did really well on time. We got through it all. Any other questions before we conclude for today?
Occam's Laser: Yeah, I think. No. Yeah, sorry. Okay.
Stochastic Panda: All good. Well, thank you so much again. It was a privilege and I appreciate it, and thank you.
Occam's Laser: Yeah, thank you, too. Have a nice rest of the day.
Stochastic Panda: All right. Yeah, you too. Bye.