I made a couple of changes to the original project to be able to write Markdown in flashcards. For the original repository checkout README.md in the repo above.
Note on flashcards: The first time you recognize you know the answer, don’t mark it as known. You have to see the same card and answer it several times correctly before you really know it. Repetition will put that knowledge deeper in your brain.
Practice, practice, practice, until I’m sick of it, and can do it with no problem (some have many edge cases and bookkeeping details to remember)
Make use of built-in types so I have experience using the built-in tools for real-world use (not going to write my own linked list implementation in production)
I may not have time to do all of these for every subject, but I’ll try.
Write code on a whiteboard or paper, not a computer. Test with some sample inputs. Then test it out on a computer.
Algorithmic Complexity
Even though I know, it is always nice to keep reviewing and watching good videos on topics you are familiar with.
Gotcha: you need pointer to pointer knowledge: [2019-07-01] (for when you pass a pointer to a function that may change the address where that pointer points) This page is just to get a grasp on ptr to ptr. I don’t recommend this list traversal style. Readability and maintainability suffer due to cleverness.
Know about the most famous classes of NP-complete problems, such as traveling salesman and the knapsack problem, and be able to recognize them when an interviewer asks you them in disguise.
Very technical talk for kernel devs. Don’t worry if most is over your head.
The first half is enough.
Final Review
This section will have shorter videos that you can watch pretty quickly to review most of the important concepts. It’s nice if you want a refresher often.
Series of 2-3 minutes short subject videos (23 videos)
Think of about 20 interview questions you’ll get, along with the lines of the items below. Have 2-3 answers for each. Have a story, not just data, about something you accomplished.
These topics will likely not come up in an interview, but I added them to help you become a well-rounded software engineer, and to be aware of certain technologies and algorithms, so you’ll have a bigger toolbox.
Emacs and vi(m)
Familiarize yourself with a unix-based code editor
Know at least one type of balanced binary tree (and know how it’s implemented):
“Among balanced search trees, AVL and 2/3 trees are now passé, and red-black trees seem to be more popular. A particularly interesting self-organizing data structure is the splay tree, which uses rotations to move any accessed key to the root.” - Skiena
Of these, I chose to implement a splay tree. From what I’ve read, you won’t implement a balanced search tree in your interview. But I wanted exposure to coding one up and let’s face it, splay trees are the bee’s knees. I did read a lot of red-black tree code.
splay tree: insert, search, delete functions If you end up implementing red/black tree try just these:
search and insertion functions, skipping delete
I want to learn more about B-Tree since it’s used so widely with very large data sets.
In practice: From what I can tell, these aren’t used much in practice, but I could see where they would be: The AVL tree is another structure supporting O(log n) search, insertion, and removal. It is more rigidly balanced than red–black trees, leading to slower insertion and removal but faster retrieval. This makes it attractive for data structures that may be built once and loaded without reconstruction, such as language dictionaries (or program dictionaries, such as the opcodes of an assembler or interpreter).
In practice: Splay trees are typically used in the implementation of caches, memory allocators, routers, garbage collectors, data compression, ropes (replacement of string used for long text strings), in Windows NT (in the virtual memory, networking and file system code) etc.
In practice: Red–black trees offer worst-case guarantees for insertion time, deletion time, and search time. Not only does this make them valuable in time-sensitive applications such as real-time applications, but it makes them valuable building blocks in other data structures which provide worst-case guarantees; for example, many data structures used in computational geometry can be based on red–black trees, and the Completely Fair Scheduler used in current Linux kernels uses red–black trees. In the version 8 of Java, the Collection HashMap has been modified such that instead of using a LinkedList to store identical elements with poor hashcodes, a Red-Black tree is used.
In practice: For every 2-4 tree, there are corresponding red–black trees with data elements in the same order. The insertion and deletion operations on 2-4 trees are also equivalent to color-flipping and rotations in red–black trees. This makes 2-4 trees an important tool for understanding the logic behind red–black trees, and this is why many introductory algorithm texts introduce 2-4 trees just before red–black trees, even though 2-4 trees are not often used in practice.
fun fact: it’s a mystery, but the B could stand for Boeing, Balanced, or Bayer (co-inventor)
In Practice: B-Trees are widely used in databases. Most modern filesystems use B-trees (or Variants). In addition to its use in databases, the B-tree is also used in filesystems to allow quick random access to an arbitrary block in a particular file. The basic problem is turning the file block i address into a disk block (or perhaps to a cylinder-head-sector) address.
MIT 6.851 - Memory Hierarchy Models (video) - covers cache-oblivious B-Trees, very interesting data structures - the first 37 minutes are very technical, may be skipped (B is block size, cache line size)
k-D Trees
great for finding number of points in a rectangle or higher dimension object
I added these to reinforce some ideas already presented above, but didn’t want to include them above because it’s just too much. It’s easy to overdo it on a subject. You want to get hired in this century, right?
Best resource is The Morning Paper, a short summary every weekday of an important, influential, topical or otherwise interesting paper in the field of computer science. Some of the papers may be hard to follow. But the writer is an expert in none of them as well.4