Data Structures and Algorithms in 15 Minutes

Tren Black
10 Dec 202016:19

Summary

TLDRThis video script offers a humorous and insightful journey into the world of data structures and algorithms, essential for computer science enthusiasts. It humorously addresses the challenges and rewards of mastering these concepts, which are crucial for problem-solving efficiency and highly valued by tech companies. The script covers various data structures like arrays, linked lists, binary trees, and heaps, and algorithms including sorting, searching, and graph theory. It also touches on the importance of understanding time and space complexity, and provides learning resources for further study, emphasizing the value of a broad understanding before delving into deeper details.

Takeaways

  • 😎 Being proficient in data structures and algorithms is highly valued in the tech industry, often associated with high intellect and attractive job offers.
  • 🚀 The journey to mastering algorithms and data structures is challenging and can be filled with frustration and feelings of imposter syndrome.
  • 💡 The motivation to learn should stem from a genuine interest in problem-solving efficiency rather than just for job prospects.
  • 📈 Understanding algorithm efficiency involves recognizing the relationship between input size and the number of operations required, often described using Big O notation.
  • 🔍 Different algorithms have distinct time complexities, such as constant, linear, quadratic, logarithmic, exponential, and factorial, which greatly affect performance with varying input sizes.
  • 🌲 Data structures like arrays, linked lists, and binary trees, each with their own properties and use cases, are fundamental to computer science.
  • 🔄 Sorting algorithms, including selection sort and merge sort, have different time complexities, with merge sort being notably efficient at O(n log n).
  • 🌐 Graphs, with their vertices and edges, are used to model complex relationships and can be manipulated to find shortest paths or perform topological sorts.
  • 🔑 Hash maps offer nearly constant time data retrieval and are built on arrays with a hash function to map keys to indices, making them extremely powerful for data storage and access.
  • 🎓 Learning data structures and algorithms is more effective when approached with a general understanding first, followed by deeper dives into specific topics.

Q & A

  • Why is being proficient in data structures and algorithms considered prestigious in the computer science field?

    -Proficiency in data structures and algorithms is considered prestigious because it signifies a deep understanding of efficient problem-solving in computer science. It often leads to high-paying job offers from prestigious companies and is associated with high social market value in online tech communities.

  • What is the significance of Big O notation in computer science?

    -Big O notation is used to describe the time complexity of an algorithm, which is the relationship between the growth of input size and the growth of the number of operations required. It helps in comparing the efficiency of different algorithms and is crucial for optimizing performance.

  • How does the efficiency of an algorithm impact the performance of a program?

    -The efficiency of an algorithm directly impacts the performance of a program by determining how the execution time and resources required scale with the input size. Inefficient algorithms can lead to excessive resource usage and slow execution times, especially with large inputs.

  • What is the difference between a constant time and a linear time algorithm?

    -A constant time algorithm has a fixed number of operations, regardless of the input size, often represented as O(1). In contrast, a linear time algorithm's operation count grows proportionally with the input size, represented as O(n), where 'n' is the input size.

  • Why is it important to understand logarithms when studying algorithms?

    -Logarithms are important in algorithm studies because they often represent the efficiency of algorithms that involve dividing the problem size by half with each step, such as binary search. Understanding logarithms helps in grasping the concept of logarithmic time complexity, which is significant for algorithms like binary search and merge sort.

  • What is a binary search and how does it work?

    -A binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

  • Why is sorting important in computer science, and what is the best time complexity we can achieve for sorting?

    -Sorting is important in computer science because it is a fundamental operation that prepares data for efficient searching, processing, and analysis. The best time complexity we can achieve for sorting an arbitrary collection is O(n log n), which is the time complexity of algorithms like merge sort.

  • What is the primary difference between an array and a linked list?

    -The primary difference is that an array is a fixed-size, contiguous block of memory where elements can be accessed directly by index, while a linked list is a flexible-size data structure composed of nodes that contain data and a reference to the next node in the sequence. Linked lists allow for efficient insertion and deletion but do not support direct access by index.

  • How does a binary search tree differ from a binary tree, and what are its properties?

    -A binary search tree is a specific type of binary tree with the property that the value of each node is greater than or equal to any value stored in the left subtree and less than any value in the right subtree. This ordering property makes binary search trees efficient for searching, insertion, and deletion operations.

  • What is a heap, and how does it differ from a binary search tree?

    -A heap is a specialized tree-based data structure that satisfies the heap property: either the parent node is always greater than or equal to (in a max heap) or less than or equal to (in a min heap) any of its children. Unlike binary search trees, heaps are not necessarily sorted, and the primary focus is on the priority of the root element, which is the highest or lowest value in the heap.

  • What are the two main ways to traverse a tree, and how do they differ?

    -The two main ways to traverse a tree are depth-first search (DFS) and breadth-first search (BFS). DFS explores as far as possible along each branch before backtracking, while BFS visits all the nodes at the present depth level before moving on to nodes at the next depth level.

Outlines

00:00

🧠 The Journey to Algorithm Mastery

The paragraph introduces the significance of mastering data structures and algorithms in computer science, likening it to a status symbol that can lead to high-paying job offers and social recognition. It candidly discusses the challenges faced by learners, such as frustration and imposter syndrome. The speaker, having overcome these obstacles, shares a personal anecdote about receiving job offers, humorously suggesting their qualifications are now so high they could 'cure cancer.' The video aims to serve as a guide for those struggling with programming concepts, emphasizing the importance of intrinsic motivation over extrinsic goals like employment at prestigious companies. It delves into the fundamentals of algorithm efficiency, explaining time complexity through examples and introducing Big O notation as a tool for expressing this complexity. The paragraph concludes with a discussion on different types of time complexities, such as constant, linear, quadratic, logarithmic, exponential, and factorial, using relatable examples to illustrate these concepts.

05:01

🌲 Exploring Data Structures: Arrays, Linked Lists, and Trees

This segment delves into various data structures, starting with arrays and their limitations, such as fixed size. It contrasts arrays with linked lists, which offer dynamic sizing through nodes that contain data and a reference to the next node. The narrative humorously compares traversing a linked list to following a chain of YouTube comments leading to a potential virus. It also touches on doubly linked lists and the efficiency of adding, inserting, and deleting nodes. The paragraph then transitions into binary trees, explaining their structure and the concept of binary search trees, which maintain a sorted order through rules about child node values. It discusses the average and worst-case time complexities for operations on these trees and introduces self-balancing binary search trees like red-black trees. The speaker also briefly mentions heaps, another tree-based data structure used for priority queues, and different traversal methods like depth-first search (DFS) and breadth-first search (BFS), providing examples of how these methods can be implemented.

10:01

🔍 Graphs and Their Applications

The focus of this paragraph is on graphs, which are collections of vertices and edges that can be used to model complex relationships and networks. It starts by differentiating between directed and undirected graphs and explains how edges can be represented using adjacency lists or matrices. The speaker then explores various applications of graphs, such as calculating degrees of separation in social networks, finding the shortest path in map systems like Google Maps, and performing topological sorting for course scheduling. Each application is tied to a specific algorithm: breadth-first search for degrees of separation, Dijkstra's algorithm for weighted shortest paths, and a queue-based approach for topological sorting. The paragraph highlights the versatility and importance of graphs in solving real-world problems and emphasizes the practicality of these algorithms.

15:02

🔑 The Power of Hash Maps

The final paragraph emphasizes the utility of hash maps, a data structure that provides efficient data retrieval through key-value pairs. It describes hash maps as the 'holy grail' of data structures due to their ability to offer constant time complexity for operations like retrieval, insertion, and deletion. The speaker explains the concept of a hash function, which converts keys into hash codes that are used as indices in an underlying array. Collisions, where different keys produce the same hash code, are discussed, and the use of linked lists to resolve these is introduced. The paragraph concludes with a recommendation for learning resources, including a paid course with a community aspect and free college lectures, suggesting that both paid and free options can lead to mastery of data structures and algorithms.

Mindmap

Keywords

💡Data Structures

Data structures are specialized formats for organizing, processing, and storing data. In the video, they are presented as foundational to computer science and essential for efficient problem-solving. The video explains various data structures like arrays, linked lists, binary trees, and heaps, illustrating their use in different scenarios, such as searching, sorting, and managing data efficiently.

💡Algorithms

Algorithms are step-by-step procedures to solve problems or perform calculations. The video emphasizes their importance in computer science, highlighting how efficient algorithms can significantly reduce the time and resources required to process data. Examples from the script include sorting algorithms like merge sort and searching algorithms like binary search, which are crucial for optimizing performance.

💡Big O Notation

Big O notation is a mathematical representation used to describe the performance or complexity of an algorithm in terms of time or space. The video uses Big O notation to categorize algorithms based on their efficiency, such as O(n) for linear algorithms and O(log n) for logarithmic ones. Understanding Big O notation is crucial for assessing how an algorithm scales with input size.

💡Time Complexity

Time complexity refers to the amount of time an algorithm takes to run as a function of the length of the input. The video explains that time complexity is a critical measure of an algorithm's efficiency, with examples like linear search having a time complexity of O(n) and binary search having O(log n), indicating the number of operations grows with the input size.

💡Space Complexity

Space complexity is a measure of the amount of memory an algorithm uses in relation to the size of the input. While the video primarily focuses on time complexity, it also mentions space complexity in the context of Big O notation, explaining how some algorithms might be more memory-intensive than others.

💡Binary Search

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item until the item is found or the sublist is empty. The video uses binary search to illustrate the concept of logarithmic time complexity, O(log n), which is much faster than linear search for large datasets.

💡Merge Sort

Merge sort is a divide-and-conquer algorithm used for sorting lists. The video explains that merge sort divides the list into halves, sorts each half, and then merges them back together. This algorithm is notable for its consistent O(n log n) time complexity, making it efficient for sorting large datasets.

💡Linked List

A linked list is a linear data structure where each element is a separate object, called a node, which contains data and a reference to the next node in the sequence. The video contrasts linked lists with arrays, highlighting their dynamic size and efficient insertions and deletions but slower element access times compared to arrays.

💡Graphs

Graphs are data structures that consist of vertices connected by edges. The video discusses graphs in the context of finding shortest paths, like in social networks or mapping systems, and for topological sorting, such as scheduling courses with prerequisites. Graphs are versatile and can model complex relationships and networks.

💡Hash Maps

Hash maps, also known as dictionaries in Python or objects in JavaScript, are data structures that store key-value pairs and allow for efficient retrieval, insertion, and deletion of data. The video explains how hash maps use a hash function to compute an index into an array, where the value is stored, enabling average constant time complexity for these operations. Hash maps are highlighted as a powerful tool for quick data access.

Highlights

Being proficient in data structures and algorithms is highly valued in computer science, often equating to high social market value and prestigious job offers.

The journey to mastering algorithms is challenging and can be filled with frustration and imposter syndrome.

Having a genuine interest in learning data structures and algorithms, rather than just for job prospects, is crucial for success.

Understanding how to rank an algorithm's efficiency is fundamental, with big O notation used to describe time complexity.

Different algorithms have varying time complexities, such as linear, constant, and logarithmic, which affect how they scale with input size.

Big O notation is also used for space complexity, indicating how much memory an algorithm uses relative to input size.

Logarithms are the inverse of exponential functions and play a key role in algorithms like binary search.

Binary search is an efficient algorithm for finding items in a sorted list by repeatedly dividing the search interval in half.

Sorting algorithms like selection sort and merge sort have different time complexities, with merge sort being more efficient at O(n log n).

Arrays and linked lists are basic data structures with different properties, such as fixed size versus dynamic size.

Linked lists allow for efficient insertion and deletion of nodes but do not support constant time access by index.

Binary trees, such as binary search trees, enable efficient searching, insertion, and deletion with a time complexity related to the tree's height.

Self-balancing binary search trees like red-black trees ensure a logarithmic height, maintaining efficient operations.

Heaps are tree-like data structures that store elements according to priority, with the highest priority element always at the root.

Depth-first and breadth-first searches are methods for traversing trees and graphs, with each having its own order and use cases.

Graphs are used to model complex relationships and can be used to find shortest paths, such as in social networks or mapping systems.

Hash maps provide constant time retrieval of data and are built on arrays with a hash function to compute indices for keys.

Collisions in hash maps can be resolved using linked lists or other methods to maintain efficient data retrieval.

Data structures and algorithms are essential for solving problems efficiently and should be learned for their problem-solving benefits, not just for job prospects.

Transcripts

play00:00

being good at data structures and

play00:01

algorithms is a computer science

play00:02

equivalent of having

play00:04

i mean everyone assumes you're a genius

play00:06

you get high paying offers from

play00:07

prestigious companies

play00:08

and you even have a high social market

play00:10

value on internet forums but the journey

play00:12

from lead cell to algo chat is not an

play00:14

easy one

play00:14

it's filled with frustration and

play00:16

imposter syndrome i know i've been there

play00:18

but now i have offers from feng which

play00:20

basically qualifies me to cure cancer

play00:22

so to give back and help even the most

play00:24

confusing programmers

play00:25

consider this video my cure since this

play00:27

industry is cancer

play00:30

[Music]

play00:38

the most important part of learning

play00:40

something new is that you actually want

play00:41

to learn it

play00:42

this is why i failed out of spanish one

play00:44

so before we start

play00:45

ask yourself why do you want to learn

play00:47

this don't do it to get a job at google

play00:49

do it because learning this changes the

play00:51

way you think data structures and

play00:52

algorithms

play00:53

is about solving problems efficiently a

play00:55

bad programmer solves the problem

play00:57

inefficiently and a

play00:58

really bad programmer doesn't even know

play01:00

why their solution is inefficient so

play01:01

let's start with that

play01:02

how do we rank an algorithm's efficiency

play01:04

[Music]

play01:06

say we wrote a function that goes

play01:08

through every number in a list and adds

play01:09

it to a total sum variable if you

play01:11

consider

play01:12

adding to be one operation then running

play01:13

this function on a list with 10 numbers

play01:15

costs 10 operations running it on a list

play01:17

with 20 numbers costs 20 operations

play01:20

say we wrote another function that just

play01:21

returns the first number in a list then

play01:23

no matter how large the list is this

play01:25

function will never cost more than one

play01:27

operation

play01:27

clearly these two algorithms have a

play01:29

different time complexity or

play01:30

relationship between growth of input

play01:32

size and growth of operations we

play01:34

communicate these time complexities

play01:35

using big

play01:36

o notation referring to input size as n

play01:38

common complexities are

play01:40

constant linear quadratic

play01:43

logarithmic n log n exponential

play01:47

and factorial our first algorithm runs

play01:49

in o of n

play01:50

meaning its operations grow in a linear

play01:52

relationship with the input size which

play01:54

in this case is the amount of numbers in

play01:55

the list our second algorithm

play01:57

is not dependent on the input size at

play01:59

all so it runs in constant time let's

play02:00

take a look at how many operations a

play02:02

program will have to execute in a

play02:03

function with an input size of 5

play02:06

versus 50. it might not matter when the

play02:08

input is small but this gap gets very

play02:10

dramatic as the input size increases if

play02:12

n were 10

play02:13

000 a function that runs in log of n

play02:15

would only take 14 operations while the

play02:17

function that runs in n factorial

play02:19

would set your computer on fire for big

play02:21

o notation we drop constants so

play02:23

o of 10 times n and o of n over 10 are

play02:26

both equivalent to o of n because the

play02:28

graph is still linear and bagel notation

play02:30

is also used for space complexity which

play02:32

works the same way for how much space an

play02:34

algorithm uses as n grows

play02:36

unless you sit in your room doing

play02:38

algorithms all day there's a good chance

play02:39

you forgot what logarithms are

play02:41

logarithms are the inverse to

play02:42

exponential functions let's say i wanted

play02:44

to find a word in a dictionary

play02:46

one method is to check every word one by

play02:48

one this is o

play02:49

n but nobody does that so how are humans

play02:52

able to find

play02:53

any word in a dictionary with a hundred

play02:55

thousand words in seconds we do

play02:57

something more along method two

play02:59

cut the search window in half each time

play03:01

by checking the middle element

play03:02

if we passed our word search on the left

play03:04

half otherwise search on the right half

play03:06

and then we repeat this until we find

play03:08

our word

play03:08

if our input n doubled in size that

play03:10

would only grow our operations by one

play03:13

in computer science this is the binary

play03:15

search but for the binary search to work

play03:17

the collection has to be sorted which

play03:19

opens up a huge field of computer

play03:21

science

play03:21

sorting algorithms a very basic sort is

play03:24

a selection sort you have one pointer at

play03:25

the start of the list and another

play03:27

pointer that is linear scan to find the

play03:28

next minimum element

play03:30

then you swap those elements and

play03:31

increment the pointer since you're doing

play03:32

a linear scan for every element in the

play03:34

collection

play03:35

this runs in all of n squared a more

play03:37

efficient algorithm is the merge sort a

play03:39

merged source splits a collection in

play03:40

half into sub-collections until those

play03:42

sub-collections can be sorted in

play03:44

constant time and then it works its way

play03:46

back up by merging sorted subcollections

play03:48

until the entire collection is sorted

play03:49

since it's splitting in half there will

play03:51

be log n splits and thereby

play03:53

log n merges it is o then to merge two

play03:56

sorted collections into one sorted

play03:57

collection

play03:58

since we're doing that log n times the

play04:00

time complexity is of

play04:01

n times log n no algorithm can sort an

play04:04

arbitrary collection in a better time

play04:06

complexity than that so we consider

play04:08

n log n to be the cost of sorting

play04:11

perhaps the most fundamental data

play04:12

structure is an array an array is an

play04:14

indexable contiguous chunk of memory

play04:16

arrays are fixed size you can't insert a

play04:18

ninth element into an array meant for

play04:20

eight elements a list data structure

play04:21

with a flexible size is a linked list

play04:23

the idea is to package your data into

play04:25

nodes that hold one

play04:26

your data and two a point that points to

play04:29

the next node

play04:29

traversing a linked list reminds me of

play04:31

those youtube direction chains

play04:32

like you see a comment that says read my

play04:35

profile picture

play04:36

and their profile picture says click on

play04:38

my profile which brings you to their

play04:39

header which says

play04:40

read my bio so you go to their bio and

play04:43

it says click the link below and you

play04:44

click it and then it installs a virus

play04:46

onto your browser

play04:48

if a note's next pointer points to null

play04:50

it's the end of the list you can add a

play04:52

new node to the list in constant time by

play04:54

just setting that pointer to the new

play04:55

node

play04:56

by doing additional tom [ __ ] with

play04:57

pointers we can also insert and delete

play04:59

nodes in constant time

play05:00

sometimes nodes also contain a pointer

play05:02

to the previous node in a variation

play05:04

called the doubly linked list but a

play05:05

major downside of linked list is that

play05:07

you can't

play05:07

access elements in constant time via

play05:09

index like an array in practice both

play05:11

programming languages have dynamically

play05:13

sized arrays or lists which work by

play05:15

creating arrays with a fixed size

play05:17

if the array is full capacity and you

play05:18

try to add a new element

play05:20

the programming language automatically

play05:21

creates a new array with double the

play05:23

capacity

play05:24

copies the current elements over and

play05:25

sets your pointer to that new array

play05:27

since this happens so infrequently we

play05:29

generally consider appending to a list

play05:31

to be a constant time operation

play05:34

link lists aren't the only data

play05:35

structure that include nodes referring

play05:37

to other nodes what if instead of

play05:38

pointing to a next node nodes pointed to

play05:40

a left and a right child node this is

play05:42

called a binary tree

play05:43

these child notes can also be called

play05:45

subtrees since trees are recursive in

play05:47

nature

play05:47

a node with no children is called a leaf

play05:49

node while a node with seven children is

play05:50

my

play05:51

father-in-law a common type of tree is

play05:53

the binary search tree which follows

play05:55

these rules

play05:55

basically a node's left child must have

play05:57

a smaller value while a node's right

play05:59

child must have a greater or equal value

play06:02

let's say you're looking for element x

play06:04

you start at the root and if the number

play06:05

is smaller than the root you go to the

play06:07

left tree if it's larger you go to the

play06:09

right and you keep repeating this until

play06:10

you arrive at your number

play06:12

in the worst case you have to traverse

play06:13

the height of the tree so the time

play06:15

complexity to search

play06:16

insert and delete elements is of h where

play06:19

h is the height

play06:20

this is efficient because on average the

play06:21

height will be log n

play06:23

but what if you inserted every element

play06:25

of a sorted array into an empty binary

play06:27

search tree

play06:28

well that's a linked list meaning the

play06:31

height would be

play06:31

n but we can guarantee log n time

play06:34

complexities using a self-balancing

play06:36

binary search tree such as red black

play06:38

trees which maintain

play06:39

additional properties to guarantee that

play06:41

the height of the tree is o of log n

play06:43

binary search trees are kind of

play06:44

considered to be a workhorse

play06:45

distribution that can solve most

play06:47

problems with decent efficiency but i

play06:48

found situations where binary search

play06:50

trees

play06:51

really shine are when you're asked a

play06:53

question about binary search trees

play06:56

another type of tree is a heap the

play06:59

primary difference between this and the

play07:00

binary search tree is

play07:02

actually use this one it's also

play07:03

sometimes called a priority queue

play07:04

because at the root of it is always the

play07:06

highest priority element

play07:08

and min heap will have the min element

play07:09

and the max heap will have the max

play07:11

element at the root but don't get me

play07:12

wrong the rest of the heap is unsorted

play07:14

it is an absolute wasteland down there

play07:16

searching in the rest of the heap

play07:18

may as well be an unsorted array we only

play07:20

care about what's at the top

play07:23

just like capitalism to insert a new

play07:25

element into a heap

play07:26

first we find the next available spot to

play07:28

add a leaf node then we compare it with

play07:29

his parents and if it's a higher

play07:30

priority it swaps and bubbles his way up

play07:32

we're doing at most

play07:34

log n comparisons you can build a heap

play07:36

from a random collection by inserting n

play07:38

times which cost

play07:39

o of n log n but there's also a way to

play07:41

build a heap in o of end time

play07:43

i'd suggest reading this wikipedia page

play07:45

because it's super interesting stuff and

play07:47

lastly

play07:47

since the heap is nearly complete

play07:49

although we can visualize it as a tree

play07:51

we could actually use these properties

play07:52

to represent it with an

play07:53

array one way to traverse a tree is a

play07:57

depth first search

play07:58

which is like going deep fully exploring

play08:00

one path and then moving on to the next

play08:02

one way to visit this tree in a depth

play08:04

first order could be to start at 10

play08:06

go to 13 go to 4 then 6 then 12

play08:09

then 8 and then 1 whereas another option

play08:12

is a breadth first search where we view

play08:14

it more

play08:14

level by level a way to print this same

play08:16

tree in a bfs manner could be

play08:18

10 13 12 4 6

play08:22

8 1. when it comes to implementation

play08:24

depth first search can use a stack a

play08:26

stack is a list-based data structure

play08:28

where the only two operations

play08:29

are add to the end and pop from the end

play08:32

this makes a stack

play08:32

lifo last in first out dfs are often

play08:36

done using recursion

play08:37

which indirectly uses a stack the

play08:39

recursive stack so if your recursion

play08:41

exceeds a certain amount of depth then

play08:43

you get a stack overflow let's look at a

play08:45

way to print this tree in a dfs matter

play08:47

using a stack so first initialize the

play08:48

stack and add the root

play08:50

then while there are still elements in

play08:52

the stack pop from the stack print that

play08:54

element and then add its children to the

play08:56

stack on the contrary a breadth first

play08:58

search uses a queue

play08:59

a queue is fifo first in first out so

play09:03

instead of popping from the end of the

play09:04

list

play09:05

you pop from the beginning doing the

play09:07

same algorithm as before but

play09:08

using a q instead of a stack the tree

play09:10

will now print in a bfs

play09:12

order all trees are graphs but not all

play09:16

graphs are trees a graph is a collection

play09:18

of vertices which are like points

play09:20

and edges which are like connections

play09:22

from one vertex to another vertex a

play09:24

graph can be directed meaning edges can

play09:26

only go one way

play09:27

so this edge means you can only go from

play09:28

a to b or undirected meaning you can

play09:31

also go from b to a

play09:32

two common ways to model edges are

play09:34

adjacency lists and adjacency matrices

play09:37

graphs are my favorite part of

play09:38

destruction algorithms so i'd like to

play09:40

show how cool they are with three

play09:41

example scenarios on where you can use

play09:43

them

play09:45

so it recently dawned on me that i know

play09:47

kanye west

play09:48

and by that i mean i know joma tech but

play09:50

joma tech knows jarvis johnson who knows

play09:53

mkbhd who knows elon musk

play09:55

who knows kanye west which is five

play09:57

degrees of separation between me and

play09:58

kanye west i wanted to find something

play10:00

shorter

play10:01

well turns out i know bretman rock who

play10:03

knows rihanna who knows kanye three

play10:05

degrees of separation

play10:06

which also means that anyone who knows

play10:08

me is at most

play10:09

four degrees of separation away from

play10:11

kanye if we wanted to make a program

play10:12

that computes the smallest degrees of

play10:14

separation between two people

play10:16

a graph would be the perfect choice you

play10:18

model people as vertices and you model

play10:20

relationships as edges the shortest path

play10:22

between the source node

play10:23

me and the target node kanye can be

play10:26

found with a breath first search

play10:27

since we're moving out level by level we

play10:29

can guarantee that the first time

play10:31

reaching the kanye node will also be the

play10:33

shortest path

play10:34

the problem with implementing this

play10:35

algorithm the way i just described is

play10:36

that

play10:37

nobody has a concrete list of all the

play10:39

people they know nor would that be

play10:41

publicly accessible by me but a possible

play10:43

variation could be in a social network

play10:45

like facebook where we can use the

play10:46

friend list as edges

play10:48

we would then be able to run this

play10:49

algorithm and find the smallest degrees

play10:51

of separation between

play10:52

any two users in that social network

play10:55

imagine a map system like google maps

play10:57

that wants to find the shortest path

play10:58

between two locations

play11:00

this is different than the last example

play11:01

because although they both deal with

play11:03

shortest paths the degrees of

play11:04

separations did not have

play11:05

weighted edges where a map system does

play11:07

for example if we're computing the

play11:08

shortest path between two vertices and

play11:10

there's a direct edge between them

play11:12

weighing 20 versus a path of two edges

play11:14

weighing eight

play11:14

each a breath first search would give us

play11:16

the shortest path in terms of the

play11:17

vertices away but not the smallest

play11:19

weight one algorithm that computes the

play11:21

shortest path in a graph with positive

play11:22

weighted edges is dijkstra's algorithm

play11:24

using the heap data structure in the

play11:26

original version of this video

play11:28

i explained dijkstra's and my video shot

play11:29

up 6 minutes so instead just research it

play11:32

for yourself if you're interested

play11:34

but graphs aren't just good for path

play11:36

finding imagine a course schedule in

play11:37

school with classes

play11:38

and prerequisites for each class and say

play11:40

you wanted to find the order in which

play11:42

you can take all your classes while

play11:43

still fulfilling your prerequisites well

play11:45

model the classes as vertices and

play11:47

prerequisites as edges count how many

play11:49

incoming edge each vertex has add

play11:51

vertices with zero incoming edges to a

play11:52

queue then pop and print the element

play11:54

from the queue and decrement the

play11:55

incoming edges of all its children

play11:57

if a child now has zero incoming edges

play11:59

add it to the cube and repeat while

play12:00

there are still elements in the queue

play12:02

this algorithm is known as a topological

play12:04

sort

play12:05

[Music]

play12:07

hash maps are sort of the holy grail of

play12:08

data structures with basically constant

play12:10

time retrieval of data

play12:12

the saying goes that if you don't know

play12:13

what you're doing just try throwing

play12:15

hashtags at the question

play12:16

as an example one time i was in a coding

play12:17

interview and froze so

play12:19

i just told the interviewer hmm i think

play12:22

the solution to use a hash map

play12:23

unfortunately the question was what are

play12:25

your biggest weaknesses

play12:27

so the better answer was hang up the

play12:28

phone to show that i have none a hashmap

play12:30

is a data structure built on top of an

play12:32

array optimized to store

play12:33

key value pairs what makes it so

play12:35

powerful is you can retrieve delete and

play12:37

store data

play12:38

in on average constant time here we have

play12:40

a map where keys are strings

play12:41

representing people's names and values

play12:43

are their corresponding ages

play12:45

we can directly access trend black's age

play12:47

like this it's almost as if strings can

play12:49

be used as indices

play12:50

but how is that even possible because of

play12:53

this little thing called a hash function

play12:55

a hash function will take a key and

play12:56

return a hash code if we take that

play12:58

number modulus the length of its

play12:59

underlying array we can use that as an

play13:01

index to store its value but the hash

play13:03

function has to compute the same hash

play13:05

code if

play13:06

given the same key so hash of trend

play13:07

black should always return the same hash

play13:09

code or else we lose the index but what

play13:11

if hash of trend black and hash of ziz

play13:13

both end with the same index well this

play13:15

is called collision

play13:17

one way to deal with this is to store

play13:18

our value in a linked list

play13:20

so when we go to stores is and see that

play13:21

index three already has a value we have

play13:24

that value

play13:24

point to the new value this is why a

play13:26

hash map is not strictly of one because

play13:29

if you write some

play13:30

god awful hash function then it won't be

play13:32

balanced and we will have to do a lot of

play13:34

linkless traversing good hash functions

play13:36

evenly spread out hash codes

play13:37

in practice modern languages use very

play13:39

good hash functions so you don't have to

play13:41

write your own

play13:41

an example of a hashmap is the

play13:43

dictionary in python or the object in

play13:45

javascript and remember

play13:46

constant lookup of data is very

play13:48

overpowered so try to use it when you

play13:50

can

play13:50

[Music]

play13:52

and that's pretty much all you need to

play13:53

know for data structures and algorithms

play13:55

a six month college course taught in 13

play13:58

minutes now of course you didn't learn

play13:59

anything in great detail but trust me it

play14:01

is a lot easier to learn something in

play14:03

great detail if you already learned the

play14:05

big picture first

play14:06

this is why college sucks at teaching it

play14:08

dives very deep into one topic and then

play14:10

moves on to the next

play14:11

it's like a depth first search i believe

play14:14

the better way of learning is to get a

play14:15

general understanding and then build on

play14:17

it

play14:17

like a breath first search so if you

play14:19

want to keep going what are my

play14:20

recommendations to build on your

play14:22

knowledge well the first one

play14:23

is jomo class you know those really nice

play14:25

animations in this video like this one

play14:28

yeah i got them from joma class if you

play14:30

don't care about getting extremely

play14:31

theoretical and just want simple

play14:33

to the point everything you need to know

play14:35

and nothing you don't type lessons then

play14:37

jomo class makes this difficult topic

play14:39

very accessible but i will admit that i

play14:41

roasted the

play14:42

[ __ ] out of jomah a while back because

play14:44

he was pushing some

play14:46

actual snake oil well unlike some people

play14:48

he took my criticism very well and to

play14:50

vindicate his name

play14:52

he made something that is actually

play14:54

valuable and i will defend that

play14:55

he put much more effort into these

play14:57

explanations dropped the price from a

play14:59

thousand dollars to eight dollars a

play15:01

month and most importantly he dropped

play15:03

the

play15:05

dead weight if you're a complete

play15:06

beginner it also comes with a course on

play15:08

how to code in python and of course on

play15:10

sql if you're a bit more advanced but i

play15:12

gotta say the best part is the community

play15:14

aspect

play15:14

each lesson has a whole community behind

play15:16

it where people ask questions

play15:18

discuss topics and just learn together

play15:20

well i like the course so much that i

play15:22

actually called joma

play15:24

and i was like yo what the [ __ ] dude

play15:27

this is actually good i'm gonna start

play15:29

recommending this to people

play15:30

and he was so excited to hear that i

play15:32

liked it that he was actually willing to

play15:34

offer my audience a discount

play15:35

so if you go to trend.jomoclass.com

play15:38

then you'll get 15 off but even though

play15:41

paying for stuff increases the chance

play15:43

that you'll actually complete it you

play15:44

don't

play15:44

have to spend money not everyone has

play15:46

eight dollars a month to drop and i want

play15:48

to assure you that you can still learn

play15:50

everything for free

play15:51

so it might take a bit more

play15:52

self-discipline but you can do it so

play15:54

don't listen to anyone who says you

play15:56

have to pay so if you do want to go down

play15:58

the free route i'd recommend these

play16:00

college lectures

play16:01

they're literally taught by mit

play16:02

professors and posted for free online

play16:04

they're pretty theoretical but very

play16:06

comprehensive and it's perfect if you

play16:08

like that old-school

play16:09

chalkboard setting so yeah good luck

play16:11

guys and go get that guck 3000

Rate This

5.0 / 5 (0 votes)

相关标签
Data StructuresAlgorithmsComputer ScienceEfficiencyCodingProblem SolvingEducationalLearningTech Tutorial
您是否需要英文摘要?