Приятного просмотра

Technical interview with a Google engineer

Опубликовано: 6 месяцев назад
395 423 просмотров
👎 139
Скопируйте и вставте на Ваш сайт

Описание

Check out the feedback by the Google interviewer and the full transcript on
This is a recording of a mock interview in Java by a senior Google engineer on . Interviewing.io offers senior engineers free, anonymous technical interview practice with engineers from Facebook, Google, and more.

Субтитры

Oh hi hi how's it going good how are you doing good doing good yeah I've been here you for sex so I I just wrote this on the on the screen there um have you ever used the platform before yes a couple of times okay so then then I guess you're familiar with how it all works and so then I'm just going to jump straight into a coding question all right.

So first question is have you are you familiar with the concept of order statistics if you heard that that term before no okay it's actually it's a very simple thing with a overly complicated name so so given a unordered set of numbers like what I've written here the order statistics are like the int the elements in the list if it were sorted so like.

The like the first smallest number in this list is going to be one and then the second smallest number is two and then basically the order because of the order the nth order statistic is then the end smallest some exams because this is a bad set of numbers to have chosen so then this makes it a little more clear all right so we're just going to have some algorithmic questions about.

Finding some of these order statistics and just to get started with sort of a warm-up problem how about if I if you write a function that given a list of numbers that are out of order you just find the smallest so basically the the first order statistic okay sounds good so I'll just declare it here I'm.

Ecstatic insist the return and then I'll just call it a min yep and that's taken I'll call it n all right so then here oh yeah okay yeah this will be like a right yeah yep yeah okay no what okay so then I'll loop through the array and then for each of those iterations I'll compare it against a men that I've already set up so I'll set the men to be ARR zero and so what should I return if the array is.

No or if there's no values don't worry about that case where well we'll just we'll just assume it always had some values in it well there's something um so then we'll set them into the first one and then going through if and then we can actually start okay yeah so then going through to moving through the array if the in the element at the index of I is greater or sorry less than min.

Then we make that the new min and then at the very end of the for loop your return yep so just to test it to make sure um I'll write a little test here sounds good oh and input is equal to let's see they're like two three dick should give us zero double here min input and let's try that done.

Oh I put it inside the for-loop okay all right there we go so it returns zero perfect and what's the what's the run time and Sal rhythm I don't then and is there any faster way that you can do it um for an unsorted array that I know of no correct okay so now you're definitely up the idea um now let's make this a little harder little trickier and how about you give me the.

Second smallest number okay so for the second smallest number um then I think what we would need to do is maintain two variables and then kind of check across both of them to see um like sort of like a larger min and a smaller min or something like that then you can check me if there's a number that's smaller if it's smaller than both of them then we'll put it into the smaller min and if.

It's only smaller than larger one then we can put it into the um the larger min the new larger Minh um so once again are we assuming that the arrays length is two or greater yes okay so then I'll just call this min two and we'll put this at the second element of the array and then here if the array is greater than the min does the very smallest one for the men become array at one and then.

Min to becomes minun well we'll do this for 7 min to should be set to min and then min is set to the new minimum and then um other five if the array element is less than min - oh okay so if it's less than min - whereas it's still greater than than one then this means that this should be set to um so then min - becomes the new element and then instead min becomes min.

2 min - becomes the array weight but what happened to min then oh sorry yeah maintains a missing yeah because if it's less than min - then men wants min 1 is still the smallest of them that should stay the same but min to get updated mm-hmm okay now let's look like this oh I have to return min to this time okay so this one should give me 3 oh sorry if you give me two okay there give.

Me two yep perfect okay yeah interesting kind of sync if there is trying to see if there's a corner case here with the fact does it does min - what if um yeah I guess what if these were the numbers here um kind of thing let's try those up so the number so should actually be three because three.

Is the second smallest yeah and do you do so min to get set to I guess I'm just looking at this Oh what if what if there were no oh because you because you start back at zero again and then you you flip it all around I got it okay yeah perfect okay and what's the runtime of this one this one is still open okay so let's just say that we're.

Because he might be guess we're going to want to move this and and turn it into N so we're going to want to add another another parameter here that says I want to find that the end smallest now one way you could do it is you could just expand on this idea and you could just create sort of a list of all of the mins up to up to n right now what would the runtime of that algorithm be um well if.

We're storing them all then we need to check across each of them each time so the runtime would become N squared since we're running through all of the previous values every time most of you up here right yep okay so so the first so to get the zero if or the the first you it just to go of 100 of n to get to to go of n but now if you expand this in that same sort of pattern it actually.

Becomes OV n squared so there a way that you can improve on that Oh of N squared time all right let's see um so maybe there's a way where it is oh absolutely yeah I think one way to improve would just be a sort the array and then that would make it n login immediately and then all you have to do is find is the end index in the sorted array yeah okay perfect now.

Here's the real challenge can we do better than n log in for for any arbitrary I guess I guess I give this the wrong the wrong letter for any arbitrary M that we're trying to find so so we saw that when M is 1 we can do it in end time when M is 2 we can still do to them in time you think that there's a way that you could extrapolate on that sort of pattern and say oh I can just.

Always do it in n time no matter which one of these I'm trying to find all right so the reason why we should do it in event time for its N equals 1 is because we could just go through and compare them all and see whichever one is the smallest and for N equals 2 we had to compare it with each of them and also the previous minimum um without having a compared to all the previous.

Minimum I'm trying to think if there's a way to figure out the nth moment if we delete turn object but then that wouldn't help either because if we go through but if you did if you delete with so it certainly it's tricky so if if you get stuck I have some have some hints for you yes I would appreciate a hint okay so what so you mentioned the.

The n log in case of sorting and and then just picking the the M item in the in the list so in that sense you know once we sort this input when you have two three five six and then let's say your M is is three basically you just go straight to the five right and you know that five is in the correct place and that it is that everything to the left is below it and everything to the right.

Is above it and it's in position number three so that means it's necessarily correct now what you've also done and actually if we expand this out just a little bit more then um guess I could just do this and what you can see is and 15 into one so you had that this number five is in the correct position but also every single other number is also in the correct.

Position so you've also done work to make sure that the three is in the second position and the two is in the first position and the ten is in the fifth position and you put them all in the right places even though at the end of the day all you really cared about was that that five was in the right place because whatever order any of these other ones are in it doesn't.

Really matter you don't really care because you're only interested in this one right okay that's interesting so basically we're looking for a way to ensure that a certain value is in a certain spot but all the other values don't have to be sorted correct and the one that we want to be in the right place is a TM index right so if we did this for the first minimum then.

Basically we would have to go through each of the elements and then put all the ones that are larger than a certain minimum to the right of it so that it would be at the beginning so basically we have to go through and figure out like how many numbers are lower than that number and how many numbers are larger than that number so right what if we do that then is it like maybe there's.

Some way that we can balance so say we want and to be um to like in this case where the index is 2 that means that we want two numbers to be less than the one at em and then four numbers to be to the right so then maybe we can sort of like choose um some somehow there should be a way where we can go through and figure out and make it balanced so that it's like um equal on both sides even though.

Those aren't sorted um but we would need to know what's the number five already is in to go through and actually put that in this right spot so there needs to be a way where we can figure that out without knowing five right yeah and if we just chose a random number or went one by one like we did here then it wouldn't work because then we would still go back to.

Being N squared we just still have to go through all the numbers see which one was right right but let's let's take a look at that that example that that you had just said that you just talked about saying you you kind of describe this process where you take this input array you take the first number that you found and you made sure that it went in the right spot right so you you described a.

Process of saying take this number three and put it that just that one number where it goes so that everything to the left is less than it and everything to the right is greater than that okay load up a binary search tree um yeah I mean so there's that that's that's kind of a part of it but so so describe how you might how you might do that how would you find it so just given I mean you.

Don't really have much information about this this array coming into it because it's unsorted it could be in any order so you might as well just start with the first number you find and say I'm just going to find I'm just going to put that first one where it belongs and then I'll tackle the rest of the problem after that so you know for example you can think of what it would look like.

Afterwards would be twenty one and fifteen so you can imagine that this might be what the array would look like after you found the the first place so so three goes in this spot and everything to the left is less than three and everything to the right is greater than three and you still don't really know about what's what's going on on either side and you.

Haven't really sorted it altogether but you do know that three is in the right spot mm-hmm so does this then give you some additional information in terms of now trying to like where would you proceed from here so so keep in mind that like we're still looking for the third largest number and you just figured out that the number three goes in position number one so then I know.

That the number three is the second largest number and at this point I would have enough information to find the third largest number using the technique that I just did before where if I know the previous minimum then I just have to run through the array one more time to find the next minimum right that's true but in the and and what which part of that array would you run that algorithm.

On the whole thing or a part of it all right because the right is a part that's unsorted right well actually in a sense that the left is also unsorted kind of because we don't really have any any guarantees about what's going on to the to the left I mean in this case in this case you do because it's only one element so there's not really much sorting to do but what what else is is.

An interesting property so now that you have this three that's in the right spot what do you know about like in terms of what you're looking for are you interested in anything on the left or you interested on anything on the right or are you interested in both sides well right now looking at this array I would be interested in the right since this the three and only.

Element at index one but we're looking for is index three mm-hmm but in terms of ordering what we're looking for and since hmm but the two could be two five two like what if what if there was a five years of the two but then yeah it could be it couldn't be because you've already you you've sort of you split this this.

Array up maybe I wasn't clear in exactly the the the thing that I did but if I let me let me start by just kind of like rearranging this a little bit more and making it kind of a little more random and then and then sort of all I'll do oh I'll do it again so so given and I guess you've been talking about a sort of M gamma okay you just keep this the way the way it is but so so you start with.

This ten and you first make sure that everything on your left is less than ten and everything in your right is greater than 10 so this might look like this 2 5 6 3 10 15 11 so you've just kind of you've shifted things around but you've shifted them around and in a way so that everything on the left is less than 10 and everything on the right is greater than 10 so it's not just that you found.

That the one right place for it but you've done a little bit extra to to make sure that you sort of you split the array in two pieces yeah so this is actually pretty helpful because if the 10 is over here and this is one zero one two three fourth index and we know that M has to be to the left of it so we don't really need to worry to.

The right anymore because those are greater than ten anyway exactly so so then when you when you repeat this and you you sort of go for another iteration of it you're only going to be looking at the left side right yeah yeah okay so does that give you some ideas about how how this might how this algorithm might might work yeah it does um yeah because then in the first time around I'm.

Iterating through all the numbers to find where it belongs and then the second time around I'm only iterating through the left side so this kind of reminds me a little bit of like binary search so maybe the run times will also get a little bit better than N squared when we do it this way okay all right so all should I start implementing it then yeah let's see what.

Happens all right so we're outputting just the number this time again okay and this is the N smallest okay so first what we have to do is um so I'm just going to write the code for the first time and then we can probably iterate through and make that repeat so the first time around I'll have to go through the entire array and then so.

I'll have to select so if I look at the first one I'll have to put it in the right spot so then I'll take I'll take sort of like int index to the place I'll just call it index is let's say I M or actually yeah if we make it zero actually before the array before this loop and we're looking for so this looks that we're going through them and then if we say that if the item at that index.

Is less than or if it's greater than whatever is there then we need to move it to the right so kind of like swap it yeah Sophia written X is greater than all right I then we need to do some walking here so just to make things should I just kind of abbreviate it and just write swap here or do you want me to write the whole swap um you can just write 12:16 okay and then.

Well actually I'm going to need to test it later so I might as well just do it now never mind um so then we'll write in temp uh array at I and D all right at I move to or index and a right index is equal to temp so this switches them around if it's greater than um but if it's less than and essentially we need to well we just.

Need to keep moving actually so we don't want to do anything there but if they're equal to each other then we stop yeah so if the array index is greater than wait did I do this right let's see so we start with index equals zero and if it's some greater than okay there's a problem here because if it's starting with the first one then it'll just stop immediately since its equal to the same.

One um so then we'll start at the first here hmm yeah so then if okay so if we start with the first one then first so index is equal to zero and the first element is 10 and then it checks to see at array at 1 which is 2 and 10 is greater than 2 so then it's Squa and now it's 2 and then 10 and then it compares it again 5 10 is.

Greater than 5 so it's flop 6 6 is greater than 5 2 swaps and then it looks at 11 and they are okay so this brace now because it'll stop since its greater than but it needs to continue and look for that 3 wait it wouldn't rate if so those two numbers don't equal each oh so that way so the triumph is equal oh yeah so what did it stop but it still needs to well yeah so nevermind yeah it would.

Stay there and then it was going through and then check again 3 and then now that is less than 3 it'll swap with that one instead and then 10 will be where the 3 was and then it will check again 15 is greater than so it'll stay there and that puts it we've been s not ready oh wait so that would that would actually work for this specific input.

But think about what would happen if the input was something like this so you know you first swap the 10 with the - so that's right and then you swap the 10 with a 5 which is which is totally ride many stops of 10 with a 6 then you leave that then you swap the 3 with the 10 so that's cool and then you swap the 0 with the 10 yeah that's not that's not right quite.

Right because when you skipped over the 11 now you have something on the left that is bigger than it should be so then I think maybe we have to move the 11 along with the 10 now every time um so maybe we can swap the 11 with whatever next to it so that it keeps like sort of moving away swap the 11 so so you had this point where you had the 10 and the 0 is like this but then then what were.

You going to do now it 1 1201 11 know if ya know it's like the pen was here mm-hmm what was here before 303 m yeah and then you would check the 10 in the 11 and then since 11th grade you could swap it away so that it goes - yeah you could just actually just swap it with like the end of the array so then this becomes 0 and this becomes 11.

Mmmmmm your weak ties against the zero is greater than and then it's swap and then you check the ten and the three eighth grader so it's luck okay so then presumably if there was another number that was greater than ten you would swap it so like so we had it here that was like ten eleven so we're sort of looking at the ten now um three and we had a 15 so then it was first.

Compared to ten eleven and then it was okay now I see what you're saying then once if it swaps there and we'll just skip over and it wouldn't work so so but you have another might drag like this is this is definitely the kind of sort of manipulating that year that you're going to want to be doing in this in this array so and indefinitely the like you're definitely right track with.

Respect to looking at you know when you when you started with this number ten and you're looking at each one of these numbers as you're going is you're going up and as long as it's less than then you know you're you're sort of keeping it to the left and as long as it's greater than you're keeping it to the right so that's kind of its kind of how you're sort of scanning this list of.

Numbers so can you think of a way and yet so you didn't do this one sort of problematic case that when you start to have multiple numbers that are bigger then it gets kind of tough with how do you deal with the how do you deal with the sort of bookkeeping of where where does it go who can you swap it with yeah I can think of one way to solve that which would be to just create another.

Array and then if it's less than forever we want we put it into the beginning of the array and hold to sort of like counters for where the beginning of the array and then where the end of the array and then if the number is larger we add it to the end until there's only one spot left and enough to where the tenth has to go that's a good way to do it.

All right so then I'll try to implement that instead I'm stupid okay so then we have namo two counters so inch starts is equal to zero and intend is equal to the array dot length and then we loop through and so we know the number that we're looking for so I'll just yeah I'll put that in as yeah actually yeah I'll just put that in this index again and then that will.

Start at zero this time and then so basically if the number that we looked at we looking at that we're looking at right now which is array at I is less than the array at index then we put it to the right so then we have this new arrays that have to create and that's the same length and then if the array is less than the array index then it should go in the.

Beginning so then it does in at start oh sorry what do I call it no all right noria start becomes a right index and then we have to do start plus plus to show that we've added an element and then if the all right I wait sorry is it a so so in this line here you set array the numerators start is array of index yeah is it indexed or is the value.

Oh sorry yeah Susan who's different name okay um and then are there any duplicates in this array or no let's just say no for that okay so if there's no duplication any other element we look at cannot be the one that we're searching for so then we can just do an else here and then this basically says that the array up I is now greater than.

What we're looking for so it needs to go to the right so then it goes to new array at n is equal to the array at index yeah wait no I I made a mistake okay and then um do n minus minus and then this loop has to this have to end whenever um start and end are one apart from each other because then that means that we found if we have found our index.

Then out is doing it so it's start - or n - start is equal to 1 then we return start plus 1 all right so I think it should work for just for the first one to place it the right spot so let's try it uh oh I see so this is going to be sort of a so I think you're like we're turning the number right away but I I'm wondering so this this is going to return not the end.

Smallest but this is going to return some smallest that the you're basically going to return wait actually the index you're returning which position the first element will have gone - yeah yeah I just wanted to break down the problem I want it he's got good okay so in this just this is the ring um I'm not actually sure where this so the two three five six so.

It's getting for input and and them yeah it's not you don't even use them so Oh interesting question so when will end minus start equal one and what so this line here number 42 when when will this be true um and - start will be one when we've gone through all the elements of the array and now we're looking at that one empty space where the element should go.

Okay so if that's going to happen once you're already completed with this array is it is this ever going to be seen oh yeah you're right um you can just recognize those and then start six out of bounds oh it have to end up my okay zero one two three four I think actually because you incremented starts right here you don't increment start there I think.

That's what yeah all right let me try with another mm-hmm just make sure so now please deleted one of these then it should become she come three deadly yeah okay alright so now I have the functionality for figuring out the spot where one specific element should go but I have to pretend wherever the element at the MS index is so essentially this um this whole start.

If it starts is M then we know that we found our element right but but the thing is this index um have to change every time so I'm thinking maybe we can sort of do this like a binary search where we choose like the middle like the middle number in each half and then we try to put that where it belong and then if and then if M is greater than the index there then we run it on the right.

Half and if M is less than then we can run it on the left half so good ok so then here we'll start with instead of zero we'll do start + + / - here okay and then SB so then looking at the edges we the index is is representative of the num of the index of the number you're comparing everything way that's right so in that sense you know index represented this number 10 here is it does it get.

You anything to pick them number in the middle like this this number here is the number in the middle does that one really I mean does it really matter whether I mean remember this is an unsorted array does it really matter that you take index 0 or you take index start + end/2 no is it yeah it's not going to really be that it's it's going to be 5050 right.

It's not going to be exactly in the middle dinner and there's kind of no way to tell where like how well this number that you're picking at random is going to split this array into so I mean you can you can you can do that but I think starting with index 0 is a totally reasonable way to go because at this point you know it's just a random array there's no order so you might as well.

Just pick any anything and and then um go from there yeah yeah I think that's fine we can use 0 then um yeah and then I think we can actually make this recursive to maybe do a little less work where once we find where the UM the spot that an extra go then will determine whether n is on the right or left and then we will again do it but actually that might be ler yeah I think that.

Might be one way of implementing it because then we can always keep index as zero because then the array that we're looking at is now um like a sub array so the index will always be zero or women's we could do this just have these arcs that start and then move through an and kind of just keep doing it with a new start and end that would be another way of doing so yeah or we could just.

Like make a new parameter here for starting and and then implement as recursive so there's like multiple waitresses crisco so I like your recursive idea because it's definitely going to make the code a little bit simpler do you actually need to add more parameters here if you do it as a as a recursive algorithm no I don't have to if I change the array and I don't have.

To mm-hmm yeah I'm just wondering like that would still take up more memory because technically like I would have to come somehow cut off here right going too far so I'll just leave it like this and I'll probably send it in some sub array mm-hmm okay okay so you're using index zero and then at the end of this we're returning start which ends up being the index of whatever element is.

At zero do permanent if M is greater than or less than start so if M is greater than start let me know we need to redo this on the right side of the array so then we should warm and Palace on actually forgot the method for sub arrays in Java think yeah I'm just looking on the I think there's a thing called range Oh subset chill dude subsequent copy of range I mean you.

Could just use copy of range if you want to do it's not that bad so it's um actually I got yeah there was a code completion on here and it says that it's a method so just use that Ben so clearly okay yeah so then the original would be arr and then from I'm assuming that the firm is inclusive so then we would use start plus one because start we've already.

Looked at and that's the one good that we found and then uh and then the end would just still be end mm-hmm and then we can delete that and then here would be the other way around so if we have and smallest then it would be array and then instead of start plus one this would be zero and this would be just start and then else that means that M is equal to start which means that we.

Found the elements at the end X what we want so we just return start okay thanks now n smallest actually takes two parameter right so then n minus need to add in is it M because that's relative to the entire the entire it would go for it yes right so if the um so if the M that we're looking for is greater than start then it would need to be M minus start and then its element that we're.

Looking for is uh oh wait I mess it up so if M is less and start then now we're looking for still M yeah okay um so now like all right I'm going to test this now to see if there's any issues let's just see if we give zero as em then we should still get back ten so let's just see those get three so three is the smallest three is the the.

Smallest one oh yeah yeah so then it should give that reason okay um I get on YouTube again afford this is it raise uh java.util Oh Shelby you tone oh as the lowercase C oh I don't see what happened now I'm missing your return statement because you're you don't have returned in in these ones wait which one are they looking at so 52 and 54 you know that you're just.

You're calculating it without returning it alright now it's giving me zero which that wasn't even in the input array so the index oh I wonder will you that's still not right all right definitely magic looks right I'm guessing there must be some kind of off by one bug so we already figured out that with this list and you go the first time start equals oh yeah wait start was was three.

Before so it should have put it in the so maybe there's some need to do some debugging with the with some print statements to see because yeah definitely the the logic here is looking solid maybe here I'll just print the help a new array.

Okay so the new array the first time oh I think it's because I know that's not it so 5 6 3 15 11 10 interesting that you have the 10 in there so in that sense I think you want your your new array to be one element smaller so if you see what's happening here is that you started with index 0 and then you're also checking index 0 again and really or the size is.

Going to be one left because you're kind of taking one out right and then sort of partitioning it after you've taken that one out so then yeah so then now there might be so now now that you've like reduced the size by a little bit now you have to make up for that in when you make this copy well that wouldn't be affected by the newer right with it cuz the new array okay oh well see so now.

The end actually has to be array of length minus two so right you have to you have to start the because the end is actually the end of new array dot length minus one is ice oh right well it's the initial array minus one so it's like the ending but then in a new array um it's not so in the new array so although I mean you you're you're placing these you're.

Placing these these cut you're cutting these values over into the new array so the not ready HAP's - yeah all I'm going to do is for a that length here because the end is not actually the end it's just starts - but what I'm I'm looking at 38 here oh yeah so that end is actually the end of new array length minus 1 which is array the.

Original array of length minus 2 okay and then in this one you're not actually copying the original array you want to copy the new array because the original array is like totally out of order a new array is the one that yeah and and also you have made the new array dot length okay I get it a new array has to be smaller yeah wait why didn't ya it should be no it's.

Not including those in the numbers right so in this one and you want to just copy to the new array dot lang ah well no worry that nice would include the values above it wouldn't it well new array dot length is the the end it's the end of the of them to array and you're trying to copy like from from your position all the way to the end oh yeah.

Then here um there's still something wrong besides of newarray wait wait you can try running again what's wrong sighs again now 46 you're right yeah oh no this one here wait you had just changed it 38 oh you were just changed again so this should be at yeah or you could also just set and underneath the new array or you could you could move this one up and.

Just say end is new array dot length minus one either way it's the same number oh and then this should meet yeah okay and still AR don't lines minus one is this one similar okay no three okay yeah that's actually right there it is not bad no and I try to do numbers too so if we try like one then that should give us five no close all right um yeah I think there must be I'm.

Guessing there's there's like an off by one like my guess is is off by one in either in this M minus start or this M here or the zero to start or what this I'm guessing there's like a tiny little off by one bug in there somewhere which is not a big deal just cuz we're running a little bit short on time so you definitely you did all work and now you are you're inspecting less and.

Smaller and smaller pieces of the array as you workers into it what is the runtime of this algorithm okay so the question is is that you did always work and and or there's always extra code to like be careful not to do any more work than you need to so the question is has this actually sped it up or is it still and login or is it even greater than well I think um well I.

Think it depends on the case because thanks for example if this array was like sorted in backwards order basically this one that wasn't that would be two to the end and that is really backside amends the person to the end big one and if there was zero then we'd have to keep going through that array over and over and so we basically be looking at the entire arena see one two three four five.

Six will be six plus five plus four plus three plus two plus one which in the end still comes out to O of N squared so I think it's been worse our new algorithm is still enough okay but what about it and say the average case like what is you know for example you you randomized like that that's sort of a common thing that people do with these kinds of divide and conquer algorithms is that if.

There is kind of a like a poisonous input then you just kind of randomize it to make sure that it's there's no that it's just going to be kind of in this big ol jumbled order so what can we expect sort of on the average case you're totally right there is a there's a worst case input that makes it N squared but what can we generally expect this to to be in the average case um I.

Think this is no n log n then because we're looking at the first time wait actually uh well the first time so in the average case it would be like we're looking at half the array since then it wouldn't be too much and it would be too little so the first time increases then what now what happened haxe then actually look at six and then three and then one which is like n log n.

I would say close so typing a book among the end smallest so so the first time you run through this in the first iteration you have n elements that you're going over and then like you said you break it down by half and then the next time you you just go over the N over two right and then the next one is n over four and over a etc so what is that we're going to add up to UM is it.

Uh oh you know it's just um it's just n right yes becomes n okay yeah so you did it you got it you got it down from n log n to n and the the trick is that when you do the sort you you will you have this having that you do each time but you keep doing more and more work so and over four plus eight times marking every one increased in the.

Sorting yeah so so when you do a sort you split it in half and then you you do both sides and so even though it's getting smaller and smaller you have more and more of them that you have to kind of deal with and so and the the the length of this is is log n so like the number of of iterations is log in and so then that's why it becomes in log n but in your case you don't like.

You don't have this ever increasing coefficients on the in front of it and so it just adds up to 2 to N and it's bounded so you got it very good alright thank you it's really interesting yeah I'm glad glad you liked it yeah so for so I'll leave some comments and stuff on the platform but just before we go if you have any questions.

For me about interviewing or anything else I'd be happy to answer them I think I myself feedback on it ok awesome then then you'd have a good night and good luck with all of your future breakfast realms thank you have I guess the way

Комментарии

Iulian George • 11 часов назад
I'm lazy. What i would do to get the min is arr.sort() then return arr[0];
👍 0
Toasty • 4 дня назад
If you have not learned the quick sort algorithm by the time you are applying for google, you need to go back to school or get your money back lol.
👍 1
vidy • 6 дней назад
sort the algorithm in ascending order and look for index n-1 to find the nth smallest in the list… anyone? what am i missing?
👍 0
Hindu S • 5 дней назад
+Zeyu Wang they want to do that in an interview? something that research teams take semesters?
👍 0
Zeyu Wang • 5 дней назад
They are looking for a better run time than the best sorting run time... so they are looking for a method with run time lower than O(nlogn)
👍 0
Vikas Gupta • 6 дней назад
FIrst, I would be surprised to know that the interviewer's name is 'Intergalactic avenger' & the interviewee is 'Supersonic Taco'. Hahahaah Kinda cool.
👍 1
Teri Beckham • 6 дней назад
+Vikas Gupta Yes, follow the link below the video.
👍 0
Vikas Gupta • 6 дней назад
+Teri Beckham or is it someone's idea to create a channel like this?
Where they can discuss the questions asked in technical rounds and help young minds.
Isn't?
👍 0
Teri Beckham • 6 дней назад
It is an anonymous platform.
👍 0
Kazuko Mahar English-train • 7 дней назад
That's would be really exiting to hear those.
👍 0
Remario Richards • 8 дней назад
What about just using a min heap , and pull N amount of min elements. The last element pulled is the m smallest. Worst case should be O(N) for building the heap and O(N) for largest m search.
👍 0
Ahmed Mansour • 8 дней назад
why tf is the interviewer eating and a F*** chewing sound is on the mic?
👍 0
Z J Hu • 8 дней назад
Curious to know if the interviewee got into the 2nd round? Just in sense of the time complexity...
👍 3
Tom Whitcombe • 4 дня назад

Yup
👍 0
steelpanther88 • 9 дней назад
I was doing this in C++, and I think I may have found a small improvement to the classic sort-all and select strategy.
Please critique if you have any thoughts also.
general principle:
1.) corner cases when k<= 0 or k>vector.size() return -1 because illegal k value[ time complexity should be constant]
2.) from ind0 to and including k, sort the subarray with quicksort,[quicksort time complexity with the subarray size.]
3.) make that ind(k) as candidate min
4.) iterate from ind(k+1) until the end and check if the looped vector value is smaller than candidate min,[need to check rest of the array]
5.) if you find smaller than candidate min, make a binary search into the already sorted subarray on the lefthandside of the array, and then you need to insert that new candidate min into the index indicated by binary search. (this was a little tricky in C++
because the default binary search sucks and I just used lower_bound I think.). This can give bad memory performance at least in C++ because if you insert into the middle then vectors have to shift the elements forward I think...
6.)return the candidate min.
7.) probably it will not give a huge boost in performance, but something that I thought about...???
👍 0
steelpanther88 • 9 дней назад
wow apparently I was wrong also that this is not best case... allegedly it should be possible to get k-smallest in O(N) for average case
👍 0
steelpanther88 • 9 дней назад
hmm... I may have made some off-by-one error in that description because I used iterators mainly for the sort subarray and lower_bound, but that was still my general principle. I also had it so that k=1 smallest is a separate special case where I just find the minimum, and general principle starts for the k=2
👍 0
khalid alhussein • 9 дней назад
what a fancy and complicated way to ask the interviewee to find the minimum number in an array.....
👍 0
P Y • 10 дней назад
If he wanted to ask her to write a quick select little by little, but, the interviewer, just did not know what is a quick select.
👍 0
P Y • 11 дней назад
This is painful to watch... Before watching this, I thought everyone knows what is a quick select how does it make a quick sort happen....
👍 1
David Fogarty • 13 дней назад
I think it’s pretty awesome that the interviewee’s name (top-left corner) is Supersonic Taco lol
👍 0
L Wave • 13 дней назад
Simply a randomized variant of quicksort🤔
👍 1
Scott Sun • 14 дней назад
I have an interview 4 days from now.. think makes me dying inside...
👍 1
Scott Sun • 8 дней назад
Nothing I think I did okay. The first question was a string manipulation question, which was pretty easy. The second question was a binary tree question, which was much more challenging than the first one. I figured out both so feel like I did well. They said I will hear back within 10 days for the result 🤞🤞🤞
👍 1
Scott Sun • 8 дней назад
Anthony Martinez Haven’t tried that one yet. Mainly used leetcode but I’ll check it out!
👍 0
Nothing • 10 дней назад
How did it go :D
👍 0
Anthony Martinez • 12 дней назад
Good luck! You got this. Also tryout firecode.io , I like that one .
👍 0
kirualex • 22 дня назад
Pretty interesting problem actually. Took me a few minutes before seeing that it screamed recursion.
Here's my solution (in ruby) :
def self.min(nth, arr)
curMin = Float::INFINITY
arr.each_with_index do |item, i|
if item < curMin
curMin = item
end
end
arr.delete(curMin)
return (nth == 1) ? curMin : self.min(nth - 1, arr)
end
👍 0
Eric Chen • 22 дня назад
I would terminate the interview in 2 mins, if an interviewee does not even know Quick Select algorithm O (n) for n-th smallest number.
👍 0
Harshit Gupta • 22 дня назад
This can be done using Max Heap in O(n) time. Right?
👍 0
Dmitry Chernivetsky • 22 дня назад
Sort it! Sort it! Radix sort O(n+k)
👍 0
John Michael Garrido • 23 дня назад
People freaking out about someone eating on a call, and I'm just confused about why it bothers them so much. I personally wouldn't do it, but if I can understand what you're saying and we're doing what we need to get done, you could be rock-climbing and I couldn't care less.
I've had some of the best phone meetings with a person biking around the city on the other end. We have something to get done, and if you are able to do it in your current state, then by all means.
👍 0