Python Interview with a FAANG engineer

Watch someone solve the efficient sampler 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

Efficient sampler

Interview question

1) Given a sorted integer array arr, and an integer x. Find the first and last index where x occurs in the arr. 2) Design and implement an efficient sampler that can handle the following operations in constant time: - Adding a String - Removing a String - Perform a uniform random sampling over the current set of Strings

Interview Feedback

Feedback about Verdant Gyroscope (the interviewee)

Advance this person to the next round?

How were their technical skills?

4/4

How was their problem solving ability?

3/4

What about their communication ability?

4/4

Context is preparing for a software development engineer internship position at a FAANG company. I gave a phone screen with two technical questions. You meet the requirements for a phone screen at a FAANG company, I would recommend you come for an on-site. You have strong data structures and algorithms knowledge, and even better I feel like I'm talking with a peer when evaluating trade-offs and thinking through approaches. Something my company values in interns is their ability and willingness to be mentored and coached, and you give a great impression in this regard. You write working code in idiomatic Python. Some suggestions: - Be ruthless about time, avoid long discussions or at least clarify with the interviewer if they want to have a discussion. For phone screens you don't get much time for questions. You need to propose code, propose time and space complexities, trace with one example, and cover edge cases. - Take a look at the Python bisect module, it's interesting. https://github.com/python/cpython/blob/3.9/Lib/bisect.py. Insert some print statements play around with edge cases for the problem. - Use typing hints at least for your method signature, this is a powerful and easy way to communicate what inputs and outputs are. https://docs.python.org/3.9/library/typing.html#module-typing - If you're interested dive a little deeper into how lists are implemented in Python, https://docs.python.org/3/faq/design.html#how-are-lists-implemented-in-cpython and https://github.com/python/cpython/blob/5c22476c01622f11b7745ee693f8b296a9d6a761/Objects/listobject.c#L22, but I wouldn't spend too much time on this. Good luck!

Feedback about Orange Malamute (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

Honestly you were the best interviewer I've had on this site -- very knowledgeable about interviewing practices at FAANG companies, lots of great advice, and you also had helpful feedback at the end of the interview. Thanks!

Interview Transcript

Orange Malamute: Hi, can you hear me?

Verdant Gyroscope: Hi. Yeah.

Orange Malamute: How are things going?

Verdant Gyroscope: Pretty good? How about you?

Orange Malamute: I'm doing well. Thank you. So before we get started this interview, I wanted to ask you a few questions to make sure that I asked you the right kind of questions. Okay. So is this the first time that you're using interview.io?

Verdant Gyroscope: No, I've used it before.

Orange Malamute: And what position are you applying for?

Verdant Gyroscope: So I'll be applying very soon for internships for next summer software engineering internships. I'm a rising junior in college studying computer science.

Orange Malamute: Okay, software engineering internships. And sounds good. And what kind of companies are you applying for internships?

Verdant Gyroscope: Um, I think generally, like the larger established software companies, like, you know, all the FAANG companies, and similar kinds of like, large software engineering companies, I'm not necessarily as focused on on going to work at a startup, I think at least for next summer, I'm aiming to just work at a more kind of like, established, well recognized company, and, you know, some software engineering practices, and then maybe start my career there, hopefully, if I can get a return offer. So that, yeah, that's kind of really what I'm focused on.

Orange Malamute: Sounds good. And have you actually gone through any interviews yet? Or are you still preparing?

Verdant Gyroscope: Not, not for this, this recruiting cycle now.

Orange Malamute: Have you done? So for previous recruiting titles?

Verdant Gyroscope: Yeah. I'm actually currently interning at a company called DX, which is a software company. And yeah, so I interviewed for a bunch of companies when I was applying to stuff last fall.

Orange Malamute: How did that go for you? Not the job. But the preparation.

Verdant Gyroscope: It generally went, it went well, like, I think I was I was fairly, fairly prepared. But I think definitely, I've done a lot more practice since then. And I was a little bit like, definitely a little bit shaky on like, especially the harder type problems, which I think this given I'll be applying to probably more difficult, like, companies to get into, or to get an offer from. Those will probably be like, more important this time. And so like, Yeah, but generally, it went, Okay.

Orange Malamute: And how prepared would you say you are for this current interviewing cycle for these larger Fang type companies?

Verdant Gyroscope: I think for 20 interviews, I've been doing a lot of prep, and I feel fairly prepared. But I still am a little bit unprepared for like behavioral interview stuff. And I don't know, like if some companies do like system design, so I'll definitely be practicing that stuff. As I start to, like, apply to places and hopefully get interviews. Yeah.

Orange Malamute: Awesome. Great. Thank you for that information. So I can help you. And let me give you some background about myself and the way my company does interviews and my advice for you preparing and then the kind of question that I can give you today. As I work for large fang company in Seattle, I've been working there for seven years, more than seven years. And I have specific experience with helping interns with the company and interviewing interns. So with these large fang companies, fortunately, or unfortunately, a lot of the process is automated. So you'll go through some automated phone screen and believe it or not, at this company, automated behavioral questions. And if you pass you pass, you get an offer. But if you don't, if you don't quite pass, there's a human who intervenes to give you additional interviewing. So at the large fang company that I work for in Seattle, there's an emphasis on data structures and algorithms in terms of coding 50% and 50% behavioral questions. And you can't pass if you don't have either of those. So when you say that you're preparing for coding, that's great. You should be prepared for behavioral as well, at least for my company, and I would suggest for you for university students They feel like they're disadvantaged because you don't have previous experience. It doesn't work out like that. And I suggest to get specific practice on interviewing.io with me or anybody else for behavioral, and at least my company. Interns and entry level SDEs are not expected to have system design experience, nor are they evaluated on it. They do evaluate you on object oriented design. So like how to organize code, but not system design. You know, it may be different in different companies, not that this is how my company, I wouldn't worry about system design.

Verdant Gyroscope: Yeah, I'll definitely, I guess, started scheduling some like behavioral interview practice. In that case.

Orange Malamute: Yeah. Yeah, yeah, that's, that's all I can say, for this specific sessions. What you paid for is data structures and algorithms, I can help you with that. And you. So I'm guessing you're probably preparing by going through leetcode, or what other resources are using?

Verdant Gyroscope: Yeah, generally going through leetcode. I actually started out on a different service called algo expert, which turned out to be not as good as leetcode. But yeah, so I'm just doing kind of practice problems doing interviewing.io. I read, I went through Cracking the Coding Interview, the book, which has helpful kind of like, information, and then like practice exercises. So yeah, that's really it.

Orange Malamute: Cool. So that's great. I also said, I'm going to delete the code here. It's not very useful. I also suggested Look, I don't elements of programming interviews. I really like this book, I recommend getting in. And besides this, what language were you planning on... Or what language do you want to interview and

Verdant Gyroscope: I usually interview in Python three.

Orange Malamute: Okay. So, and Python three is fine. Usually, for FAANG companies, I would say, if you have time, I would suggest interviewing in a in like, one of those boring big languages, Java or C++. But if you don't have time, Python three is fine, and nobody looks down on you. And nobody really cares what language you use just that in Python. Unfortunately, sometimes the idioms are so powerful that you can solve into your questions without necessarily having much algorithms and data structures and object oriented programming knowledge. And some interviewers may count that against you. But you have to weigh that against the fact that you would have to learn Java or C++. So I would suggest sticking with Python three, but just be aware, don't get stay away from the standard libraries or too much cleverness if, especially if the question calls for data structures and algorithms. Okay. Yeah, I am sure.

Verdant Gyroscope: Yeah, I'm pretty familiar with Java. But I've been doing practice in Python, just because I guess I found that it's, like easier to, to write like more concise code in an interview setting. But I'll definitely, maybe try some practice in Java and see, see how, how easy it would be to transition? Because I guess that makes sense. And like, most like software engineering, internships, or jobs, you're not really going to be doing much programming in Python, given that it's highly inefficient. So but...

Orange Malamute: Yeah, I don't want to take up too much time at this point. Python is very appropriate for some roles, especially for research scientists and machine learning roles. It often is mandatory. But at least at my company, the large FANG company that I work with 80, 90% of the software is written in Java. There's a renaissance in Rust, but mostly Java. Python inefficient. Yes. It's just that it's easy. I don't know. Java is very common in industry. But interview, nobody cares what language you use. It's just like in Python, there's things like binary search in the bisect module, like don't use that just as a silly example. It's just like, don't don't use too much standard library or clarify if you can use it. That's okay. That's cool. That's all the advice I had. So how do we get started with questions unless you have any questions for me?

Verdant Gyroscope: No, I think I'm ready to go with with practice questions.

Orange Malamute: So what I'm going to do is... Give you some regular phone screen data structures and algorithms questions. Okay. And so the bar for these questions at so this is very common at companies. So for a phone screen, the goal is not is to determine if somebody can should be allowed to go to an onside? Would they just flounder? Or do they have a reasonable chance of success? It's not the bar is not will they be a good intern at this company. And there's a subsequent round to the on site, which is has more intense questions.

Verdant Gyroscope: And in the on site, I'm guessing that's when you do like whiteboard questions.

Orange Malamute: In this day and age, in my experience, yeah, that, you know, over a video, video conference, whiteboarding just doesn't work. Sometimes it's come with whiteboards, and they struggle to draw things, it just doesn't work. Really, especially as an intern, you'll be expected to do system design. So you won't be whiteboarding anything. You can get away with just an interactive code editor, I wouldn't worry about that. Okay. If you're more experienced, that's far more difficult. But let's start with a simple question. And so, for a phone screen, you should expect two coding questions each one lasting 25 minutes. And I'll make a note of the time and the right hand side. Okay. For onsite at my company, for interns, okay, this is more tricky. In turns is far more different. Often the loop is very small. So often you'll only have one or two interviewers. And it'll still be one hour each, and they will evaluate you and behavioral or and coding, but it'll just be one or two around not that long. Okay, cool. So let's start with the first question, I'm going to just paste it here. Also, the final piece of advice I'd give you is, for internships, when you do the automated code screens, you will have an environment at least at my company where you can run code. So on the one hand, that's great. But at these large FANG companies, when you get to a in person phone screen or an on site, you won't have the ability to run code. So my advice is not to rely on the code runner during and as you're practicing. Okay.

Verdant Gyroscope: All right. Yes, sir. Sounds good. So looking at this question, I think given that the array is sorted, we're looking for a target integer. I think the right strategy will be binary search to find one of the elements that matches that target. And then I believe just going to the right, as much as possible for that point, to find the last index and going to the left as much as possible to find the first index would be the most efficient strategy, I don't think there's because once you reach the section where it's just, you know, presumably like a bunch of matching integers, like one or more, then there's nothing really the sorted property kind of isn't really useful anymore. And I think at that point, you just kind of have to do a linear search for the first and last indices. But certainly to find that section of elements matching x, in binary search will make it much more efficient to get there.

Orange Malamute: So your proposal, your proposal is to find this section of integers using binary search and linear search left and right, what's the time and space complexity for proposed solution?

Verdant Gyroscope: So I guess in a complete worst case scenario where like, you have O(n), like, matching integers, it would just be O(n). But sorry, what? Yeah. So but in the case that there are I mean, in the expected case, where you don't have a bunch of matching integers, who would be... I guess it'd be, it'd be like, O(log n) + m if m is the number of like, integers matching x. So, yeah, that's kind of that'd be the runtime. And then I think this can be implemented with just a constant space. Because we don't really need, we can do a, an iterative binary search, and we don't need to store any data structure or anything like that.

Orange Malamute: So for the focusing on this case, where you may have a long run of the same integer x, is there, is there any way of avoiding the linear search?

Verdant Gyroscope: Yeah, that's a good point. So... I suppose... Okay. So I think actually, if we try and find like, the, the closest element to x that's like, strictly less than x, which we can also do with binary search. And we stored the index of that. Then we could use that to like, that would be like on the left side of the stream of matching elements. And then you can do the same thing to get to the right side, but I guess it's still problematic, and like, thinking about the absolute worst case, because we could have like a long string of those of that element that's like, less than x. But so yeah, I think, um, but actually, okay, so I think, once you find like an element matching X, you can kind of do a binary search to find like the left side and right side, I think, because you can, like, I guess, like, go halfway to like, to like the left side of the array, see if that still matches x, if it doesn't, then you've gone too far to the left, and then you can go to the right. So so you can kind of use that a different sort of binary search to find the left side, and then same thing, find the right side. And that would lead to, to just ~O(log n)~` running time.

Orange Malamute: So what I what I think would be great for this question is, let's try to keep it. And let's see if we can figure it out.

Verdant Gyroscope: So you said let's try to keep it...

Orange Malamute: Let's try to keep it. Let's try to keep it log with and see if we can figure it out. Okay.

Verdant Gyroscope: All right. Yeah, sounds good. So I think that strategy would work with even logarithmic. And so yeah, I'll first right. So I guess we're given an array. So first to find like one of the, like, an index that matches x, we'll just to kind of like a normal binary search. So yeah, I guess we'll say, left is zero. Actually, so if the length of the array is zero, then in this case, like, I guess, and this will come up later, also, if X isn't in the array, I'm guessing we should return None, or some sort of raising exception or something like that.

Orange Malamute: That's a great question. Maybe if, if we decide x is not an array, we can return minus ones. Okay.

Verdant Gyroscope: And, Alright, so now I'll maintain kind of left and right, left and right corner. The left, sort of zero the left side of the array, and right, we'll start at the last index in the array. So I'll say well, left is less than or equal two, right? Let's see. So I'll make a pivot equal to left foot, right. Integer division by two. And then I'll say, so if array two equals x, then I'll just write out the cases first, but then The case where we found we found x I guess the elements to the break. So or maybe pivot element, pivot element equals x pivot element is less than x, then we want to go right, and then we have put it on the screen. And so we want to left. So, yeah, in the case where it equals x, this is where we want to then do a binary search to find the left and the right side. So I think we should probably split this out into a helper function. So let's say like find left. So this will like find, find the first of the element, the given start index and then maybe find first big verses and then find last on the last occurrence and these might, these will look probably pretty similar, but they'll be going in different directions. So I think it'll be like reverse logic. But yeah, so we'll like we'll basically say, in the case that we find x will return, find first array, pivot, and then find last array pivot. Indicate its pivot. In the case we want to go right, we'll just say left is the first one. If we want to go left, we'll say Right? Instead of minus one. And we have to take care of the case where I guess we're so left and right are or equal, then you could have this case where where pivot will just equal like left equals right. And then I believe, yeah, but actually, I think because we, we, you know, plus one and minus one here. Like, in any case, the pivot will change. So I don't think we can actually get to that stationary point where pivot is never changing. So I think no matter what, like because the difference or it will say like, because right minus left, strictly decreases at each variation, or we can so, yeah, so I think we can... Yeah, we can probably implement the find item find less functions now. And, yeah, I think this is basically everything besides at the end, if we don't find like if the while loop terminates, and we haven't found the element yet, then we can return negative one. Okay, so fine first. So I suppose. And actually, we can probably even make this more efficient by maybe like storing like the rightmost element that's less than this one. I don't think this would change the overall complexity, but it would make it more efficient. If we stored like the most index that where the element at that index is less than our target, and the leftmost index, where the With that index is greater than our target and then that can kind of bound our search here. So like find first arrays start, and then like left. Yeah, basically like a left bound. Left.

Orange Malamute: So this will this idea of having left or right bounds wouldn't change the overall complexity, but might make it faster.

Verdant Gyroscope: Yeah, like if I guess? Well, I mean, maybe it's not even worth the extra the kind of extra effort to maintain those variables because honestly like it, so it would only help, I guess, if you happen to, I mean, in pretty much any. Like, in an old binary search, like, because it's logarithmic, it's not going to take very many iterations to, like, get the target. And so like, I guess, like having, you know, storing that, like that last iteration, where you're to the left, and like the, or the sorry, the last index view to the left and the last image where you are to the right, like that would cut out like a initial steps that it took to get there. Cut out like reproducing those, but I mean, maybe it's something like an optimization where like, in practice, you would want to, like actually, just first do it simply and then try out the optimization, see, if it actually helped, like maybe updating the variables, in all normal cases, just waste your time when it helps. And, and then, like, you know, go with that, if it if it does actually help in practice, but I don't know, I guess, because this is like a kind of small optimization, maybe I can just implement a first and then thing and then maybe add that later if... Yeah, if we have the time where in practice, like if it actually we've tried out, and then see if it helps, but alright, so I guess... Yeah, to start on just logic here, because we need that to be able to solve the problem. So I'll say equals zero and right equals start. So I guess we want to say like we basically want to find the spot at which it changes from an element less than, like our start or target to the target. And so I think at each like step of the binary search, we want to look at the element and we want to look at the element to the right. If the element equals, if the elements still equals are, or I guess like, yeah, the element and the element to the left, if the element to the left equals, like something less than and or I guess in the like, to start if the element equals our target, then as a sub case, if the element to the left is less than the target, then we know we found the Left Bound, or like the first occurrence. If the on the left is the same, then we need to go left. So yeah, I guess our cases are like, we say, target equals, since this is kind of like an internal function. Like, I won't add, like input validation or anything like that. Like I won't check that start has to be in range. And like, besides I guess the first time we index into it would throw an exception. We're out of range anyway. So yeah, like basically, the target will just be arrays. And left equals zero right equals start. So I guess we'll have a... I mean, for now, we'll just say like while true, we might update this, but I think the main we may see we know that eventually will break from this. And it's not like it's not like this loop where you might terminates a loop, like left might be greater than right? And you haven't found anything because you know that like you're looking for the first occurrence of start. And to start is could be the first occurrence. If there are no elements to left, then it is there any elements that you just choose. So like, in all cases, we will return a valid answer for this function. But anyway, so I'll just repeat this that that logic I was discussing. So like, if so I guess like first... Yeah, so different array, like pivot equals left, right. Same thing like a daily loop. And I'll deal with like the edge cases later, but for now, I'm just like the main mode. So if array minus one is less than or sorry, for a pivot, equal target. Array is at minus one is less than target, then return pivot. So if it equals target then we want to go left. And those are the only cases because it's a sort array. So yeah, so this case, like red equals to minus one. And also like, I might update this, but I feel to edge cases. But yeah, for now. It's good. So like else. Arrays, pivot is less than target, that means we're too far to the left. So we want to go right. And so like, let's select one. And so there are some edge cases like if we somehow reach like the left side of the array, which is possible. It's like we just want to return the current index. So like if pivot like equals zero, basically, which is the only case where pivot minus one would be out of bounds, then we just want to return. Actually, wait... if, yeah, so sorry, if array pivot equals target, just return pivot. Else, you... Yeah, else? I guess like, because we've only gone left? I think there's actually an unreachable case. So like, because we have this invariant of the array sorted and we only left in this process... I think... I think we can actually yeah, we can actually just return it in the case of common thing. Are you returns here? So now? I think yeah, oh, replicate this for find last. It should be pretty similar, but we've kind of reversed cases. So now left to start and right is length array minus one. Same thing here except if pivot is length array minus one. Then yeah, same thing we return. In this case returns.... Could it just be consistent. If array equals target, then, so in this case, we actually want to look at pivot plus one. So if n plus one is greater than target, then we return to this information plus one equals target and we want to go right and then else we want to go left. Because like, if the right pivot is greater than target, then we know we've gone too far to the right. So and I think that should be the main logic to justify that this loop will always terminate, we can kind of use. So I guess, just be careful like a pivot, like do this only stationary points or pivot would be left equals right. And yeah, I guess looking at all these cases, in each case, either left move strictly to the right or right move strictly to the left. So you can never have that kind of like stationary points, left and right. And never changing. And so I think that should be all the logic. I guess should I write some test cases? Or?

Orange Malamute: Could you go through an example? Okay.

Verdant Gyroscope: Yeah, so I guess I'll go through either through maybe this one and just below read the number. Yeah, so down here looking at this example. So in this type of a function, like V Ray is not here. So we want return in this case. So we'll say like, I guess I'll keep track of like left and right in each iteration. So like, first left will be zero and right will be six.

Orange Malamute: I wanted to give you enough time for the second question. So I think that this code is on the right track. And I wanted to go on to the second question if that's okay.

Verdant Gyroscope: Okay. Yeah, sounds good.

Orange Malamute: So, I'm going to delete this text. I'm going to paste in a problem description at the top. Alright. Quickly switch to paste in a switch.

Verdant Gyroscope: Okay. Okay, so, sample will select a random string. Yep. Okay. Yeah, so and I guess like yep. So I'm assuming we kind of take the string as like we want a uniform. Yeah, a uniform sample over the current set of strings. So like, if even if you add like two identical strings, that shouldn't bias the sample towards that string right.

Orange Malamute: Correct.

Verdant Gyroscope: So, I mean, I think using a set obviously, we would allow for adding and removing but I guess the trick is how to kind of maintain it so that you can select at random so I think I mean, ideally, like, I guess the issue is like we can we can generate like a random number. But in a set in a hash set, I guess there's no ordering, there's really no efficient way to elect like, a, a string corresponding to like a random number. Yeah, certainly not like, uniformly across all the existing keys in the set. So I think actually, so, my initial thought is like, if you maintain like a tree of the strings, that would, that would kind of afford, like logarithmic add and remove. And then there should be a way to do like a logarithmic sample. If you... I think like. I mean, if you maintained, like, if you augmented the tree with like, the number of nodes, root of that, you know, each node, then, like, at each step, you could kind of generate a random number. And then like, have the threshold be like, proportional to the sizes of the left and right, like, sub trees. So like, if the left subtree had like, two nodes in the right subtree at like four nodes, then you'd want to cut off of your random number to be like, two, six. So if the random number fell below two, six, then you would want to go to the left. And if it was about 261, to the right, so that'd be that like, login, like four and six.

Orange Malamute: And what if we want a constant time approach?

Verdant Gyroscope: Yeah. You mean constant time sample?

Orange Malamute: A constant time for all the for all the operations.

Verdant Gyroscope: Okay. So I guess, the only way to have a constant time, like set implementation would be to use like a hash set. So I guess...

Orange Malamute: That is true. Yeah. What you're saying is like, if I want to be able to track use a unique set of set of strings and constant time I need a I need a hash set a focus on that. What other ways could you have a constant time add or remove whilst maintaining uniqueness?

Verdant Gyroscope: You mean, like, not using a hashtag, just another kind of strategy or data structure for holding these strings in and affording out in route?

Orange Malamute: Yeah.

Verdant Gyroscope: So I mean, I guess like the to have constant time add or remove? Like, you could use something like an ArrayList or something like that, or but I guess the issue is like, you don't know when when you get, I guess? Yeah. That's constant time add, but it's not... Yeah. I mean, it's not really it's like, you don't you don't know if there are duplicates. And also, when you remove if you have to remove from the middle of the range, and that constant time. It's like...

Orange Malamute: Yeah, let's focus on that. Yeah, you're precisely correct. So you have a you have an ArrayList. Yeah, it's a more time constant time adds and you don't know when there's duplicates. And you don't know when you remove? If so, what can we do about each one of those problems? Let's focus on the first one. You said we don't know whether there's it's already there or not. What could we do about that? If we had we had an ArrayList.

Verdant Gyroscope: Okay, so yeah, I guess we could map like we could maintain like a dictionary, or like a HashMap mapping the string to the index in the array. And then I guess, to remove... Yeah, so to remove, you could, like, swap it with like the last element, I guess, update the last elements index and update the, you know, the element that you just swapped to the end. Or, I guess, since you removed that, just delete it from the dictionary of the HashMap. And pop from the end of the array. And then yeah, just...

Orange Malamute: Why can't I just remove it from the middle of the array? Why? Why do you have to swap it to the end?

Verdant Gyroscope: It doesn't? Well, okay, so I guess... Yeah, the reason why is because under the hood, like, an ArrayList is like implemented as an array. And then like, you have, this is not necessarily a variant, but like, you have this capacity, or you have the capacity of the array, and then you have the actual size of the list, which is the number of elements and you have this invariant, that the all the elements up to, like, from from index, zero, index size minus one, that all those elements are in the list, and then everything beyond that is not in the list. So the way that it's implemented, requires that like, all those, like, if you just remove them from the middle, there's no way in an ArrayList just like remove that from your list. Unless you like the only ways to remove something is effectively to just decrease the, like the size variable. And so it has to be like that last element for you to be able to remove it efficiently.

Orange Malamute: Are you saying you can't remove elements from the middle of a list? Or you can't efficiently remove elements in the middle of the list?

Verdant Gyroscope: Yeah, I mean, you can, you certainly can, you could remove it and then shift all the elements. But I guess, since we don't really care about the ordering in the list, it would be more efficient to swap with the end, and then just reduce the size variable, and then we still have that amortized constant. Because like, sometimes we'll have to do open work to shrink the array. But we avoid that, that requirement of doing open work every time to like recopy the elements and shift them over to the left. Okay. So I mean, I guess to implement this like, so, I guess as like a class or Yeah, like, I'll just copy this from this interface like, sampler and so I'll have this add and remove sample. So we're gonna want to have like a string index HashMap. And we're also gonna want to have a like an array. So every time we add we want to say like, if this item is not in not already in the HashMap, then then append it to the array. And say, update the HashMap to have this like last index. And if it if it was already in the set, then we don't need to do anything to remove. In this case, we want to check if it is in the HashMap. Then in this case, we want to say so I guess let's first guess index. And then we want to say yeah, we want to swap it with the last element. So like indexes, comma. Yeah, that's like the element we're interested in and the last element and then we just swapped them reversing this. And then. So now, the element, we're actually sorry, we need to, we need to say, self, that's the index. Strings or strings array, like index equals index, because previously this element had the was in like the last index. So yeah, so now that's updated. And we can say, just delete things to index item. And, and just pop them from the array. So this maintains, like these, these data structures. And so I guess in the remove, we could do if the item doesn't exist. Like, I guess, should we return? I guess remove is void. So I'm assuming it's fine to just ignore in the case where you remove and it doesn't exist.

Orange Malamute: Yeah, let's say this case, we don't mind if it doesn't exist, and we call remove. Okay.

Verdant Gyroscope: So for sample now, we just need to, I guess, select a random element in the in the list. So I guess this would be like, C? I'm sure there's a random number generator in Python.

Orange Malamute: You don't have to get the syntax exactly correct. We can just you can pretend that some library exists and use it.

Verdant Gyroscope: Okay. Yeah, so I'll just say like random. Like just assuming this. Like, this just returning. And so we would just say like, so random times. Like, I guess we need to be careful because we're mapping this random, float onto integers. And we want to make sure it's still uniform across all the index indices. So I think it'd be random. Times like, the length of the array, and then we would want to floor actually. Maybe like yeah, like, if we somehow just like, did like, so. Indexes random times length of strings array? And then like, index is len of. Oh, and I guess like if the if the, if we haven't added any elements? For sample? Should we like return none or for throw an error?

Orange Malamute: Should... What do you think we should do?

Verdant Gyroscope: Well, I think since you can probably store elements, you can store none elements. Or, I mean, I guess like strings. Technically, none could be considered a string. But maybe a better thing to do would just be in the add and remove just make sure that item is not none. And then in in sample, or none indicate that it's that there are no elements. I mean, I think it's probably better to like just raise an error in that case.

Orange Malamute: Okay. Okay. Let's do that.

Verdant Gyroscope: Yeah, so I'll just say like, yeah. So the length is greater than zero. And then here like and I guess we're removed, it doesn't matter, because none won't be in the... it won't be in the HashMap. Anyway, so. And I guess we've kind of fallen in the pattern that like remove, we don't care if the element doesn't exist. So. So index equals, like, the length of the string. Then we just want to say index minus equals one. And I think this so. This effectively means we're like, basically pretending as if random like... in like the range like zero to one, but with one being closed and so now we can just say... like or if not for index and then we just returned so, yeah, basically, I mean, the, the reasoning here is like, this number will be like it'll be random, but in the range of zero to, like 10 strings array. And so we just want to make sure, like, flooring, flooring to get the index will give a, like a uniform sampling of like the integer indices, as long as we just prevent the like, basically, zero probability case of it being exactly equal to length of strings, right? And so in that case, we just like we do for like, yeah, I guess we can say like, it index is just like, like minus one. And then do this. So. So now like, now, index should be a random number in like, zero to the length minus one, which is what we want. So, yeah, I think that should be, it should be every step.

Orange Malamute: Can you go through your code with an example?

Verdant Gyroscope: Yeah. So like, if we were going to put in the pre insert, like, on the string, like a, then that would cause like, add a, because strings to index to be like a to zero. And I guess like strings array will just contain and then if we like added a again, it would do the same thing. But yeah, to walk through the code, like what would happen in the code? Like, well, yeah, obviously. So do what assert that would be it would, it would the system and would return true because a in the first case isn't previously in the in the map. And so it would append a to the end of the array, which is why we get this and it would set it would said like it would map a to length of the array minus one, so one minus one, which is zero. So that's why we get this. And then the second case, it wouldn't change anything because this if statement would item, like a is now in the key set of strings index. So this will just give in the method wouldn't do anything. And then like we added another one. Like the same reasoning, it would not be in the map in the map so dependent, and then it would the to minus one, one. And then so I guess like if we removed being or sorry if we removed a whopping budget. So what it would do first, like I guess I'll just double check with an arrow. So it first would set the array to be to be this and then it would pop off the end and set it like this. And it would just remove it would set the index of B to be what the index of a was so zero and it would just remove a. So now we have basically the same thing as for like a, but it's a, b is the only element. And then I'll just like go to the sample like, I guess, before, just to show the sample it would say, like, index is random in, in like this range. And then like, index in. So in this case, this is like zero to two, index is random in zero to one for, like the integers. And so we like randomly to between A and B pushes the desired functionality in that case.

Orange Malamute: Okay, cool. Yeah, thanks. So those are, those are my two questions. And I've left some feedback in the notes. But I'd like to go over my feedback quickly. Okay. So for the first question to do with finding the start and end of where an integer appears. And you're very knowledgeable about time complexities and binary search. And you like to problem solving style where you put you, you flesh out the high level approach, you put pass everywhere you refactoring to help. We, you're able to talk through trade offs. So like when you were trying to put optimization which wouldn't produce complexity, but what make it faster? We talked through it. But something I noticed about that question and this question, as well as you need to be a bit more ruthless about how much time you have. So once you identify the solution, which targets are given computational complexity, and the interviewer agrees with you, for optimizations, I would defer, you can even leave to do comments in your code, and just be very, very focused on it. And avoid being sidetracked because he didn't have enough time in the first question to walk through with an example. But so, but still, you're able to talk through trade offs. And I liked how you were very concerned about whether pieces of code would terminate or not, or what invariants they had. I mean, especially for on screen, the first question did very well. And then the second question to do with sufficient sampler. You talk through a lot of different interesting proposals I liked, I liked your tree approach. And with the especially keeping track of the number of children nodes, and then using random sampling, that was the first time I've heard that it's clever, but try to focus on the problem statement. Often this will save you time. Pun intended, like it says all the operations must be constant time. So it's tricky, because in an in an on in interviews, yes, the interviewer is evaluating your knowledge of data structure is true. So I think the our discussion to do with the tree approach was very interesting for me. But the downside is it reduces your time for solving the problem, and then going through it with a test. Right? So I think you have very strong abilities to discuss different approaches and evaluate different time and space complexities. And you come up with very interesting algorithms, but use the problem statement to focus only on a subset of approaches that are acceptable. And don't try to use it as an opportunity to boast about your knowledge. Right. That said, like, there was one point where we were discussing how lists are implemented in Python. And your explanation was to actually, my knowledge of lists in Python might not be what I thought it was, I think I left a note saying you're wrong. I think I was wrong. But so I have two comments about that. One is when be very familiar with how data structures are implemented in your chosen language, whichever it is, but at the same time, I wouldn't focus on it, even if the interviewer wants to draw you into into a discussion, like the swap and pop approach. Like whether whether the underlying array, data structure decreases in memory or only increases in memory. It's not important, but I thought, I guess with both the questions, focus on computational complexity of the data structures and know how they're implemented, but don't focus on it in the interview, if that makes sense.

Verdant Gyroscope: Okay. Yeah, I, to be honest, I missed that, that it has been cut some time. So that's something that I guess is, you know, more carefully read the question. Like, I guess once I understood, like the operations that I wanted, I assumed that I understood the question, but yeah, I guess that constraint that had to be in constant time definitely would have saved me time from, you know, not having to consider that tree. Possibility. So, and then, yeah, with, with the list, I guess. I did feel like I was kind of not making the clearest explanation of that. But I guess the way I'm, the way I think about this in Python is just as ArrayList in Java, like...

Orange Malamute: That's exactly the way I think of it. I was doing research. It's not exactly the same as a arraylist. And like, even as I'm saying, this, it's like, especially for a phone screen, don't get drawn into it. For an onsite it's different for a phone screen. It's like, Ha, how are lists in Python implemented? Don't get drawn into it, just, you know, come across this polite, but just try to say like, Listen, you know, I'm, let's just would it be okay to assume that removing an element from the end of the list is, is oh, one time, and then it's more time, like, you know, it's a more time to grow an array? Because I think I think it's the same as Java. The more it's a, you have very strong knowledge, and you're able to use it to have interesting discussions, but it reduces your time to deliver working code, and then to walk through it with an example. Right? Your approach is to have to explain the time and space complexities ahead of time. And that's fine, too. But something the interviewer is trying to check off in their mind is, do I have code I can copy paste into an internal tool? Did they give me time and space complexities to do a walk through it with an example that they go through edge cases? And so like, that's, that's the checklist they're going through? Okay.

Verdant Gyroscope: All right. Well, yeah, that makes sense. Thank you. Thank you for the feedback. I definitely felt like I, I got a lot of new knowledge that I hadn't had before from this interview, like as far as like practices, interviewing practices, and companies and all these feedback items are very helpful. So thank you.

Orange Malamute: You're welcome. Yeah, I think your preparation is definitely on track. Definitely. Go for the elements of programming interviews, book, definitely. Do some behavioral interviews, maybe at least to the Cracking the Coding Interview, he has an excellent explanation of how to prepare for them. So use that first and then do one or two practice and interviewing.io. And don't worry about...

Verdant Gyroscope: Sorry, don't worry about what a system design. Okay. Yeah. All right. Yeah, that makes sense. Thank you.

Orange Malamute: You're welcome. Okay. Have a good day.

Verdant Gyroscope: All right. Yeah. Have a good day.