This is a repository of implementations for whiteboard questions that I've gotten during interviews.
So far, the goal is to account for the following interview questions:
- Shortest path on an undirected graph. - COMPLETE
- HashMap implementation. - COMPLETE
- Linked hash map (hash table that allows iteration over its keys in the order in which they were inserted). - COMPLETE
- Cartesian product of strings. - COMPLETE
- Postfix to infix arithmetic conversion. - COMPLETE
- Merge two sorted arrays of integers. - COMPLETE
- Reversal of a linked list. - COMPLETE
- Circularly linked list of parameterized type with support for null entries. - COMPLETE
In addition, I want to knock out some implementations of some basic data structure and algorithm problems, just to brush up.
- Dynamic array (ArrayList). - COMPLETE
- Doubly Linked List (LinkedList). - COMPLETE
- Stack (ArrayDeque). - COMPLETE
- Queue (ArrayDeque). - COMPLETE
- Tree. - COMPLETE
- Directed acyclic graph. - COMPLETE
- Heap. - COMPLETE
Most of the above structures will be implemented in something very much like the corresponding Java interfaces. I will be implementing against the interfaces as specified (abridged), but I will be deriving the implementations myself for practice.
The following algorithms will then be implemented, atop the above structures where necessary:
- Binary search through a list. - COMPLETE
- Dynamic programming (http://codercareer.blogspot.com/p/dynamic-interview-questions.html). - COMPLETE
- Preorder and postorder traversal of a tree. - COMPLETE
- Topological sorting of a directed, acyclic graph. - COMPLETE
- Union-find (disjoint set). - COMPLETE
- Bloom filter. - COMPLETE
- Quicksort. - COMPLETE
- Graph coloring. - COMPLETE
- LRU cache. - COMPLETE
- Chess move validator. - COMPLETE
- Maybe something involving Spring, since that has come up a couple times.
- Something involving hashing function distribution, vis a vis numeric analysis.