Interview Refresh


5 Tests for a Phone Screen

System Design!!!!

Ack I gotta learn Java again:

Trees, Search

A* search*_search_algorithm
* lol just pick the “shortest” or “best” path each time
* simplification of Djisktra’s algorithm

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

Dijkstra’s algorithm
* Traverse a graph, taking the next most shortest route each time
* record the minimum distance to each adjacent node as you go

* n-ary tree
* competitor for hashes

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

Javascript Style Guide

Javascript Google Closure Library

Javascript Docs


* 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?

Big Table




Bayes’ Theorem

Adjacency Matrix

Set Operations


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

+ 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

* 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

+ 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 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


+ asList
+ binarySearch
+ copyOf
+ copyOfRange
+ deepEquals
+ deepHashCode
+ deepToString
+ equals
+ fill
+ hashCode
+ sort
+ toString

+ 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

+ inside a block, use: var foo = function() {}
+ preferred: = 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

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

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

+ 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

+ graph traversal application in the browser for airport navigation
+ simulator for Peoplesoft to implement e-business process

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

+ 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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s