Common Operations

[00:00:02]
>> Bianca Gandolfo: Just a quick recap. We have been through a lot. We have gone through a journey of discovering properties and various data structures and the operations that we perform on them. Then we implemented a bulk of the data structures that you would be expected to know in an interview from scratch.

[00:00:25]
And then we talked about some themes around questions related to these data structures that you might find. So we've been through a lot, let's kind of recap what we've seen. So let's talk a little bit about this time complexity piece here. We kind of glossed over it a little bit in this workshop, last workshop.

[00:00:44]
Practical intro to algorithms goes more in depth on calculating and analyzing time complexity. So if you're feeling a little lost about what I'm talking about, I recommend checking out those videos and then coming back and hearing me out here. So let's see, what are some special things that I wanna point out?

[00:01:08]
So for a hash table, we noticed that we have constant time for pretty much everything, which means that we're gonna use our law for optimization. That's why I'm saying like if you can look a hash table to make it faster, you should do that. A lot of our insertions and deletions, they're ordered, but they're not necessarily like in a contiguous block of memory.

[00:01:35]
So when we insert and delete, we don't have to worry about shifting things over and that makes a constant time. And actually in JavaScript arrays in most browser environments are basically the same as this. So this linear time is kind of probably not true for JavaScript, depending on where your JavaScript is running.

[00:02:01]
Let's see, what are some other things that you should know? Did you check out in your sorting, that's an important thing for these data structure questions. A lot of them can be improved significantly, if you just sort the input. I would just use the JavaScript sort method. Be careful you need to learn how to use that call back function where you have to return a minus b.

[00:02:25]
So just remember how that works. One is ascending, one is descending. And under the hood, it's either merge sort or quick sort. And so, you can expect an end log in for these kind of sorts, but it's even better if the input is already sorted and then you don't even need to think about sorting it or anything like that.

[00:02:45]
Some other things to think about are doing things in place. And so this is so that you don't consume extra memory. A lot of questions will start off with sort of a naive solution where maybe you'll use hash table to make something really fast and then your interviewer will, they'll be like but can you do it in place?

[00:03:05]
And then you're like no and then you have to figure out a creative way to not use a hash table. And so some ways you can do that are like using pointers with link list is one way. What's another way? Man, there's some other ways. I don't know.

[00:03:23]
I'm blanking at the moment, but definitely using pointers, swapping. So instead of creating a new data structure, you can just swap them. You can swap only in data structures that have an order. So if it's an unordered data structure, you can't really swap. So that's not gonna help you.

[00:03:45]
Pretty much, searching the best you can do is gonna be 0 of n cuz you have to look at everything, unless it's ordered, unless it's sorted. And then in which case you can use something like binary search in that can speed things up. Trying to think of what else I can tell you about this.

[00:04:04]
I don't know, be familiar with this. You don't need to memorize this table, but you should be able to reason about the time complexity of various operations in your code. So before you get into interview questions, before you are studying data structures when you're just writing your code day-to-day just think about this array.push.

[00:04:36]
How does that work? Think about memory allocation and how that might work and then you can Google it and things like that, then you can really learn okay, what are the costs of this operation? And that will help you have a strong foundation of the time complexity of just common operations that you use day-to-day.

[00:04:55]
And then when you start to combine them into solve problems that you wouldn't normally solve at least you are comfortable with that to begin with, that would be my advice.