Basic – a collection of exercises in basic data structures and algorithms
(1 votes, average: 4.00 out of 5)
Loading ...When I started to think seriously about working for Google, I knew I had to get back into shape, fast. Google were going to test me in their (in)famous interview process, which puts a lot of emphasis on basic, “hardcore” computer science – namely, data structures and algorithms.
In the course of the recent months, I have solved quite a few problems in “classic CS” (all of which have classic textbook solutions), and coded the test cases and my solutions. I would like to share this codebase with you on Github.
Basic contains various exercises, algorithms and data structures, implemented in java. Some problems that are included are:
- The Selection Problem (finding a median or the K-th largest value)
- The Knapsack Problem (NP-complete, but can still be solved for small N)
- Writing a synchronous/blocking queue
- Various Google Code Jam problems, which essentially boil down to stuff like Dijkstra, Dynamic Programming, and Binary Search
- Data structures such as Graphs, Hashmaps, Binary Heaps, and Linked Lists
- Various sorting algorithms including Bubble Sort, Heap Sort, Quick Sort (the 3-quicksort varient, which I found easier to implement correctly), and of course Merge Sort
- Binary trees and B-Trees
- A various other riddles, including some from the wonderful site ihas1337code.
Since the purpose of writing this code was more internal than external, the level of documentation and finish is not perfect. Some tests are failing, and the code has some undiscovered bugs. Still, I think that it’s a worthy reference that can be improved in the future. Naturally, many/all of the above algorithms have better, more professional implementations (some of these are in the JDK itself). However, Basic has the advantage that it does not try to be a complete, production implementation, and thus might be simpler than some of the more complex/complete implementations.
I hope you will find it useful – although I encourage you to use the test harness only at first, and write your own implementations. You learn much more from writing code than from reading it. If you have any questions, or want me to add a specific piece of documentation, feel free to ask.
