know it Flashcards
(78 cards)
1
Q
what is the advantage of linked lists over arrays
A
you can add things to the beginning in constant time
2
Q
queue.dequeue from scratch (singly linked list implementation)
A
dequeue(){
if(!this.first) return null;
var temp = this.first;
if(this.first === this.last) {
this.last = null;
}
this.first = this.first.next;
this.size--;
return temp.value;
}
3
Q
SLL class
A
class SinglyLinkedList{
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
4
Q
SLL.insert
A
insert(index, value) {
//if index is less than zero or greater than length, return false
if (index \< 0 || index \> list.length) {
return false;
}
//if index is same as length, push new node
if (index === list.length) {
list.push(value);
}
//if index is 0, unshift
if (index === 0 ) {
list.unshift(value);
}
//otherwise use get method but with \*index - 1\*, set next property to newly created node, and connect new node to old next node
else {
var newNode = new Node(value);
var previous = this.get(index - 1);
var next = this.get(index);
previous.next = newNode;
newNode.next = next;
this.length++;
}
return true;
//increment length, return true or false
}
5
Q
SLL.push
A
push(val) {
var node = new Node(val);
if (this.head === null) {
this.head = node;
//is this the same as setting it to node?
this.tail = this.head;
} else {
this.tail.next = node;
//didnt add this on first draft
this.tail = node;
}
this.length++;
//don't forget to return!
return this;
}
6
Q
what is the extractMax method of a binary heap
A
replace the max with the min, and then bubble everything back into the correct order
7
Q
queue.enqueue from scratch
A
enqueue(val){
var newNode = new Node(val);
if(!this.first){
this.first = newNode;
this.last = newNode;
} else {
this.last.next = newNode;
this.last = newNode;
}
return ++this.size;
}
8
Q
stack.pop
A
pop() {
if (this.size === 0) {
return null;
} else {
var toPop = this.first;
if (this.first = this.last) {
this.last = null;
}
this.first = this.first.next;
this.size--
return toPop.val;
}
}
9
Q
time complexity for arrays
- access
- insertion
- removal
- built in sort method
A
access isn O(1) just like for objects
adding or removing something to the beginning of an array means you have to re-index every single element though, so that;s O(n),
try to add and remove things from the end, not the beginning
built in sort method is nlogN time but doesnt take any space
10
Q
can you implement a priority queue from scratch?
A
class PriorityQueue {
constructor() {
this.elements = [];
}
enqueue(val, priority) {
let newNode = new Node(val, priority)
this.elements.push(newNode)
this.bubbleUp();
}
bubbleUp() {
let index = this.elements.length - 1;
const element = this.elements[index];
while(index \> 0) {
let parentIndex = Math.floor((index -1)/2)
let parent = this.elements[parentIndex];
if (element.priority \<= parent.priority) break;
this.elements[parentIndex] = element;
this.elements[index] = parent;
index = parentIndex;
}
}
dequeue() {
const max = this.elements[0];
const last = this.elements.pop();
if (this.elements.length \> 0) {
this.elements[0] = last;
this.bubbleDown;
}
return max;
}
bubbleDown() {
let index = 0;
const length = this.elements.length;
const element = this.elements[0];
while(true) {
let leftChildIndex = 2 \* index + 1;
let rightChildIndex = 2 \* index + 2;
let leftChild, rightChild;
let swapIndex = null;
//make sure that the children exist
if (leftChildIndex \< length) {
leftChild = this.elements[leftChildIndex]
if (leftChild.priority \> element.priority) {
swapIndex = leftChildIndex
}
}
if (rightChildIndex \< length) {
rightChild = this.elements[rightChildIndex];
if (rightChild.priority \> element.priority && rightChild.priority \> leftChild.priority) {
swapIndex = rightChildIndex;
}
}
if (swapIndex === null) break;
this.elements[index] = this.elements[swapIndex];
this.elements[swapIndex] = element;
index = swapIndex;
}
}
}
class Node {
constructor(val, priority) {
this.val = val;
this.priority = priority;
}
}
let ER = new PriorityQueue();
ER.enqueue(“cold”, 1)
ER.enqueue(“gunshot”, 5)
ER.enqueue(“high fever”, 2)
11
Q
what is big O for insertion, deletion, and access for hash table
A
O(1)! amazing!
12
Q
DLL.pop
A
//pop removes the last item and returns it
pop() {
if (this.length === 0) {
return undefined;
}
var storedTail = this.tail;
if (this.length === 1) {
this.head = null;
this.tail = null;
} else {
var newTail = this.tail.prev
this.tail.prev = null;
this.tail = newTail;
this.tail.next = null;
}
this.length--;
return storedTail;
}
13
Q
linked list Node (S or D)
A
class Node {
constructor(val) {
this.val = val;
this.next = null
}
}
14
Q
when storing a heap as an array, what is the parent of a child?
A
floor(n-1)/2)
15
Q
DLL class
A
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
16
Q
mergeSort
A
function mergeSort(array) {
//break up the arrays into halves until you have arrays that are size zero or 1
//once you have smaller sorted arrays, merge those arrays
//once an array has been merged, return the merged array
// Recrusive Merge Sort
if(arr.length \<= 1) return arr; let mid = Math.floor(arr.length/2); let left = mergeSort(arr.slice(0,mid)); let right = mergeSort(arr.slice(mid)); return merge(left, sright);
}
17
Q
popping a singly linked list
A
there’s no pointer, so you have to reset the tail by going through the whole thing
18
Q
DLL.insert
A
//creates new node and adds it at that position.
insert(index, val) {
//can be optimized for beginning/end, also can use unshift/push
if (index \< 0 || index \>= this.length) {
return undefined;
}
if (index === 0) {
this.unshift(val);
}
if (index === this.length) {
this.push(val);
}
else {
if (index \<= this.length/2) {
var current = this.head
var count = 0;
while (count != index) {
count++;
current = current.next;
}
} else {
//from the tail
var count = this.length - 1;
var current = this.tail
while (count != index) {
count --
current = current.prev;
}
}
addNode(current, val)
}
function addNode(current, val) {
var savedNext = current.next
var newNode = new Node(val)
current.next = newNode;
newNode.next = savedNext;
savedNext.prev= newNode;
newNode.prev = current;
}
this.length++;
return true;
}
19
Q
big O for searching a heap
A
O(n) - remember, no implied order between siblings
20
Q
how do you find shortest distsance in a graph
A
BFS
21
Q
what are binary heaps for
A
they are useful for priority queues and for graph traversal algorithms
22
Q
graph breadth first traversal code
A
breadthFirstTraversal(start) {
const queue = [start];
const result = [];
const visited = {};
let currentVertex;
while (queue.length) {
currentVertex = queue.shift();
result.push(currentVertex);
this.adjacencyList[currentVertex].forEach(nieghbor => {
if(!visited[neighbor]) {
visited[neighbor] = true;
queue.push(neighbor);
}
});
}
return;
}
23
Q
DLL.push
A
push(val) {
//create new node
var newNode = new Node (val);
//set old tail.next to new node
if (this.length === 0) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next =newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
//set new node.prev to old tail
//change the tail
//increase length
this.length++;
return this;
}
24
Q
what even is a heap
A
a heap is a special kind of binary tree, where the parent nodes are always either larger or smaller than the children (max and min), and left children are filled first - there is no guarantee of ordering between siblings
25
how to implement a stack using a linked list
use a doubly linked list so that removal is constant time, or singly linked but remove from the front
26
queue node and class from scratch
```
class Node {
constructor(value){
this.value = value;
this.next = null;
}
}
```
```
class Queue {
constructor(){
this.first = null;
this.last = null;
this.size = 0;
}
```
}
27
recursion - dont forget
has to have a base case
has to return
28
DLL.shift
```
//removes a node fom the beginning
shift() {
if (this.length === 0) {
return undefined;
}
var storedHead = this.head;
if (this.length === 1) {
this.head = null;
this.tail = null;
}
```
this.head = storedHead.next;
this.head.prev = null;
storedHead.next = null;
this.length--;
return storedHead
}
29
linlked list implementation of a stack class
```
class Stack {
constructor() {
this.first = null;
this.last = null;
this.size = 0;
}
```
30
disadvantage of singly linked lists over arays
no random access like you have in an array
31
when storing a heap as an array, what are the children?
The left child ofa parent is at 2n+1, the right child is 2n+ 2
32
what is the extractMax method of a binary heap
replace the max with the min, and then bubble everything back into the correct order
```
extractMax() {
const last = this.values.pop()
const max = this.values[0]
this.values[0] = last;
this.bubbleDown();
return max;
}
```
```
bubbleDown() {
let index = 0;
const length = this.values.length;
const element = this.values[0];
while(true) {
let leftChildIndex = 2\*index + 1; //note, this might be out of bounds
let rightChildIndex = 2\*index + 2;
let leftChild;
let rightChild;
```
let swap = null;
//swap variable keeps track of the position that we're going to swap with
if (leftChildIndex \< length) {
leftChild = this.values[leftChildIndex];
if (leftChild \> element) {
swap = leftChildIndex
}
}
if(rightChildIndex \< length) {
rightChild = this.values[rightChildIndex]
if (rightChild \> element && rightChild \> leftChild) {
swap = rightChildIndex
}
}
if (swap === null) break;
this.values[index] = this.values[swap]
this.values[swap] = element;
index = swap;
}
}
33
BFS implementation
```
BFS() {
var queue = [];
var visited = [];
if (!this.root) return visited;
queue.push(this.root)
while (queue.length \>= 1) {
var current = queue.shift();
visited.push(current.val);
if (current.left) {
queue.push(current.left)
}
if(current.right) {
queue.push(current.right)
}
}
return visited;
}
```
34
what is the graph lingo
a vertex is a node, an edge is the connection between the node
35
binary search
```
// Refactored Version
function binarySearch(arr, elem) {
var start = 0;
var end = arr.length - 1;
var middle = Math.floor((start + end) / 2);
while(arr[middle] !== elem && start \<= end) {
if(elem \< arr[middle]) end = middle - 1;
else start = middle + 1;
middle = Math.floor((start + end) / 2);
}
return arr[middle] === elem ? middle : -1;
}
```
36
what is a binary tree? a binary search tree?
each node has max two children in a binary tree. in bst, for any node, numbers smaller than that node are to the left, and numbers larger than that node are to the right
37
difference between DLL and SLL
basically the same but with a prev property in the node
- insertion still constant, this is where linked lists excel
- removal is constant, UNLIKE SLL
38
SLL.remove
```
remove(index) {
//handle index being undefined
if (index \< 0 || index \>= list.length) {
return undefined;
}
if (index === 0) {
this.shift()
}
if (index === this.length - 1) {
this.pop()
}
//find the item at index, and reset the previous next to that one's next
else {
var previous = this.get(index - 1)
var current = this.get(index)
previous.next = current.next;
this.length--;
return current;
}
}
```
39
stack.push
```
push(val) {
var newNode = new Node(val)
if (this.size === 0) {
this.first = newNode;
this.last = newNode;
} else {
var oldFirst = this.first
this.first = newNode;
this.first.next = oldFirst;
}
this.size++;
return this.size;
}
```
40
queue implementation
you can use an array with push/shift, or with unshift/pop, but it kind of makes sense to implement your own class since you have to reindex everything with an array. with singly linked list implementation, add to the tail and remove from the head
41
what is the main difference between pre, post, and in-order DFS algorithms for traversing trees?
Pre-order makes it relatively easy to reconstruct the tree
DFSpost: the root gets visited last, you visit all the children first
inOrder: the main thing here is that the data is….in order (on a binary search tree)
42
time complexity for objects
- access
- insertion
- removal
- "hasOwnProperty"
- .keys, .entries, .values
constant time for access, insertion, removal
O(n) for keys, entries, values
43
big O of merge sort
best case and worst case are the same (ONlogN)
44
main big O difference between SLL and DLL
removal! is constant in DLL
45
SLL.pop
pop() {
if (this.length === 0) {
return undefined;
}
```
//find the penultimate node, set to tail
var current = this.head
var previous;
if (!current.next) {
//handle edge case where there is only one node
this.head = null;
this.tail = null;
list.length--;
return current
}
```
```
while(current.next) {
previous = current;
current = current.next
}
//at the end of this while loop, current will be the penultimate node
this.tail = previous
this.tail.next = null;
this.length--;
//check if length is zero now, if so, reset head and tail to be null
if (this.length ===0) {
this.head = null;
this.tail = null;
}
return current;
}
```
46
how to do breadth first search on tree travesal
use a queue (dont worry about implementing your own class, can be an array) and a variable to store the values of nodes visited
Place the root node in the queue
Loop as long s there is anything in the queue
47
graph depth first iterative
```
depthFirstIterative(start){
const stack = [start];
const result = [];
const visited = {};
let currentVertex;
```
visited[start] = true;
while(stack.length){
currentVertex = stack.pop();
result.push(currentVertex);
this.adjacencyList[currentVertex].forEach(neighbor =\> {
if(!visited[neighbor]){
visited[neighbor] = true;
stack.push(neighbor)
}
});
}
return result;
}
48
properties of a singly linked list
head, tail, length
49
SLL.get
```
get(index) {
//handle case where index is undefined
if (index \< 0 || index \> list.length - 1) {
return undefined;
}
//traverse the list, incrementing a counter until you get to an index
var count = 0;
var current = this.head
while (count \< index) {
current = current.next;
count++
}
return current;
}
```
50
basic graph class
```
class Graph {
constructor() {
this.adjacencyList = {}
}
```
addVertex(vertex) {
this.adjacencyList[vertex] = [];
}
addEdge(a, b) {
this.adjacencyList[a].push(b);
this.adjacencyList[b].push(a);
}
```
removeVertex(vertex) {
var edgeList = this.adjacencyList[vertex];
for (var i = 0; i \< edgeList.length; i++) {
var connectedVertex = edgeList[i];
this.removeEdge(vertex, connectedVertex);
}
delete this.adjacencyList[vertex];
}
```
removeEdge(a, b) {
this.adjacencyList[a] = this.adjacencyList[a].filter(v =\> v !== b)
this.adjacencyList[b] = this.adjacencyList[b].filter(v =\> v!==a)
}
51
big O of singly linked list
- insertion
- removal
- search
- access
O(1) for insertion
removal kind of depends - instant from the beginning but O(N) at the end
search is O(N) (worse than arrays)
access is O(N) (worse than arrays)
52
heap insert
```
insert(element) {
this.values.push(element)
//compare to parent
var index = this.values.length - 1;
while (this.getParent(index) \< element) {
//swap with parent, change variable "index"
var parentIndex = Math.floor((index - 1)/2);
var parent = this.values[parentIndex]
this.values[parentIndex] = element
this.values[index] = parent;
index = this.values.indexOf(element);
}
return this.values;
```
53
SLL.unshift
```
unshift(val) {
var newNode = new Node(val);
if (list.length === 0) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head
this.head = newNode;
}
this.length++;
return list;
}
```
54
DLL.unshift
```
unshift(val) {
let newNode = new Node(val);
if (this.length === 0) {
this.head = newNode;
this.tail = newHode;
} else {
var oldHead = this.head;
this.head = newNode;
this.head.next = oldHead;
oldHead.prev = this.head;
}
this.length++
return list;
}
```
55
big O for heap insert
it's log(n) - each row is twice as long as the row before, but in the worst case scenario you're only swapping once per row
56
graph depth first traversal code (recursive)
```
depthFirstRecursive(start) {
//create a list to store the end result, to be returned at the very end
//create an object to store the visited vertices
const result = [];
const visited = {};
const adjacencyList = this.adjacencyList;
//create a helper function which accepts a vertex
function dfs(vertex) {
//the helper function should return early if the vertex is empty
if(!vertex) return null;
//the helper function should place the vertex it accepts into the visited object and push that vertex into an array
visited[vertex] = true;
//loop over all of the values in the adjacencyList for that vertex
result.push(vertex);
adjacencyList[vertex].forEach(neighbor =\> {
if(!visited[neighbor]) {
return dfs(neighbor)
}
```
```
})
//if any of those values have not been visited, recursively invoke the helper function with that vetex
}
```
```
//the helper function should place the vertex it accepts into the visited object and push that vertex into an array
//loop over all of the values in the adjacencyList for that vertex
//if any of those values have not been visited, recursively invoke the helper function with that vetex
dfs(start)
return result;
}
```
57
SLL.set
```
set(index, value) {
//use get function to find value
var foundNode = this.get(index);
if (foundNode) {
foundNode.val = val;
return true;
}
return false;
//if node is not found, return false
//if node is found, update value and return true
}
```
58
graph depth first traversal pseudococd
The function should accept a starting node
Create a list to store the end result, to be returned at the very end
Create an object to store visited vertices
Create a helper function which accepts a vertex
The helper function should return early if the vertex is empty
The helper function should place the vertex it accepts into the visited object and push that vertex into the result array.
Loop over all of the values in the adjacencyList for that vertex
If any of those values have not been visited, recursively invoke the helper function with that vertex
Invoke the helper function with the starting vertex
Return the result array
59
graph DFS(vertex) pseudocode
DFS(vertex):
if vertex is empty
return (this is base case)
add vertex to results list
mark vertex as visited
for each neighbor in vertex's neighbors:
if neighbor is not visited:
recursively call DFS on neighbor
60
graph depth first traversal iterative
The function should accept a starting node
Create a stack to help use keep track of vertices (use a list/array)
Create a list to store the end result, to be returned at the very end
Create an object to store visited vertices
Add the starting vertex to the stack, and mark it visited
While the stack has something in it:
Pop the next vertex from the stack
If that vertex hasn't been visited yet:
Mark it as visited
Add it to the result list
Push all of its neighbors into the stack
Return the result array
61
DLL.get
get(index) {
```
//check if index is valid
if (index \< 0 || index \>= list.length) {
return undefined;
}
//figure out if index is closer to beginning or end
if (index \<= list.length/2) {
var current = this.head;
for (var i = 0; i \< index; i++) {
current = current.next;
}
```
```
} else {
var current = this.tail;
for (var i = list.length-1; i \> index; i--) {
current = current.prev
}
}
return current;
}
```
62
how to do DFS pre-order
```
DFSpre() {
var visited = [];
if (!this.root) return visited;
var current = this.root
```
function visit(node) {
visited.push(node.val)
if (node.left) visit(node.left);
if (node.right) visit(node.right);
}
visit(current);
return visited;
}
63
graph breadth first pseudocode
BREADTH FIRST
This function should accept a starting vertex
Create a queue (you can use an array) and place the starting vertex in it
Create an array to store the nodes visited
Create an object to store nodes visited
Mark the starting vertex as visited
Loop as long as there is anything in the queue
Remove the first vertex from the queue and push it into the array that stores nodes visited
Loop over each vertex in the adjacency list for the vertex you are visiting.
If it is not inside the object that stores nodes visited, mark it as visited and enqueue that vertex
Once you have finished looping, return the array of visited nodes
64
SLL.shift
```
shift() {
if (list.length === 0) {
return undefined;
} else {
var storedHead = this.head
this.head = this.head.next;
this.length--;
return storedHead;
}
}
```
65
how to implement a stack using an array
push and pop
66
DFS post-order
```
DFSpost() {
var visited = [];
if (!this.root) return visited;
var current = this.root
```
function visit(node) {
if (node.left) visit(node.left);
if (node.right) visit(node.right);
visited.push(node.val)
}
visit(current);
return visited;
}
67
what are some examples of graphs
social networks, location mapping, "frequently bought with", "people also watched"
68
DLL.set
```
set(index, val) {
if (this.get(index)) {
var changeNode = this.get(index);
changeNode.val = val;
return true;
}
return false;
}
```
69
DFS in-rder
```
DFSinOrder() {
var visited = [];
if (!this.root) return visited;
var current = this.root
```
function visit(node) {
if (node.left) visit(node.left);
visited.push(node.val)
if (node.right) visit(node.right);
}
visit(current);
return visited;
}
70
to DFS a graph, you use a \_\_\_\_\_
STACK
71
to BFS a graph, you use a \_\_\_\_
QUEUE
72
easy DepthFirst for graphs
73
easy depth first recursive for directed graphs
```
function depthFirstPrintRecursive(graph, start) {
console.log(start)
for (let neighbor of graph[start]) {
depthFirstPrint(graph, neighbor);
}
```
}
74
easy breadth first print for directed graph
```
function breadthFirstPrint(graph, start) {
const queue = [start];
while(queue.length \> 0) {
const current = queue.shift();
console.log(current);
for (let neighbor of graph[current]) {
queue.push(neighbor);
}
}
}
```
75
what are your options for traversing a graph?
depth-first recursive (uses call stack)
depth-first iterative (uses stack)
breadth-first iterative (uses queue)
76
easy hasPath function for directed graph (breadth first)
```
function hasPath(graph, src, dest) {
//breadth first solution
const queue = [src]
while (queue.length \> 0) {
const current = queue.shift();
if (current === dest) return true;
```
for(let neighbor of graph[current]) {
queue.push(neighbor);
}
}
return false;
}
77
explain easy hasPath function for directed graph (depthFirst)
```
function hasPathDepthFirst(graph, src, dest) {
if (src === dest) return true;
```
for (let neighbor of graph[src]) {
if (hasPathDepthFirst(graph, neighbor, dest) === true) {
return true;
}
}
return false;
}
78
explain a hash table
