Existential Crumpet: Hello? Anyone there?
Chaotic Pizza: Hi. Hello.
Existential Crumpet: Hi. How are you?
Chaotic Pizza: Good, good. How are you?
Existential Crumpet: I'm good. Well, a little hungry. I should order some food.
Chaotic Pizza: Yeah, sorry. Are you also in the in this time zone?
Existential Crumpet: I'm on the west coast.
Chaotic Pizza: Yeah, yeah. So, eight o'clock.
Existential Crumpet: How about you?
Chaotic Pizza: Yeah, me too. Yeah. I'm in Seattle.
Existential Crumpet: Did we do a practice interview together, earlier? Have you been doing these for a little while?
Chaotic Pizza: No, no, no. Just my second time.
Existential Crumpet: Your second time? Okay. Cool. So let me start off by telling you a little bit about me, my background as an engineer. And I think it's just standard practice interviews for me, as the interviewer, to ask you about your background. So if you feel comfortable talking about that, practicing your schpeel. I'll ask you about that. And then maybe we can figure out something you'd like to work on. We can work through a problem together.
Chaotic Pizza: Okay.
Existential Crumpet: Cool. So, I am a backend applications engineer at LinkedIn. And I've been in the industry for like, three years, relatively young. And I work mostly in Java and Scala, on backend systems and services, like web services, as well as Hadoop jobs, usually running on Spark, but occasionally, things like Scalding or, you know, low level, Hadoop jobs. That's me. What about you?
Existential Crumpet: Oh, okay. So you use Go for the back end, but it's not truly back end?
Existential Crumpet: Cool. Cool. So is there anything you'd like to practice specifically today? What's your given objective? Um, search?
Chaotic Pizza: Yeah. For recently, I don't have any interviews. Actually, I just failed one. But I'm thinking of, you know, doing some improvements there. To hearing some, like feedback from like, from the interviewers to see where I could improve. So yeah.
Existential Crumpet: Yeah, that's what this is really great for. You know, what you wish during the interview is that the interviewer would just break character and help you out and give you the points. Cool. So you work on sort of web software, which uses a lot of these data structures. So since you don't seem to have, do you have any kind of like preference, if I had to go through, sort of, categories? Like do you want a more algorithmic question or maybe more data structure oriented? Or it's okay, if you don't have any preference also.
Chaotic Pizza: Yeah, I don't have any preference.
Existential Crumpet: Cool. So let's say I give you a list of numbers. So let's start with five, three, two, three, three, and I also give you a target number. I would like you to write a function that will return the pair with given difference, provided the best and the difference. And so in this example, the solution to this particular one would be actually... Okay, yeah. So the solution here is 80 and 2, because 80 minus 2 is 78. And, in this particular problem, I think there's an emphasis on runtime. So keep that in mind as you try to think of the solution.
Chaotic Pizza: Okay, okay. So if there are multiple answers, is it okay to like, you just need one?
Existential Crumpet: If there's multiple answers, you mean... Oh, yeah. It's fine just to list the first one that you come across.
Chaotic Pizza: Okay. Yeah, yeah. I guess one solution would be to really, you know, calculate each for each pair and calculate the difference until you find one that match. That means, you know, you get a number and you try to... you basically want to loop through all the pairs. Yeah. Okay, so that's, that's O(n^2), if you wanted it time wise.
Existential Crumpet: Okay. Can we do any better?
Chaotic Pizza: So basically, you could, okay. If you use, like, a stack or map, you know, basically to record each one you go through. And maybe you can check along the way if there's something. Maybe I can write it. For example, you want to 78, you want to see the 78 When you hit five, you can check if I have say 83. So it's minus. So do I have 83 or not? If I have a 83 already, I could just you know, return the, the pair. And if I don't know, I will just record five. And I go to the next one. I say I made 20. And I will check if I have 98. For example, if I have 98, I could just return the pair. If I don't I just record 20 and go to the next one. So I think when I go to the 80, I need to check if I got two, I already got two here. So I just returned 80 and 2.
Existential Crumpet: Cool. What happens if... Yeah, that seems fine. I think there's one specific technicality to that. I think I'll leave it to you. Let's see if you anticipate it in your code.
Chaotic Pizza: Okay, I would just say, oh, maybe start to write down. You know, generally there might be bugs, but we can we can fix it maybe later on. It's not so obvious. So I could start writing this algorithm. Like it's a... Yeah, we have something like, yeah, like this. Um, so basically, See? Right? Maybe I can run it.
Existential Crumpet: Yeah. Show me how it works.
Chaotic Pizza: I'll use this list. See? And maybe not if diff plus E, I still have some cases I should find. Okay. Yeah. But it might be E minus. No, no, it might just be minus E. Yeah. But in this case, the diff will be.... Yeah, if the diff is larger than... So essentially, I needed to have absolute value, some something like absolute value. Because this one should give me the answer. Right? Because the when the E is 80, last two.
Existential Crumpet: I'm not as familiar with the ES6 API.
Chaotic Pizza: Yeah, yeah, maybe I shouldn't do something like forEach. Yeah, yeah.
Existential Crumpet: Yeah. And so for these purposes, personally, I don't care. And I don't think usually an interviewer won't care too much. As long as your algorithm is right, I mean, sometimes they're looking, "Okay, do you know ES6?" So while you might want to... Yeah, I mean, it's usually nice to to be conservative with your syntax.
Chaotic Pizza: Yeah. Because the for each syntax, we're basically taking a function for every element is like transforming every element, but it won't return, the return won't be returned to the outside function, it's just returns inside the function that gets assigned to each element. So so it's not right. Just like that. There we go. Yeah, so yeah, definitely.
Existential Crumpet: Nice. Okay. So usually, I give that one and people either do pretty fast or it takes the whole time. So when you It took us only about 20 minutes, which is pretty fast. And you basically have the optimal solution here. Which is great. Because I think the cleverness of doing the two checks. So you say diff + E is our number. Or if E - diff is our number. Yeah, that saves us a loop through the list. So we don't have to go through it twice. We can just go through it once. Yeah. Because in either case, it's its O(1), right?
Chaotic Pizza: Yeah. Okay.
Existential Crumpet: So let's give you another one. If you're up for it. All right, here's one. This one's fun. We're gonna try to get this one done in time. So this one's kind of similar. It also involves summing numbers. And with this one, our goal is to given an array and also given a target, our objective is to figure out the indices of the sub array that when the values of that sub array are summed, equal the provided target number right here. So in this case, 3, 15 is the first zero through four. Okay.
Chaotic Pizza: So we're still looking for just the one answer.
Existential Crumpet: Yeah, it really doesn't matter which solution you provide. Although that's a good question to ask.
Chaotic Pizza: Yeah. Like, one obvious solution will be you know, you just I think calculate all the subarray sums. And check along that way if you see one, if you got one, you just return. So calculate the array sum is like, you can first add them up like, so you have a new array, that's the sum of from zero to this index i. And you can do the minus when you go through the array. So for example, you have this one, maybe one plus two will be three, one plus two plus three will be six, an array like this can. So your sum of this subarray from the beginning. And you can you know, you can minus any two of them. You move through this array. So that will also take O(n^2) time.
Existential Crumpet: What I want to make sure I make clear is that you could encounter, I don't know if I said this, you could encounter a case that looks like this.
Existential Crumpet: Okay what happens... Did you find something?
Chaotic Pizza: No, no I think this seems to have a bug in the code. But yeah, yeah, go ahead.
Existential Crumpet: Well, I think I found the same bug, so I'll just let you work through it.
Chaotic Pizza: Okay, okay. I see, so there's one edge case.
Existential Crumpet: So, describe to me your sort of current thought process on this algorithm.
Chaotic Pizza: Yeah. Yeah, it's still has some bug, I'm afraid. But to the biggest, I'm thinking about you know, you can have this, you can accumulate a sum. So from the beginning, and the sub array sum is really just the, you know, you subtract two subarray sum, right? So you got, you know, from the beginning, so you got the difference between them. So that's a subarray sum. So since you're doing this kind of difference or subtraction, it's sort of similar, like the first problem where you want to find to a pair of integers that which has the difference.
Existential Crumpet: Can you explain the difference to me a little bit more? So where's the difference come in to the picture?
Chaotic Pizza: You mean, the difference between the two problems?
Existential Crumpet: Oh, no, not between the two problems, but I guess what I mean, you started, I think you talked about that difference, like subtraction.
Chaotic Pizza: Okay. It's like, the subarray sum is, I think the sum from zero to i. So, basically, sum from i to j is equal to sum from zero to j, minus from zero to i. So yeah, that's the difference I am talking about. So it's, it's a basically a difference between two sub arrays from the beginning. Right, so if you consider the each sum from the beginning, you know, as an element in array, you basically you have the problem. Similar to problem one, so yes. So I'm thinking using a set to do it as well. Or map.
Existential Crumpet: No, I see. Yeah, just to sort of keep you on course, here since we're a little tight on time. I think that might be a bit of a red herring. Because you know what... why don't see if this works. I don't want to stop you.
Chaotic Pizza: Yeah.
Existential Crumpet: Okay, I would try to keep the two problems separate. That would just be my recommendation here. And let me know if you'd like a hint. I mean, I'm trying to make this as realistic as possible.
Chaotic Pizza: Gotcha. Yeah, yeah.
Existential Crumpet: So can you explain to me why you think calculating sum i through some j is easier done by this different approach versus just calculating out some i through sum j when you need to?
Chaotic Pizza: I guess it's just a one way to do it, it doesn't, it's not necessarily the better way to do it. It's just because I, when I saw the, you know, sub array sum, I would think of a minus, you know, the difference between two sum. So that's just how I think of it. So in this case, if you really want to calculate the sum of all the sub array, that's really, that's not very efficient, I guess. Yeah. So do you understand this function I wrote? Like, roughly?
Existential Crumpet: Yeah. I didn't realize that this was a this was a prepared solution. I thought you were still working on the problem.
Chaotic Pizza: Oh, no, I'm trying to figure out what's the bug, where's the bug. But yes, it is. I think this will work. Yeah, but it seems it has some. I mean, you should go to the details to try some example to to fix this.
Existential Crumpet: Yeah, so let's check a specific case. Let's say I give you 15 right here? Can you walk me through the test case on line 18?
Chaotic Pizza: Okay, okay. So I think maybe we can try an easier example. Maybe we can try maybe, like, if you want to find five in this, in this case, you will have to keep the sum of one. And and you try to find maybe you try to find the four but you didn't find, you know, you couldn't find four. So then you go to the next one you are you added up this. So now your current sum is is three. So you try to like find the two, but yeah, you still can. So now you've had up to add up to six. Right? So six. So now you have the sum of six, now your target is five. So yeah, I guess that might be the problem. So, you want to find in this case it would be minus one. So you fail. So you, so you need to try the other way around. So, maybe you need to check if you can find like one, because six minus five, you also find one, and now you have one here. So now you can just basically use six minus one. So that gives you five, which means your sub array is from the first index to the second index to the third index. So that will give you five, because the six here minus one is is equal to your target five, because you will have already recorded this one in your map or set, you can easily find it like so you don't need to do the find multiple times, you just do it once. And you use a map or set to record the sum so far. And you can find the answer. So I think the algorithm function I wrote is still problematic because I only check the target minus sum. But there will be cases where the sum is actually larger than the target. So it's absolute value. So I may need to check the sum minus target as well. And let me try if I can. Let me try if I can. I'll put something. Yeah, so I guess I will plus one here. Yeah. Oh no, no plus one here. Yeah, that's why. Yeah. So yeah, yeah. It's because this example is 1 2 3. So 2 3 7. Yeah, yeah.
Existential Crumpet: Okay. I think this looks pretty good to me.
Chaotic Pizza: Yeah, sorry. This took a lot of time to figure this out.
Existential Crumpet: No, it's fine. I mean, we we managed to fit two in one interview, so that's great. And you move through these both pretty fast and it's a good efficiency. So yeah, yeah. I have to go pretty soon because I have another interview at nine and I need to eat a little bit. Do you have any questions for me? On feedback or anything like that?
Chaotic Pizza: I haven't interviewed anyone. So I cannot really, I think you're doing great. So I didn't know how to, you know, I don't really have much feedback to you. Is just, so I actually have one question. So do you do like interviewing for LinkedIn? Like, in the past?
Existential Crumpet: Yes.
Chaotic Pizza: And what is the difficulty? Is it sort of matched to what we did?
Existential Crumpet: I think you would be happy to hear that the answer is yes. Yeah. These are both questions definitely on par with what'd we ask, and the level of difficulty in terms of the amount of help I gave you, for this interview, you would definitely pass LinkedIn. So, yeah, don't let it go your head, but that's a good thing.
Chaotic Pizza: Yeah, sure.
Existential Crumpet: Yeah. So I think just one last piece of feedback would be I think, if you find yourself in a place where like, maybe you get stuck, or you hit an edge case, it can be helpful for the interviewer. What you ideally want to do is you want to make sure that the interviewer is always sort of aware of your mode, if that makes sense. Like, is your mood is this problem? Or is my mode, okay, and coding up this problem? Am I thinking of the solution, or if you run into a thing, and you're like, oh, like, I have to backtrack and think about this edge case, then make sure you communicate. This is the edge case I'm thinking about, and it breaks my solution because of this. And now I'm going to try to think of a new solution.
Chaotic Pizza: So you actually get confused along, like, along the way, right? Like, for some time, I'm not sure what I'm doing.
Existential Crumpet: Yeah, and some of that, you know, is my fault because I need to eat but some of it, I think, in terms of, you know, trying to hack the interview process in terms of like, trying to make things go as well as you possibly can. Anything you can do to make the process easier for the interviewer is sort of points in the right column. So.
Chaotic Pizza: Okay, okay. Good. Great. Yeah, I'll definitely improve on that. Try to make that. Because I get really nervous when I am stuck, basically on some case.
Existential Crumpet: Yeah, it's actually it's very normal to get stuck. A lot of people who interview think that if they get stuck, they are, they are already in trouble. But typically, what we try to do is we try to get problems that don't have super clear answers that you can just think of right away. Usually, there's one or two tricks involved. And so the most important thing to think about is keeping, I think like keeping your head on straight, if that kind of thing happens in like backtracking.
Chaotic Pizza: Okay. Yeah, sure.
Existential Crumpet: All right. Well, yeah, thanks very much. Let me know. I'm open to sharing my contact information if you want to follow up with any questions or hear about workplace at LinkedIn.
Chaotic Pizza: Oh, sure. Sure. Yeah. That'll be good.
Existential Crumpet: Okay, cool. Thanks very much.
Chaotic Pizza: Yeah, yeah, that thanks for interviewing at such a late time. So and yeah, see ya. Good night.
Existential Crumpet: Good night.