Data Structures & Algorithms

Question 1

Find Height of Binary Tree

Answer 1

Recursive: Check to see if the root node is null, if so return 0. Otherwise, set an int left equal to a recursive call with the root’s left node, and the same for the right, which will recurse until it’s found the last node for each left and right. The function returns the max of left and right plus one for the root node, which happens for every branch off of left and right until the tree is fully traversed.

Question 2

Tree

Answer 2

Data structure comprised of recursive nodes

Question 3

Binary Tree

Answer 3

Tree where each node has up to 2 children

Question 4

Binary Search Tree

Answer 4

Ordered tree where all left descendants are less than or equal to their right descendants.

Question 5

Balanced Tree

Answer 5

Balanced enough, not perfectly balanced, so that we can ensure O(log n) insert and lookup.

Question 6

Complete Binary Tree

Answer 6

Every node has either 0 or 2 children.

Question 7

Perfect Binary Tree

Answer 7

Full and complete.

Question 8

In Order Tree Traversal

Answer 8

“Visit” left, current node, right. In a Binary Search Tree, ascends in order.

Question 9

Pre-Order Tree Traversal

Answer 9

“Visit” current node, left, right. Root will be first visited.

Question 10

Post-Order Tree Traversal

Answer 10

“Visit” left, right, current node. Root will be last visited.

Question 11

Min Heap

Answer 11

Complete Binary Tree where each node is smaller than its children.

Question 12

Min Heap insertion

Answer 12

Insert at bottom rightmost location, fix by moving up into right spot and swapping nodes as you sort.

Question 13

Min Heap extract

Answer 13

Remove top (min node) and replace with bottom rightmost node. Swap now-top node until min is inserted at top and tree is in correct order.

Question 14

Tries

Answer 14

A prefix tree. Variant of n-ary tree with characters at each node. Each path down could be a word, with the end of the word represented by a null node.

Question 15

Uses for Tries

Answer 15

Autocomplete. A trie could be used to store the English language and do O(n) prefix lookup, where n is the string prefix being searched.

Question 16

Graph definition

Answer 16

A collection of nodes with edges between (some of) them.

Question 17

Directed Graph

Answer 17

Edges point the way, like a one way street.

Question 18

Undirected Graph

Answer 18

Edges go both ways, like a two way street.

Question 19

Connected Graph

Answer 19

Graph with an edge between every pair of vertices.

Question 20

Cyclic

Answer 20

Graph that cycles, end node touching root node

Question 21

Acyclic

Answer 21

Graph that does not have a cycle

Question 22

Adjacency List

Answer 22

Way of representing a graph where every vertex (node) stores a list of adjacent vertices (nodes).

Question 23

Adjacency Matrix

Answer 23

A NxN boolean matrix where a true value at matrix[i][j] indicates an edge between i and j. In an undirected graph, the matrix will be symmetric, and in a directed graph, it will not necessarily be symmetric.

Question 24

Depth First Search

Answer 24

Way of searching graphs that starts at the root (or another arbitrary node) and explores each branch completely before going to the next branch.

Question 25

Breadth First Search

Answer 25

Way of searching graphs that starts at the root (or other arbitrary node) and explores each neighbor before going to any of their children.

Question 26

BFS Use Case

Answer 26

Best for finding shortest path between two nodes, as it stays as close to the source node for as long as possible.

Question 27

DFS Use Case

Answer 27

Best if you want to visit every node, as all children are explored before moving on to a neighbor node.

Question 28

DFS Algorithm

Answer 28

``` void search(Node root) { if (root == null) return; visit(root); root.visited = true; for (Node n : root.adjacent) { if (n.visited == false) { search(n); } } } ```

Question 29

BFS Algorithm

Answer 29

``` void search(Node root) { Queue queue = new LinkedList(); root.marked = true; queue.add(root); ``` ``` while (!queue.isEmpty()) { Node r = queue.remove(); visit(r); for (Node n : r.adjacent) { if (n.marked == false) { n.marked = true; queue.add(n); } } } } ```

Question 30

Bidirectional Search

Answer 30

Used to find the shortest path between source and destination nodes by running two BFS searches from each node. The path is found when the searches collide.

Question 31

Bubble Sort

Answer 31

Swapping elements in pairs by order, then moving to next pair until sorted (nested for loops). O(n^2) time and O(1) space

Question 32

Selection Sort

Answer 32

Find the smallest element, move to front (nested for loops). O(n^2) time and O(1) space

Question 33

Merge Sort

Answer 33

Divide in half, repeat, sort, merge. O(n log n) time, memory depends.

Question 34

Quick Sort

Answer 34

Pick an element, move all less than to the left, greater to the right. O(n log n) time, O(log n) space.

Question 35

Radix Sort

Answer 35

A sorting algorithm that takes advantage of the fact that integers have a finite number of bits. We iterate through each digit of the number, grouping numbers by each digit. Then we sort these groupings by the next digit, and so on until the list is sorted. O(n*k) time, where n is the number of elements and k is the required passes through to sort.

Question 36

Binary Search

Answer 36

Look for element x by comparing to the midpoint of the list we're searching. If it's less than x, we search only the right half, and if it's greater we search the left half, repeating this until we either find the element x or each sub array is length 0. O(log n) time, O(1) space.