Introduction to Data Structures for Interviews Data Structure
Transcript from the "Data Structure" Lesson
>> Bianca Gandolfo: So we went over what to expect at an interview. What does the process look like. What are some ways to do well? What are some ways that you might have messed up, so that you can keep these in mind during your interview? So once you're actually sitting in the seat on your on-site or maybe at your kitchen table, if it's a phone screen, and you're asked a specific question.
[00:00:28] One technique that you can use to solve it is to think about, what intuition do I have about interview questions and data structures can help me solve this problem? So if you're asked a,
>> Bianca Gandolfo: You might be asked for specific data structure like reversing a linked list. That's a classic one.
[00:00:53] If you don't know how to do it, we'll do it today, so that's one you need to know. But there are other ones where, another one we'll do today, which is, how do you keep track of a minimum value in a stack in constant time? So you need to think about, okay, so how can I reason about this problem based on the data structures I know and the operations I could do on these data structures?
[00:01:21] And so that's why we're gonna be focusing on data structures all day today, part of the day next time, when we talk about trees. So we'll do a half day of the tree data structure, and the rest of it is just, okay, let's do everything you could think of with a tree.
[00:01:36] Balance it, flip it upside down, put in a blender, all kinds of stuff and then the same thing with graphs the next day. And so that's what we're gonna be focusing on, so what does it, that's why you should care, what is a data structure? You guys should probably know what a data structure is but it's just an arrangement of data.
[00:02:19] That's fine. What else? Yeah, so then you have ordered data structures, so data structures that come with some order. You have hierarchical data structures that have parent child relationships, and then you have complex relationships, and so we need to represent this somehow in our applications. And so we can model all kinds of real-world things using data, but we just need to structure it appropriately so that we can do the particular operations on that data structure in less than a billion years.
[00:02:54] So searching things, sorting things, getting particular values, these are all kinds of things that you wanna do all the time, but in different scenarios, right? You can use data structures to model real world systems, which we'll do a lot in the graph class. Or even just, the DOM is a tree.
[00:03:24] So you're traversing the DOM all the time and you need to understand how that works, so that you know. Maybe you're traversing a lot of data and you have a lot of DOM nodes. And you have a performance bottleneck and you want to figure out what that is.
[00:03:39] Understanding the time complexity and how traversing something like a tree works will help you with that. Here's some common interview data structures and kinda what they're used for. This is very general. So arrays and strings, you can use them for any kind of ordered data. Obviously, strings, we use them for words and text, things like that.
[00:04:07] Hash tables we tend to use to optimize other things. We use to optimize, typically lookup, quick lookup, that's what hash tables are for. You're gonna say that a million times today. Linked lists, so linked lists, we use a lot to build other data structures. So you can use, so under the hood, you can think of a JavScript array as a linked list, stacks and queues are often implemented as a linked list, hash table collisions are handled with a linked list.
[00:04:40] So there's a lot of linked lists underlying other data structures. And stacks and queues, we use stacks and queues in a lot of creative ways, to keep track of things as an auxiliary data structure, when we're solving problems, so keep that in mind. And so these are the things that we're gonna cover today.
[00:05:02] And next time we're gonna do trees and heaps, and we're gonna talk about arranging data in a hierarchical, learn how to say that word before that time, hierarchical way, and how we can work with that. And graphs, we're going to be modeling complex relationships like the Internet or the world as a map, or all of the sand on a beach.
[00:05:28] Things like that, simple things.