Python Interview with an interviewing.io engineer

Watch someone solve the print k largest elements problem in an interview with an interviewing.io engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Print k largest elements

Interview question

1) Given a integer as a input, replace all the ‘0’ with ‘5’ in the integer. 2) You are crossing a river using a series of rocks that stick out from the water. You can move across either one-rock at a time, or jump a rock in order to move ahead two rocks. Given there are 'r' rocks, how many distinct ways, 'n', can you cross? 3) Write an efficient program for printing k largest elements in an array. Largest elements are returned in order largest to smallest.

Interview Feedback

Feedback about Quantum Cheetah (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?

3/4

Great overall. As mentioned, pushing the pace a little is positive but take care it doesn't come a the expense of missing details in the questions that are being asked.

Feedback about The Incredible Croc (the interviewer)

Would you want to work with this person?

How excited would you be to work with them?

4/4

How good were the questions?

4/4

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

4/4

1/4

Interview Transcript

The Incredible Croc: Hello.

Quantum Cheetah: Hi there.

The Incredible Croc: Hi. How are you?

Quantum Cheetah: Doing well, how about you?

The Incredible Croc: Really well, thanks. Quick question to get started. Have you done an interview with interviewing.io before? Or is this your first time?

Quantum Cheetah: Yes, I have done two previously.

The Incredible Croc: Awesome. Cool. Okay, I guess you're already probably familiar with how the interface works in the editor, and so on. But if any questions, of course, let me know. And we'll figure it out together. What I'm going to do is just give you a quick overview of how I like to conduct these interviews and check that's okay with you, and then we'll kind of jump in from there. Cool. So I'll just start off with a few background questions get to know your experience and interests a little bit. It's an anonymous service so don't feel pressured or compelled to, like, share anything you're not comfortable with. But just give me a bit of a sense of, yeah, like where you've been and what you're interested in. And maybe we're going to next can help me to tailor the questions, can tailor the conversation in the problems that we work on to areas that will be most valuable to you, hopefully. So we do that upfront, I'm happy to share a little bit about my background as well. So you know, who's on the other side of the call, then we'll dive into some problems. That's really where we want to spend most of the hour together. The other thing I'd like to do is kind of find a good moment, a couple of minutes before the end of the hour, before the end of the call just to switch to a bit more of a review mode or reflection mode so we can kind of... I can give you some feedback, you know, ask me some questions, we can discuss how you did before we wrap up the call. You get written feedback afterwards, which I guess you've seen. But I find that having a little bit of dialogue bit of discussion before the end, before the time's up is valuable as well. So that's kind of how I like to do it. Does that sound okay to you?

Quantum Cheetah: Yeah. Sounds great.

The Incredible Croc: Cool. So yeah, let's get to get down to business with a couple questions here. First one should be fairly straightforward. I'm wondering, what was the first programming language you started with?

Quantum Cheetah: Yeah, I guess I'm most used to Python especially under this setting.

The Incredible Croc: Yeah. Have you done any other work with any other languages Other than Python.

Quantum Cheetah: Yeah, you know, some, just random, like MatLab, that sort of thing in college. And at the company I work at, we actually have a sort of, like a proprietary language based off of really old, like scripting, database language, called mumps. Probably not sure if you've heard of it, but that's like, a little different from sort of, you know, more modern languages. Yeah, that's probably and you know, like, it's sort of like a full stack web developer job. So there's, um, you know, some JavaScript, that sort of thing throwing it.

The Incredible Croc: Cool. That's, so that's what you're doing at the moment. Awesome. Right, right. Python is your go to language.

Quantum Cheetah: For this, this sort of setting.

The Incredible Croc: Yeah, yeah, totally understand. Are you doing? You're mostly Python3, or maybe still?

Quantum Cheetah: Yeah, Python3, mostly, I did use two at the beginning. And I guess there were some changes to get used to, once the switch happened, but by this point, I'm pretty used to Python3.

The Incredible Croc: Cool, cool. And you mentioned some full stack is the scope of the role that you're in at the moment, have you?

Quantum Cheetah: Yeah, it's like, uh, so I work in like, electronic medical record system. So it's, you know, sort of the stereotypical, you know, you have like a front end web application. And, you know, there's like a database back end for storing patient details. That sort of thing. Medications, you know.

The Incredible Croc: Makes sense. Yeah, I've done, I've done a little bit of work in the Ehealth space, like, when I very first got started my career. So EMR, EMR is really just like the hot topic back then. And a lot of, you know, hospitals and doctors where I was from was still dealing with a lot of paper at that point in time. So that's cool.

Quantum Cheetah: You know, now, I think it's hard to get the sort of, like the, I guess, the oldest generation of doctors now on to, you know, electronic. Yeah. I mean, habits are hard to break, I guess.

The Incredible Croc: For sure, for sure. And so is the system that you're working on, kind of is a cloud SAAS-y sort of stuff, or is it more like deployed, installed by a customer, maybe you know, installed and managed in their own data center. It's sort of like SAAS, so it's where we actually so... the structure of the company is that we actually just sort of sell the the proprietary language that we use as its own product, but there was a period a while back where they sort of acquired a lot of their customers who were using just that software sort of language. So they sort of acquired companies that were using that original product and sort of like under the umbrella of...

Quantum Cheetah: Okay, was the probably not super related to the programming side of things, but I'm just curious and hopefully, quick one. It was, was the company and the language, like the software language that you mentioned, is kind of the core proprietary thing. Was that always focused on the health space? Or was it broader than that? And then they kind of like?

The Incredible Croc: Originally, the language was used in like a hospital. So I guess like, originally, it was this... the language is called mumps. Like the disease. Right? But yeah, so originally, it was that and then sort of this company like, or like, the company I work at, eventually, like, added sort of like database management aspects to the language. And, but like, a lot of the syntax current syntax follows from the original, which was, I think mumps was like, during like, 70s, maybe even earlier. 80s. So there's sort of like some old there's some, like, aspects of it that are quite different from, like, modern languages that people are used to working with.

Quantum Cheetah: Yes, yeah. I can imagine. Cool, cool, cool. And so let's swing it back a little bit to more like the Python development that you've been doing that that's probably most relevant for what we want to kind of cover today. You mentioned it's like web applications getting kind of do a full stack stuff. So there's some Python in there, you... what's sort of what's the scope your role, you look mainly on application features, you're doing like Site Reliability Engineering, sort of stuff, tuning the existing code base, what's your, what's your day to day?

The Incredible Croc: Mostly, it's, like feature work and sort of tuning the existing. So I work within the like, within the EMR, I work with, like medication management. So it's sort of like dealing with like, you know, both administration of the medications, like, you know, the nurses have a system of like, we gave the patient or there's a medication administration that's due at this time, and then the nurse, you know, has to go in and like mark down the administration. So we deal with that aspect of medication, and also, sort of the pharmacy side. So you know, we track like stock. We track like the pharmacy packing medication for usage, because like, in a lot of other countries, they have like, like a crate of pills, basically. And the hospital itself does the bottling. Yeah. Yeah. So there's that aspect as well. So I'd say those are the two main aspects. And of course, it ties into other systems, but, uh, you know, within the EMR. But yeah, that's like the, the main parts of it. And also, I should add, well, there isn't actually any Python in the, like, my work. This Python is like Python usage is entirely, you know, when I'm like, sort of practicing for problems or for my own interest. Yeah. So I work we exclusively use that proprietary language for the back end, and like JavaScript for a front end. So there's actually no Python there. But yeah, cool.

Quantum Cheetah: Okay. Gotcha. Thanks. It's good that you can clarify that I'll clean that up. Yes, with being with being clear about that. That's cool. Sounds really interesting. Like, you know, I think we could probably spend a whole hour I'd be really curious. Yeah, for sure. But we should swing it around. And yeah, get into some of the problems. So just by way of a quick introduction for myself, I'm a full stack developer, I started out as I mentioned, well, back back when the first project I had out of university was more in the consulting space, like technology consulting and, and strategy, which is way away from well, quite some ways away from, you know, software engineering and programming. But it happened to be that I was working on an IT strategy for a technology strategy for the health department, in the state that I happen to come from in Australia. So yeah, that was a that was an interesting first project out of university, looking at things like the EPharma. And yeah, what's like a mas and things like that were just coming onto the scene back then. So that it's kind of a tie in to, to what you've been up to. I spent like five or six years as a consultant. So there wasn't there was a bit of programming in that and but it was more like enterprise stuff. So it was really like big, big business. A lot of back office systems for like fortune 500 companies. So I eventually kind of decided to move into more of a customer consumer web sort of space around about 2011. And I started a startup at that point myself. So that's when I really got back. But back to back to what I'd studied at university and what I was really passionate about when I was younger, which was programming, and, and building software. So I've been been back programming now, full time, pretty much for like, nine, eight or nine years now. Do a lot of Python, full stack, Python, Angular front end, built in JavaScript as well, obviously. And then you kind of like systems and application architecture, systems architecture with restful web service interfaces, and you know, this kind of thing I read quite enjoy putting together software systems like that. So yeah, it's a bit about me. So you know who's on the other side of the call. We want to jump into some programming now. So what we're going to do is, I'm going to, as you probably can imagine, I'll give you some questions I'll give you, I got a few kind of queued up, just to see how we do for time. So try and move through them as quickly as we can. But at the same time, like no rush, let's give it the time to understand the problem, kind of discuss what the potential approaches are. See how you can formulate a solution. Definitely ask any questions that you have clarify things like maybe the inputs, the potential outputs, the expected outputs, edge cases, that sort of stuff. A little bit interesting to cover at some point, in each of these questions, time and space complexity to be go type of evaluation. Yeah, and that's pretty much it, I'm looking at three things like technical skills with a programming language of your choice. We've already talked a bunch about how you know your into Python. But it's not your day to day. So I'll kind of your day to day language. So keep that in mind. Problem Solving ability. So coming up with different solutions, evaluating which is going to be most applicable to use, which is going to be most suitable to use, given the time we have available, and that sort of thing. And then thirdly, is your kind of communications skills and communication style. So how easy is it to follow your ideas? How clearly are you articulating the solution that you're coming up with and kind of the approach that you're taking as well. So to do so good. So I'm going to just basically set up a little multi line, comment at the top here, on line one. And I'll paste the problem in have a read of it. And then let me know. And I'll switch to much more of a watch and observe mode. So I'll try and shut up a little bit more and let you do your thing. But I'll jump in, if anything interesting pops up, or if I see something that's worth talking about as well.

The Incredible Croc: So this last part, uses strings, arrays or other data types to store the input. What does that just mean? Like we don't want to, like, you know, working with strings in Python is kind of weird, because if you tried to like, modify a string, it'll create a copy of it. So that's gonna take a hit with the, the space complexity, so like, for example, my original idea is to just you know, iterate over string, sorry, initialize an empty list, iterate over a string, and then add elements to list. If zero. Add five instead. So this is not allowed, right? Because we're using a empty list. Yeah. Okay, so. Okay, so use the strings to store the digits is not allowed. So what else? What else?

Quantum Cheetah: Yeah. The input is going to be an int. We'd prefer not to convert it to a string. So like you described, the trivial solution that just just convert it to a cast and type convert it to a string and then iterate over each character or each digit. But we want to see if we can come up with a better setup than that.

The Incredible Croc: Yeah, I see. Yeah, that's cool.

Quantum Cheetah: Yeah, of course, like, you know, working variables are fine. So if you you know, if you need to use other integers and so on, that's totally fine. But yeah, let's see if we can come up with a way that doesn't rely on using arrays or lists, I should say. And other types.

The Incredible Croc: Yeah. Yeah. So I think it's sort of the same idea, except obviously are the answer we have is now an int. So I think all initialize the answer to be a zero and then. So let's let's just start off with some inputs here. And so given the interest input, so I'm assuming n can also be a negative integer.

Quantum Cheetah: Yep, let's keep that. Let's keep that in mind.

The Incredible Croc: Yeah, right. Yeah. So, so the I guess the idea is that so we start off with. So we can change that really easily. Since the sine doesn't matter, we could always just for now, assume that we're working with a positive int, you know, we can just put the sign back at the end. So let's say our initial is zero. So if we basically want to do the same thing we sort of want to our, my strategy is we sort of want to take the last digit of n, and move it into this answer. And then at the same time, we'll sort of chop off that last digit of n. And just keep doing so while we're building up this answer. So we want to get the last digit of n. So that's just so we can do remainder is equal to n percent 10, this will give the last digit and then we want to do. So I think we can actually do like nr is equal to this is just, I'm just coding a little bit. But also, if there is pseudocode, I'll just write it out. So this will make n into this new remainder with the remainder lopped off, and R will be the remainder. So we will then multiply the answer by 10 to shift over a space for this digit that we're adding on. And then we'll also add in this remainder, so this point, answer will contain this last digit, and R will have its last digit, lopped off. So when we go again, we will start to keep going. And as long as n is not zero says for assuming it's positive. So zero, then it has an R. So there's an issue here with how we're putting in the... So we're putting the last digit, so this will actually give us a reversed version. Let me think so. This, it gets the last digit, then we'll put it at the end. But we actually want to... sorry, this might be a little nasty way of doing it, but we'll have sort of like, exponent variable as well, to keep track of which power of 10 we're going. So because actually, our answer should be we should be adding our times 10 to some exponents. And our answer should be answer answer plus r times some exponent. Right? So I think actually, this will be fine. So they're so zero exponent is equal to zero. I don't worry, I will increment the exponent. I'm actually writing this now. So answer plus equal to... So first of all, we do want exponent to be zero. I forgot to deal with the sign. So we can do sign equals one is greater than zero. Negative one. It's just telling me it's used, so sometimes answer. So it's zero. We don't really care if the sign is negative one, that's fine. So we could try to at this point, I think this is looking okay. I mean, if there was a little bit more time, I probably would work out, you know, a different way to do this exponent so we're not... Yeah, actually, it's kind of it's kind of fine. We should just do this now. Yeah. Okay. There's going to be an off by one error. And with the way I'm currently thinking about it, but yeah, there's no way we need to do like 10 to the same power, we could just store the last power that we're using. But we have to do this. It'll be a one to begin with. And then yeah, I'll just leave it like this for now. I don't think that'll be... that'll affect the runtime too much. But yeah, so I think at this point, yeah, I'll try. Let's just try a quick. I'll do it in line. So for example, with... Oh, I didn't do what the question was asking for. So sorry. So if r equals... if we don't have r equals zero, r equals five.

Quantum Cheetah: Yeah, right. So that's a key part of the problem is to...

The Incredible Croc: Yeah, right. Because that's the number again. Yeah, I got a little little careless there. So yeah, sorry. So if we're trying to say if our given like, 1020, for example. So 1020. So and as defined that, then an R becomes 102, and zero, so R is five, so then answer becomes five, right? R times 10 to the exponent exponent is zero. And then and becomes 102. This becomes 10. Two. So we have to be a little careful here. So answer is. So five plus 10 to the first power now times the remainder, which is two. So that's 25. Yeah, so I guess we could do the rest. But I think this is okay. For now. There is one big issue that I'm running into, which is if n is zero, we need to make sure that we return five instead. So I mean, I guess we could just deal with that separately. Because if there's an x equal to zero, we don't have to really run into any of this code. Yeah, yeah. Okay. There might be some other cases that I'm currently not considering. But yeah, this this exponent thing I should probably deal with, but we could also just run it now. If you'd like.

Quantum Cheetah: Yeah, I think I should be doing. I think that's a good option. I think we've thought through the main, you know, we picked up the obvious qualifications. And there's also enough complexity in the implementation, we should check we've got a working solution to start with. So let's, let's crack on that and then see what we are.

The Incredible Croc: So let me just do to given one. So it looks okay. We got the zero case dealt with, let's just do a negative case. Cuz I'm sure I think Python takes care of the negatives well, but we didn't actually deal with the negatives. So sign equals one is, and then we should make n equal to absolute of n. Sorry, so now the negative cases should be fine. Yeah, okay.

Quantum Cheetah: Are you feeling good about the negatives.

The Incredible Croc: The only bad thing with this exponent, because I guess the current runtime is, like, O(log(n)^2). We have to do this multiplication, but that's kind of easily sorted. Just sort of blinking on the fact that like, making it a little bit, like, a little bit nicer, so...

Quantum Cheetah: Okay, so when you're saying, clear this works, let's let's talk about the runtime complexity, and then we can touch on whether, and how, if and if it makes sense to kind of really drill in on that exponent multiplication. So overall, when looking at it as implemented currently, how would you describe the time and space complexity with sort of big O notation?

The Incredible Croc: Yeah, so. So in terms of n, for each, we're sort of looking at it one digit at a time. So that's a O(log(n)). And but for each while loop, we have this 10 to the exponent, which is also O(log(n)). Because this exponent goes from zero to log n of the number, so it would be log times log of n, I think. Yeah.

Quantum Cheetah: Okay. So we're kind of we must be into the, into the low level implementation of an exponent calculation here. Oh, yeah. Unless I unless I misunderstand kind of way.

The Incredible Croc: Sorry yeah it'll be like O(log(log(n)). For exponent, I think. Because they do that thing fast squaring, right? So like, it'll just be clear. So I think it's like o of log n times log log of n. But I think this can, it's like, we can easily change it so that we're storing the current exponent instead of sorry, storing the current, like this entire thing is the exponent, and then we just multiply by 10. Each time.

Quantum Cheetah: So yeah, I think it's a good point. It's good to think of that. Yeah, I might need to not worry about it.

The Incredible Croc: You know, I think it's Yeah, I think we can just do this and then deal with the exponent at the end, so the next one is correct. I think this will be fine. If we try to run it. Yeah. So now it'll be, it'll be this thing. Yeah, I was basically I just got a little confused, because I was dealing with the exponent here. And then like, we want the exponent to be a one. So we can't Yeah, we just have to multiply by 10. After we do the current computation for the current iteration. So yeah, I think now this will be O(log n) algorithm, because we don't deal with the repeated square repeated exponent anymore.

Quantum Cheetah: Okay. Yeah, I gotta be honest, I think that I would probably expect the... because I can't recall exactly the previous line now that he changed it out. But and I don't think we should spend too much time on it. My only thinking was like, I would hope that that would be optimized by the compiler, like I would, I need to check this to be honest with Python. But my hunch is that a you know, an exponential calculation should be constant time. In which case, how you've assessed it currently, and after the modification, indeed, it's there's going to be a O(log n).

The Incredible Croc: Yeah, I think it just does, like it finds the binary representation, and it just repeated squaring, but I think that I mean, it's log log n is, you know, very negligible. So I think, yeah, it was fairly close both times.

Quantum Cheetah: Yep. Cool. Okay. Yeah, we're on the same page for that, in terms of runtime complexity, space complexity.

The Incredible Croc: I guess also, so if we if we don't care about this... Well, I guess there is sort of space trade off now because we're keeping track of this exponent as a... This exponent is now like an integer with eventually log n places. So we could say the storage is log n. For this, but we did do sort of a trade off... before and we just remembered the exponent as an as an integer, it would have been log log n, since we just keep track of like, because it takes like sort of log n bits to represent an integer with n bits, because you're just looking at the how many spaces it takes. So the exponent is already log n, but represent the exponent you will need log of log n bits. So yeah, the only thing is with this, yeah, this exponent could get... You know, quite large, because it's sort of it has the same amount of space as how long how much this integer actually takes up.

Quantum Cheetah: Right? I see what you're saying. Yeah. Yeah, yeah. Again, I think we're, my, the way, I usually look at that sort of thing. And I think that the more typical way to assess space would be to consider the type. So we're always we're always defining an integer. And an integer is a fixed, you know, it's 32 bits, right? It doesn't matter how many, unless you, like, want to overflow and use a different type, or you sort of say, you know, and we would adapt this algorithm to switch to using a, you know, a double or something like that, or big number, which isn't really a concept in Python.

The Incredible Croc: I definitely see what you're saying. Yeah, I was like Python, because I think they sort of let your integers go as big as you want. So yeah, but no, for sure. I think in like just a regular if we're just talking like, regular big... Yeah, I think this will probably be like just the log n algorithm. And we don't really care the space, I guess we could just take to be, like constant or can be constant.

Quantum Cheetah: Yeah, I think that will be the generalized way to assess this that way. You will also be pretty consistent across languages as well, you know, whether or Java, you need to constant constant space, log n runtime. Nice one. Okay, cool. And we got the different edge cases out, I think that with what we've got here, we've covered all the things that I believe are important to consider. We didn't talk about the possibility of overflows and large numbers like that. But let's let's leave that for now. You definitely got the ones that I was most interested in and paying, keeping an eye out to see whether you spot them. So the zero is an interesting corner case. I think you handle that quite pragmatically. And then also the, the negatives you picked up as well. So good job. That's the first problem out. Yeah, so it's really cool. We can move into a second problem now. Do the same sort of thing. I'll toss a question question into the editor, and then just let you take a look at it and see what we get to.

The Incredible Croc: So you're crossing a river using a series of rocks that stick out from the water. You can move across either one rock at a time. There are rocks, how many distinctive ways and can you cross and will be positive? Okay, so just sounded like you're crossing. So like, the rocks are sort of like just adjacent, right? There's like, you know, in this case would be like five rocks. And we want to wear either jumping out either one or two. Yeah. Can you see my when I highlight? I'm actually not sure. Okay, so we can either jump one two here or jump to two here, right?

Quantum Cheetah: Yeah, I like it even with the red squiggly lines with the sometimes the editor doesn't quite like that. Okay. It's like it's a Red River. We can work with that.

The Incredible Croc: Yeah. So Well, basically. So that I think there's like several ways to deal with this. So first, if we have like, you know, something like, or are just so if we say like, like, J of n is the goals are our equals number of ways to make the jump with r... am I in the comments, right? Oh, no, I think it's because we were already in a comment. That's why the number of ways to jump make the jump with... That we close this, okay. Oh, sorry, because we're closing okay. It should be fine. Yeah, there we go. Make the jump with our rocks, then we can look at like sort of how the path looks like before. So to get to the rth rock, we there.... So to get to rth rock, we either came from r minus rock minus one or minus two. But these you know, this is sort of J of r minus one. And this is J of r minus two. Yeah, so, sort of, we could even do this with like dynamic programming, but we also just realize that we don't need all previous base cases, we only need the last two. So we sort of don't need to keep an array, we can just sort of keep two variables with like the previous two and update them accordingly. So j of r is the number of ways to cross that make the jump with r rocks. So I guess for now, I guess, I have a question with like base case. So if r is zero, you know, it's, I think the convention is that we take that as like one way to make the jump with no rocks, just by not doing anything. But I'm wondering if that convention is okay with you. So like sort of the what we're looking to return as n when we're r is zero, because we could either make that the base case, or we could make r equals one, the base case. Yeah, I think I have like a since I have a slight math background, I usually prefer making zero the base case. So we can just so I think the idea is kind of self explanatory now. So J of r so zero, bar so well. So we have started that because of our zero we want to return. if r is zero, we want to return one. And if r is one, we would also like to return one. Because there's one way to make the jump now if you jump one, so we can just do if r is... I guess like we're not dealing with like negative numbers of rocks right, just as like a side case, are we expect them to deal with that at all?

Quantum Cheetah: No, we got line six says n will be a positive number. So we can easily ignore that. But that's like that's n which is the return the number of returns?

The Incredible Croc: No that's a mistake in the question.

Quantum Cheetah: Okay. Yeah, that's good. Yeah, sorry. Okay, cool. All right. So then, from here, we can have just set up our base cases. So these two numbers will keep track of the last two things. So A and B would be... And then we can do... I need to keep a track of off by one errors. And so I'll just keep a little note of what we're expecting. So r equals two, were expecting two ways. r equals three, we're expecting four ways. Or sorry, three ways. Right? So for r... so A B will now become. So it so A B is like this is sort of j r minus one, j r and we want to plot come from R. And when we want to compute our R, we just add these two. So to facilitate that, a will now become B and B will now become a plus b. So, you know, as we enter, do one iteration, the numbers sort of swap. Yeah, so now I just got to make sure that the off by one error doesn't mess it up for us. So if, let's say R is equal to one, then we also have already used to go to one, we already deal with it here. So let's say R is equal to two. Then after the first iteration, we get one, two, and then the second iteration we get two three. So if r is equal to two, the answer should be two. So we just return A here, so I think that's fine. So I think this should do it. So if r is equal to two... I only did it once I think so... Initially, it's one one, and after the first one, it becomes one, two, then after the third one becomes two, three, so we're returning this... So yeah, I think that should be fine. So it could give this a run I think. I'm not sure if I see. So I guess like, you know, it's hard to tell if it's really working. You know?

The Incredible Croc: I got a couple of answers here.

Quantum Cheetah: Yeah. So I'll do 10. I'm assuming your values go up there.

The Incredible Croc: I only got to nine, hold up, hold up, hold up.

Quantum Cheetah: Okay. All right. Well, I guess we could just add the previous two. Yeah, that's true. We can Yeah. So I, I will say here that, since I do a lot of math problems in the background, or like, out of my interest, this is like the Fibonacci sequence. It's sort of like, you know, it's like a linear recurrence. So actually, there's also a log n time algorithm to compute this. And the way we do that is we sort of compute its characteristic matrix, which in this case, I think, is 1101, I want to say, and this just comes from like, it's like defined in terms of what because like, you can sort of write this as n equals minus one, two, so this like matrix is defined in terms of the initial conditions and the like, it's these coefficients that sort of are hidden in this case, because they're next to, they're just one. But yeah, you can like take this to the nth power and just read off a term from the matrix to get your current one and matrix exponentiation you can do with the same technique as just regular exponentiation in O(log n). So there's like a O(log (n * k^2) algorithm, where k is sort of the number of terms in your like, you know, if this was also dependent on like, f of n minus 3, k would be three here. But there is a well, I guess this power is also how fast you can multiply matrices, which is, you know, who knows what they got that down to? But yeah, there's like, this matrix, this algorithm as well, which I didn't think we had enough time for. But this is like a fast linear, constant space way of computing Fibonacci numbers.

The Incredible Croc: Yep. So we got linear. Like you said, linear time, constant space complexity for the function J, your, your current implementer. Yeah. Yeah. Yep. Cool. That works. At least I can see the the the base algorithm there. I want to check if you take one more look at the question is spot any kind of edge to this that we need to address?

Quantum Cheetah: Ah, yeah, I guess my... Okay, my R value is kind of weird, right? Is that because like, I guess, like r equals... So you can either one... So like, I guess, like r equals one. Like, are we doing this as like you're at land, there's a rock and there's a land. So this would correspond to the r equals one case. And you know, this would actually return like n equals two, because you can go from land to rock and one hop and the rock to land your first way and then land to land in one hop. So this is so r equals one should actually return two is that is that what you sort of had in mind?

The Incredible Croc: Yeah, that's what I'm looking for. Yeah, exactly. That's a you know, that's a subtlety, you're the requirement versus the canonical, like, you know, yeah, right. Right. To the canonical problem, a little bit. Yeah. So it's like a, it's a, I guess, he described it as kind of an off by one error, even though the output will not be off by one. It's an iteration of one. We're off by we need to iterate one more time. Right. And then handle a case based slightly differently as well.

Quantum Cheetah: Yeah. Yeah. So let me just make sure so if r is equal to one, we do this once. Well, I guess we could... Should we do this all once? This will become one to do at once. I guess we're just returning here. I think that does it. I could also change the area. There's like a million I could have made this a zero and then yeah, there's like, I feel like a lot of ways to do it.

The Incredible Croc: Yeah, yeah, that's okay. As long as we're clear on what the...

Quantum Cheetah: Yeah, yeah, that was I should Yeah. So yeah, now this should return the last value. I think I commented out. Yeah. But okay. So I'm guessing... Yeah, this will return like. Yeah. Yeah. Makes sense. Yeah.

The Incredible Croc: Cool. Nice, one. So that's a good one, that's a it's an interesting kind of thing to keep in mind, you know that you've got the you've clearly got the canonical kind of solution, the problems, you know, a Fibonacci based kind of dynamic programming problem. But then there's some twist in the way the problem is stated that you want to make sure you're paying attention to and ideally catch first time around. So good job getting the solution out, and definitely clear explanation of the concept that we're working with there. And it was pretty cool for the for the bonus points, having the the mathematical kind of proof progression, to work with the Fibonacci type sequence. So that's our second problem solved. I've got a third problem up here, which we've got probably like 10 minutes now. So we may or may not get it. Yeah, we can try. This problem also has some more interesting kind of concepts to discuss as well. So we might run a little bit of code, we might like to talk a little bit more in terms of conceptually how to approach it, and what are the trade offs to some different solutions. So I want to give you that kind of cue. And propose that upfront that like when, when I when you see this problem, let's, let's kind of try and articulate you know, one or two or three, maybe different ways to attack it. And then let's really focus on the time and space complexity of the different possible solutions, I think you're probably going to get the we'll just start with one. Obviously, that's, that's the ideal situation, we get one way to do it. Hopefully, pretty quickly, you know, maybe one or two or three different options will come out. And then we'll look at the time and space complexity and figure out what will be the best way to go forward, if we would actually implement it. So Sound good?

Quantum Cheetah: Yep. Sounds cool.

The Incredible Croc: If I got it on my clipboard correctly, yeah. So you got to got a third problem there up at the top.

Quantum Cheetah: Right. All right. Write an efficient program for printing, k largest element in array are just elements are returned in order. largest to smallest. Right. Okay. So just the first solution that comes to mind with so we could use like, quicksort on this on this. So I guess the first question is, like, do we care if the array is sort of you? If we mess with the order of the array?

The Incredible Croc: No, we can, we can mutate the input?

Quantum Cheetah: Way number one is just like run a n log n in place sorts. Return last k elements. So this has runtime O(n log n). And space of O(C). Yeah, so you know, not too bad, I guess. But this, the runtime can get better? I think. So yeah, this one is so you know, sort of really easy to implement. Yeah, I mean, you don't really have to write a lot of code unless you had to write the story yourself. But you know, Python has a fast in place sort. So that's not bad. And then to get a faster runtime, given an array. You're asked for the largest three elements. So we could sort of use like, I think like a heap which sort of maintains the... The sort of... Yeah, I'm trying to think of the... so if we insert the elements one at a time. Yeah, I'm trying to think of like some data structure that, you know, sort of maintains the list in sort of like, like a sorted order.

The Incredible Croc: Yeah. So, as you're inserting them.

Quantum Cheetah: So like, maybe it just, yeah, cuz I, I'm thinking like, you know, obviously, like, there doesn't exist, something that a data structure that as you put in the elements, it sorts them for you in faster than n log n time. Because otherwise, we would just be using that sorting algorithm. Is that what I'm thinking? Like, maybe there's like, I think like, he like there's, I think it's heaps, like maintain the maximum. But as you start with the drawing numbers, it does like a login shift to fix it for you.

The Incredible Croc: If you want to maintain that he there's that maintenance.

Quantum Cheetah: Right. So yeah, so I guess for if we, we use a heap, I think it's like, runtime is, like a O(k log n), I guess? Which is a lot better, unless you're trying to pop out a large number of maxes, you know, after a certain point? I'm sure quicksort is just a lot better, because it has better constants that are constants as well. Yeah, so I guess these are the two main strategies. I don't think we can... I think we can turn the original array into a heap, right? So it is just constant additional space? I don't, because there's the you know, the way to represent like a flattened heap is sort of like a binary tree, right? And you could flatten it and you know, just mutate the original array to look like it. So I don't think we need constant space. But yeah, if we did do that, then it'll be you know, we have to obviously commit the entire array into memory again. But I think like...

The Incredible Croc: Yeah, I like the two I like the two streams, I think, then what can get interesting is to just clarify what we're doing with the heap. So just talk me through, you know, like the next layer of detail here, we sort of heap are we working with? And how would we walk through the solution using a heap? Because I think there's some details in there that might be pertinent to deciding whether there's the first option or whether they like it, I think there's some other ideas that can spawn off from using a heap depending on which approach you go in. So talk me through it, how are you going to set it up? And how are we going to implement this using a heap?

Quantum Cheetah: Yeah, so I was thinking, I was thinking.

The Incredible Croc: So let's start simple questions, start with a guess. And then this will help to probably like figure out what next? Do we do we heapify the input array of length n? Or do we start with an empty heap, and then start iterating over the input array, and insert one by one? Like, that's kind of level of detail, I want to get to to, to then see how that will, that will shake out this heap based solution.

Quantum Cheetah: Right. So I guess, like if we heap the entire thing that is like O(n log n) process, right? Because we're putting in n elements. So if we're doing them one at a time.

The Incredible Croc: So yeah, so I wanted to kind of just, like be explicit about that. Like, you've definitely pointed out that there's some sort of O(k log n) thing happening here. But so what is k how are we going to, how are we going to set this up to get to O(k log n) then what would be the be the order of, you know, processing to do that upfront?

Quantum Cheetah: Right. So let's see. So, we have so we start. So we, we keep going for. So, for doing them. Yeah. So this O(k log n) now, so yeah, I guess if we do them one by one we sort of don't have a good idea of, you know, when if we can stop until we we've like put in the last element, you know, because the last element could be like the largest. So I'm wondering, is it also O(n log n) for this, where if I'm just not seeing something, maybe we don't have to? Yeah, I'm trying to think is like, I don't quite remember, it's, if we like heapify, the entire thing, it's in O(n log n). But we also don't need the entire, we sort of want like some of like the work to be done when we're sort of extracting each element, right? Instead of doing all the work of the sorting at the like the front, because there are possibly a lot of values that we're sorting, but we're wasting time as we'll never actually get to them.

The Incredible Croc: So you're kind of right on the cusp of the solution here. And I think it's more than the kind of time that we have left, and you're feeling the time pressure that's probably kind of holding this up, blocking you a little bit here. So I think I think we should, you know, and I think you did a good job of like, take the concept and intuition for where the solution is, I can tell which got that. And then like, you know, I drilled in on this, because I think we could say, you know, I can trust that you would get a solution out of this pretty quickly. But then that's also what like, like to really test you and to, you know, to be able to say, yeah, we've solved this problem, you know, I want you to be able to describe at that lip next level of detail, how is it actually going to play out? And I know that, you know, I got a good sense that you're right there. It's just, it's just a timing factor here that's going to prevent us from solving this. So I think we should just kind of like park it here. And I think if you spend an hour like 15 or 20 minutes on this, you'll you'll have it out no problem at all. And you've you know, you'll have a good sense for the the alternatives. I'll loop back, and maybe give you a few more pointers on this specific problem right at the very end. But for now, I just wanted to give some high level feedback, and then let you ask any questions as well. Like, overall, yeah, really nicely done. Your solutions came out real quick. You were kind of clear in the code that you wrote. Quite clear in the explanations as well. I think it was interesting... My observation was with the first problem. It was relatively novel, and new to you... You relied upon, you know, a really solid foundation in, you know, math, and then just being able to apply some mathematical techniques in to some algorithmic solutions into some problem solving, which is cool. I think I got the impression that dynamic programming solution, or problem was one that you've practiced and sort of seen before. Right, I get that impression, because you definitely had the canonical approach down, you know, you'd send the the connection to the Fibonacci sequence, it's well documented in, you know, the textbooks and in the courses, and that was interesting, that little nuance to the question that the twist in the question, you know, you picked it up pretty quickly. But from a practical point of view, I, you know, I'd encourage you to just kind of take a moment to write...

Quantum Cheetah: Yeah, I wasn't sure. Yeah. I definitely just sort of rushed in with the algorithm.

The Incredible Croc: But yeah, yeah. So don't blow by those kind of things. When when you see that a problem is a slam dunk. That's, you know, like, that's the thing that kind of pulls up, hit pause a little bit upon. And then with this problem, again, you know, you've demonstrated at a conceptual level, we're really kind of good level understanding of abstract data types. Sorting, you know, the fact that sorting is usually the first thing to pull out of the toolbox to solve a problem that relies on some sort of ordered result. So that's really good from a fundamental sort of level. Problem Solving looks really good. The code that you wrote was, yeah, it was it was nice. It was interesting, you know, you picked up on the divmod, built in function, which not even like experienced Python developers don't always know that that exists. I think, like, I'll probably ask this question, maybe 25 30 times over the last 12 months. And I think only like two or three people, like maybe 20 people, maybe two thirds or three quarters of people get this solution out pretty easily. And but yeah, like only maybe like 5% of people who solve the problem will use divmod. So clearly, you've kind of studied parts of the API, even though you're not using Python day to day. And then like, on the flip side, when it comes to the, you know, just kind of readability of the code. And this is not the highest priority for these sorts of interviews and stuff like that, but and I know you don't program Python daily. So there's some sort of like, coding style, Pep8 style guide type things that you're a little bit away from. So you know, if that's not a huge issue, but if you you know, if you're looking to really impress an interviewer, and you know, that they're a Python shop, as opposed to, like, you know, a Fang big four where you don't know, you know, the language isn't at all important. You may want to spend a little bit of time and give that maybe a fraction more attention, like you really know it is a Python gig that you're going for, again, that's going to depend on who you're interviewing with and what their priorities are. But yeah, like the snake case, kind of function name and a little bit of the use of whitespace. In an ideal world, you could you could tweak that up and improve just ever so slightly in that area. Communication was totally fine as well. So you know, you're very clear in your explanations. Particularly. Yeah, where you had your way, you had a good grasp of some of the solutions, and the approaches that you wanted to talk through. Yeah, I think, high level as well. Even early on, you know, you were pushing that pretty good pace. I felt a little bit like we were rushing things a little bit.

Quantum Cheetah: So in some earlier interviews, I definitely noticed there was like a time crunch towards the end. So I've been, you know, trying to adapt to things as we as I've been doing them, so I figured, you know, like a little bit better at least. Yeah, because I feel like, especially with this first problem. A lot of this, like, early logic is sort of not, you know, just, you know, thrown in as I, as I saw them, which is not a great way to, but yeah, one of my other interviews, I just straight up missed some of those cases. So I figured, you know, it was at least better to sort of go over them quickly, and just throw them in as rather than just not just Yeah, not mentioning them at all. Yeah, for sure.

The Incredible Croc: Yeah. No, I think that's, that's spot on. So you want to find those corner cases, you want to find those edge cases. And I think you did a good job of like, identifying that they're calling him out. Taking a note for yourself, come back to them. Like I think you mentioned, though he did is a great way to do it. I think most specifically, we got a little bit caught up on like, you know, should I be really should you be refactoring out that exponent call? And to me that was like less relevant, less important, we should try to get the solution coded and run it. Well, you know, I think you did a great job of walking the code, putting a few example solutions through or example inputs through. The walking code was great. You then kind of then go a little bit sidetracked into like, can we improve it immediately before we'd seen the result pass the test cases. That's the that's what would be the step to make sure you don't miss that. And then yeah, just to kind of be careful. But in the in the, in the in the attempt to kind of speed and speed things up and push through things. You're not missing things in the requirements like missing details in the requirements. Not like this is pretty this is overall this is like really nitpicky so hopefully, you know, don't take this just trying to help you out. This is not what I would be writing down in the notes after an interview. For instance, I think you did a really good job overall. This is just the sort of things to assimilate takers take a somewhat constructive feedback and you can, you know, take it or leave it in in a lot of ways because I think overall, you're doing a really good job. Yeah, the last point around that the heapsort solution. The little bit of extra detail, I think would help you to maybe clarify your own thoughts quickly, would be to describe are we dealing with a max heap or a min heap, because they're two different things, and they can be used different ways in your solution. And we didn't, you didn't quite articulate that level of detail. Maybe as quickly as you could have, or at least like, if you were thinking at that level, I think that would have helped would help you to get to the next solution. So think like, min heap, max heap. I asked about specifically like that, what what's the next level of detail in solution? And then that's where also started to become a little bit clearer that you would need more time to solve this. And knock out a few more of the details. If we just said, wave their hands and said, Oh, yeah, he's got this, he knows what to do. It's gonna involve a heap, I think there is a little bit more of, you know, you'll need to noodle on this a little bit more and try a few different variations on what you're going for. But you definitely go down the right track. So that's a positive thing. So there's a good stuff to take away from that as well. Yeah. So think about like, the type of heaps that can be used, can be good to understand how the heap API works in Python, as well. And some of these adts, python is a great language, because it's got some built ins. And they have different languages have different, they expose different functions. For the most part, they are all fairly similar in terms of runtime, and you know, space performance and things like that. But you do get a few little some languages have some extra syntax candy, and some in terms of making it more easy to work with the implementation. And others have some shortcuts as well that offer some performance improvements in certain scenarios and certain situations. One of which is quite pertinent to this problem. When you work with Python, specifically, you can kind of there's a push pop operation, which it saves a little bit of time, due to the way that the underlying Python implementation works. So this is a fun one to kind of go away and understand a little bit at a conceptual level. And then this last problem we didn't quite get to, like after this.

Quantum Cheetah: Just make sure, yep, yep.

The Incredible Croc: Hey, I gotta jump out in a moment. But I got time for a question or two. Is there anything on your mind or anything that I can clarify for you?

Quantum Cheetah: Um, no, I think I think it's been really great. Yeah, thank you for you know, even staying a little bit later to give all the like some of the feedback. But yeah, I think really great. I really enjoyed the interview. So yeah, I think there's nothing more on my end.

The Incredible Croc: Okay, no trouble at all. Appreciate your feedback there. And yeah, I appreciate that. You got something out of it. So that's good. That's what I aim for. Yeah, we can leave it here. I want to wish you all the best for the interviewing, going for your programming career and stuff like that. And otherwise, have a great day. Bye for now.

Quantum Cheetah: Bye.