Week 3 + 4 + 5 Flashcards
Define stack.
Container with insertion and removal based on LIFO (Last-In-First-Out).
Define push, pop, top with stack.
push, inserts onto top of stack
pop, removes off of top of stack
top is last item pushed.
How is stack implemented using array?
Top of stack is set to the size of the array - 1. pop reduces top by 1 push adds element to top + 1 space and increments top. top = -1 for empty stack.
How is stack implemented using linked list?
Top of stack is set to lastNode added. pop sets top to lastNode->nextnode. push creates newNode with next lastNode and sets top to newNode. top points to null for empty stack.
Explain String Builder syntax. Why use string builder?
StringBuilder sb = new StringBuilder();
sb.append(“String”);
+ all other normal string functions.
String builder is mutable so a new String is not created after every modification unlike with normal Strings.
Define queue.
Container with insertion at back and removal from front. Based on FIFO (First-In-First-Out) data structure.
Define enqueue, dequeue and front for queue.
Enqueue inserts at rear of queue
Dequeue removes the element at the front of the queue.
Front returns the front of the queue.
How is queue implemented using array.
Front variable keeps track of front of queue, rear location is always empty. Enqueue grows the rear and dequeuing grows the front variable. Elements crawl to right in array as we modify the queue. We use circular arrays so when we reach the end of the array the elements circle back to the start.
Implementing Circular Array:
For enqueue: Insertion position set to (front + size) % CAPACITY
For dequeue: Front set to (front + 1) % CAPACITY.
How is queue implemented using linked list?
Doubly Linked List used. Enqueue, performs addLast, Dequeue performs removeFirst.
Define deque.
A queue where we can insert and delete from both the front and the end.
Define a tree.
A tree consists of nodes, where each node (except the first) has a parent and all nodes have zero or more children.
Define root.
First node which has no parent.
Define internal node.
A node with at least one child.
Define external node.
A node without children.
Define subtree.
Tree within a tree consisting of a node and its descendants.
Define depth of node.
Number of ancestors of p other than p itself.
Define height of tree.
Maximum depth of any node. The height of its root node.
What is the ordering in a tree?
Siblings are arranged left to right, from lowest to greatest.
Define binary tree.
A tree consisting of a single node or a tree whose root has an ordered pair of children each of which is a binary tree.
Define height of a node.
Number of edges on longest path from the node to a leaf which has a height of 0. Defined recursively. H (Node) = 1 + Height (child node). Where H (leaf) = 0
Define proper or full binary tree.
A binary tree where each node has either zero or two children.
T or F. In a binary node depth d has at most 2^d nodes.
True
In a non-empty binary tree what is the minimum and maximum number of nodes n.
h + 1 <= n <= 2^(h + 1) - 1
In a non-empty binary tree what is the minimum and maximum number of external nodes.
1 <= ne <= 2^h
In a non-empty binary tree what is the minimum and maximum number of internal nodes.
h <= ni <= 2^h - 1
In a non-empty binary tree what is the minimum and maximum height in terms of the nodes.
log(n + 1) - 1 <= h <= n - 1
In a non-empty PROPER binary tree, what is the number of external nodes.
ne = ni + 1
Explain inorder traversal.
Left subtree -> Node -> Right subtree
Explain preorder traversal.
Node -> Left subtree -> Right subtree. Moves top to bottom.
Explain postorder traversal.
Left subtree -> Right subtree -> Node. Moves bottom to top.
Explain breadth-first traversal.
Pushes all nodes at a particular depth onto stack and visits them first before moving down to next level. Moves top to bottom.
What is the Catalan number?
The number of full binary trees with n + 1 leaves.
Cn = 1 / n+1 (2n C n)
What is the expected height for a random binary tree of size n = 30.
3.3 log (30) = 11
Distinguish between iterable and iterator.
Iterable:
Represents a collection that can be iterated over using a for-each loop.
When implementing an Iterable, we need to override the iterator() method.
Doesn’t store the iteration state.
Removing elements during the iteration isn’t allowed.
Iterator:
Represents an interface that can be used to iterate over a collection.
When implementing an Iterator, we need to override the hasNest() and next() methods.
Stores the iteration state
Removing elements during the iteration is allowed.
Distinguish between the lazy and snapshot implementation of iterator.
Snapshot:
Maintains its own private snapshot of element sequence
Constructed when iterator object is created
Unaffected by subsequent changes to original
Lazy:
Does not make an upfront copy.
Piecewise traversal of original.
Affected by subsequent changes to original.
