**Refresh**

http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html

5 Tests for a Phone Screen https://sites.google.com/site/steveyegge2/five-essential-phone-screen-questions

**System Design!!!!**

http://research.google.com/pubs/DistributedSystemsandParallelComputing.html

http://labs.google.com/papers/gfs.html

http://labs.google.com/papers/bigtable.html

http://labs.google.com/papers/mapreduce.html

Ack I gotta learn Java again: http://javarevisited.blogspot.com/2011/04/top-20-core-java-interview-questions.html

**Trees, Search**

A* search http://en.wikipedia.org/wiki/A*_search_algorithm

* lol just pick the “shortest” or “best” path each time

* simplification of Djisktra’s algorithm

Heap http://en.wikipedia.org/wiki/Heap_(data_structure)

binary tree held in an array

* every node is greater than its children (max-heap) or less than (min-heap)

* useful for priortity queues

* can be used for sorting — heapsort

fibonacci heap http://en.wikipedia.org/wiki/Fibonacci_heap

?

Dijkstra’s algorithm http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

* Traverse a graph, taking the next most shortest route each time

* record the minimum distance to each adjacent node as you go

Trie http://en.wikipedia.org/wiki/Trie

* n-ary tree

* competitor for hashes

Ternary Tree http://en.wikipedia.org/wiki/Ternary_tree

* Tree where each node has 3 children, less than, equals and greater than

Balanced Tree

* depth is uniform (within one) across tree

* distance from root to each leaf differs by no more than 1

Java Concurrency/Synchronization http://www.javamex.com/tutorials/synchronization_volatile.shtml

Javascript Style Guide http://google-styleguide.googlecode.com/svn/trunk/javascriptguide.xml

Javascript Google Closure Library http://code.google.com/closure/library/

Javascript Docs http://code.google.com/p/jsdoc-toolkit/

**Classifications**

NP-complete http://en.wikipedia.org/wiki/NP-complete

* problems with solutions that can be **confirmed** in polynomial time — i.e. confirming them is doable.

* P is set of problems can can be solved in polynomial time — i.e. doable

* the big question is, for every NP problem, is there a polynomial-time limited way to solve it? We know P != NP problems exist,

but can we say P == NP?

Interesting https://www.facebook.com/notes/facebook-engineering/software-design-glossary/10150309412413920

Interesting http://blog.8thlight.com/uncle-bob/2011/09/30/Screaming-Architecture.html

**Math**

**Bayes’ Theorem**

**Adjacency Matrix**

**Set Operations**

**Problems**

**Permutation Generation**

* use a stack, at each iteration push current + next unused

**Combination Generation**

* a little trickier than permutations

* use a stack, at each iteration push current + next unused for all unused > used

* if len(current) + len(unused > max) == choose length, then done

**Graph Coloring**

? permutation problem

**The Knapsack Problem**

? permutation or combination problem — generate & evaluate permutations

**Quick Sort**

+ for in-place sorting, first swap index item with last

+ swap into place at the end of partitioning

+ watch out for annoying edge conditions

+ use sort2 and sort3 to work out tricky final sorts

**Heap**

+ stored in array

+ parent of node i is i/2

+ children are at 2i and 2i + 1

+ parent is greater than children (max heap)

+ parent is less than children (min heap)

+ can use as a priority queue

**Merge Sort**

+ recurse to find range

+ sort small ranges fast

+ sort 2 ranges together

**Breadth First Search**

+ uses FIFO queue

+ head recursion (roughly)

+ space complexity O(b^d)

+ time complexity O(b^d)

+ exponential in depth of graph

**Depth First Search**

+ uses FILO queue

+ tail recursion (roughly)

+ theoretically, space and time complexity same as bredth-first

+ in practice, depth can be limited based on available memory

+ better suited for branch-searching heuristics

**Djijstra Search**

+ traverse shortest path first

+ record distance to all cells

**Red-Black Tree**

* balanced tree

* similar to B-tree of order 4

?

**B-Tree**

* balanced tree

* each node contains n values

* on insert, find & add value to the node where it belongs

* if that node is already full, split into two nodes at the median value

* push the median value into the parent node, which may cause it to split, or create a new root

**Trie**

+ n-ary tree, record each character in the string until you get to the end

+ use instead hash map

**Tree Insert and Removal**

? sorted vs. unsorted

**Balanced Tree Insert and Removal**

?

**Javascript**

?

**Javascript Custom Exceptions**

?

**Javascript Type Casting**

?

**Javascript Prototypes (for real)**

?

**Javascript Google Closure Library**

?

**Javascript Functions that take a variable number of arguments**

?

**Java volitile for synchronization**

+ synchronized on reference, not on object

**Reference**

**Arrays**

+ asList

+ binarySearch

+ copyOf

+ copyOfRange

+ deepEquals

+ deepHashCode

+ deepToString

+ equals

+ fill

+ hashCode

+ sort

+ toString

**Collections**

+ addAll

+ asLifoQueue

+ binarySearch

+ checkedCollection…List…Map…Set

+ checkedSortedCollection…List…Map…Set

+ copy

+ disjoint

+ emptyEnumeration…Iterator

+ emptyList…Map…Set…ListIterator

+ enumeration

+ fill

+ frequency

+ min/max

+ reverse

+ shuffle

+ singletonCollection…Map…List…Set

+ synchronized

+ unmodifiable

**Javascript**

+ inside a block, use: var foo = function() {}

+ preferred: Foo.prototype.bar = function() {

+ note: closure keeps a pointer to its enclosing scope

+ note: If you need a map/hash use Object instead of Array

+ ‘default’ || operator: var win = opt_win || window;

+ note: The following are all false in boolean expressions: null / undefined / ” the empty string / 0 the number

+ note: But be careful, because these are all true: ‘0’ the string / [] the empty array / {} the empty object

+ note: use an array as a stringbuilder, and convert it into a string with myArray.join(”)

+ note: that since assigning values to an array is faster than using push() you should use assignment where possible

+ note: for (var i = 0, paragraph; paragraph = paragraphs[i]; i++) {

+ note: The point of having style guidelines is to have a common vocabulary of coding so people can concentrate on what you’re saying rather than on how you’re saying it. We present global style rules here so people know the vocabulary, but local style is also important. If code you add to a file looks drastically different from the existing code around it, it throws readers out of their rhythm when they go to read it. Avoid this.

**Order of Complexity**

Type |
Search |
Insert (front) |
Insert (end) |
Delete (front) |
Delete (end) |
Amortized Cost? |

binary tree | O(log n) | find + O(c) | NA | find + O(c) | NA | rebalancing |

Trie | O(m) m = size of string | O(m) m = size of string | NA | O(m) m = size of string | NA | no |

**Technical Highlights**

Dawn of Time & Home

+ serial port library in C/C++/embedded assembly

+ bit-level vga graphics library in C/C++/embedded assembly

+ sold to a startup for stock options (value: $0)

+ cascading property pages — Spring-like framework using Json-like syntax with cascading object properties

Mosaix

+ Mo phone home — scripts to invoke autodialer to call the help desk on some error conditions

RealNetworks

+ Roxen/Pike templates for dynamic pages which remained fundamental to e-commerce side for years

RevX

+ MtoM — generalized Many-to-many structure allowed arbitrary resources to appear as lists on either side of a list, for easy association between large-ish lists of items (huge hit with our customers at British Petroleum)

+ DateFormatter — Trie implementation parsed a fixed date (Jul 4, 2001) to produce a date format string, which was then used for localized date formatting in server pages

+ Dynamic HTML & HTTP data get — AJAX before it was called AJAX

SMO

+ graph traversal application in the browser for airport navigation

+ simulator for Peoplesoft to implement e-business process

IS2

+ chained XSLT processor pulled XML from the mainframe & chained it through XSLT files to produce XML served to the customers

Disney

+ live metrics — super-fast, lightweight in-memory statistics

+ relationship service prototype — modeled a graph of relationships between aribitrary resources (URIs) with provisions for type definitions and custom lifecycle state machines

+ API to global registration as JSON/HTTP service, mapping URLs to Command objects using reflection

+ access control model for JSON/HTTP registration service

+ oauth 1.0 2-legged implementation