Linear Search & Kata Setup

[00:00:00]
>> So we are now gonna jump into the A of algorithms. So we have defined our first kind of data type. We are gonna have that. And so again, JavaScript doesn't really have arrays in the sense that we want to have arrays. So I will treat a bracket like an array, it will come.

[00:00:17]
It will have a dot length property. And just to make it easier, I won't go full c neckbeard and require the length to be passed around and all that. But we'll just treat it as if it only has one thing, dot length. So as we program, we practice, keeping it a certain size and using it in a specific way.

[00:00:32]
I think it's a lot better to do it that way. It just is a good way to practice these algorithms. All right, so one big thing we're gonna be doing here is that we're gonna be visualizing all the problems first we're gonna be discussing it with circles and arrows, boxes and arrows and then we're going to program it.

[00:00:50]
We're gonna do a lot of data structures if possible. It's definitely a core competency. If you can get really good at this visualizing creating your problems first on a whiteboard, and then being able to translate abstraction into concreteness. It's going to follow you for the rest of your life.

[00:01:04]
It's an extremely good skill to have, and at this point often I can just think about it in my head in these terms, and I can just write out a program without doing the intermediate step, and it's a great skill to have, all right? So first, we're gonna start with search, because search is by far something that you do often, right?

[00:01:22]
I think everybody here has had to find some sort of value out of some data structure. So let's just start with the simplest form of search which is search on an array. And even moreso, we're gonna start with the even simplest version of search, which is a linear search.

[00:01:37]
So again, the first thing we do is we whiteboard this. So let's go over here, and do I have space for this? I think I have space for this, awesome. So if we have an array that's from 0 to n, and we want to find some sort of value, right?

[00:01:51]
So we have some sort of function called Search in which takes in an array and a value v. And we want to see is this in here. So the simplest form we can do is do a linear search. In other words, we go to 0 and say x0, are you v?

[00:02:08]
And if it says hey I'm v, we're like awesome. It's at position 0, else we'll do it again. X1, hey, are you v? Where's Mark? You are, awesome. Here you go. Now this may look very familiar because I bet who in here hasn't used index of? Wanna guess what index of is probably doing underneath the hood?

[00:02:31]
It's just walking linearly until it finds the thing. So, we are literally implementing, if you will, index of. It's the simplest form of any sort of search. Now before we do that, I think, do I have it as notes right here? Yeah, what is the Big O of this type of approach?

[00:02:49]
So, remember growth is with respect to input, constants are dropped, worst case is usually what we're gonna measure. So what is the possible worst case situation? So that's the first thing you should probably define in your head. What's the way that this thing fails? Well, just like in our first kind of example, we had E and if E, the string E that is, right?

[00:03:11]
Or the character E. If that's not in our array and we're searching for it, we're gonna go from 0 all the way to N and never find it. So what does that mean? If our input goes from say 1 to 2, we have to search double the space.

[00:03:27]
From 2 to 4, we'd search double again that space. And it keeps growing equally with the array. So what type of running time is that? Say that again?
>> O(N) type.
>> O(N), all right, awesome. O(N), we say O(N), that's what it actually looks like when you draw O(N).

[00:03:45]
What that simply means is that as your input grows, so does the time it takes equivalently or linearly. So if it grows by 10, you get 10 more cycles in this loop if you will. It's the easiest way to look at it. And so of course I wanted to implement this because it's very, very simple but not only is it very, very simple I also wanted you to get this onto your machine if you wish to follow along.

[00:04:09]
So we can execute these things one at a time. I created this little library to be able to just do a bunch of algorithms and if you want to do them every day, it actually creates a way for you to be able to do them as much as you want.

[00:04:21]
I made it for you, so it's a proper chill. There we go. So here we go, grab this thing, go to wherever you want to clone it out, and let's just clone this thing out. There we go, I'm gonna clone it onto my machine, awesome. So I'm gonna open up vim, I'm gonna go to scripts, I'm gonna go to day one and I will get a whole bunch of stuffs, so long as you executed install and generate, you should see all these.

[00:04:45]
A lot of these are gonna be data structures or algorithms that we are going to implement today. Yes, you do see min heap in here. There's a joke, it'll be great, but for now let's start off with linear search. So we'll open up linear search. This should be a very simple one I believe all of us can just kind of program this on first try which we will hopefully first try all of our algorithms today.

[00:05:07]
So here's the signature of course, which is linear search. I do like using snake case. Now I don't know what happened to me, I always hated snake case. And I love snake case. So if you don't like it, sorry. So there you go. Our signature of course, is that we have a haystack, a bunch of numbers and a needle that we're looking for, the number we're looking for.

[00:05:23]
And we're just simply gonna return out the Boolean if we did or did not find the number, all right? So let's just implement that really quickly, we're gonna do a classic for loop, right? And i has to be less than of course the haystack. There we go. And if haystack i equals the needle, well, guess what?

[00:05:45]
We can return true, I normally do not return in the middle of a for loop. But for algorithms, I'm totally willing to make concessions on good programming techniques. So there we go. As simple as that. If we see it, we return true, if we don't we return false.

[00:06:02]
The simplest form of search that we're going to do, in fact this is the simplest algorithm we're going to do today. To test if you've done it correctly, what we're going to do is we'll run this, npx jest and then just partially type in the name of the algorithm.

[00:06:17]
So npx jest Linear, this should just run jest with a filter of Linear. If you've successfully done, it'll give you a green passing. You could also just return true the first time it executes and false the second time. And if you can keep state between the two tests, you will also win.

[00:06:33]
So there you go, don't do that actually program. But there you go. This is as simple as it gets. All right, I am assuming everyone was able to do that, awesome. I really just wanted to make sure everyone has that piece of software on their machine. So, I figured this was the easiest way to know that you have it, it should run.

[00:06:52]
The reason why you don't use yarn test, is that if you cut out the package and grep for test, you'll notice that I put all of them in there. And the reason why I did that, the reason why I do it this way, is that if you look at, you'll now see what Twitch has currently called this thing.

[00:07:09]
If you go to your ligma.config, you'll notice that you specify all the algorithms you want to generate and then it generates them all. There you go. Pretty straightforward.