Starting short training before competency test at my current work. You can find list of things you have to know. And comparison to those from Amazon. Below you can find advices what or where to read to be ready to interview or smth like this
Needed materials and topics can be found here:
Data Structures - array, linked list, stack, queue, dictionary, hash table, tree, binary search tree, hashtable, heap, AVL/RB tree, B-tree, skip list, segment tree
Useful links: Arrays article, Article about structures, used to implement dictionaries, Skip list implementation
Algorithms - sorting, searching, data structure traversal algorithms, algorithm complexity, O() notation, space/time complexity, greedy and dynamics algorithms, tree, graph algorithms, N-logN sorting
Useful links: Several O(N*logN) sorting implementations, quite good Wiki article about Binary search
Graph algorithms - dfs, bfs, loops (usual and Euler’s), Floyd-Warshall, Kruskal’s algorithm
Concurency - shared state and synchronization problems, sync primitives, basic parallel algorithms, sync primitives efficiency, data and task parallelism patterns, deadlocks, race conditions, thread scheduling details, GUI threading models
The best info about concurency&threads&processes you can find in Richter’s “CLR via C# 3rd edition” book and in APUE book (“Advanced Programming in Unix Environment”). Richter gives samples and explanations, and APUE gives real world situation. Thread scheduling article, WPF threading model
Coding skills - OOP, refactoring, static and dynamic typing, script and compiled languages, closures, declarative programming, lazy evaluation, tail recursion, functional programming, code generation
Basic things can be found in Wiki and StackOverflow. Declarative programming topic on SO, about tail recursion and lazy evaluation see some functional language (say, ocaml). Short intro to code generation in wiki
Low-level programming - PC architecture, memory, processor, multitasking, address space, heap memory, stack, virtual machine concept, kernel mode vs user mode, process context, memory address translation, swap, static and dynamic linking, compilation, interpretation, jit compilation, garbage collection, memory addressing, interrupts + microcode
Multitasking article, Stack&Heap, Quite nice pdf about Virtual Memory and address translation
Architecture - architecture layers, common-used design patterns, describe component with diagrams, SOA, communication with RPC or message-based
Database - SQL queries, transactions, ACID, views, stored procedures, triggers, serializable transactions, normal forms
Testing - unit tests, refactor code to be able to test it, integration tests, moqs and stubs
Network and communication - basic understanding of network concepts, web services, HTTP, DNS, SSL, socket-level programming, SOAP, JSON, whole network stack, OSI model, stateful/stateless models
Source control, CI - merge code, resolve conflicts, CI, automation scripts
For comparison, same table from Amazon
Tech Prep Tips
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.
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.
Whenever someone gives you a problem, think graphs. They are the most fundamental and flexible way of representing any kind of a relationship, so it’s about a 50-50 shot that any interesting design problem has a graph involved in it. Make absolutely sure you can’t think of a way to solve it using graphs before moving on to other solution types. This tip is important!
Other data structures
Math – a plus if you go over it, but not a must
Basic discrete math questions. Counting problems, probability problems, and other Discrete Math 101 situations. Familiarity with n-choose-k problems and their ilk.
Operating Systems: Processes, threads and concurrency issues. Locks and mutexes and
semaphores and monitors and how they work. Deadlock and livelock and how to avoid them. What resources a processes needs, and a thread needs, and how context switching works, and how it’s initiated by the operating system and underlying hardware. A little scheduling.
Concurrent Programming in Java.
Coding: Preferably C++ or Java. C# is OK. Please know a fair amount of detail about your
favorite programming language.