Data Structures & Algorithms Flashcards
Stacks - use cases
Recursive algorithms - push temporary data to the stack as you recurse and remove as you backtrack (e.g. if the recursive check failed)
Queues - use cases
Breadth-first search: store nodes we need to process - each time a node is processed, add adjacent nodes to the back of the queue so that they can be processed in the order they’re viewed
Implementing a cache
Complete binary tree
Every level of the tree is fully filled, except maybe last level (rightmost)
Full binary tree
Every node has either zero or 2 children, no nodes with only one child
Perfect binary tree
Both full & complete - all leaf nodes are at the same level, and each level has the max (2) # of nodes
In-order tree traversal (binary tree)
Visit left branch, then current node, then right branch
Depth first search
Pre-order tree traversal (binary tree)
Visit current node before child nodes, root is always first
Depth first search
Post-order tree traversal (binary tree)
Visit current node after child nodes, root is always last
Depth first search
Tree
Type of graph - connected graph without cycles
Data structure composed of nodes
Graph
Not all graphs are trees
Collection of nodes with edges between some of them
Directed –> goes one way
Undirected goes both ways
Can consist of multiple isolated subgraphs
Can have cycles, or be acyclic
Binary search tree (BST)
Not the same as a binary tree
Binary tree in which every node fits an ordering property: all left nodes are smaller than the right node
Clarify: sometimes duplicates aren’t allowed, sometimes they are, sometimes they have a particular ordering property too
Balanced vs. unbalanced tree
Balanced != exactly perfect, but balanced enough for O(log n) insertion and find
Examples of balanced: red-black trees, AVL trees
Connected graph
If there’s a path between every single pair of vertices
2 ways to represent a graph & which is better
Adjacency lists
Adjacency matrices
Which is better? Adjacency lists generally; graph algorithms like BFS done on matrix may be less efficient because you can’t easily reach node neighbours without going through the whole thing
When are matrices better? When edges are weighted, just replace the 1s in the matrix with weighting
2 most common ways of doing graph search
Breadth First Search (BFS)
Depth First Search (DFS)
Breadth first search (BFS)
Start at root / given node and traverse each neighbour before going to any children
Go wide before deep
Use: find shortest path / any path between 2 nodes
Depth first search (BFS)
Start at root / given node and traverse each branch completely before moving to the next branch
Go deep before wide
Use: visit every node in graph
Bidirectional search
Find shortest path between search & destination node by running 2 simultaneous BFS from each node, finding the path when they collide
