graphs

Question 1

Three different Types of Graphps

Answer 1

1) Edge Lists
2) Adjacency Matrixes
3) Adjacency Lists

Question 2

Two most common ways to use graph data structures

Answer 2

1) Breadth First Search

2) Depth First Search

Question 3

Edge List B-O

Answer 3

O(n)

Question 4

Data structure for Edge List

Answer 4

Array
[0,1]
[1,2]

Question 5

Adjacency Matrices B-O

Answer 5

O(1)

Question 6

Data structure Adjacency Matrix

Answer 6

connect 4 type matrix (maybe battleship)

Question 7

Problem with Adjacency Matrix

Answer 7

Takes up a lot of space

Question 8

Problem with Edge List

Answer 8

slower

Question 9

Data structure Adjacency Lists

Answer 9

Write each of it’s neighbors as a list in an array
0 -> [1,4] // 0 is connected to 1 and 4
1 -> [2] // only one neighbor

(an array of arrays)

Question 10

Adjacency Lists 3 Advantages

Answer 10

1) Fast lookup
2) easy to find neighbors
3) Not as large as Adjacency Matrices

Question 11

Edge List (unidirectional)

Answer 11

Two array lists

[0,2] [2,0]

Question 12

Adjacency Matrix (unidirectional)

Answer 12

Flipped gride (both sides)

Question 13

Adjacency Lists (unidirectional)

Answer 13

Just add an other item to array

0 -> [1,4,5] // 0 is connected to 1 and 4
1 -> [2,1] // only one neighbor

Question 14

Breadth First Search (what is it)

Answer 14

start in the middle and move outward

Question 15

Breadth First Search what 3 things is it used for?

Answer 15

1) Social Graphs
2) Recommendations
3) Nearest Neighbors

Question 16

Depth First Search (what is it)

Answer 16

Starts with a node and drives deep and ignores nodes around it. Following it till it hit the end

Question 17

Depth First Search what 3 things is it used for?

Answer 17

1) Path Fionding
2) Unique solutions (path remains)
3) Cycle detection in graph

Question 18

Breadth First Search uses what structure?

Answer 18

Queue (first in first out) FIFO

Question 19

Depth First Search uses what structure?

Answer 19

Stack (First in last out) LIFO

Question 20

interview question: Breadth First (uses)

Answer 20

Nearest Neighbor (Social Networks, FB, Linkedin)
nearby peers in games

Question 21

interview question: Depth First (uses)

Answer 21

Better way to find things faraway (chess game, paths

Question 22

interview question: Breadth First (tech)

Answer 22

Queue (first in first out)

Question 23

interview question: Depth First (tech)

Answer 23

Stack (in in last out)