Day 6, Hash Table and Binary Search Tree

Today is the last day of the second sprint on data structure, and I am getting into a new domain of knowledge.

In the last three days, we covered fundamental data structures such as Stack, Queue, LinkedList and Set. They are very simple, with real world analogy and easy to understand. In contrast, HashedTable and Binary Search Tree are slightly further away from the physical world. Jake and I finished almost all the extra credit on HashedTable, and some extra credit on Binary Search Tree. I should find sometime to finish all of them because they are helpful in job interviews.

The big learning today is the algorithm for algorithm. In short, you need a plan before writing the program. In more elaborated terms, you need:

– Establish the rules of the problem. In other words, clarify around the problem and make sure you are not solving the wrong problem. Marcus gave an example on how to arrange queens on a chess board. The problem could mean any of the following thing:

1. An arrangement of eight queens

2. A single solution for any n queen

3. The total number of queens you can possibly put on a board

– Explore the problem space. It includes limited testing (still inside the problem domain) and edge cases (borderline and maybe outside the domain). A good example is when testing sum(a, b): limited testing would be a=0, b =10; edge cases would be a = infinity, b = infinity or a = “hello”, b = “bar”.

–  Test Driven Development. You start by writing a tiny test that is doomed to fail and try to fix the test. The only problem I had is the “tiny” test piece. I prefer a reasonable size of test that is going to fail and then try to fix that test.

– Make a plan that solves the problem. For example, if you are going to pair socks from a pile with 10M socks, are you going to try sorting all socks by color first, or are you going to do context based hashing(?) ?

– Write pseudo code. Jake and I tried some pseudo code today and it works pretty well for us.

– Step through your pseudo code.

Oh, social night. We went to the trampoline park today for a social event. It was fun and someone were definitely more adventurous than others. I begun to wonder whether adventurous is a good thing or bad thing for being a developer.

Advertisements
Standard