Technical Interviews: Difference between revisions
| (7 intermediate revisions by the same user not shown) | |||
| Line 5: | Line 5: | ||
==Algorithms== | ==Algorithms== | ||
{{main | Interview Algorithms}} | {{main | Interview Algorithms}} | ||
In general, consider the following approaches | |||
* Brute-force and searching | |||
* Dynamic Programming | |||
* Greedy (sorting + take the best at each step) | |||
* Linear searching (with 2 pointers or sliding window) | |||
** Usually the answer if you're searching for a connected segment along an array or string | |||
** E.g. max contiguous subarray | |||
Be familiar with common algorithms and data structures: | |||
;Sorting | |||
* Merge sort | |||
* Quicksort | |||
* Quickselect | |||
* Counting sort | |||
* Radix sort | |||
* Binary search | |||
;Linked-lists | |||
* Doubly linked list, circular linked list | |||
;Trees | |||
* Preorder, inorder, postorder traversal | |||
* AVL rotations | |||
* Union-Find | |||
* Heaps | |||
* Using <code>std::set</code>, <code>std::map</code>, <code>std::priority_queue</code> | |||
;Graphs | |||
* DFS, BFS | |||
* Minimum spanning tree (Prim's or Kruskal's algorithm) | |||
;Hashing | |||
* Using <code>std::unordered_set</code> and <code>std::unordered_map</code> | |||
==Computer Systems== | ==Computer Systems== | ||
| Line 33: | Line 68: | ||
* Make sure you can identify server from id of data (e.g. adding it to hashing or maintaining an index) | * Make sure you can identify server from id of data (e.g. adding it to hashing or maintaining an index) | ||
====Caches | ====Caches==== | ||
* Place a cache on the request layer. | * Place a cache on the request layer. | ||
* Cache in memory, not disk (e.g. [http://memcached.org/ memcached], redis) | * Cache in memory, not disk (e.g. [http://memcached.org/ memcached], redis) | ||
| Line 47: | Line 82: | ||
* Collapsed Forwarding: collapse the same or similar requests and return the same result to clients | * Collapsed Forwarding: collapse the same or similar requests and return the same result to clients | ||
* You can also collapse requests that are spatially close together on the database | * You can also collapse requests that are spatially close together on the database | ||
====Indexes==== | ====Indexes==== | ||
* Indexes are used to quickly find small data in large datasets | |||
* Indexes are stored in memory, data separated across several servers | |||
* Possibly many layers of indexes | |||
====Load Balancers==== | ====Load Balancers==== | ||
| Line 67: | Line 104: | ||
==System Design== | ==System Design== | ||
==Misc== | |||
* [https://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html Steve Yegge Get that job at Google] | |||