C++ Interview with a FAANG engineer

Watch someone solve the number of unique islands problem in an interview with a FAANG engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Number of Unique Islands

Interview question

Given: A 2D array of integers representing land and water. Values of 0 represent water. Values of 1 are land. An "island" is a set of adjacent (N, S, E, or W) values = 1. Your task: count the number of unique island shapes.

Interview Feedback

Feedback about Metal Taco (the interviewee)

Advance this person to the next round?

How were their technical skills?

3/4

How was their problem solving ability?

4/4

What about their communication ability?

4/4

Fantastic problem solving ability and intuition. Broke down the original problem into parts and knew generally the approach that needed to be taken. Had some good ideas on how to uniquely identify the structures involved. Great communication as well, asking questions about bounds and limits and letting the interviewer know the direction you were going. You included lots of comments in your code (//up, for example) that made it instantly obvious what direction we were going, if the row and column variable names weren't already clear enough (which they were). Quickly able to write the needed code. Great intuition on the second "tough" problem (I pulled this from an actual real world problem I faced!) and I wouldn't worry too much about being asked bit-manipulation questions on most interviews; however, the "lesson" in this question is that at it's heart, it's simply a binary search problem, using bits instead of "a sorted list of integer powers of 2". Recognizing a common problem (binary search) wrapped in a cleverly disguised package (hey, here's a integer) is a good problem solving skill to have, and it's how you'll realize "pythagorean triplets" is really the same as "3sum" and if you can solve one you can solve the other. Try to recognize these patterns in your problem solving. Room for improvement that I noted: - be absolutely familiar with the most common algorithmic data structures you'll see in these types of problems (set, hashmap/dictionary, list, queue, stack, heap, array, etc.). In the real world you get to look up syntax, but for interviewing where you get to pick the language, you should know these cold. - one tiny communication nit: you used the same function name for findIslands for both searching the ocean and navigating an island. that's ok obviously but might be better with a different name like exploreIsland, etc. easier for me to refer to when asking a question as opposed to "the findIslands method on line 31".

Feedback about Fabled Lion (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?

3/4

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

4/4

N/A

Interview Transcript

Metal Taco: Hello.

Fabled Lion: Hello good afternoon. How are you doing today?

Metal Taco: Good, how are you?

Fabled Lion: I am doing pretty good, thanks.

Metal Taco: Awesome. Good to hear.

Fabled Lion: Sorry I'm a little late here. I was kind of expecting it to be connected, and I realized it was waiting for me to click a button.

Metal Taco: No worries at all.

Fabled Lion: Hey, great to virtually meet you in order. Help me target this interview a little bit better. It would be helpful if you any information you're willing to share on where you are in your career, what types of roles you're targeting, any experience you may have.

Metal Taco: Yeah, definitely. So I graduated from college last December and currently applying for full time positions after I had a position at a fang company, and it was rescinded or delayed a significant amount because of all the hiring freezes and stuff. I had two internships with them, and so right now I'm working up and doing prep for technical interviews for companies. I have a couple that I'm currently in the process with, but yeah, I just generally wanted to get some experience kind of in a real life situation because it's a bit different, like solving these problems on your own, like on leak code or something, versus having to do it live and with an interviewer.

Fabled Lion: Absolutely. Yeah. The main difference is you have to say what you're doing as you're solving it.

Metal Taco: Right.

Fabled Lion: All right, excellent. And just some advice on that. In addition to just getting a professional interviewer like me, who actually has done interviews with candidates, there is this peer interviewing thing. On interviewing I o, it's free. I think if you are a peer interviewer, for every two interviews you give, you earn a free one where another peer can interview you. So it's just a free back and forth thing.

Metal Taco: Oh, cool.

Fabled Lion: If you just want to practice talking to someone. Now, granted, they're just going to be a candidate just like you, but you learn something interviewing them. They learn something interviewing you, and it's free and it's useful. So just a suggestion.

Metal Taco: Check that out.

Fabled Lion: Check that one out. Yeah. All right, great. Well, let me just jump into it then. Actually, there's two main purposes of these types of interviews. When you go to a company, one of them is just kind of the basic, hey, can you code? Do you know a programming language and any of the basic algorithmic types of things? Can you do loops and conditionals and know just enough about computational complexity to not write stupid code? So that's kind of the goal, and there's kind of going to be two halves of the interview, and you'll kind of see the first part. Or sometimes there's one problem that gets complex, or sometimes there's two different problems, but you'll kind of get an easy problem to solve to write the code. And then as it gets further on, either it'll be a harder problem that you have to explore some unique aspects of, or you'll just get peppered on more detailed questions. Or hey, do this a different way, even if it's not the best way, but you'll have to answer questions about trade offs and more detailed in depth knowledge. Basically, don't worry if you can't answer something. The interviewer is probing to find your breaking point. If you ace the interview, then the question wasn't hard enough. Yeah, okay, they're going to raise the level as needed until they find out where your breaking point is. Don't worry too much about style, capitalization underscores, Camel case, all that kind of stuff. Typos it's mostly the algorithms we're going to be talking about. Most important part here, though, do please think aloud. The worst thing you can do is just sit there and struggle along silently and make me try and understand what you're thinking based on reading your code. And don't worry about mistakes. 90% to 95% of the time, maybe even higher, you're going to make a mistake. It's fine, right? You're nervous. Everybody does that. It's not a killer in these things. So as long as you find either find it yourself or when prompted, if you quickly say, oh, this was a stupid thing, and fix it. That is extremely common in interviews and doesn't really hurt you. It's stuff that your IDE would normally catch, right? Okay, great. So in the upper right corner of your screen, you will see a drop down. A language drop down currently says plain text. Feel free to switch that to the language of your choice.

Metal Taco: Cool. Go ahead with C plus plus, if that's okay.

Fabled Lion: That's okay with me. It's a challenging language, so good luck to you in that. All right. And I am going to go ahead and paste a question here below.

Metal Taco: Where.

Fabled Lion: That current text is and let me see if I can figure out. It is a standard star comment file comment style. Okay, so here's your question. I am giving you a two dimensional array of integers and you can see the example on line 20. Ones represent land and zeros represent water. So you can think of that as an ocean with a bunch of islands in it. And there are currently four islands in that ocean. You can see one in the upper left hand corner, kind of an L shaped, three vertically and one horizontally. You can see that same shape in the third column down near the bottom. And then in the second row, third column from the right, you'll see a third island. It's two ones in the top with one below the right hand side. And then in the lower right hand corner, there's two ones in the top and one below the left hand side. Okay, basically when we're talking adjacent, it's only the horizontal. So north, south, east, west, or left, right, up, down, if you want to call it that way. Not diagonally as far as Adjacency goes. So there are four islands. However, I want to know how many unique islands there are.

Metal Taco: Got it.

Fabled Lion: And the key here is the one in the upper left and the one in the third column near the bottom are both identical in shape. You can see the shape on line 32. There's three different shapes. So that's what a value I want to get and go.

Metal Taco: Okay. All right. Yeah. So just from taking a look at this, thinking about some of the edge cases we might need to handle for so are there any guarantees about the minimum size of the two dimensional array? Sure.

Fabled Lion: I'll tell you, it's not empty, so you at least have one row and one column.

Metal Taco: Okay, got it.

Fabled Lion: And I'll also give you that it'll be rectangular, so you can assume that the length of the first row is the same as the length of all the other rows.

Metal Taco: Okay. Yeah. So this is an interesting problem just thinking about it's kind of in two different stages in my mind. One would be identifying islands, and then the second problem is that we only want to count unique islands. So I think that's the interesting aspect of this problem to solve. So starting off with figuring out how many islands there are, I'm thinking that the basic solution would be an O of N times N, or length, width and height complexity, and the same space complexity. We'd essentially loop through with a Doubly nested loop through all of the elements in the two dimensional array. We would keep track of a visited two dimensional vector as well. And this visited array would make sure that we don't visit the same cell twice. And essentially, if we find a zero, we would mark that square as visited and continue on. And then if we find a one, we could have a separate function that essentially traverses through the array, marking each cell that's visited and discovering exactly where the extent of the island is using the four cardinal directions. But that would just count the number of islands. So additionally, we're going to need to figure out how many unique island shapes there are. And so just thinking through that about how we could determine whether or not the islands are the same or not. One thing that comes to mind would be trying to make all the islands generic to a zero index so that we would easily be able to compare their dimensions. So, for example, when we have this island in the top right and this island here, we would zero index the top left of each unique island, which would be the first time we encounter a one for that island before we recursively search. And then after we find all the unique islands and store the coordinates of each one within that island, we would then loop through that new structure that we've created and only count them if we haven't seen that same structure before.

Fabled Lion: Okay.

Metal Taco: So that's the first way to track if there are unique islands that comes to mind. Trying to think if there would be another way.

Fabled Lion: That's a pretty good intuition. Okay, go ahead.

Metal Taco: Okay, yeah, I'm just thinking if there would be another way to do that. I don't think it's entirely simple and it does require us to go back through, like create a data structure storing all the island information and then go back through that again.

Fabled Lion: Okay, are there any data structures that are particularly well suited for removing duplicates?

Metal Taco: Yeah, I mean, with sets you can only store one of each element within it.

Fabled Lion: Okay, so that might save you going back through it a second time. Step true.

Metal Taco: Yeah. To be honest, I'm not sure how set comparisons would work with, like if you had a set of vector indices of the so you have a set and each element within that set is a vector of indexes of where that island is on like a zero index scale. And then you could just return the length of that set. But yeah, to be honest, I'm not sure how set comparisons work when it's not a single element within that set. Like I said, if we have a set of vectors okay, well if we would need to establish our own comparison function or not.

Fabled Lion: Okay, well, so maybe you would, but maybe you can also turn it into a single element. What kinds of sets have you dealt with in the past?

Metal Taco: Yeah, interesting. If we could turn it into a single element, that's a good idea because what if we zero indexed all of the islands and then instead of storing a vector of the indexes of the islands, what if instead you stored some sort of a sum of all the indexes? Then that should be unique for each of the islands, for each of the island shapes.

Fabled Lion: Okay, you're thinking in the right direction. Let's table that conversation for later. You mentioned earlier kind of separating this to two problems. One, finding the islands and then finding unique ones. So let's go ahead and do the first part and then after we're done with that, maybe we'll revisit this second conversation.

Metal Taco: Sure, sounds good. Yeah. So can go ahead and write we'll need two functions to do this. So we're returning an integer, which is the number of unique islands. So find islands and then we're given a two dimensional array of integers called islands. So additionally, on top of that initial data structure, we will also need a two dimensional visited visited array. So just initializing that with negative one for not visited and have a visited array. Then we would need a doubly nested for loop it and then we can store it as an integer, current tile, island, row and column. So we can say if current tile is equal to zero. Otherwise, and just to clarify, there will only be zeros and ones in the array. We're not going to get any sort of like bad input.

Fabled Lion: Sure, for now that's a good assumption.

Metal Taco: Okay, so if current tile is equal to zero, we simply mark it as visited and continue. Otherwise the current tile would be one, in which case we would need to find the islands and we can use Find Single Island. And for this I'm thinking we'd need another function that essentially would recursively search through the two dimensional array looking for all instances of that island. So call it find island. I guess the parent function is called Find Islands. We need islands, we need visited, we need row, column and then to this function takes in visited, takes in row, takes in column. And then if we've already visited, don't care about that. Otherwise we'll mark this current square as visited. Then if it, if the spot we're on is a zero, then we would simply return. We've already marked it as visited. Otherwise this is the case where we need to then curse in all cardinal directions. So if row minus one is greater than equal to zero, this means we can go or sorry, this is up, down if column one, if column plus one's. And so then this is up or sorry, this would be left and right. And then what we would do is marking is visited. We would call Find Islands, islands visited, row minus one, column plus one. And then we want to search right. Sorry, we want to search left and then we want to search right. And so then once we encounter the start of an island and we haven't seen that island before or any piece of that island before, so we should be entering each island at the top left corner of that island. Then we enter into this function find island, islands visited, row and column. And if we've already visited this tile before, then we return. Otherwise we're setting visited to true, we don't care about zeros because they're not part of the island itself. So we don't want to recurse if we encounter a zero tile and then otherwise if we can, if we're not at an edge of the array, then we want to search in all four directions for other island tiles. And then essentially what this will do is mark every single island, every single tile of that island as visited. So then each time we find a unique island, we know that that is the only island. So this essentially solves I haven't put any return here yet because the question was asking for unique islands. But if we wanted to find every island, we could simply increment some sort of islands counter and then return islands at the end.

Fabled Lion: Okay, great. So I think you've effectively found all the islands. So let's go back to the question of uniqueness. Let me just ask a question about your algorithm here. When you're navigating these shapes in that second, the line 35 method or function, I forget what the name in c plus plus is I'm a Java guy. Line 35. When you call that, will you always navigate the island in the same order? Like you were saying, you're always going to start in the upper left. Is that always going to be true and so forth?

Metal Taco: Yeah. So because we're marking all of the successive island tiles as visited, there's no way we could enter an island in any other tile other than the top left one of that island. So we should always enter the island at the same spot. And each time we find a single tile, we're always looking for those islands in the same order.

Fabled Lion: Okay.

Metal Taco: We're looking for the rest of the tiles in the same order. Essentially, we're looking up and then we're looking down. Yeah. Interesting. If we're going to because once we go up, then we're in a new tile.

Fabled Lion: You got quiet thinking about something.

Metal Taco: Yeah. Just to clarify, I'm just thinking about that question of if we'd always traverse the island in the same exact order.

Fabled Lion: Yeah, I mean, it's kind of a bigger question here on a search of the style that you're doing here, is the order guaranteed or repetitive or what's the word for a predictable deterministic? Deterministic. Thank you. That's the word I'm looking for. Bonus points for you filling in a blank for me there.

Metal Taco: Yeah.

Fabled Lion: So that's the question. Is it a deterministic algorithm here? And I think you're saying it is.

Metal Taco: Yeah, I think it would be since we're always recursing in the same order. We're always going to go up as far as we can. Yeah, I'm pretty sure it would.

Fabled Lion: All right, great. So knowing that, let's go back to your idea of trying to come up with something you can stick in a set that will help you remove those duplicates very well. So what kinds of data are you used to putting in your programming past? What have you put in sets?

Metal Taco: Yeah, usually I guess I'm not sure the term for it, but like single item variables. So like integers or, you know, I guess no, because you can put strings in sets.

Fabled Lion: Okay. Yeah, you can put.

Metal Taco: Anything yeah, you.

Fabled Lion: Can put anything in. And as you mentioned earlier, you just need to come up with some sort of a method of making sure that that all resolves to some unique number. But let's explore the string option, knowing that you're always going to be going in these same directions.

Metal Taco: Oh, interesting.

Fabled Lion: Or, you know, your relative coordinates or something. Is there a way you could just build a string dynamically and end with a string that describes the shape?

Metal Taco: Yeah, definitely. And string comparisons are very easy to do. We don't even need to do string comparisons because we just throw it in a set. But yeah, essentially I'm thinking you could store like essentially so let's say here we have a string called, I don't know, called island or something, and then we go ahead and pass this in to Find Island. And then what I'm thinking is every time we travel in a direction, we would append to the string the direction that we're traveling. So each island that has the same traversal that follows the same direction would end up with the same string. The one thing we do need to handle for is that we're not checking if the island is zero ahead of time. So you'd get a lot of extra junk in the string. You wouldn't just get the directional of the one tiles. But I think we can definitely still do it. I think it just requires tweaking a bit of how this Find Island works. Um, yeah. So we pass it in by reference. So as we go through this recursive path, we're going to keep updating island, and then at the end, this island string will contain the entire directional input that we use to find that island. And then we would just push the island into the set, and then we can just return the set length at the end.

Fabled Lion: All right.

Metal Taco: Okay. And I'm actually not sure of the exact syntax for a set in C plus plus. Do you mind if I just Google that real quick? Is that okay?

Fabled Lion: Sure, go for it.

Metal Taco: Okay.

Fabled Lion: That would probably not happen in a normal interview, but this is practice, so I'll let you do that.

Metal Taco: Okay. Yeah. Definitely not something I use regularly, but it's a good reminder that I should practice with it more. It okay. So this should handle the Find Islands function now. And now we just need to handle this because if we just append the direction here to the island string, what would happen is that we would get a lot of extra directions for all of the zeros. We could solve that pretty easily, I think, just by doing a check before we make the recursive call of what tile we're trying to go into.

Fabled Lion: Okay, well, let's pause for a second. Is it a bad thing to have a bunch of junk in your string?

Metal Taco: Yeah, I mean, we're traversing always in the same direction, so I guess it wouldn't necessarily.

Fabled Lion: Let me give you a hypothetical look ahead. Look down at line 90, which is where these examples have gone, and take a look at the right hand. Two islands, they're both going to involve going right once, and they're both going to involve going down once, but they are different. So how are you going to distinguish between those two in your algorithm?

Metal Taco: Yeah, interesting.

Fabled Lion: If you only stored the directions, they would both have right down or east, south or whatever those are. So you need at least something to say, hey, I'm moving my start point.

Metal Taco: Right. So essentially as we're backtracking through so we needed to track what direction we're going in addition to what direction we're going when we backtrack.

Fabled Lion: Correct, correct. Yeah. I'm also just saying that this extra junk that you're trying so hard to get rid of might actually be useful there. So I'm just saying don't rush to get rid of it.

Metal Taco: Okay. Yeah. Interesting. So what if instead of you could say just back up something like this to track when we've returned from going upwards.

Fabled Lion: Okay.

Metal Taco: Whoops. This says islands, because essentially, I'm thinking when we're looking through here, we wanted to track what direction we're going, and additionally, when we're returning from that direction, because here we're going right. But once we've gone right, there will also be coming back from going right. Whereas in this string, the order will be different. Right. Because we're going to go right. But instead of going back right in the same order, we're going to be going down before we encounter that back. Right. So the strings will be different. Okay. Yeah.

Fabled Lion: No, I see. That looks good.

Metal Taco: Okay.

Fabled Lion: Might be shorter with just a single character than the entire word.

Metal Taco: Yeah, true.

Fabled Lion: It looks good.

Metal Taco: Yeah. Okay. It so we want to concatenate the string. Yeah. Just complaining about the quotes here, but we want to concatenate the string as we traverse through each island, and then at the end, we're pushing this string back onto the set, and the set can only store unique elements, so if we encounter the same string twice, that should not be added to our island list. Yeah. And so then we push it onto island list, and at the end, we can just return island size.

Fabled Lion: All right, that sounds great. Okay. This looks good to me. One question I did want to ask. So you mentioned when you added that island parameter to pass around, you made a comment about you're passing it by reference. Can you explain why you said that?

Metal Taco: Yeah, it's because let's say we add island up here. Yeah. I'm passing it by reference because we want the value through all of these recursive functions not to be copied, but instead just to retain that same initial value. And also because we're not returning from Find Island, we're simply passing in island. You could do it where you're, like, concatenating a string, change this to a string return, but with this way, we can just pass the variable in by reference, and then island is automatically, like islands change once we get down to line 28. Because we pass it by reference, this initial variable is going to be altered every time we're concatenating the string.

Fabled Lion: Okay, great. Do you know the word for being able to alter a variable as you pass it around?

Metal Taco: Um, I'm not sure. I'm not quite sure you're going to.

Fabled Lion: Lose the bonus point you got for deterministic, but yeah, I know.

Metal Taco: It's muted by value, passed by reference.

Fabled Lion: Mutability was the word I was looking for. That's all right. It's fine.

Metal Taco: Okay.

Fabled Lion: Hey, great. We have some time left, so I want to jump to another problem here since you've pretty much solved that one. So I'm going down to the bottom of your screen here. And this one you don't need to write any code for. I would just like you to talk about an algorithmic approach that you would take to this and just say anything that comes to mind in terms of, hey, this reminds me of this type of a thing. So starting on line 105, it is a very succinctly written problem, but it ends up kind of being a little bit more complex once we start thinking about it. I would like you to write a function that rounds an integer to the nearest power of two. Here's two examples. If I give you the number 800, it should round up to 1024 because that's closer than 512. And if I give you 1500, that should round down to 1024.

Metal Taco: Okay.

Fabled Lion: I'm going to give you another bit of information that assume this is going to be, like, on the hot path, and it really needs to be optimized to be the most computationally efficient as you can possibly get.

Metal Taco: Right, okay. Yeah, I can definitely talk. There's a slower approach and there's a faster approach. Before that. Are there any guarantees about the polarity of the integer? Like, can it be negative?

Fabled Lion: Sure, I guess I'm trying to think how I would even handle that, actually. No, I'll say powers of two are always going to be positive. So assume it's a positive integer.

Metal Taco: Okay. Yeah.

Fabled Lion: If you want to use an unsigned data type. So it's always guaranteed positive, that's fine, too.

Metal Taco: Yeah, that does bring to mind that do we have any guarantees about the size of the integer that we're being given? What comes to mind when you say unsigned is that if we're given an integer that's close to the maximum integer of a regular integer variable type, trying to find that larger value would overflow the integer.

Fabled Lion: Sure. Let's just say it'll be within a 64 bit value.

Metal Taco: Okay. Yeah. So in that case, I'm thinking the slower way to do it is just essentially what we want to do is we want to find the power of two less and we want to find the power of two greater, and then we just want to compare and find which one is closer. Okay, so the slower way to do that so we have our initial starting integer starting with the power of zero, which is one, and then you just increment go to the two to the power of one, two to the power of two, two to the power of three. And just like continually doing that until we find the first power of two greater, we store the previous power of two that was less than as we're finding that greater value. So we have the two values to compare. But yeah, faster way to do that just would be to do like, a binary search. So instead of incrementing by one. Well, the initial faster way would just be to, like, thinking about. So I know we want to do some type of logarithmic search because that would be much faster than just incrementing by one every time. What I'm thinking about is how we would find that initial value to binary search over.

Fabled Lion: So I'm liking your intuition here on binary search. Let me just throw a question out there, irrespective of this particular question. When you think binary search, what are kind of the requirements? In order to search something that way?

Metal Taco: Yeah, you need to have a minimum and a maximum. And that's what I'm kind of thinking about, is like I'm thinking about how we would find that maximum value, that initial maximum value.

Fabled Lion: Well, I mean, if I tell you because if I tell you it's a 64 bit number, then that might be your maximum, right?

Metal Taco: Oh, yeah, true. With the binary search, you have your minimum value, which would, I guess, be zero, and your maximum value, which we could just set to like an Int max, and then we would binary search based on taking that value. Well, the thing I'm thinking about is like if we set Int Max to be the maximum, then when we try and set that number to the power of two, it's going to overflow. Because essentially what we want to do is have the search space every time we iterate, we have a minimum and a maximum of integer maxim. Instead of setting the maximum value to be Integer Max, you could just do some sort of computation beforehand to find two to the power of what gets us as close to possible as Integer Max without overflowing and then set that to the maximum.

Fabled Lion: Okay, so good intuition there. So what is integer? Max? If I tell you two to the power of something is Integer Max, what's that something?

Metal Taco: I'm not sure. I'm sure there's a fast way to do that well, but I'm not sure.

Fabled Lion: If it's a 64 bit number. What's the largest 64 bit number?

Metal Taco: I'm not sure off the top of my head.

Fabled Lion: Let's go to the easy one. What is the largest eight bit number?

Metal Taco: Yeah, I'm sorry, I'm not good with okay, you found my breaking point.

Fabled Lion: I found your breaking point. What's the largest one bit number? Okay, what's the largest two bit number?

Metal Taco: Four.

Fabled Lion: Okay, are you following now? So the largest eight bit is going to be 256.

Metal Taco: Right?

Fabled Lion: So two to the whatever number of bits is what you get, and there's a minus one involved here. The yellow brick road I'm leading you down here is when I'm giving you these integers, really all you have is a 68 array of bits that are all either one or zero, which you can represent. Those are all just a sorted list of numbers between zero and two to the whatever, 63rd. But the point here is that you're looking for the most significant one in this list. So you had a fantastic intuition of. You need to do some sort of a logarithmic search, and you even called it binary search. In a binary search, you have a sorted list of numbers or whatever that you're going through. And those bits are actually they represent numbers. Each bit represents a number one, two, 4816 and so forth. Got it.

Metal Taco: Binary search on the array of bits.

Fabled Lion: Yeah. Now, given all that information, let's go back to your algorithm. So you want to do have your search space. How are you going to do that?

Metal Taco: Yeah, so the way I initially conceptualize with this was simply using numbers. But you're talking about having the search space within an array of bits, correct?

Fabled Lion: Yeah, correct. Okay, let's go really easy. You have a two bit number. I'm thinking of a number between zero and three, and I want you to guess it in only two steps.

Metal Taco: Yeah. So if you have a two bit number, then your middle value is size minus one, and you make that bit one.

Fabled Lion: Okay, so if my possible numbers are 0123, and I want you to guess it in only two steps, the first thing you're going to do is you're going to ask if it's smaller than two or at least two, right?

Metal Taco: Yeah, you could do that as well. I mean, I was saying go to one first, but you could also go to two as well. Yeah.

Fabled Lion: Okay, so basically that's going to be your approach. You'll split the number in half bitwise. So a 64 bit number, you will split into a 32 bit number.

Metal Taco: Okay.

Fabled Lion: So basically you would ask the question, is my number bigger or smaller than two to the 31st.

Metal Taco: Right. So you would take your first integer and you would find the highest index where the bit is one.

Fabled Lion: Um, all you need to do is ask the question, is it bigger or smaller than this number? And then continue to logarithmically iterate, chopping the thing in half with a little bit of complexity of some bit shifting in the middle, which that's okay, since we've identified this as your weakness, I don't think we're going to get there with this question.

Metal Taco: Yeah.

Fabled Lion: I do want to compliment you, though. That intuition of a logarithmic search is that's what most people miss in this problem, and you had that right up front and you just didn't quite have the details to get it there. All right, hey, great. We have about ten minutes left in this and you've done really well. I want to just kind of open this up for you to ask any questions you want. If you want, I can give you live feedback, but I'll give you also some detailed written feedback afterwards. So if you just have any other random questions about interviewing process or just overall in general, I'm happy to give the rest of the time to you to use as you please.

Metal Taco: Okay, cool. Yeah, some live feedback would be great, but I guess first, maybe. When you've been interviewing, what are some things that you've learned that have maybe been kind of, like, you think have really helped your performance within these technical interviews?

Fabled Lion: Sure. There's only a small number of actual types of problems that can be asked.

Metal Taco: Okay.

Fabled Lion: The reason is and I've even gone into interview hiring training, and they're like, yeah, you have to have this special it needs to be hard enough but not too easy, and you have to be able to measure all these things out of a single question. So there's a fine tuned calibration of getting just the right question, which you might notice the question I asked kind of meets that there's an easy solution, and then it starts to get more complex and then you're digging into all these unique aspects of it. That's why it's one of my favorite questions. There's some other really good questions out there. Boggle is if you've ever done the Boggle question, that's also a particularly good one.

Metal Taco: No, I write that down, though.

Fabled Lion: Yeah, when you boil it down, there's really only like seven different data structures to know and maybe about ten or 15 different algorithms to know. And every problem is just some combination. Every problem is a combination of those.

Metal Taco: Yeah.

Fabled Lion: So have you ever seen the site? I think it's called neat code. I'm typing the name here on line 119. I think it's neatcode IO.

Metal Taco: Yeah, that's pretty funny, actually. I usually just do like, leak code. I was like, doing Blind 75 for a while. Perfect. But just like last week, I heard about Neat Code, and I've been kind of using it to go back through some problems I haven't done in a while. Because it'll take you from kind of ground zero with just like arrays and strings up to two dimensional dynamic programming problems. Yeah, it's a website. I've actually been using it recently.

Fabled Lion: Yeah, it's kind of probably one of the best website because it covers all the different types of problems that you're ever going to possibly see. So if you are comfortable with solving 75 or 150 problems, you don't need to do every single leak code problem. Those kind of COVID it. But don't focus on just solving the problem. Focus on how do I do this? Why do I do this? Up in our question that we solved, I'm sure that's actually a leak code question somewhere. I think it's one of the hidden ones that you have to subscribe to. The counting islands is available, but the counting unique islands is one of those you need to be a member to do this kind of thing, but it's there. Would you have found it? No, but what's important about that, knowing these important things, like is it a deterministic algorithm, and when you hear the word unique, you should immediately think, oh, this is a set. I need some function that's hash that's hashable so it can go into a hash set or a hash map or something like that. And you kind of need to know, okay, what does a hash function actually mean? If I had to write one for a vector, how would I do that and just do those mental exercises? It's not just about solving the problem. It's kind of exploring every corner of the problem.

Metal Taco: Okay.

Fabled Lion: Sometimes I used to ask two sum, which is like one of the simplest leap code questions you can get, right? But it's like I wouldn't just say, hey, solve it. I would say solve it all three different ways. And you would have to go through those. And then I say, why is this one better than that one? Or what are the advantages and disadvantages of each one of those? And you would kind of have to go through that. There's some other cool problems. Have you heard of three sum?

Metal Taco: Yes, I have. Yeah, I've done that one a number of times and every time it's difficult.

Fabled Lion: Yeah, but really all it is is it's two sum, which is, you know, trivially and you know the way to do it with a loop around it. Okay. Have you ever done Pythagorean triplets?

Metal Taco: No, I haven't.

Fabled Lion: Okay, well, no, don't write it down. This is one's easy. You've got A squared plus B squared equals C squared, right? I'm going to give you three numbers, and I'm going to ask you for combinations that match that. Do you know what that really is? It's three sum. It's cleverly disguised in terms of math. There's a sliding window, one where I'm like, hey, I'm giving you random XY coordinates on this graph. And then I'm going to give you an angle, and I want you to tell me the maximum number of these coordinates that you can stick in this angle that you're looking at like you've got a telescope. How many stars can you see in? It kind of a thing. And sure, it's basically do a polar coordinate transmutation. And then the rest of it's just like the standard sliding window of how many jobs are running at any particular time where you're incrementing and decrementing and keeping track of that and that type of thing. All of these problems that are the same algorithm, they're just dressed up creatively in different ways. But you're always going to be either doing a two pointer iteration like in Tucson, or you'll be wrapping that. It's the same building blocks. So as you do neat code or lead code, problems kind of uncover what those building blocks are, and every problem is going to fall into one of those. This unique thing is it's basically a depth first search that you're iterating over with a few creative additions to how you're going to do it. And you can optimize it and things like that, but it's truly just that simple type of a thing. Okay, so know the different data structures. One thing that was kind of a surprise here is that if you're choosing the language, you should know all the data structures in it that you would expect to see. So sets and lists and queues and stacks and stuff like that. So any of the common data structures you're going to see, you should be able to recall immediately by memory, but there's not that many.

Metal Taco: There's like interesting, I've actually been in interviews where they let you look things up before it's fine.

Fabled Lion: For your chosen language, you should be an expert in that language, or at least to that.

Metal Taco: Okay.

Fabled Lion: Also, things like are strings mutable? They are not in Java, but they are in C plus plus. So that was kind of one of those. I had to Google while you were asking a question. I'm like, oh, are strings really mutable in C plus plus? And it's like, oh, yes they are. It's kind of one of those.

Metal Taco: Yeah, I don't even think about that because I use C Plus Plus for so long I don't even realize some of the things it gives you by default.

Fabled Lion: Yeah, well, in the real world, people use stupid languages like Java and JavaScript, so have fun joining the professional workforce. But anyway, it's good to know those things, otherwise they're going to bite you later. But just knowing, hey, I use this language so I'm able to do this and just knowing those little levels of detail kind of help guide as you go along, but that's kind of where you're going to go.

Metal Taco: Is it a detriment to use C plus plus? Because I personally have never used it in professional settings between interviews, internships, smaller jobs I've done, I never actually use C plus plus, but it's always my go to language for leak coding just because my college education was all in C plus plus. Standard library stuff.

Fabled Lion: Yeah, it's fine. It's probably okay because your interviewer is not going to know it, so you can probably get away with a little bit more than you would, but it's kind of one of those. Whatever you're comfortable with is a good one to use. It's mostly about the algorithms and then knowing key things like is this a determinist algorithm, is this a mutable data structure? Things like that, pass by reference, pass by value. Knowing those little aspects of the language is kind of important, so you're totally fine. It is kind of one of sometimes you actually run your program. I don't know if your program would actually compile and run. It would be fun to see if it would, but I've only had.

Metal Taco: I've.

Fabled Lion: Only had one other person try and do C plus plus, and they debugged for like, ten minutes because it's like the program looked good, but there's all these little subtle oh, I didn't do this silly thing that I need to do in C plus plus, so I didn't even ask you to run your program.

Metal Taco: Kind of interesting because the environment you code in. Sometimes with leap code you don't have to worry about all these tiny little errors, but then you get into this coding environment where they actually give you the main function and everything like that, where all of a sudden these little errors pop up. So it's definitely like a good reminder that I should practice more with a real compiler and not just those web compilers.

Fabled Lion: Well, doing leap code kind of gives you that real compiler, so I think that tends to be less a problem in an actual interview. They used to be on whiteboards, so you'd be writing all this stuff on a whiteboard and nobody's ever ready to compile that. There's a balance in between those. If you have the most beautiful algorithm and you have a typo that syntax error so it doesn't actually run, I'm not going to fail you on the interview, as opposed to someone else who did a very simple computationally horrible solution but got the right answer, you'll still win on that. So the algorithm wins, that's the important part. But having code that works is also pretty fun, but one cool data structure if you're not familiar with it. I do want to just throw one data structure at you and it's good for that boggle problem. It's called a try T-R-I-E. Have you heard of that?

Metal Taco: I have, yeah. I've actually used one of those before. Never in a real environment.

Fabled Lion: Yeah, I use it in a real environment every day as a part of a distributed wow, okay. It's basically nested hash masks, but it's a really efficient way if you're dealing with distributed computation in any way at all, that is kind of the way to do it. A distributed hash mapped type of or hash ring type of a thing is pretty important. So look that up, look up consistent hashing and hash rings and stuff like that. They're pretty cool things to understand when you get an interview. All right, great interview. I think you're ready to go. If you want just more practice, I would encourage you to keep doing some of the free peer ones. Interview other people, ask them this question and you might learn something from their answer as well, and maybe any other elite code problems you're doing. Ask your peers those questions and you'll learn something from their approach, they'll learn from you, and it's free all it costs you a little bit of time.

Metal Taco: Cool, awesome. Thanks for the interview today. This was super helpful.

Fabled Lion: Yes, absolutely. Great talking to you and best of luck in your job search. I know it's really tough out there. I'm hoping things are going to get better next year. We'll see. See how it goes.

Metal Taco: Yeah, me too.

Fabled Lion: All right take care.

Metal Taco: See you.