by Asim Jalis
In many job interviews I am asked to write code on the white
board to solve simple problems, such as:
(a) Write a function itoa that converts an integer to a string
using base 16.
(b) Write a function that tests if a binary tree is sorted.
(c) Write a function to convert an integer to a string containing
the equivalent Roman numeral.
(d) Write a function that reverses all the words in a string
without reversing the string.
I have been fumbling my way through these, writing and rewriting
until I get them right. Then I manually try some test cases
through them and fix them if they fail the tests.
Because of my test-first approach I end up moving too
incrementally. I have been thinking of a way of making this more
systematic. I also want to make the design of these functions
more like a mathematical proof, so that it is easier to verify
that the functions are correct by looking at them. So the two
goals are: (a) the technique should make it easy to analyze the
problem, (b) it should make it easy to transform the intuitive
solution to code, (b) the solution should be easy to verify.
Here are some approaches that I have come up with.
1. Divide the input into cases. Write the code in this way:
Try case 1.
Try case 2.
Try case 3.
. . .
This is almost like a pattern. Each one of these can be
translated into: result = TryCase1(args); if (result) return;
2. Another type of pseudo-code that is pretty general is:
Find when CONDITION is true.
This usually translates to something like:
Node* p; while(!CONDITION) { p = p->next; }
int i; while(!CONDITION) { i++; }
What I am looking for here is a kind of pseudo-code language that
is a little higher level than the normal programming constructs,
and that makes it easy to assert pre and post conditions, and to
break down programming problems formally.
