Hash Table, Array & String

[00:00:00]
>> Bianca Gandolfo: So hash table is a lot about counting occurrences, deleting duplicates, finding unique values, things like that. So, I always think of a hash table as an optimization steps. So when I'm pretty much done with a solution, when I'm starting to think about, okay, what's the time complexity of the solution?

[00:00:23]
Does it seem reasonable? Can I make it faster? Like the first thing I think of is, how can I use a hash table, because that could really increase the speed of my algorithm.
>> Bianca Gandolfo: So that's my little tip about hash table. Also, think about maps and sets, and when you would and wouldn't use those.

[00:00:45]
>> Bianca Gandolfo: So, for stacking or array and string questions, some tips are, so some fun array questions are matrices. So that's an array of arrays. So if you have like a matrix of some size, can you rotate it? Which means like, so you have corners like you have the top left, top right, bottom left, bottom right.

[00:01:11]
So if you rotate it, you just move all the values like that, to some degree. Like you can rotate it by a certain number, they will specify like how they want you to rotate it. You can also rotate a string. So if you have a string like abcd and you want to rotate it by one, then it would be bcd,

[00:01:30]
>> Bianca Gandolfo: Or it would be D. God, I can't do that in my head right now.
>> Bianca Gandolfo: So if you have a string and it's abcd and you want it to rotated by one, it would be dabc. So you're like moving, if you rotated by 2, it would be cdab.

[00:01:50]
>> Bianca Gandolfo: Mm-hm.
>> Speaker 2: And that's not using shifter anything like that, right, I mean?
>> Bianca Gandolfo: So strings are immutable.
>> Bianca Gandolfo: So what you would have to do is you would need to split it into an array, yeah. Or I would split it into an array, it's much easier.
>> Bianca Gandolfo: Yeah, so that's what a rotation is.

[00:02:12]
So similarly, if this was an array, it would be really similar.
>> Bianca Gandolfo: If it's a matrix, right, it's just kind of, you have like a little bit more going on. So it's more of like, I guess maybe this is one d and then a two d matrix would be two d, something like that.

[00:02:32]
>> Bianca Gandolfo: Okay.
>> Bianca Gandolfo: So rotating, zeroing out, so if you have like a matrix like this,
>> Bianca Gandolfo: Imagine that this valid syntax, it's not right now, and you have mostly ones.
>> Bianca Gandolfo: You need to zero it out. Typically, it is like either a diagonal or like up and down or left or right, something like a chess piece would move.

[00:03:06]
A lot of those are base on solving games, like chess, checkers, Sudoku, things like that tic-tac-toe. So if you have a 0, then you 0 it all out. So this could represent like if you have like a,
>> Speaker 3: What's the chess piece, the castle one?
>> Bianca Gandolfo: What's that one called again?

[00:03:30]
>> Speaker 3: Rook?
>> Bianca Gandolfo: The rook, so if you had a rook, so if we go back here,
>> Bianca Gandolfo: So if we have a rook here and we want to represent, where you could not move another piece in the chessboard without it being killed by the rook, we would add 0 in all, that's kind of what that represents.

[00:03:52]
One of the many things that you could represent with.
>> Bianca Gandolfo: So if you hear anything about like, a chessboard or checkers or tic-tac-toe, start thinking about 2D matrices. Also, when you're thinking about 2D matrices and it's binary, you can also distill it down to something like this. So for example,

[00:04:15]
>> Bianca Gandolfo: Maybe you can't in this example. But sometimes, you could actually make it just one array, and this could represent everything, but in this example, it doesn't work. But also, just think about how you could,
>> Bianca Gandolfo: Represent it even more simply in. Anyway, searching for a value. So when you search for a value,

[00:04:39]
>> Bianca Gandolfo: You have linear search where you just loop through and you find it. Thus, we do a lot of linear search when we are working with linked list.
>> Bianca Gandolfo: Otherwise, you probably wanna sort your input or have it pre-sorted would be nice and then you could do binary search.

[00:04:59]
>> Bianca Gandolfo: Which cuts down your,
>> Bianca Gandolfo: Time complexity considerably to log in, if it's pre-sorted. Once you're sorting, then you also have to count also the sorting. So,
>> Bianca Gandolfo: In coding strings, this is a thing where you're gonna need to split it into an array, like some edge cases for these kinds of string problems.

[00:05:23]
It's like what if there's punctuation?
>> Bianca Gandolfo: What if,
>> Bianca Gandolfo: What else? What about characteristics in other languages, things like that, you need to consider. Merging two sorted lists into one list. There's a bunch of different variations of this.
>> Bianca Gandolfo: This is sort of like a subroutine of merge sort.

[00:05:48]
So you'll learn this, and then you'll learn merge sort, you'll notice that it's the same. But there's a way to use two pointers to, in linear time, merge two sorted lists. So you just go through and you kind of like, if this is less than and then you, kind of, keep moving them as they,

[00:06:08]
>> Bianca Gandolfo: I'm not explaining that very well, I'm sorry.
>> Bianca Gandolfo: Here, let me just show you.
>> Bianca Gandolfo: So let's say you have 2,5,6,
>> Bianca Gandolfo: And then you have,
>> Bianca Gandolfo: 1,4,7, and you wanted to merge them into one list if that's sorted. So you would start at the very beginning, you have two points.

[00:06:33]
One would point here and one would point here. You say, what is less? One is less, so you would take this one off,
>> Bianca Gandolfo: And you put it here. So this is still pointing here, this is still pointing here. In reality, we probably wouldn't remove it. We probably wouldn't remove it, we would just move the pointer over, but I'm just gonna delete it for,

[00:06:54]
>> Bianca Gandolfo: From the example. And then we say, okay, which is less? Okay, two is less, and then we add it, and we remove it.
>> Bianca Gandolfo: Which is less? 4 is less. Okay, we add it,
>> Bianca Gandolfo: And then we remove it. So this is the way that you efficiently merge two sort of lists, which is less 5.

[00:07:16]
>> Bianca Gandolfo: And you can imagine some of these might like be always less. And then suddenly, it might not be this is almost like perfect order. My example is not very good.
>> Bianca Gandolfo: So that's how you would go about doing that.
>> Bianca Gandolfo: Okay, so,
>> Bianca Gandolfo: Those are kind of just like some tips and tricks about arrays and strings, and hash tables and linked lists, and stacks and queues.

[00:07:46]
Some things that you like just some common questions and operations you would be expected to do.