Базовые знания для собеседования в amazon

Всем привет, наверное многие уже слышали о том что в Киев через месяц приезжают сотрудники амазона для проведения собеседований. Мне на почту выслали материал для подготовки. В принципе ничего секретного в нем нету и по сути это университетская база для каждого программиста. Вообщем вот, может кому-то будет дополнительный стимул подучить забытое =) :

Algorithm Complexity: you need to know Big-O.

Sorting: know how to sort: the details of at least one n*log(n) sorting algorithm, preferably two
(say, quicksort and merge sort). Merge sort can be highly useful in situations where quicksort is
impractical, so take a look at it.

Hashtables

Trees: basic tree construction, traversal and manipulation algorithms. Binary trees, n-ary trees,
and trie-trees at the very very least. At least one flavor of balanced binary tree, whether it’s a red/
black tree, a splay tree or an AVL tree. Tree traversal algorithms: BFS and DFS, the difference
between inorder, postorder and preorder.

Graphs: There are three basic ways to represent a graph in memory (objects and pointers,
matrix, and adjacency list), each representation and its pros and cons.

The basic graph traversal algorithms: breadth-first search and depth-first search. Their
computational complexity, their tradeoffs, and how to implement them in real code.

Dijkstra and A*, if you get a chance.