Overview & Stack Exercise

[00:00:02]
>> Bianca Gandolfo: All right, so, we're gonna hop into the implementation piece of the workshop now. So we did the kind of discovery phase where we discussed what these data structures are, kind of the theory behind them. We talked a tiny bit about time complexity analysis of certain operations and we drew a lot of pictures.

[00:00:25]
And now sort of like the first phase of learning data structure, the theory. Now we're getting to like, how do we turn those pictures into lines of code? And this is the implementation piece. And then, the next step is going to be how do we take those lines and code and solve the real problem that you may be ask to interview?

[00:00:43]
And then we do recap. But first, I'm gonna go over the structure of the boilerplate code I'm gonna give you, that's gonna be the prompt. So, I recommend when you guys get home when you have some free time to go through and implement all of them. Those of you who are taking this class online, I recommend implementing all of them.

[00:01:04]
Just for the class, we don't have time to do all of them here today, cuz it'll take 20-30 minutes for each, and then suddenly that's two hours for us. And that's most of the day, and we don't wanna focus on that, we wanna focus on, really, the application of these data structures, to real interview questions, and I want to leave a few hours for that.

[00:01:22]
Okay, so,
>> Bianca Gandolfo: Some things to keep in mind are this table, this is a very famous table, this is a big old cheat sheet. Most of the pictures in my slides are secretly a link. So if you click on this it'll bring you to the website, where you can find this.

[00:01:43]
So, these are the data structures that we're going over today. The time complexities for most common operations. As you can see, they all share access, so that's the lookup, insertion, search, and delete, deletion.
>> Bianca Gandolfo: They all have their pros and cons, and you need to keep this in mind when you're implementing your data structure, because you need to meet these requirements, okay?

[00:02:08]
>> Bianca Gandolfo: And then we have sorting algorithm, time complexity here as well. And this is good to know for when you're actually solving interview questions, cuz you'll find that often you can increase the time complexity of your solution by sorting the list if it's an ordered data structure. So basically, anything other than a hash table, you can sort.

[00:02:39]
>> Bianca Gandolfo: Okay,
>> Bianca Gandolfo: So,
>> Bianca Gandolfo: I'm trying to think if I should have go through each one. Well, we'll go through it when I go through the bolierplate. And then we'll talk about the specifics of each one.
>> Bianca Gandolfo: And then you need to make sure that you implement it that way.

[00:02:59]
Okay, so we have our stack. So if you click this button,
>> Bianca Gandolfo: It will take you to the prompt.
>> Bianca Gandolfo: And,
>> Bianca Gandolfo: Then what you can do from the prompt is you can fork it, and then you can write your solution here.
>> Bianca Gandolfo: And so,
>> Bianca Gandolfo: Just know that.

[00:03:28]
>> Bianca Gandolfo: How do I go back?
>> Bianca Gandolfo: Stick to the original, okay. So here we are implementing a class that represents a Stack. So we're using a constructor.
>> Bianca Gandolfo: A class contractor here.
>> Bianca Gandolfo: And, anytime you wanna put a property on a data structure itself, right, so this is like, storage or,

[00:03:57]
>> Bianca Gandolfo: What else? If you have a pointer to the head or the tail, you would put this is in the constructor method. So this just ES6 classes, if you're used to ES5 classes, this is just inside of the regular function, where you call new and you return this .storage,

[00:04:17]
>> Bianca Gandolfo: This is just a different syntax.
>> Bianca Gandolfo: When you create an instance, which means that, from your constructor, you create one, it's a factory, right, you create one of the things that you're making, in this case, it's a stack, how we use it is we say new Stack, and we call it like this.

[00:04:44]
And so what myStack will look like? Is it will look like an object that has a property _storage, that has an object inside of it? That's what that looks like. So we could take look and then we have some methods as well.
>> Bianca Gandolfo: But we'll get to those in a second.

[00:05:04]
So if we wanted to console.log, and I highly recommend that through different steps, you should inspect what the code actually looks like, instead of just assuming it looks like a certain way. So let's take a look and see,
>> Bianca Gandolfo: What it looks like. So we have, again, here our storage.

[00:05:25]
>> Bianca Gandolfo: Okay, questions about how this works? So this is how we make classes in ES6. If we wanted to put another thing, let me say this .otherThing. Whoa, you know and then you can do it again, and you can see it's also there.
>> Bianca Gandolfo: Okay.
>> Bianca Gandolfo: So we don't really need this.

[00:05:49]
So the underscore is a convention that says like, this is an internal property you shouldn't be working on it directly. So if you were consuming this Stack class, which means, you're the person who called new. So I'm consuming this Stack class, I am not supposed to do stack.storage.

[00:06:14]
Cuz the underscore says, this is private, you're not supposed to access it, you can only access it through the methods that are public. Right, and the public methods that we have, which aren't implemented, we have peek, pop, and push.
>> Bianca Gandolfo: So that's what the underscore means.
>> Bianca Gandolfo: Cuz you could, right, you could do that.

[00:06:34]
>> Bianca Gandolfo: It's returning that value here.
>> Bianca Gandolfo: It's not important.
>> Bianca Gandolfo: Okay, so your task is to read through this code comments. This is just JS Stack format which means that, it kind of has a description, and then we'll talk about the parameter that it takes. And then, the name of that parameter, right?

[00:07:00]
So in this case, when we say push, we will say, push value, put this here. And then, if there's a return value, we also talk about what it may return. So push doesn't necessarily return new thing. However, pop, we'll return the last, newest value. And so this is defining the interface of this method.

[00:07:17]
And so, you're task is, how do we interact with our storage? And, do we need to make more properties to make this work? What is the logic that we need to put inside to have push work, to have pop work, and have peek work, in the time complexity that is required of this data structure.

[00:07:41]
So this needs to be a constant, this needs to be constant, this needs to be constant time. Which means that, we can't shift anything around, like there shouldn't be any looping, there shouldn't be anything other than lookups. So lookups, simple math, things like that are gonna be constant time operations.

[00:08:08]
And if you're confused about what is or isn't a constant time operation as you're going through this, feel free to ask, and I can chat with you about it. For those of you who are watching the video, you can check out my time complexity videos in the algorithms portion of this course.