Wait here.

Now today is going to be a technical topic.

We're going to go through three hard coating interview questions.

So these are going to be white boarding questions that top tier tech companies like Facebook, Google, those same companies that they may ask you specifically, we're going to take a look at some of the harder questions.

The bar raised questions, so don't feel too bad if you don't get them.

And if you're not much of a program with an, you could listen in.

Or this may not be all that interesting to you because we are going to be doing some coaching here.

So here's the first question, and it is known as auto completion.

This is a question that I used to ask that Google.

Occasionally you're given a perfect and the list of words, and you need to return all of the potential words that would match this.

So, for example, if you have t o with the potential worse that this can also complete to our dog door and the Dutch.

So then the opera that you want to return is going to be an array dock door and Dutch.

So that's the question.

Feel free to pause now if you want to think about that, otherwise we will get to the solution.

Quick pause.

This video, sponsored by brilliant, brilliant, helps people achieve their learning goes.

So whether you're a student or professional brushing up, we're learning, Cut the edges goes.

Or if you're just curious to learn more about the world, they use your checkup.

Brilliant set.

Go to improve yourself and then work on that.

Go a little bit every day.

So check them out over at brilliant.

That work slash tech lead.

I get 20% off for the 1st 200 people.

All right, so let's get to the solution.

Well, one brute force technique is Listen, you're given this industry, Theo, and its size is K and you have an array of size.

And then what you need to do is you illiterate through each element of K, like your first take a look at the you mash up with all of the first matters in this array of size.

And you, under our other words, that don't start with the and then you go to the next letter in K and take a look at Oh, and you filter through everything here and essentially this will get you a solution, but the running time is going to be big o of K times and and that's okay, But I'm wondering if we can even make this faster And that's where we can use a tried a disrupter t r i E.

So the way the tragedy Destructor works is actually looks very similar to a standard tree.

You have a written up, and then you have letters at each other note.

So you have B, C O G.

And any time you have actual work, your market like hit, this is a work you may have a r k.

Here you have t o r so fast spells out the work door and then the oh, the g e for Dutch.

And so, essentially, once you have this tried a the structure built out, you'll be able to id rate through it.

Like if you're looking for d o you first traverse toe, try over to D o onto this note And then from here you run a death first search looking for all of this up knows that form a complete work, and those aren't the although completion results to return.

As for the time space analysis, well, there are really two steps here.

First, we need to get to this actual mood, and that's when to take O of K time, right?

And then from here, we need to reiterate through all of the potential words that can be formed.

The number of words are going to be a maximum of Oh, right, because we could potentially return every single result.

And Viggo is the worst case time complexity.

So this is going to be your planet complexity, and that's better than what we had previously, K Times said.

Space complexity is going to be.

The size of this tray is pretty much a weapon, which is the total size off the inputs.

Let's take a look at what the coat looks like.

So for the try, I'll start off by creating a know that they destructor.

Then I will create a solution class and I'm going to create the build function here and this is going to build the try.

Then we're going to have another method here called, although complete, which, given a prefix, it will return a set of words and let me come up with the driver function here.

And the answer that we're expecting is Dog Door and Dodge given this input.

So in order to build the try, what we really need to do and this is simple is we just iterated through all of the words and traverse the nose like a standard tree.

Creating them, if necessary, saw create a trance structure and then our trade through each word in the worst given and then from there, our trade through each character in each work.

And I have a current know that starts at the top of the try.

And so if their character is not in the current Children, then I will create it and then our Travers to that child at the end.

I will mark that current note as a word, and that should do it.

Okay.

And then, for the other completion, there are two portions.

The first half is we need to actually traverse to that sub note following the perfect.

So let's do that.

So I create current note starting at the top of the try and then for each character in the word I would just traverse.

So if the character doesn't actually exist, then we know that we couldn't find any words.

There was no match.

Otherwise, we're just going to move the current No, to the child that matches that character.

And then once we found that seven, though, that we need to perform with the first search.

So our brand new function find words from note, given the current note and the word.

And this is going to be a standard that for search function, which is something that you may want to practice.

And the return value of this function was going to be a set of words, right?

So initialized the set of force to nothing at first, and then we'll say work.

The note is actually a word.

Then we're at that.

And then we need to go through all of this up Children and add any words that we find from those look Children into this words array as well.

So for each character and then those Children, we will add recursive lee self doubt, final words from note given the child and the new prefix, which is the perfect plus that current charts.

So now if we were to run this program than Yes, we're seeing the answer.

Dog door, Dutch.

So that completes the first question.

What did you think?

Did you get it?

Oh, and by the way, if you're finding these problems helpful, then make sure to also check out my program code.

A pro dot com were ex Google ex Facebook engineers.

We run through over 100 of these coding top of white board and questions to make sure that you are well prepared for the coding, data, structures and algorithms portion of your technical interview.

We breeze you through all of these problems explaining them with complete time space complexity.

Analysis Bago notation in the way that top tier tech companies will accept.

So check that out over a code a pro dot com.

There'll be a discount for you in the description below.

All right, was that fun?

Are you getting the hang of this?

Let's move on to the second question.

This is known as cake largest number.

It is a fairly common question because there are so many different ways to solve it.

But I'll give you the rundown for if you've never heard of this one and then I look over some of the solutions for you.

So the way this world works is you're given an array of numbers.

5723416 They're not really sorted.

And you need to return the Cato largest number.

So given the index three, we want to find the third largest number.

So from here you can actually see well, seventh is the largest, then six and then five.

So the number we wanna return is five.

That's the question.

I'll give you a moment to think about that, and then we'll get into the solution.

All right, welcome back.

So let's go over the solutions.

Well, there's the brute force technique where you essentially it right through the array K.

A number of times where Caisse say three.

And that each generation you just remove the largest number from the array.

You can either make a copy of it or you could mutate the in place.

So in the brute force technique, it would be K times in because you're making que passes over an array of size and that is your time complexity.

Well, what's another technique?

Well, another one you can think about is.

Why don't we just sort this array so you could just sort it?

1234567 Once you've sorted that, you can simply return the array value at the index of the length of the array minus Kate.

And that reference is going to be constant time.

But sorting the array well, the fastest sort we have the same like quick sort that's going to take end, log and time.

So that's another technique.

But I wonder if we could go even faster and in fact we can.

And if your experience you would know that there is something called the heap data structure, so they keep they destructor.

It's a little bit of an obscure one, but it looks like a binary tree, and it maintains this constraint that the maximum or minimum value is going to be at the root of a tree.

And any time that you take off the top, Element is able to fight the next largest value, our smallest value in log rhythmic time, and set that up to the top well with the heap.

Generally, you'll be open to build it in linear time, and then once you've built it.

You need to get the case elements, so you need to run the pop operation K times, and each operation is going to take long of end time because it needs to traverse the height of the tree.

Generally, the height of that tree is going to be locked in.

That brings your total running time to over and plus O of K log in.

That's pretty decent, actually.

And if you were to solve this and write the code for this and generally, by the way we don't write the entire heap data structure, it's a little bit too complex for an entire interview setting.

So if you know how it works, I can explain the usually that's gonna be good enough.

You can use some buildings or classes or libraries for that, but if you were to do that, then that would be sufficient most of the time.

But there's actually even a faster way to do this.

I can't think about what that would be.

So if you think about that, the heap is actually doing some additional work because in addition to getting the Kate element, you're also getting the K minus one element became on the second element that came on this third element.

And essentially, you've sorted half of theory.

Perhaps by the time you found that case element, so we can actually avoid sorting a lot of this array by using a special technique known as partitioning.

So here's how partition works.

You pick a random number traditionally, you're just pick the last one and then you're going to partition around it.

You're going to keep track of an index at which you know this person off, the array is going to be sorted, and you're going to increment that index, making sure that each value you put in there as you increment and go is less than this current value.

So you take a look at five.

Is it less?

Yes, it is is fine.

So we're going to move the index forward and take a look at the next.

Value is seven less than six.

No, it's not.

So we're going to not touch that index and just continue on to the next value to is to lessen six.

It is.

So we're going to swap to with the value at the index so too soft with seven and then we moved The index fort moving on is three less than the index it is.

So we're going to stop again here.

And so in this manner, we're pushing that value seven all the way to the end of the array for also soft with seven here and then one will stop with seven.

And then at last Valley, we see six sixes not lessen itself.

So we leave that there.

And then the final step is we stopped that pivot value with the index at which we got to so six and seven stop here and in this manner, we have partitioned around that number six other numbers less than that are on one side out the numbers greater than there are on the other side.

And what's more, we can keep track of what value this index is that, like we know this is going to be at index five.

Actually, in the next step, we can continue to partition the other half of the array, and we can keep doing that until we get to the Cape Index.

So what's the time complexity of this?

Well, it's actually an algorithm that keeps subdividing so on the first pass, you go through every number and the second pass.

You've divided the array and to say, two different halves.

So it's only going to take in over two alterations.

Been an over four.

Been end over eight and so forth until as sympathetically.

If your toe add up these numbers, you would get off two of end, then your time.

Pretty much space complexity.

If you're doing this ed relatively, it's pretty much constant.

You're just keeping track of a few pointers and swapping valve use.

So let's take a look at what the code looks like.

Someone to start with a solution class this time and would define the function.

Find Kate largest given in the ray and index K, and here we're going to want to return some number, and then I'll come up with the driver function here, and we are expecting the value.

Five.

So there are two compliments here when there's a loop in which we keep subdividing the problem.

And then there's also another function partition in which are able to mutate the array.