Interview Refresh

Refresh

http://dondodge.typepad.com/the_next_big_thing/2010/09/how-to-get-a-job-at-google-interview-questions-hiring-process.html

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?

Big Table http://static.googleusercontent.com/external_content/untrusted_dlcp/labs.google.com/en/us/papers/bigtable-osdi06.pdf

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

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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