# Review Basics - CS(2)

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

## Section 17

Question | Answer |
---|---|

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 combinations | for 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 combinations | n!/(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

Question | Answer |
---|---|

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

Question | Answer |
---|---|

XML | a standard data model to share and distribute data |

pros of SQL | easy 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 SQL | pretty hefty and complex, hard for humans to read security isn't the best |

pros of XML | easy to distribute and readable for humans and machines, most languages can perform XML parsing, easy to edit data |

cons of XML | if clients want only part of the data, they have to parse the entire file |

text files | simple, but complex parsing, and if any changes, parsing needs to be edited |

## Section 20

Question | Answer |
---|---|

bidirectional BFS | lookup from source and destination. |

compare running time of bidirectional BFS and BFS | BFS, if branching is b for n nodes: 1 + b + b^2 ....b^d. bidirectional: 2 + 2b+ 2b^2 +... b^(d/2). |

smart machine distribution | by location, or something similar |

big data cannot be stored in space | spread 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

Question | Answer |
---|---|

steps for solving a problem | listen, good example, brute force, optimize, walk through, implement, test. |

example for algorithm vs testing | testing should be smaller! also check edge cases |

when you find an error | don't quickly jump to fix it. what caused it? |

mark things you want to check | say todo, check this value, so your interviewer knows you are going to come back and didn't just ignore the error |

testing | first walk through conceptually. then check hot spots. then small test cases. |

brute force | state the running time |

## Mistake Review

Question | Answer |
---|---|

if it's a messy problem | think through and write out all the possible situations. organize!! |

creating classes sometimes helps! | makes code prettier |

check | one more time than you feel necessary |

examples | should be challenging |

be careful if hashmaps | changed. AND when you PUT something and you're counting. = 1 |

## Pages linking here (main versions and versions by same user)

No other pages link to this page. See Linking Quickstart for more info.