We helped write the sequel to "Cracking the Coding Interview". Read 9 chapters for free

C++ Interview with a FAANG engineer

Watch someone solve the buildings with an ocean view 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

Buildings with an ocean view

Interview question

There are n buildings in a line. You are given an integer array heights of size n that represents the heights of the buildings in the line. The ocean is to the right of the buildings. A building has an ocean view if the building can see the ocean without obstructions. Return a list of indices (0-indexed) of buildings that have an ocean view, sorted in increasing order. (later Example: [1, 0. -2, -1]) Example 1: Input: heights = [4,2,3,1] Output: [0,2,3] Explanation: Building 1 does not have an ocean view because building 2 is taller. Example 2: Input: heights = [4,4,1] Output: [1, 2] [4,3,2,1] [0,1,2,3]

Interview Feedback

Feedback about Digital Fresh (the interviewee)

Advance this person to the next round?

Yes

How were their technical skills?

3/4

How was their problem solving ability?

3/4

What about their communication ability?

4/4

ypo on my side: it's Kadane's algo (not Kanade...!) Thank you for the session today and great to e-meet you. Overall would vote 'yes' with good confidence. For a 'yes' with even more confidence, a few more timed coding rounds / practice would likely do the trick. You demonstrated solid intuition and very good fundamentals. In addition to the feedback in our call: Strengths: - Communication -- positive, affable; seems great to work with -- attentive listener and open to hints while being proactive to find solutions (and persistent) - Time management: -- great job in general on first asking clarifying questions, sharing thought process for solution space, and implementing code -- especially on the first problem - Technical -- very comfortable with arrays -- time and space complexity spot on -- overall looks solid on general c++ Potential areas of improvement - Problem solving -- Second problem with skylines had more components and nuances to it: recommend to walk thru one or two complete examples -- In the examples, articulate more on what your solution should track (e.g. a running sum vs a current max score) --- having a detailed walkthru could lead to good pseudo code -- Clarify what the intended output is --- understanding the definition of (max) "score" in second problem may have led you to a more complete solution - Technical: -- nit: using "&" in method signature -- nit: for reversing an array, you could also use STL's "reverse"; could be preferable to "sort" in first problem -- nit: proactively write down Time and (extra) Space complexity at end of solution -- nit: practice iterating thru hashmaps/dictionaries in c++ -- additional related problems to the skyline exercise below Further suggestions / resources: - https://en.wikipedia.org/wiki/Maximum_subarray_problem - Leetcode: -- https://leetcode.com/problems/maximum-subarray/description/ -- https://leetcode.com/problems/subarray-sum-equals-k/description/ -- https://leetcode.com/problems/maximum-score-of-a-good-subarray/description/ - neetcode.io -- I'm a huge fan of the "150" problems list, esp ahead of interviews: --- especially how the author's video solutions: these are excellent examples of articulating a solution space prior to implementing code - my dedicated coaching link: -- https://start.interviewing.io/dashboard/interviewee/dedicated-coaching?mentor=6446d56fafe02b008d520b74

Feedback about Stochastic Panda (the interviewer)

Would you want to work with this person?

Yes

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

This was a very informative and supportive interview. I appreciate the extra time you gave me at the end to discuss my questions with you. This interview was conducted in a very professional manner. I look forward to potentially working with you further for some mentorship. Have a great rest of your day.

Interview Transcript

Stochastic Panda: So yeah, generally what I would like to do in rounds like this is just make sure we're on the same page regarding goals, some brief intros, then the main thing, so go over that and then with the rest of our time we can do a summary and feedback. So before we go into interest, what I have in front of me is that you may be a candidate with about two or more years of experience and are looking to do a mock coding round for data structures and algorithms. Is that right?

Digital Fresh: Yeah, yeah, exactly.

Stochastic Panda: Great. And is there a target level that you are aiming for?

Digital Fresh: By target level I'm assuming you mean like I am targeting an entry level position.

Stochastic Panda: For example. Yeah. So some Companies like in FAANG, so to speak, have the notion of like, like E3 at Meta or L4 at Amazon, or like L62 for example at Microsoft. Any of those numerical levels at company specific that would be good for us to aim for or just kind of general. Two years of experience.

Digital Fresh: Yeah. So probably I believe E3 is like the intro junior level developer. Right? Like coming out of school or a little bit of experience into like an intro role in the industry. Is that what E3 is?

Stochastic Panda: Yeah, generally speaking, that's right, yes.

Digital Fresh: Yeah. Then, then I am, yeah, I'm looking for like an E3 level. I have two years of experience, but yeah, I'm still looking for like more of an entry level role.

Stochastic Panda: Excellent, excellent. Well, thank you. So let's move on to. Yeah. Oh, right. And one more thing in terms of the goal from the notes I have is that we are doing more of a real life mock interview and not necessarily like a mentorship interview, if that's right.

Digital Fresh: Yeah, yeah, that is correct.

Stochastic Panda: Excellent. All right, so for intro, I guess.

Digital Fresh: One thing real quick. Could I ask questions quickly because we have a little bit of time. What is the mentorship style interview? I saw they offer that and it's something I'm interested. I just wasn't sure what that actually was.

Stochastic Panda: Excellent question. So generally I take mentorship session to mean that for example in DSA there will be a question, but the mentorship comes in with a Few more hints, but definitely more interruptions in saying like okay candidate, we're at minute 10. Usually we want to get to the code by now and you might be slightly stuck. So let me give you some extra hints. And also the universe of extra hints might include toward the end where we say, hey, there's five minutes left, you didn't talk about this or that. So you know, why don't we do that now? So it has or integrates more elements of hints and interruptions that might not be representative of a real coding round, but some candidates find helpful as part of their preparation. Whereas mock there might be, yes, a few times like in a real interview where I provide potential hits, but if structured more as a, as having more resemblance to the real thing of times interviews, which is also helpful for candidates to practice sometimes.

Digital Fresh: Okay, yeah, perfect. I think we'll go with the mock for now and if I get, if I do get like really stuck on somewhere, I'll speak up and let you know and we'll move from there.

Stochastic Panda: Okay, that sounds great. Wonderful. So for intros. So this is an anonymous platform, so feel free to share as much as you like or reticent as much as you like. And why don't we spend a minute or two each just on basic intros. Would you like me to get started or would you like to get started?

Digital Fresh: Sure, I suppose I'll get started. I'll tell you a little bit about myself. So yeah, my name's [REDACTED] and I'm currently a full stack software engineer at a of a startup company called [REDACTED]. It's a really cool company, I really enjoy it. We do fleet diagnostics for trucking companies and like early maintenance reporting within like the commercial trucking industry. And that is like a web app style application and it's kind of a part of my job. The data we work with is we integrate like telematics data and wireless sensor data and preventative maintenance schedules and some more proprietary information into our platform and then we provide that to our customers to use to manage better manage their fleets. So that's kind of a little bit about me and where I'm at and I do have two years of experience doing that and I'm kind of looking to grow in my role to pursue, to pursue more of a larger company with a little bit more structure.

Stochastic Panda: Excellent. Thank you. Yeah. So my name in real life, first name is [REDACTED]. It's got about 10 plus years of industry experience. My specialty is machine learning but my overall tool set, if you will, is engineering, but especially or software engineering is applied to machine learning. And yeah, basically I'm at one of the largest companies in [REDACTED] and before that worked at another pretty large company, [REDACTED], you can probably guess which. And I've been on interviewing IO for some time now, started off practicing, really like it and these days have been focusing more on technical coaching as well as some career coaching. So that is me and I think we're doing pretty well on time. So let's move on to the main thing. So yeah, we'll have basically I have two questions in mind that are a bit general but I think representative of some interviews, let's say at so called things in the past few months. So yeah, let's go ahead and do that. And before we get started, even though this is a mock, usually I do like to mention some of the general rubrics that interviewers look for in these types of rounds. So the first one is clarifying questions, just kind of reminding ourselves that before, you know, jumping into code, it's probably a good idea to make sure you understand the question corner cases that you might think about initially. And then the problem solving is kind of right before articulating or going into the code is articulating how you think about the problem and what a solution might look like. And then third, but also of course is just as important is the implementation. Right. Like the code itself, is it relatively easy to follow and does it, you know, basically solve the problem? Any questions there?

Digital Fresh: No, that makes sense.

Stochastic Panda: Excellent. So we're doing well on time. From the top right of your screen, if you see a little button that says info and the next to it a drop down. Yeah, exactly. All right, C. Fantastic. So yeah, let me put these things up here and we can get started. So I'll go ahead and paste in the question, take some time to read it and we can get started. I'll paste it in starting from line 14 just to have consistency. Or line 16. Yeah.

Digital Fresh: Okay, perfect. So let's see here it looks like we have N buildings. In a line you are given an integer array heights of the size of size N that represents the heights of the building in a line. The ocean is to the right of the buildings. A building has an ocean view. If the building can see the ocean without obstructions. Okay, perfect. Return a list of indices of buildings that have an ocean view sorted in increasing order. Got it. Okay, so I'm just going to go over it in my head real quick again to make sure I fully understand. Okay, so the first thing I'm just going to see I see you have some examples down here. Perfect. So for example, number one, we have an input of heights 4231 and the output is going to be the indices sorted in increasing order. And now is that increasing order, it looks like in terms of their index or increasing order of the. The height of the building. Let's see. I suppose that would be the same exact thing. So per. Yeah, that would be the same thing. Okay. Building one does not have an ocean view because building two is taller. Perfect. Input heights four, four. So first one does not have an ocean view because second one is blocking. Perfect. Ok, so I think I have a pretty good understanding of the problem here. So we're just going to get an input of some buildings, say 4, 3, 2, 1. And if a building, if the building can see the ocean, does not have any buildings to the right that are taller than it, then it has an ocean view and we want to return the indexes of those buildings. So in this case it'd be 0, 1, 2, 3. We have the edge case right here. I'm assuming a building probably can't have a height of zero, though. Suppose it doesn't really matter if we make that assumption because that is still a height. I'm going to hope they don't have any negative heights.

Stochastic Panda: Yeah, let's think about. Yeah, let's think about negative heights briefly and how, just high level, how you might account for them or think of them.

Digital Fresh: Okay. Yeah, so if we want to assume that our buildings can have negative heights, I suppose that's fine. Let's see. I mean, I suppose we could just treat them as any other number. I don't see why that would change much of our algorithm implementation. I'm sure when I get to the implementation though, that might be different, but just at a high level. I can't see why that would affect much. I. Yeah, yeah, I don't see why that would affect much.

Stochastic Panda: Got it. Okay, let's come back to that. And based on your good observation for now, let's assume that all heights are strictly bigger than zero.

Digital Fresh: Gotcha. I just thought of one other thing as well. With negative heights, which I mean, I guess heights zero and negatives, do we assume that those do have an ocean view? Is this like a sea level thing? I know that's kind of silly, but if you're, if you're negative, do you still have an ocean view?

Stochastic Panda: Yeah, so. Exactly. So let's think of a. Let's table this example for now. But we can think of it just for a minute, like if we had an array, let's say maybe building height one and then zero, and then maybe like minus two and minus three. Right. We might want to specify. Okay, well, even better, like minus two. Sorry. So if we look at the value at index three, so the building with height minus two, technically the building to its right has a larger height. Right. Because minus one is what I want to say.

Digital Fresh: Yeah.

Stochastic Panda: Is taller. But from a practical perspective, we might actually say, well, if these things are like underground, then maybe to begin with, buildings with height -2 -1 don't have an ocean view if they're underground. And there's variations on that. But let's come back to that.

Digital Fresh: Okay, so we'll table that from now, but we'll assume that all of our buildings have an ocean view. Maybe we'll even assume they're all above zero. And we'll get into the kind of talking about how we're going to implement this.

Stochastic Panda: Great.

Digital Fresh: So the first thing I'm kind of thinking is that the building. Does it say the building to our far right, or does our building to the left and right both have an ocean view? I guess that's another clarifying question. Building has an ocean view. If the building can see the ocean without obstructions, the ocean is to the right. Okay. So what I'm thinking right now is that our building at the farthest. Right. So that the building at the size of our list minus one, I suppose, always has an ocean view. So we can take that, we can grab that index and store it in like a little index buffer to make sure we keep that. And then we can also store its height and say, like, this is the maximum height we've seen, so everything to the left of it must be taller than this to also have an ocean view. And then as we iterate through, if something is taller, we'll add it to our index list and then also change our max height, so to speak, to that new height and then go through our entire list.

Stochastic Panda: Yeah, that sounds like a good plan.

Digital Fresh: Okay. I'm having trouble thinking of any edge cases we might encounter here, but is it okay if I go ahead and start making some comments and setting up some code to implement this?

Stochastic Panda: Definitely. That sounds like a good idea.

Digital Fresh: Okay, cool. So right off the bat, I was thinking we need some. I'm just going to put some data structures here that we just talked about so we can have an int. I'll call it max height, but this is really the maximum height we've seen so far. Don't need to initialize that yet we also want some vector of integers. And this vector of integers we can call indexes, probably. And I'm going to assume this function that we were talking about is going to return that vector of integers, if that's okay, and then take in vector of integers called building heights. Looks like we're getting a little bit of an error, so I'm going to quickly include vector. Cool. I'm not returning. Okay, cool. So now that we have that, we can kind of create our for loop to iterate through this buildings list. So, and I equals building heights dot size minus one. And then while I is greater than or equal to zero, I plus plus. That is not right. Cool. Now we're going to iterate starting from the far right and go to the first index of buildings. But first what I'm going to do is I'm going to initialize really quick that, that the first max height that we're going to deal with is for building heights, building height size -1. And then we're actually going to start at -2. Actually. Do I want to do that? Yeah, yeah, that's fine. Okay. And we're also going to include indexes, pushback building heights size minus one, which is our last index. I am making the assumption here, however, that we have building heights. So I. Is it safe to assume we'll always have building heights? Because we're always going to. I guess we could return an empty list, so I'll account for that right now.

Stochastic Panda: Sure.

Digital Fresh: Okay, so now we can start iterating through. And so what we said we want to do is we'll look at building heights at our next index and we'll see if that is greater than or equal to our max height. I did not make this an if statement for some reason. Fix that. And if it is, then we set our new max height height to building heights I and we store I in our list indexes. Push back I. Okay. So as I do this, I'm sort of realizing maybe I didn't plan ahead perfectly, that our indexes are going to be backwards. They're not actually going to be in the order we want from our output. An easy way to fix that is after we do this for a loop, we could do do some sort. And I'm assuming our sort would be, you know, in less than O of n, which is kind of what our time complexity is right now. So if you think that's fine, we can just go ahead with that solution. But it is like less efficient than it could be if I wrote my algorithm in A way that sorts the indexes as I put them in.

Stochastic Panda: Yeah, I think your first approach with basically the for loop, so to speak, as is, and then reversing at the end of the for loop is a good approach to this.

Digital Fresh: Yeah. Okay. Okay. So if it's not. If the building height I is not greater than or equal to. No, it needs to be greater than. So if it's equal to or less than, then we simply want to do nothing, I believe. And then, you know, at the end here, we can sort our indexes and return indexes. Still getting mad at me. But let's see. Get to look over my code real quick, make sure I'm not missing any edge cases here over returning. If building size equals zero, an empty list, I guess it doesn't matter right now how big building size is. Should still be fine. Okay. Yeah, I'm pretty happy with this solution here. Do you have any comments on kind of where we're at right now?

Stochastic Panda: I think this is looking good. And yeah. What would you say is the time and space complexity?

Digital Fresh: Gotcha. Yeah. So what we're seeing right here, building heights. We're going through that list one time here. So for every element, we're. We're gonna touch each element once and then we are doing that sort. So it might be kind of like a 2n or whatever sort is here. It might be a log n, but it'll be n log n or 2n, which we can abbreviate to, you know, just sort of an O of N time complexity, I believe.

Stochastic Panda: Mm. All right. Yeah, Time looks good. And sorry, did you mention space?

Digital Fresh: Oh, and yeah, so the space complexity here is going to also be O of N. Because if our. If every building can see the ocean, then that's how much space we're storing up with our indexes vector. And returning.

Stochastic Panda: Yes. Yeah, I would agree there. Okay, great. And all right, I'm happy with that. And yes, you did catch something good. Which is at line 59 should be a strict inequality. Right. Because if we go to example two in example two. Right. Do you recall why the output some on line 32? Why the output is not 01, 2?

Digital Fresh: Yeah, yeah. Because for. There's a building of the same height in front of each other. And so the rightmost building is the one that can see the ocean.

Stochastic Panda: Exactly. Yep. Yeah. And you caught that. Excellent. So let's move on then to one more question and let's see if it's. Okay. I'll paste the question starting on line 75. Here we go. And yeah, Take some time, read it, and then we can get started.

Digital Fresh: Okay, so the skyline of buildings. Each building has an integer height value and the buildings are arranged in a line. Okay. You are given an integer array heights of size n. Each element height I represents the height of the ith building. Okay? So you're given an integer array of heights. Oh, perfect. Okay, so it's very similar to our previous problem. A skyline is valid if it meets the following conditions. The skyline has at least two buildings, okay. And the first building, the first and the last building in the skyline have the same height. Interesting. Okay, perfect. As the city planner, you can demolish any building from the skyline. Okay, interesting. Return the maximum possible score of some valid skyline after you have demolished any buildings. Okay, interesting. So I'm assuming a score would be the largest skyline possible. So if I could set up some examples to make sure I understand the question. If we have the skyline, that's like 4, 3 to 4. This is a valid skyline because 4 and 4 are looking at each other and there are at least, at least two buildings in it. There are four in this case, I believe. Same thing for the example 4 and 4, that's one with at least two. But something like 4 and 3 or simply just 4 would not be valid. Is that correct?

Stochastic Panda: Yes, exactly. And let me put in one more example that could be interesting. So let's suppose we had something like 1, 5, 6, 5 and 5. Yeah. One more example to think about. So let's call this guy example three. And you know, if we said this was the input, roughly speaking, then the output, what would you say should be.

Digital Fresh: Gotcha. So you know what I'm thinking here, because we're specifically talking about skylines, is it would be 2 for the 5 and 5 on the right, however, because that 6 building is taller. So that would kind of obstruct the skyline. But is that correct? Can we assume that it's only the last two fives that go to the score?

Stochastic Panda: Yeah, great question. So the notion of a skyline is now a little bit more general because we're not considering, let's say, oceans or views. So in fact, some valid skylines would include basically the sub array 5, 6, 5, because right there's that there's at least two and the ends, so to speak, are the same. But another valid skyline in this example is actually the sub array corresponding to 5, 6, 5, 5 and 5.

Digital Fresh: Yeah, that does make sense. Cool. Okay, so I'm happy with that definition of skyline. Okay, let's see. This is a pretty interesting problem. The first thing I'm thinking about is let's look for skylines with the same height. So I could loop through this array once. And this is kind of what I'm thinking right now is I could loop through the array and store, maybe create some sort of map and store a map where the key to that map would be something like the height. I'll say, like height is the key. And then the value would be a, you know, some list of indexes to say that, you know, we can look through. Then this map to say, oh, we have two heights, five and five, let's see how far away they are from each other and then compare all of those distances. That's kind of where my head's at right now.

Stochastic Panda: Yeah, I think at least one part of that sounds like a good idea. High level, which is keeping, you know, some sort of mapping, if you will, between the height and basically how it compares with, well, basically having some structure like a map that says, you know, the keys can for sure be heights, but the values can either be right, the height, or something else that we've been tracking.

Digital Fresh: Yeah. So I actually, I think I've thought of maybe a better solution and I think you're kind of leading me there is if we loop from through it left to right, then we could store the leftmost position of each index. And then as we come across a duplicate value, say 5 and 5, we'll see as we come across this first duplicate 5, we'll see that the height of that skyline is 1, 2, 3. But then as we come across and we can store that in some max, keep track of the max. And as we come across the second duplicate five, we'll see that that's actually 1, 2, 3, 4, because we're only keeping the leftmost reference of that value. So maybe that's a better way too, to only loop through this once.

Stochastic Panda: Yeah, I think that's the right idea. And let me make two comments on that because I think you're generally in the right path. But let's Finish up example 3 before we move on because, right. We want to return the maximum possible score of all basically valid skylines. And I think on purpose, I wasn't very clear on what we mean by score. Right, gotcha. And so by score of a valid skyline, if you will, is going to be the sum of heights and that valid skyline. Right. So, yeah, in this case, yeah, indices to a degree are less important in this problem than the previous one. What's going to matter a bit more is the heights themselves. So if we go back to. Okay, so two things, right? I think we're good now on the definition of what is a valid skyline. But now if we think about what the problem is asking to return. In example three, if we look at the set of valid skylines, there's basically, I think, just three possible sets, right? And then basically between these three possible sets of skylines, the one with the maximum score would be the last one, which has score. Well, let's say max score, which is going to be equal to the sum of that one, which is 21. Right. So that would be our output in example 3. And just to kind of, to wrap up our examples, let's say I said example one was the first one you mentioned. So if this was the input, then in this case it's pretty clear. I think the output is just the sum of everything, which is 7, 6, or 13. So. Yeah. Does that kind of make sense now on the SOT output?

Digital Fresh: Yeah, so that was definitely something I should have dug into more because I know I did gloss by that detail. I assumed the max or that the score was actually going to be the size of the skyline, but it's actually the sum of the heights. So perfect. That does bring in one detail. And it's kind of. We touched on this before, but I'm going to assume maybe for my first implementation of this, no negative heights. But, you know, that would definitely change how I go about this. Is that safe to assume or should we talk about negative heights?

Stochastic Panda: Yeah, it's. Let's do kind of similar to the last problem. If time permits, let's discuss at the end how we might think about negative heights. But for now, let's assume actually that the input consists only of strictly positive integers.

Digital Fresh: Okay, perfect. So I'm trying to see how this sum of heights, if I could do this more efficiently. I'm still sort of thinking this would. This would take me to go through this list twice, but if each height had an index of the furthest to the left, and then I could sum afterwards the furthest distance. But I'm assuming there's a way to do this much more efficiently. So I'm just sort of thinking about that real quick.

Stochastic Panda: Yeah, go ahead, Take some time to think about it.

Digital Fresh: Yeah, I'm struggling to think of any way to do it without also looping through our sort of map of heights again to just sum everything that's in there one at a time. So I might go with this index solution for now and see where that gets us, if that's okay.

Stochastic Panda: Okay, so yeah, let's go ahead and do that and then see if we have time to optimize it or think about it towards the end. Sure.

Digital Fresh: Gotcha. Okay, so we want to return a score. So I'm going to assume some int. Let's call this, just call this score sky. We're going to take in some vector of integers. This is our skyline. Okay, great. So here we're going to have some unordered map with int and int, where the key is going to be the height and the value is going to be the index or leftmost index of that height. In my case, I'll call this skymap. Might need to include this as well. That not the include for it. I'll figure out that include later, but I'll move on for now. Okay, let's see. So we're going to start at index zero. We're going to see if skyline, if sky map includes our skyline height. So skyline I. And if that map does include it, then let's calculate some. We need to store two things here. So I'm going to say like, oh, I see. Okay, so I am making an assumption here. I'm still thinking about it in terms of indexes and it's not going to work the way I want it to. I see. Okay, so, so the reason why it's not working the way I want it to is because what I was going to do is, you know, given some, some height, I was going to see where it was and where the next one was. And then, you know, the longest distance I was assuming was going to be the highest score. And then I was going to go sum that up at the end in another for loop. However, that's not going to work because if we have 100, 110, 10 or 100, 110. 110, it's going to look like 10. 110 is the highest score, but 100, 100 is going to be the highest score.

Stochastic Panda: Right, right.

Digital Fresh: And the only way I can sort of consider to get around that right now without thinking of some more complex solution would just be to implement some O of N squared solution where we, we do the same thing. We're going to score. We're going to. If it's the first time we see an element, we're going to store that height and then we're going to, every time we look at a new height, sum our previous heights. And then if we end up ever seeing a duplicate, we'll store that in some max height value and keep track of the max height that way. But that is N squared. But I apologize. I just can't seem to get to a more optimal solution right now. So we can go ahead and start programming up that solution if that's okay.

Stochastic Panda: Sure. Yeah. Let's go ahead and try the N squared solution.

Digital Fresh: Okay, gotcha. So yeah, so we're going to go through our skylines and it's going to be the same thing. If sky map does have some value skyline with height I then in here we're going to check if it is greater than the max height. Yeah perfect. Else we will store. We're going to initialize this to the skyline's height. This should actually be a contains and if it contains then we're going to go look at it and we're going to sum it with the current skyline and then we're going to. Then we'll update our max value. Maybe initialize that to zero if we assume everything's going to be above zero or greater. But we might run into problems with this if there aren't any valid skylines. So great. We'll also need to keep track of some. I'm just gonna do that by keeping track of some bool. You know valid initialize it to false. If we ever do find this duplicate value then we'll set valid equal to true at the end we'll have to check if valid. If we do have a valid skyline, we'll return the max height or else we'll probably return some negative one. Okay great. So if it does contain, we're going to add it. Okay, but even before this. So for every new skyline we look at going to do another for loop and I'm going to iterate over every sky map value we have and sum them so we actually won't need this anymore. Because we're going to take care of that in this other for loop. Oops. I'll do this the it's been a while since I've iterated through a a map. Believe this is how we do it.

Stochastic Panda: Oh yeah. The items. Mm.

Digital Fresh: This not how I do this. Oh wait. Whoops. Believe this is how we do it. It's been a little while since I've iterated through a map. Iterator plus equals our new skyline. I does not like this. This should be an iterator. I want to dereference that and set it. I apologize. This I'll circle back to why this isn't working. But this should be just going through our entire list of mapped items and summing each value with a new yeah. With the, with the current skyline. And then what we're going to do if we do ever find a duplicate skyline, we're going to. That's going to be considered valid. And so we're going to get that max height with the latest skyline summation, or else we're going to create a new skyline in our map and just initialize it to its own height and then either return that maximum height or negative one. So I believe this is our, this is our algorithm.

Stochastic Panda: Okay. And so we're getting near the time, but the basically inner loop starting on line 116, if I understood that's where you want to check if you have a valid skyline in the sense that the beginning of some sub rate matches the end of the sub rate. Is that right?

Digital Fresh: Or for line 120.

Stochastic Panda: Oh. In line 120. So yeah.

Digital Fresh: So we'll only ever update a maximum height if we ever do have a valid skyline. So if a skyline already exists within our map, then if we ever. If something already exists, then we have a valid skyline because it's the same height. And then we'll take whatever that current summation is at that time and store it in a max height value.

Stochastic Panda: Got it?

Digital Fresh: Does that make sense?

Stochastic Panda: Yeah. Okay. Got it. Yeah. Because you. Okay, you updated that part like previously, you were adding to it. And now we're just doing the condition on line 120 to say, have I seen basically that. That skyline before? And if I have, then max height. Okay, and then where are we doing? Like, we need an addition, right? Like, so once we like identified.

Digital Fresh: That, that's what this is right here. For some reason I have the syntax incorrect and I'll attempt to fix that right now. But our sky map stores the current, the current score actually of each height. So if we have something like 5, 1, 5 at the first iteration of this, it's going to initialize 5 with the score 5, and then when we get to 1, it's going to update 5 plus 1 in this line 117. So then the index 5 in our sky map will store the score 6. And then when we hit another 5, it's going to add it again, so we'll have 11. And then it's going to say we contain a 5 already. So it's a duplicate 5. So it's a valid skyline. And we'll store that maximum height. So that addition is happening from line 116 loop.

Stochastic Panda: I see. Okay. And in that line 116 loop, like if we take, you know, 5, 1, 5 and the values of your map called sky map Skyline of I. Oh, okay. So you're basically changing part of the input in place. Right. So if we start off with an array called Skyline, you're tracking the cumulative sums in Skylines itself. Got it, got it. Okay. Right. And of each values. Yeah, of each height. And then the values corresponding to sky map. I see. Sky map contains skyline. Yeah, because I was just. Yeah. I think with more time, the code would be reflecting my next question, which is, you know, if we. If we have an initial skyline with values 5, 1, 5. Right. At some point we want to keep track of cumulative sums. So like, you know, values like 6. But in another data structure, we don't want the value six to appear because we only want to compare original height values to determine whether it's a valid skyline. Right, okay. Yeah, so. So I think that general idea makes sense. And. Right. So. So at worst, if I see like line 116. Right. We would be doing an O of N operation if Skyline. Right. Deconstruct is of size. Right. So the overall time, as you suggested. Right. Would be N squared. Okay. And then terms of space also. What might you propose?

Digital Fresh: Let's see, in terms of space. Yeah, I think we're. I think we're dealing with O of N here. Because if there's like. If every value in Skyline is different, then that will hit an O of N space complexity, I believe.

Stochastic Panda: Yeah, yeah, exactly. Because you have basically two data structures. Well, one additional data structure, this sky map that you're introducing. And at worst, that'll get O of N. Okay. Yeah, I think I follow the general idea there. Cool. So I think this is a good stopping point. Do you have. Do you have a hard stop at the hour or can you go over like a minute or two?

Digital Fresh: Yeah, if you have the time, I'd love to even talk to you a little bit more if we have the time. About some of the other services you do. You said you do like that mentorship and stuff. I'm really interested in that. But, yeah, I have time.

Stochastic Panda: Yeah, definitely. Okay, great. So, yeah, we can get to those good topics and let me start with some feedback, so if you're open to it. What I usually like to ask folks is the following question. How did you feel you did today?

Digital Fresh: You know, on the first one, I think I did rather. Okay. I know that was more of a simpler implementation, so I might have. I might have spent too much time actually talking about it. And then when we got to the second one, you know, I did miss that. The score I Should have clarified the score and I feel like I didn't find a near optimal time complexity here, so I feel like I did. Okay.

Stochastic Panda: Yeah, great. I would agree, especially for the target level of like E3 or you know, a position for someone in general with two or so years of experience. I would agree for at least a few reasons. Right. Like going problem by problem. Agreed. On the first problem, you solved it really nicely. You asked good clarifying questions. Right. Like, you know what, what do we mean by the right? Okay, it's the right index. And also you understood the output. Like what does it mean for the output to be increasing? Right, it's the indices. And also I liked how you structured your solution out loud. Excuse me, before writing the code, which was, hey, if I start from the rightmost or the element at index minus one and then traverse basically from right to left, here's the overall solution and then you wrote the code. So I thought that was really great. On the first problem. What I would offer for the first problem is. Well, on. It's slightly a nitpick or slightly more advanced, but if you find this problem actually on Leetcode, which is where it is, you'll actually see on Leetcode that some people argue whether line 65 and 70 constitute extra space. And that's just something to be aware about. I think some interviewers like me would say, yeah, we are using extra space because there's this extra thing called indexes. But some people on leetcode say, oh, there's no extra space because index is a thing that we're returning and if we're returning something then we don't need to count it. So as long as you keep that in mind and say, just give some justification to say, because I'm building indexes, I'm going to count it, extra space, then I think you're perfectly fine. The other nitpick I would have on the first one is kind of the pass by reference or copy which is in the method signature. Like whether you want to include the ampersand on line 47. Again, depending on the interviewer, some interviewers will be super happy with okay, just the code, go on, nitpick, move on. But others, if position is very specific to C, they might ask you like, you know, why? Why do we do ampersand or not? There's some pros and cons, just some things to be aware about. And also I think it's complaining. This is also kind of a nitpick. Some. I guess it depends on the IDE or the experience is that we don't have, I believe, like a public class. Right. So you might reasonably ask, like, how would you test this? You don't need to code it, but you can just say out loud like, well, if I made a public class that maybe contains a method called max buildings indices, and then I put, you know, like something called public class solution to wrap it around and then I would do these basic unit test, adding those comments, if you can, proactively would be good. Again, you don't need to code it, but just gotcha. Here's how I would test my thing and also what I wanted to say. Okay, let me not dive into more nitpicks because I think those were the main ones and. Oh, right. One more thing that I think you did really well on the first problem was your time management. I need to go back probably to the replay, but I think between the time I pasted in the question and the time you finished it, I think it was around 12ish minutes, which is really, really good. So no worries about talking. In fact, I think the amount of time you talked on the first problem was basically perfect. Interviewers are happier with a chain of thought taking, you know, five or 10 minutes, especially if it's going to inform the solution really, really well. So. So I think you did well there. Okay, so let me pause there if you have any questions or comments on first problem feedback.

Digital Fresh: No, I think that that all makes sense perfectly. Yeah.

Stochastic Panda: Great. Okay, so moving on to the second problem. So one thing I'll say as a preface is that both problems, I think in general leetcode classification, are considered mediums. But I would say the first problem is closer to a slightly easier medium on the spectrum, whereas the second problem is a little bit closer to slightly harder on the medium spectrum. So the second problem in general, I think a reasonable interviewer would give you like closer to 30 minutes as opposed to maybe 15 or 20. So there is a bit of a time crunch, but I think you did well on initially exploring like, okay, what does it mean to have a valid skyline? And you also did well in general about structuring your thought process because you caught a few things on your own as you were going through what the solution might look like, what you need to keep track of, and finally what we need to return. And again, I would say in general, good clarifying questions, good thought process. The tricky part though was in the code itself. So one thing I would say is if you feel like you're maybe getting stuck and not seeing a potentially optimal solution, then if you feel like, okay, I might have an N squared or N cubed solution and I feel confident about it, that's a good fork in the road where you do need to make a decision and kind of go with it. So I think you would get brownie points at least for that. Right. That decision making to say, I think there's something better, but let me do N squared and here's why it's N squared. So that's good. Now part of, I think what tripped you up in time just a little bit was. Yeah, like you said on iterating through the dictionary, I think there's a way to do it with basically something like an it dot first and an it second or some sort of like attributes that you can think about calling. So just having some of that or iteration. Right. Because you can also do it. There's different ways to do this right in C. So I think if you had done that inner loop a little bit faster, you could have probably gotten the solution that would work with O of N squared and also. Okay, so those were the. Okay, so the positive parts I mentioned. Now I'm starting to go into potential areas of improvement. So okay, that's one thing, just that iteration. The second though is. Yeah, as you called out, like just making sure you understand the output that we're seeking. Yeah. In this case it was that sum of the maximal valid Skyline. And I think if you maybe did this problem again, but clarified that you want to do this max score in terms of that sub array sum, then I think you would have solved more of the problem. And another thing I would mention too is in general it's okay idea to say, hey, I'm going to have this boolean to tell me whether I've encountered a valid or non valid Skyline. But one trick you can do is to say, well, from the beginning can we always assume there's going to be a some valid Skyline in my input? And the reason to do that is it makes the code a bit cleaner and it still gets you actually to the main solution. And a reasonable interviewer would say, yes, let's always assume that there's going to be at least a valid Skyline in your input. And then you can get to the more general case at the end and say something like, well, if there is no valid Skyline, then maybe will just return zero. So it's always okay to make those simplifying assumptions on whether there is a valid Skyline. Or as we did before, that we can start by thinking of integer values as just being positive because that Tells the interviewer, like, you're actually making very good simplifying assumptions that will lead you to a solution. So, yeah, that's basically it. Oh, and just one more nitpick. I like that you wrote time and space on line 121, 21 for two reasons. It's very clear you're saying this thing is time, this thing is space. Also, there's quite a few candidates that in a real interview will say say at the end of their solution, okay, and by the way, here's my time and extra space, worst case. But they won't write it down. And sometimes that's an issue because in the final interview loop, some interviewers might say, like, hey, let me see your notes on this candidate, or I need to go back to my notes on what the candidate did. And if they don't see it written down, they might not remember. So it's always to your benefit to write it down.

Digital Fresh: Gotcha.

Stochastic Panda: Also, yeah, to just define your variables too. Like it's clear you set up. But if you write something like, you know, is defined as skyline dot length or something like this, that'll help too.

Digital Fresh: Yeah, that makes sense.

Stochastic Panda: Cool. Okay. So that was my kind of rapid fire summary feedback. Any questions or comments for me about the feedback?

Digital Fresh: Yeah, I really like everything you told me. I think that was really good, you know, like setting up the solution to be testable. Yeah, I think writing more notes as I go along is definitely good. I think on the second one, on the second question, I was definitely feeling the time, so I was just sort of making some decisions really quick, like iterating through and using the Boolean. But I think asking those clarifying questions is always better. So. No, I think I really like the feedback you gave me. I don't think I have any questions there besides, I guess, I mean, if you could give me an overall assessment, you'd say about like how I did. These are some of my first interview practices I've done. I didn't even really interview much to get the position I currently have. So just, I kind of want to know where I'm at, where you think I'm at. You know, if this was like a first round, would I have moved on? Maybe something like that. Can you give me anything in that regard?

Stochastic Panda: Yeah, I would say it's probably a yes to move on to the second round with like close to 75 or 80% confidence. The. The reason I might not say like, you know, 90 or 100% confidence is partly due to me because I kind of purposely gave you a harder question in the second problem. And most phone screens, if they ask two questions, they'll generally be closer to the same scope of complexity. And the challenge though is that when there's kind of an unfinished problem in like a 40 or 45 minute round, that's where the level of confidence might be put into question a little bit. But all that's to say based on the level, based on your thought process, how you're writing code and you know, thinking about these questions and that you solved the first one basically flawlessly and the second one like 60 or 75% of it. That's why I would say overall it would be a yes on, in my view.

Digital Fresh: Gotcha.

Stochastic Panda: Cool.

Digital Fresh: That definitely like to hear that. Awesome. And then I guess I do have some other questions if you do have the time just to hear about, you know, a little bit more about the mentorship stuff you do. If we have time to talk about that a little bit.

Stochastic Panda: Yeah, definitely. So two things. The first is that, yeah, I can share with you my so called dedicated coaching link. And then using that, you can basically sign up for packages and then packages. I think it's on this platform anywhere between like three or five or ten pack. And. And if you sign up for those. Right. Like one of the first things that we would do is to set up some sort of strategy like working backwards from your goals, basically. So if you were to say, hey, I'm going to sign up for three and you know, my timeline is to interview at something in two weeks, we can do that. Or you can say like, okay, I first want to schedule a phone screen and once I've got that schedule, then we'll do more sessions. So it's very flexible. And the second thing I would say is I believe the folks over at interviewing IO are having some sort of Memorial Day sale pretty soon. And so you could always email the organizers and say, hey, [REDACTED] mentioned you guys might have a sale soon. Would that apply to the dedicated coaching packs? And. And then we can take it from there.

Digital Fresh: Gotcha. Okay, very interesting. I'll definitely look into those. You said you could share a link. A link with me?

Stochastic Panda: Yes. Yeah, let me. I can do that now. It'll just take a minute. This way. I also don't forget. So one second.

Digital Fresh: And of course, if, if you have anything, I know we're going over time, so if you have anything you need to do, I want to be respectful of that. Just let me know if you need to hop off.

Stochastic Panda: Yeah, I have two or three minutes, so I will need to hop off soon.

Digital Fresh: Perfect.

Stochastic Panda: But let me, let me do two things too. Okay, so hopefully this is copied. Let's see if it pastes. So I'll try line 45. 145. Okay, so that is the link for me and. Oh, right. Something just as a fun tidbit or heads up. The second problem is very much related to a technique called Kanata's algorithm and general approach with something called prefix sums, which you kind of mentioned. But I think it would be good to practice because I think these types of problems, and I'll link some similar leetcode ones, they tend to come up. They tend to come up quite a bit these days, especially for companies that do not ban dynamic programming. These come up quite a bit. So they're pretty frequent in saying, except for Meta. Meta is the only company I know of at the moment that generally does not ask dynamic programming related questions. But anyways, not only because they're popular, I think they're good practice problems. So I'll include some more practice problems in the written feedback afterwards.

Digital Fresh: Sounds good. Yeah, this, this definitely felt like a dynamic programming problem. I was looking at the time and I was like, I don't know if I'm going to be able to come up with that solution in the amount of time we have left, but perfect. Cool. What was the name of that algorithm again? Just so I can write it down.

Stochastic Panda: Oh yeah, the general one is algorithm and I think he was actually a statistician, so called Bayesian. And somewhere along the way he found this neat method to tackle these types of problems.

Digital Fresh: Okay, awesome. Yeah, Canary's algorithm. Cool. Thank you. Well, I definitely want to be respectful of your time, so if that's all you had for me, I'll definitely let you go.

Stochastic Panda: Sounds good. Well, it was a privilege to work with you today and I hope to speak with you again soon.

Digital Fresh: Yeah, thank you so much. And you have a good day.

Stochastic Panda: All right, you too. Bye.

Digital Fresh: All right, see you.