Data Structures Algorithms Final

Front 1

What is Polymorphism?

Back 1

Permits parent class to dynamically take behaviour of descendent class

Front 2

What does Method Overloading do?

Back 2

Allows there to be two methods with the same name but different signatures

Front 3

What is the algorithm for rotating a binary tree root to the right

Back 3

1. copy root.left --> temp

2. set root.left --> temp.right

3. set temp.right --> root

4 set root --> temp

Front 4

What does the static keyword mean?

Back 4

static means that the method or class belongs to the TYPE and not the INSTANCE of a class. A static member cannot be referenced through an instance. Instead it is referenced through the type name

Front 5

What does the override keyword mean?

Back 5

The override modifier is required to extend or modify the abstract or virtual implementation of an inherited method property

Front 6

What is an Interface?

Back 6

An interface contains only the signatures of methods properties

Front 7

a class can only have...

Back 7

one parent class

Front 8

a child class exhibits AT LEAST...

Back 8

the same behaviour as the parent class

Front 9

A class can implement multiple...

Back 9

interfaces

Front 10

A class MUST implement all methods defined in the

Back 10

interface

Front 11

What is Stack topIndex when the stack is empty?

Back 11

-1

Front 12

How does the Stack work? What are its main methods?

Back 12

LIFO: last in, first out

OR

FILO: first in, last out

Methods:

Push(T item): adds item to top of stack

Pop(): grabs item from top of stack

Peek: returns top item of stack

Front 13

How does a Queue work? What are its main methods?

Back 13

FIFO: first in, first out

OR

LILO: last in, last out

Methods:

Offer : adds element to back of queue

Peek: returns element at front of queue

Poll: takes element at front of q

Front 14

What is a Hash Table

Back 14

Data structure that maps keys to values

Front 15

How does the hashing of a Hash Table work?

Back 15

Distributes key/value pairs across an array of buckets

hash = hashfunc(key)

index = hash % array_size

`hash` is independent of array size, and is reduced to an index (number between 0 and array_size - 1) using modulo operator

Front 16

Why is does the hash table use modulo with prime numbers?

Back 16

when you're repeating over a set space, you're going to provide an even distribution across your hash space.

Front 17

What is a binary heap?

Back 17

A tree-based data structure where each row is filled out from left to right. The goal is to fully saturate all rows.

Front 18

What are the two types of binary heaps?

Back 18

Max Heap: value of each node is less than or equal to its parent (largest value at root)

Min Heap: value of each node is greater than or equal to its parent (smallest value at root)

Front 19

Given a binary heap stored in an array and an element at position n, how do you find its parent?

Back 19

n / 2

Front 20

Given a binary heap stored in an array and an element at position n, how do you find its left child?

Back 20

2 * n

Front 21

Given a binary heap stored in an array and an element at position n, how do you find its right child?

Back 21

2 * n + 1

Front 22

First 10 prime numbers (for hash tables)

Back 22

2, 3, 5, 7, 11, 13, 17, 19, 23 and 29

Front 23

What is the IComparable interface?

Back 23

Defines a generalized comparison method for classes

Front 24

How should you implement the IComparable interface?

Back 24

Generally, return an integer (1, 0, -1) to show the sorted order of two instances of the same class

-1 = this.object precedes object being compared to

0 = equal

1 = this.object is greater than object being compared to

public int CompareTo(Item other)

{

if (this.Number < other.Number)

return -1;

else if (this.Number == other.Number)

return 0;

else if (this.Number > other.Number)

return 1;

}

Front 25

How does Binary Heap array implementation work

Back 25

Front 26

How does Binary Heaps Delete/Percolate Down work?

Back 26

(assuming max heap)

1. Delete root node

2. Take element at bottom, right-most position and place it at root

3. Compare new root with children, swap if out of order

4. Continue until correct order

Front 27

How does a Fix Heap/Heap Sort work with the Binary Heap?

Back 27

It is a recursive Delete and Percolate down operation to return a sorted array.

1. Delete root and place in array

2. Perform Percolate Down to find next root in correct order

3. Continue steps 1 and 2 until heap is empty

4. Return the sorted array

Front 28

What is a binary tree

Back 28

Simple tree data structure that is either:

a) empty

b) a node with a left and right binary tree

Front 29

How does a pre-order traversal work?

Back 29

1. Root

2. Descent left subtree

3. Descent right subtree

Front 30

How does post-order traversal work?

Back 30

1. Ascend left subtree

2. Ascend right subtree

3. Root

Front 31

How does in-order traversal work?

Back 31

1. Descend left subtree

2. Root

3. Descend right subtree

Front 32

What is the definition of a Binary Search Tree?

Back 32

All values in the left subtree are less than the root value

All values in the right subtree are greater than the root value

Front 33

How to perform insert in a Binary Search Tree?

Back 33

1. Start at root

2. If new node smaller than current node, go left. Otherwise go right

3. If we reach a node with no children (a leaf node), insert new node to the left if smaller, insert new node to the right if larger

Front 34

What are the three cases for Deletion in a Binary Search Tree?

Back 34

1. If the node has no children, remove it

2. If the node has 1 child, remove the node and replace it with its child

3. If the node has 2 children, find the smallest node in the right subtree and replace deleted node with this node.

Front 35

What are the properties of a Red Black Tree?

Back 35

It is a self-balancing Binary Search Tree

1. Every node is Red or Black

2. Root node is Black

3. All leaf (nil) nodes are Black

4. If a node is Red, both of its children are Black

5. The path from any node to a descendant nil node MUST have the same number of black nodes (this is called the Black Height)

All operations (Insert, Delete etc) are performed like it is a Binary Search Tree, after operation is complete, you then rebalance the tree to satisfy the properties above.

Front 36

Red Black Tree Balancing: What is Case 1?

Back 36

Case: Uncle of the new node is Red

Solution: Recolor!

-Grandparent becomes Red

-Parent and Uncle become Black

Front 37

Red Black Tree Balancing: What is Case 2?

Back 37

Case: Uncle is Black, Parent is a Right Child

Solution: Left rotate around parent of new node

This then leads to Case 3 for more rebalancing

Front 38

Red Black Tree Balancing: What is Case 3?

Back 38

Case: Uncle is Black, New Node is a Right Child

Solution:

-Parent and Grandparent of new node become Black

-Right rotate around Grandparent

Front 39

In general, what are the steps for Binary Search?

Back 39

*assume array is ordered lowest to highest

1. Given a target, X

2. Find the midpoint of the array with equation: (low + high) / 2

3. If X == midpoint, return true

4. If X < midpoint, recursive call to binary search on the subarray of the midpoint to the last element

5. If X > midpoint, recursive call to binary search on the subarray of the first element to the midpoint

Front 40

Algorithm for balancing a LL tree

Back 40

rotate parent right

Front 41

Algorithm for balancing a LR tree

Back 41

1. rotate child left

2. rotate parent right

Front 42

Algorithm for balancing a RR tree

Back 42

rotate parent left

Front 43

Algorithm for balancing a RL

Back 43

1. rotate child right

2. rotate parent left

Front 44

Set method that does union

Back 44

setA.addAll(setB) =

setA union setB

Front 45

Set method that does intersection

Back 45

setA.retainAll(setB) =

setA intersect setB

Front 46

Set method that does subtraction

Back 46

setA.removeAll(setB) =

setA minus setB

Front 47

Map method for retrieving an element

Back 47

map.get(Object key)

Front 48

Map method for adding an element

Back 48

map.put(K key, V value)

Front 49

Qualities of a good hash table

Back 49

1. size of table much > # of values

2. hash algorithm that chooses "random" location in table

Front 50

What is "chaining"

Back 50

Using another data structure (linked list) in place of a hash bucket so multiple values can be stored in same bucket

Front 51

what is a "collision" in a hash table

Back 51

when a value is added to a bucket that already has a value in it.

Front 52

what is quadratic probing

Back 52

when a hash table collision occurs, add the element to a cell n distance from original hash based on quadratic equation

Front 53

performance of open addressing hash tables

Back 53

c = 1/2(1+ 1/(1-L)) where

c = comparisons

L = load factor

Front 54

performance of chaining

Back 54

c = 1 + (L/2)

c = comparisons

L = load factor

Front 55

big-O performance for hash table

Back 55

O(1) expected; worst case O(n)

Front 56

big-O performance for unsorted array

Back 56

O(n)

Front 57

big-O performance for binary search tree

Back 57

O(log n); worst case O(n)

Front 58

recursive algorithm for greatest common divisor

Back 58

if n is a divisor of m

gcd(m, n) = n

else

gcd(m, n) = gcd(n, m%n)

Front 59

recursive binary search algorithm

Back 59

if the array is empty

return -1

else if the middle element matches the target

return middle element

else if the target is less than the middle element

recursively search the elements before the middle

else if the target is more than the middle element

recursively search the elements after the middle

Front 60

Stack applications

Back 60

finding palindrome

balancing parenthesis

Front 61

implementation of stack

Back 61

array = O(1)

list = O(n)

vector = O(n) and all methods are accessible

Front 62

application of queue

Back 62

operating systems, printers

Front 63

implementation of queue

Back 63

double linked list = O(1)

single linked list = O(1)

circular array = O(1)

Front 64

storage requirements of queue implementation

Back 64

circular array = 1/2

single linked list = 1

double linked list = 1.5

Front 65

what is a deque

Back 65

double-ended queue

ArrayDeque recommended implementation

Front 66

unit testing

Back 66

tests smallest pieces of the software

Front 67

integration testing

Back 67

tests interaction among the units

Front 68

system testing

Back 68

tests the whole program in the context in which it will be used

Front 69

acceptance testing

Back 69

system testing designed to demonstrate that the program meets it's functional requirements

Front 70

black-box testing

Back 70

tests the item based on its interfaces and functional requirements

Front 71

white-box testing

Back 71

tests the unit with knowledge of it's internal structure

Front 72

JUnit test framework

Back 72

a test harness is a program written to test a method or class. it provides known inputs for a series of tests and compares the results with known results

Front 73

test driven development

Back 73

writing tests and methods in parallel

Front 74

what is an expression tree

Back 74

(x+y)*((a+b)/c)

Front 75

what is a Huffman Tree

Back 75

Examples:

d : 10110

e : 010

Front 76

algorithm for searching a binary tree

Back 76

1.if thetree is empty

2. return null (targetis not found)else if the target matches the root node's data

3. return the data stored at the rootnodeelse if the target is less than the root node'sdata

4. return the result of searching theleft subtree of the rootelse5. return the result of searching theright subtree of the root

Front 77

full binary tree

Back 77

A full binary tree is a binary tree whereall nodes have either 2 children or 0 children (the leaf nodes)

Front 78

perfect binary tree

Back 78

A perfect binary tree is afull binary tree of height n with exactly 2n – 1nodes

In this case, n = 3and 2n – 1= 72

Front 79

complete binary tree

Back 79

A complete binary tree is aperfect binary tree through level n - 1 with some extra leaf nodes at level n (thetree height), all toward the left