Review Basics - CS

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

Section 1

Question Answer
Search sorted arrayO(logn)
Build sorted arrayO(nlogn)
Search linked listO(n)
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

Question Answer
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

Question Answer
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

Question Answer
trim()removes leading and trailing whitespace
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

Question Answer
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

Question Answer
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
considerationsfailure, availability, reliability, read or write heavy, security. there is no perfect system. talk about tradeoffs. be open about the weaknesses of your design

Section 6

Question Answer
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

Question Answer
radix best, worst, avgnk, nk, nk (k passes on n values)
radix spacen+k
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

Question Answer
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

Question Answer
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

Question Answer
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

Question Answer
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

Question Answer
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

Question Answer
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.
What is Thread.currentThread() ?returns the currently executing thread object
What is Thread.isAlive() ? returns if THIS thread is alive
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

Question Answer
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

Question Answer
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.

Section 16

Question Answer
Why are there new concurrency things?to keep up to date with modern multi-core and multi-processor systems
What are lock objects?similar to the intrinsic locks/monitors, they can only be owned by 1 thread and have wait/notify capabilities. BUT you can back out of an attempt to acquire a lock (tryLock)
What are executors?help launch/manage threads for separate management from app. recycles threads, puts them in a queue.
What are semaphores?a signaling mechanism. (imagine a certain number of bathrooms with 1 key for each bathroom) maintain a count/ "available permits"
How do you use semaphores?you release/increment the # of permits, or acquire/decrement the # of permits. if none left, wait. this can be used like lock/unlock
What are mutexes?imagine 1 bathroom and 1 key. a mutex can only be released by the thread that owns it. allows only 1 thread to access resource

Recent badges