# Review Basics - CS(2)

annire's version from 2017-01-04 18:24

## Section 17

What is the equation for permutations?(n!)/(n-k!). where n is the number of items you are choosing from to create a list of length k
What if you have repeated letters for a permutation?(total)/(amount of arguments that are the same)
round table(number of seats - 1)! *lock a person in a position
Permutations vs combinationsfor permutations, order MATTERS. 321 != 123. MORE. For combinations, order does not matter. 123 = 321.
What does "n choose k" mean?# of subsets of size k from a set of size n.
Equation for combinationsn!/(k!(n-k)!)
Equation for odds(chances it happens)/(total number of situations that are possible/right or wrong)
How can you seat 16 people in 2 tables of size 10 and 6? (16 choose 10)(9!)(6 choose 6)(5!)

## Section 18

How can you simulate a queue with 2 stacks?enqueue: pushing into inbox. dequeue: if outbox has something. pop that. if it's empty. pop everything in inbox into outbox. then pop.
How to check if a binary tree is a BST?root itself has to be in the range of min and max. its children have to be in the range of min/root and max/root.
How do you find the "next" in a BST?if right child == null. go up until parent is a left child (or root). if right child !=null, it's the min of right subtree.
How do you find the min of a BST?keep going left

## Section 19

XMLa standard data model to share and distribute data
pros of SQLeasy way for clients to query processing over the data. have standard database features (backing up data, security), integration is pretty standard in software dev environments
cons of SQLpretty hefty and complex, hard for humans to read security isn't the best
pros of XMLeasy to distribute and readable for humans and machines, most languages can perform XML parsing, easy to edit data
cons of XMLif clients want only part of the data, they have to parse the entire file
text filessimple, but complex parsing, and if any changes, parsing needs to be edited

## Section 20

bidirectional BFSlookup from source and destination.
compare running time of bidirectional BFS and BFSBFS, if branching is b for n nodes: 1 + b + b^2 ....b^d. bidirectional: 2 + 2b+ 2b^2 +... b^(d/2).
smart machine distributionby location, or something similar
big data cannot be stored in spacespread out among different machines. how to spread them out? how to access them quickly?
how to detect if you've gone to the same web page?combination of similarity in URL and content. content changes on the same web page. URLs aren't reliable. small changes in the string may seem like a diff web page, but actually are the same
for the REAL web (massive), do you ever really stop crawling?no. we just avoid going to the same places and looping. set priorities on what to visit next (places you haven't gone). if we want to stop. set a min priority in order to visit. (eventually everything will have a lower priority)

## Section 21

steps for solving a problemlisten, good example, brute force, optimize, walk through, implement, test.
example for algorithm vs testingtesting should be smaller! also check edge cases
when you find an errordon't quickly jump to fix it. what caused it?
mark things you want to checksay todo, check this value, so your interviewer knows you are going to come back and didn't just ignore the error
testingfirst walk through conceptually. then check hot spots. then small test cases.
brute forcestate the running time