Day 7, Sunday off

Finally has one day off. Extremely exhausted.

Advertisements
Standard

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.

Standard

Day 5, data structure 2 continued

We learned more about different types of data structures and continued to work on the second sprint of data structures. We learned about:

LinkedList

– LinkedList (single or double linked). The single linked LinkedList is great for modeling the prototype chains.  Constant in insertion time. Linear in look time.

Array

– Constant in lookup time. Linear in insertion time if insertion is not in the end of the array.

Tree

– Similar to LinkedList except each node can have multiple children. It is good for modelling hierarchy; and it is good for finding an element if the tree is sorted.

HashTable

– A collection of key-value pairs that satisfies the following constrains:

1. constant in lookup time.

2. constant in insertion time.

3. each key has to be unique.

Jake and I spent a lot of time time on HashTable and I think if I were an interviewer, I would ask my interviewee to implement a HashTable for me too.

The hash function is deterministic, stateless, and a upper limit. I can image those hash functions must come from the best mathematicians.

Rehash is also necessary when the current hash table becomes either too crowded or too sparse.

We end up implementing a HashTable with nested arrays. The approach is cool, just working with nesting arrays really requires a clear mind all the time.

Graph

-Marcus emphasized that optimization should focus on the # of steps, not how much time each step spend. That is a great point. We also learned about the notation of O(1), O(n), O(logn), O(n^2) and O(x^n, where x is a constant).

Oh, code review. We did our first code review with another pair. It was ok but I pointed out they shouldn’t use the javascript Object when implementing the HashTable and they disagreed. Now I can see how code review can hurt people’s feelings. Everyone is emotionally attached to his code.

Standard

Day 4, data structures 2

There are two sprints for data structures, with two days per sprint. My pair and I finished the first data structure sprint yesterday and started to work on the second data structure sprint today. We implemented LinkedList, Tree and Set today.

One thing that really slowed us down was debugging the contains function for Tree. Because the contains function needs to search recursively, the function was written as a recursive search. However, when we passed the result around as a parameter of the function, we override results from our previous round. This creates enormous confusion and it takes us a good two hours to find the bug. I swear that from now on, when possible, I will try to avoid pass results in recursive function. Using a global variable is less clean, but much easier to read and debug.

Something important for today:

– Testing. During testing, only test the interface, and nothing else.

– Coding convention about capitalized function names. A capitalized function is supposed to be run with the new key word. For example, we should run: new Tree() or makeTree().

– Constructors in JS is only referred to the psedoclassical style(?) maker function.

Git

Yes. There are so much to learn about Git such that we could have a lecture for it everyday. Marcus did a fantastic job today on Git and my understanding is getting much better.

First, I realized that pull request is a GitHub feature, not a Git feature.

Second, I realized that SHA is the unique ID associated with each state, and all the other stuff (branch names, tag names, HEAD) are variable names referring to SHA. As long as I accept the fact that Git will point those variable names to different SHA automatically in the background, life is not that complicated.

Third, HEAD is almost the same as the “you are here” star in the maps.

Fourth, I am guessing that the difference between fast-forward merge and none-fast-forward merge is whether a new SHA has been created or not, but I am not 100% sure.

Standard

Day 3 – data structures

Day 3 is the first day of 4 days of data structure.

First, we talked about high level concepts.

To break down a big problem into smaller problems and come up solutions, it is nature to do: modular -> isolate each module -> make sure each module are loosely coupled -> make sure each module has an interface -> make sure each module has some privacy

We also talked about abstraction. A good example is: a remote control abstracts the RC car. Abstraction is introduced for many reasons, including:

– to interprate js code to byte code

– to introduce modularity

– to digest complex ideas (so you can ignore most part of the idea and just focus on one tiny piece)

Second, we reflected on the previous sprint – re-implementation of the pre course work. The criterion we use are: clear / actionable / compassionate / honest. Key questions to address are: who drove / were you engaged / how could each of you improve? Because my pair in this previous sprint has three people instead of two people, we sit together and give each other feedback. My negative feedback is that I didn’t mention that we should continue to work on the extra credit.

Third, we talked about class. Interestingly, class in js is defined as “a function that produces many objects”. There are four ways to create a class. (I miss you, Python!) They are: functional, functional with shared methods, prototypal, pseudoclassical. The current sprint requires us to implement Stack and Queue in four different ways. Jake and I move fairly fast and we even had time to compare the performance of those four types of implementation. It is not surprising that pseudoclassical was about one order of magnitude faster than the functional and functional shared.

A couple of notes on those four ways of doing it:

– When use new Class1(), two magic lines code are inserted in the body of the function where Class1 is defined.


//the first magic line appears at the very top

this = Object.create(Class1.prototype);

...

...

//the second magic line appears at the very bottom

return this;

The effect of those two lines are such that we don’t need to redefine a new object and try to return it manually.

– No function can be both shared and have access to private variable inside class definition. Does this mean that the classical way of doing OOP (such as Java) is better in this regard???

– We also had tons of confusions about prototype during class. The only thing that seems to solve the problem is prototype basically means delegation of failed lookups.

Standard

Day 2

I brought FlashCards to take notes so I have a little bit more to report on the blog.

this

– the magic keyword ‘this’.

– In one sentence, ‘this’ always refers to “at run time”, the left side of the dot, of the function where ‘this’ was invoked.

– Exceptions are when there is nothing to the left of the dot, ‘this’ refers to ‘window’

Other tips:

– the prototype chains. Pass by reference. Object.protoype is the top level and there is nothing above that.

–  _.uniq() might be a common question in interviews

– Object.prototype.toString.call() will return [object Object], [object Array], [object Arguments] depending on what parameters are being passed in

– http://jsparse.meteor.com/ is a really visualization cool tool to show how your js code is being parsed

– array.reverse()

– typeof n === ‘undefined’

– In underscore, most of the time, the iterator takes three parameters, i.e. _.iterator(value, key, collection). Notable exceptions are _.reduce(function(memo, value, key, collection){})

– git commit every 5 to 10 lines

– Array.isArray() is not always working depending on the environment

– _.delay() doesn’t have the ability to pass a context as a parameter

– apply() vs call()

Standard