Additional Learning
Additional Learning
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.Machine Learning
Courses:
Great starter course: Machine Learning - videos only - see videos 12-18 for a review of linear algebra(Who doesen't Know Andrew NG : P , Still Addding it)
Emacs and vi(m)
Familiarize yourself with a unix-based code editor
emacs:
Information theory (videos)
More about Markov processes:
See more in MIT 6.050J Information and Entropy series below
Parity & Hamming Code (videos)
Hamming Code:
Entropy
Also see videos below
Make sure to watch information theory videos first
Cryptography
Also see videos below
Make sure to watch information theory videos first
Compression
Make sure to watch information theory videos first
Parallel Programming
Bloom Filter
Given a Bloom filter with m bits and k hashing functions, both insertion and membership testing are O(k)
Locality-Sensitive Hashing
Used to determine the similarity of documents
The opposite of MD5 or SHA which are used to determine if 2 documents/strings are exactly the same
van Emde Boas Trees
Augmented Data Structures
Balanced search trees
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
AVL trees
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)
Splay trees
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
MIT Lecture: Splay Trees:
Gets very mathy, but watch the last 10 minutes for sure.
Red/black trees
These are a translation of a 2-3 tree (see below).
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
2-3 search trees
In practice: 2-3 trees have faster inserts at the expense of slower searches (since height is more compared to AVL trees).
You would use 2-3 tree very rarely because its implementation involves different types of nodes. Instead, people use Red Black trees.
2-3-4 Trees (aka 2-4 trees)
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.
N-ary (K-ary, M-ary) trees
note: the N or K is the branching factor (max branches)
binary trees are a 2-ary tree, with branching factor = 2
2-3 trees are 3-ary
B-Trees
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
A good fit for k-nearest neighbors
Skip lists
"These are somewhat of a cult data structure" - Skiena
Disjoint Sets & Union Find
Treap
Combination of a binary search tree and a heap
For Add-ons and Recommendations feel free to reach me at : vivekanandayadla@gmail.com My Other Social Media Accounts: Facebook LinkedIn Instagram Twitter WhatsApp
Last updated
Was this helpful?