Design session with Eewei Chen

Friday, October 16, 2009

Codility spent half a day with user experience guru Eewei Chen of ThoughtWorks. Eewei is a great designer and a great person to work with. We left with superclearly redesigned website and few brilliantly simple ideas, that we are putting on the website ASAP.
Big thanks to Ewei and ThoughtWorks, who provided free consulting to Seedcamp winners.

The Power of Good Design

Sunday, October 11, 2009

One of my favorite interview question is reverse a single-link list (using only constant amount of memory and making only one pass through the list).

Most of candidates give up after some struggle, but those who make it, usually solve the problem by traversing the list and reversing pointers one by one. This is tricky, because you have to maintain three pointers pointing at consecutive nodes (say prev, current, next): you make the pointer in the node pointed to by current point to prev (instead of next), and you have to maintain next, so that after altering the current node, you still have some reference to the tail behind it. (If this description makes you feel dizzy, you are not alone.) At first sight it is not obvious what to do when the list has less than 3 nodes, so people end up writing lots of code to handle special cases (empty list, one-element list), which complicates the code even further and creates lots of dark corners, a favorite habitat of bugs.

This problem has, however, another solution. I love it, because it exemplifies the power of good design even in such a tiny code snippet. I learnt it from an interviewee. He looked at the problem and said: single link list is effectively a stack. You can easily pop, push and test for emptiness. So let's just create another stack, and transfer the elements one by one. Once we are done, the order of elements on the new stack will be reverted. This solution yields the same number of operations as the prev/current/next method, but is so much simpler to understand. It decomposes the original problem into four smaller, independent ones, each of which is trivial to solve and debug:

• how to transfer elements from one stack to another (one easy loop),
• how to implement empty stack with single-link list (trivial),
• how to push element onto a stack in this single-link list implementation (trivial),
• how to pop element from a stack in this single-link list implementation (trivial).

All of sudden all the worries about boundary conditions disappear. The algorithm for transferring elements is easy, and all the pointer manipulation is hidden behind the abstraction layer of pop/push/isempty, so one no longer has to think about the boundary conditions in terms of pointers. Even if one does not implement pop/push/isempty as separate functions (and in fact here it does not make sense to do so), one can clearly see which groups of instructions constitute push, and which constitute pop. This gives much more confidence in the algorithm, than analyzing the correctness of pointer manipulation.