Data Structures Overview

[00:00:00]
>> Bianca Gandolfo: So here are some operations you might be expected to do in a typical data structure based interview question. And I have some notes here, so for a stack and a queue. Again, it's not really, it is ordered, but it's usually not like ordered. It's not like sorted usually and so, these kind of sorting based operations aren't common, but you can do like the Tower of Hanoi or sort of stack with an auxiliary stack kind of questions or something you could imagine, but you're not really gonna sort it in place.

[00:00:42]
I mean, you could, it's just not a really common one, but definitely reversing, know how to reverse the stack, link list and your array string. Know how to reverse them, you can learn how to merge sort, quick sort for your raise. You could sort a link list, it's not very common, but it could be a fun experiment.

[00:01:07]
What else? So if you're merging something that's already sorted, what about if you're merging a range of values? The trick is if it's a range of values, you typically want to sort. Well, it depends on the problem, but the typical problem for merging a range of values is this job scheduling or meeting scheduling problem.

[00:01:28]
You usually wanna sort by the start time, so that's a tip, you could sort by the end time. There are other ways that you can sort them, but usually sorting by the start time. Wait, no, sort by the earliest end time, sort by the early earliest end time.

[00:01:42]
Yeah, sort by the earliest end time, that's kind of the typical best solution. So shuffling is actually really hard, randomization questions are really difficult. If you got this kind of question, you would, would it necessarily need to be able to implemented perfectly, but you should be able to talk about what are the challenges of like randomization and things like that.

[00:02:10]
A true randomization I mean, added distance is if you have like this list one, two, thee, and then you have this list it's two, two, three, how many changes do you need to make, to get this to be the same, so this is a really popular one. Usually in an interview question, it's only one step, its not a recursive figure out everything kind of problem, but the true edit distance problem is what you use to diffing the dom, and stuff like that, or going through large texts and spell-check, things like that.

[00:02:55]
So those are some things, so these two down here, I don't think you really need to know, I just like them, so I put them there. But these ones I would practice, all of these and even if it's not typical, just try it and see where you get stuck and what the challenges are, and then you'll know why you can or cannot do that.

[00:03:13]
Okay, here's more [LAUGH] cuz I knew you were like, man, that's not enough, I want more. So just some things, you should be able to search for values and all of these searching if it's sorted. You can't sort a hash table. So a Min/Max, you probably wanna have an auxiliary stack that makes it constant.

[00:03:35]
If it's Min/Max sorted, and you can just do it in place, unique, you can use a hash table. Linear time, if it's sorted, you could do it in place as well. Permutations, that's a super fun one. I definitely recommend that you do permutation, anagram, substring problems. We're out of the scope of this workshop, but those are some super fun ones and very common for strings, and also dynamic programming type problems.