# Review Basics - CS

annire's version from 2017-01-03 21:48

## Section 1

Search sorted arrayO(logn)
Build sorted arrayO(nlogn)
BST worst caseO(n)
BST average caseO(logn)
build BSTO(n^2)
RBTree buildO(nlogn)
RB tree allO(logn)
Heap buildO(nlogn) but there's a way for O(n)
Heap search O(n)
Heap insertO(logn)

## Section 2

Quicksort best, avg, worstnlogn, nlogn, n^2
Mergesort best, avg, worstnlogn, nlogn, nlogn
Heapsort best, avg, worstnlogn, nlogn, nlogn
quicksort spaceO(logn) - stack depth
mergesort spaceO(n)
heapsort spaceO(1)
which is stable?mergesort
why is quicksort better than mergesort?quicksort doesn't need extra memory. also fewer swaps. simpler. even though worst case is bad it's easy to avoid
why is quicksort better than heapsort?fewer swaps. quicksort doesn't do unnecessary swaps.

## Section 3

bubble best, avg, worstn, n^2, n^2
insertion best, avg, worstn, n^2, n^2
selection best, avg, worstn^2, n^2, n^2
how does bubble sort work?compare adjacent (so biggest goes to end. lock in place.)
how does insertion sort work?lock first. look at next, if smaller than previous. switch. repeat. lock. next.
how does selection sort work?find smallest. swap with first open pos.
which can detect if list is already sorted?bubble, insertion
insertion vs selectioninsertion is better because it only scans until the right spot is found. selection must look at everything that is left. so insertion has fewer comparisons. BUT more writing bc of shifting. insertion also has more variability in RT

## Section 4

hashmap vs hashtablehashtable is synchronized. hashmap has linked subclass, allows for predictable iterations. also allows null.
hashmap.keyset()returns a set of all the keys
get an item in the key set.. what does it return?an arraylist of all the values that have that key
Arrays.sort(charArray). what does it do?sorts the character array alphabetically
how do you turn a character array into a string?String.valueOf(charArray)
Array.sort() and Collectios.sort()primitives: quicksort. arbitrary objects. mergesort (for stability) (+guaranteed nlogn)

## Section 5

horizontal scalingincrease the number of nodes (like the number of servers)
vertical scalingincrease the resources of a specific node (like the memory of a server)
load balancingimprove the distribution of workloads across multiple computing resources (build a network of cloned servers)
database denormalizationadd redundant info, speed up reads (slowww down writes). hard to keep synchronous
database partitioning ("sharding")splitting the data across multiple machines + knowing which data is on which machine
name 3 types of partitioningvertical, key/hash-based, directory based. many architectures end up using multiple partitioning schemes
cachingsimple key-value pairing that sits between the application and data store. app first tries the cache
asynchronous processing and queuesslow operations, do asynchonously.

## Section 5.5

what is bandwiththe max amount of data that can be transferred in a unit of time (bits/second)
throughputthe actual amount of data that is transferred (bandwidth = max)
latencydelay between sender sending and receiver receiving
mapreducea program that helps to process a large amount of data. there is a shuffle - put all the keys together. reduce takes a key and associated values and "reduces"them. (sometimes multiple times).
why is mapreduce helpful?enables a lot of processing in parallel to occur --> processing a lot of data becomes more scalable

## Section 6

queue methodsadd(e), remove, element / offer(e), poll, peek
remove vs pollremove returns an exception if empty, poll returns null if empty
how to instantiate a queue?w/LinkedList, PriorityQueue...
how to instantiate a stack?Stack()
what is a priority queueit's an abstract concept like "a list" or "a map"
how can you implement a priority queue?with a heap
why are heaps useful?access max/min quickly, insertion is fast (logn) so it's good for dealing with incoming events/data, good for schedulers, also it can be represented with an array so in place sorting
how does heapify work?bubble down or trickle up, swap. once ok, stop.
how to instantiate a priority queue?PriorityQueue<E>
what is the max int?about 2 billion (2^ 31 -1)
array representation of heapL = i*2 + 1, R = i*2 +2, parent = (i-1)/2

## Section 7

radix best, worst, avgnk, nk, nk (k passes on n values)
how does radix sort work?you look at one digit at a time (either most/least significant first), sort based on that, then look at next, sort again. **STABLE**
bucket best worst avgn + k, n + k, n^2 (pass on n, then merges k buckets) **order WITHIN bucket is arbitrary**
bucket spacen
bucket vs radixbucket only does 1 pass, orders the buckets, then puts it into 1 array. radix goes through and re-buckets (one next digit)
counting best worst avgn + k, n+ k, n+ k
counting spacek
what is counting sortit's a subroutine for radix sort. it stores a single number (how many are in this bucket)

## Section 8

What does it mean to be NP complete?there is no fast (
What does NP mean?can be verified in polynomial time // another def: solvable in polynomial time by a non-deterministic TM
What does NP hard mean?the problem is at least as hard as all problems in NP. (for all X in NP, X can be polynomially reduced to Y)
list as many NP complete problems as you canTraveling salesman, knapsack, ham path/cycle, s-t, n-color (n>2), independent, clique, subsetsum, partition, SAT
what is the traveling salesman problem?given a list of cities, find the shortest path visiting each city only once, and returning to the original city. it can also be thought of as a ham_cycle with least weight
what is the knapsack problem?given a "knapsack" with items of different weights and values, find the optimum/max values with weight less than some capacity
what is the P vs NP problem?is everything that can be verified quickly also solvable polynomially/quickly?
What are the implications of P = NP?lots of algorithms used for computer security/encryption would be able to be broken. essentially the entire way the internet is secured would have to be done over

## Section 9

what traits does a hash table havehas a capacity (def 16), like the number of buckets, and a load factor (def 0.75) on when rehashing should occur
what makes a good hash function?properly disperses the elements among the buckets. the INDEX in the array is NOT the same as the key.
how does hashing/hash table work?a hash function uses a key to tell an item (with a key and value), which bucket/index to go to. then when you are given that key, you use the hash function to find that value.
collision1. linear probing (put it in next available neighbor). 2. chaining. that index --> a linked list/tree. you get the position that key/value pair should be in. then iterate through the linked list to find the key --> value.
how many keys/values can exist in a hash table?as many as you want. but each key is UNIQUE. values are not.

## Section 10

describe inorder, preorder, and postorderinorder: L, self, R; pre order: self, L, R; post: L, R, self.
what are the traits of a heapbasically a complete tree, except for last row **fill left first**
how does compareTo work?for a.compareTo(b), if ab , returns 1
what are three ways to represent graphs?matrix, adjacency list, and object/pointers
pros/cons of matrix?you can keep track of edge weights as well as direction, quick access to check relationship between 2 nodes. Slow for searching.
pros/cons of adjacency list?doesn't keep track of edge weights, but it's faster for searching/accessing a list of neighbors
what are the max number of pointers?n^2 where n = nodes
space of adjacency list?n + m
space of matrix?n^2

## Section 11

What is the running time of BFS?matrix: O(n^2), adjacency list, O(n+m) (m = all the edges/ sum of degrees)
What is the running time of DFS?matrix: O(n^2), adjacency list, O(n+m)
Compare BFS and DFSBFS can help you find the shortest path, there is more memory usage due to branching factor, relational. DFS could go on indefinitely, it is hierarchical and can help with pre/in/postorder
How to tell if a graph is not connected with DFS?if you have to call DFS twice from root

## Section 12

Compare processes and threadsa process can have multiple threads. a process is like the program itself (ex :word), and different threads do different tasks (Ex: listen to keyboard, print out words, save file). most apps today are multi-hreaded. a process is a self-contained execution environment
multi-core vs multi-processormulti-core is when there are multiple execution cores within a CPU, multi-processor is having multiple CPUs working in parallel
what are 2 ways of initiating a thread?implement runnable interface, subclass Thread
Which way is better for using thread? Why?runnable allows you to subclass other things (more general), it also separates runnable from the thread object (more flexible)
What is context switching?it's when a single processors switches work between 2 threads. this can happing very quickly and very often to feel as if the threads are running in parallel. it's an expensive procedure. also, not just for threads, but for proceses too
What does Thread.sleep() do?makes processor time available for other threads, which allows for pacing, waiting for other threads. (not exact)
What is an InterruptedException?when another thread interrupts the current thread. often intentional, and programmer decides how to respond to the interrupt (often -> terminate)
What happens if a thread doesn't throw InterruptedException?many methods throw this exception, but if the thread doesn't, then periodically check if(Thread.interrupted()) and throw a new exception. (aka, there's no automatic detection/catching of the IE)
What does Thread.interrupted() do?clears the interrupt status, (isInterrupted() doesn't)

## Section 13

What does Thread.join() do?if we call t.join in thread s. s will wait until thread t is done, then continue on. you can also specify a waiting period, and if t hasn't finished, s moves on.
Why is synchronization efficient but hard?threads can access fields/objects which allows threads to communicate with each other, it's efficient, but difficult because thread interference and memory consistency errors can occur.
thread interferencewhen multiple threads access shared data at the same time. get, change. store. there are multiple steps
memory consistency errorsinconsistent views of shared memory. let's say A is changing and B is printing. there is no guarantee that A's changes will be visible to B. control happens-before to fix
how can we fix thread interference and memory consistency errors?with synchronized methods and statements

## Section 14

What are synchronized methodspublic synchronized void ... blocks all other execution until the current one is done with the entire object. creates a happens-before relationship with all subsequent method invocations on this object.
Can constructors be synchronized?no.
What are synchronized statementsmore fine-tuned synchronization. specify the object that provides the monitor/intrinsic lock. synchronized(this) { ... } or a lock object
What are intrinsic locks/monitors?the are built into every Java object. they enforce exclusive access to an object's state AND establish a happens-before relationship
How to acquire access to a monitor?a thread must first acquire the lock, and then release when done. when acquired = "owns" the lock
When does acquiring/releasing occur for a method?acquired when invoked, released when return
Static fields' locks?different from the lock for instance of class

## Section 15

What is liveness?It's a concurrent applications' ability to execute in a timely manner. (not go on forever)
What is deadlock?it's the most common liveness problem. it's when 2 threads are blocked forever, waiting for each other. (bowing at the same time)
What is livelock?it's less common than deadlock, it's when the 2 threads are two busy responding to each other to continue their work. (passing in the corridor)
What is Starvation?when 1 greedy thread calls a very long synchronized method a lot and others have to wait.
What are some ways to help coordinate?use guided blocks and immutable objects
What are guided blocks?poll a condition before proceeding
What are immutable objects/why do they help coordination?cannot be changed after construction, make a new one instead. don't need protection from thread.