Data Structures

Question 1

Hash Table

Answer 1

A hash table is a data structure that maps keys to values for highly efficient lookup.

Question 2

Linked List

Answer 2

A data structure that represents a sequence of nodes

Question 3

Singly Linked List

Answer 3

Each node points to the next node in the linked list

Question 4

Doubly Linked List

Answer 4

Gives each node pointers to both the next node and the previous node

Question 5

Runner Technique

Answer 5

The “runner” (or second pointer) technique is used in many linked list problems. The runner technique means that you iterate through the linked list with two pointers simultaneously, with one ahead of the other.

The “fast” node might be ahead by a fixed amount, or it might be hopping multiple nodes for each one node that the “slow” node iterates through.

Question 6

Stack

Answer 6

Stack uses LIFO (last-in first out) ordering; most recent item added to the stack is the first item to be removed.

Question 7

Stack Operations

Answer 7

pop(): remove the top item from the stack
push(item): add an item to the top of the stack
peek(): return the top of the stack
isEmpty(): return true if and only if the stack is empty

Question 8

Stack offer constant-time access to the ith item?

Answer 8

False. Unlike an array.

Question 9

Stack Constant time for add / remove

Answer 9

True. Constant time for push and remove. Does not require shifting elements around (unlike an array)

Question 10

Queue

Answer 10

A queue implements FIFO (first-in first-out) ordering; items are removed from the data structure in the same order that they are added.

Question 11

Queue Operations

Answer 11

add(item): add an item to the end of the queue
remove(): remove the first item in the queue
peek(): return the top of the queue
isEmpty(): return true if and only if the queue is empty

Question 12

Trees

Answer 12

A tree is a data structure composed of nodes:

• Each tree has a root node
• Root node has zero or more child nodes
• each child node has zero or more child nodes, and so on

Question 13

The tree cannot contain cycles. The nodes may or may not be in a particular order, they could have any data type as values, and they may not have links back to their parent nodes

Answer 13

True

Question 14

Binary Trees

Answer 14

a binary tree is a tree in which the node has up to two children. Not all trees are binary trees.

Question 15

Node “leaf”

Answer 15

A node is called a “leaf” node if it has no children

Question 16

Binary Search Tree

Answer 16

A binary search tree is a binary tree in which every node fits a specific ordering property: all left descendents <= n < all right descendents. This must be true for each node n.

Question 17

Balanced vs Unbalanced

Answer 17

With a balanced tree, access^1 is O(log n).
With an unbalanced tree, access^1 is O(n) (worst case).

an unbalanced tree built from sorted data is effectively the same as a linked list

Question 18

Two common types of balanced trees:

Answer 18

red-black trees, and AVL trees

Question 19

Complete Binary Trees

Answer 19

A complete binary tree is a binary tree in which every level of the tree is fully filled, except for perhaps the last level. To the extent that the least level is filled, it is filled left to right.

Question 20

Full Binary Trees

Answer 20

A full binary tree is a binary tree in which every node has either zero or two children. That is, no nodes have only one child.

Question 21

Perfect Binary Trees

Answer 21

A perfect binary tree is one where all interior nodes have two children and all leaf nodes are at the same level.

Question 22

Tries (Prefix Trees)

Answer 22

A trie is a variant of an n-ary tree in which characters are stored at each node. Each path down the tree may represent a word.

Question 23

• nodes in Tries (Prefix Trees)

Answer 23

sometimes called null nodes; often used to indicate complete words.

EG: the fact there is a * node under MANY indicates that MANY is a complete word. The existence of the MA path indicates there are words that start with MA.

Question 24

Graph

Answer 24

A graph is simply a collection of nodes with edges between (some of) them.

• Graphs can be either directed or undirected.

Question 25

Trees are actually a type of graph, but not all graphs are trees

Answer 25

True. A tree is a connected graph without cycles

Question 26

Directed edges vs undirected edges (graphs)

Answer 26

Directed edges are like a one-way street, undirected edges are like a two-way street

Question 27

Adjacency List

Answer 27

Most common way to represent a graph; every vertex (or node) stores a list of adjacent vertices. In an undirected graph, an edge like (a, b) would be stored twice: once in a’s adjacent vertices and once in b’s adjacent vertices

Question 28

Adjacency Matrices

Answer 28

An adjacency matrix is an N x N boolean matrix (where N is the number of nodes), where a true value at matrix[i][j] indicates an edge from node i to node j.

Question 29

Two commons way to search a graph

Answer 29

Depth-first search, breadth-first search

Question 30

Depth-First Search (DFS)

Answer 30

start at the root (or another arbitrarily selected node) and explore each branch completely before moving on to the next branch.

That is, we go deep first (hence the name depth-first search) before we go wide.

Question 31

Breadth-first search (BFS)

Answer 31

start at the root (or another arbitrarily selected node) and explore each neighbor before going on to any of their children.

That is, we go wide (hence breadth-first search) before we go deep.

Question 32

What scenario to use DFS vs BFS?

Answer 32

DFS preferred if we want to visit every node in the graph; DFS a bit simpler overall.

BFS if we want to find the shortest path (or just any path) between two nodes; BFS is generally better.

Question 33

Bidirectional Search

Answer 33

used to find the shortest path between a source and a destination node. Operates by essentially running two simultaneous breadth-first searches, one from each node. When their searches collide, we have found a path (formed by merging the two paths).

Note: if the graph is directed, it searches forward from s and backwards from t (ie: running the opposite way on the edges)