We have interviewees write sample code, but now we want them to modify some simple working code. I came up with the following proposal, which is a syntax-directed interpreter implemented with a table-driven finite state machine. The interpreter simply accepts whitespace-delimited text and outputs "Hello" when it sees the case-insensitive command "HELLO". Any other input is an error.
This is a highly-simplified version of some C code converted to C# for the interview:
enum Lexeme
{
Error,
EOF,
Whitespace,
H, E, L, O
}
static Lexeme LexemeOfIntChar(int cIn)
{
if (cIn < 0)
return Lexeme.EOF;
switch (Convert.ToChar(cIn))
{
case 'H':
case 'h':
return Lexeme.H;
case 'E':
case 'e':
return Lexeme.E;
case 'L':
case 'l':
return Lexeme.L;
case 'O':
case 'o':
return Lexeme.O;
case ' ':
case '\t':
case '\r':
case '\n':
return Lexeme.Whitespace;
default:
return Lexeme.Error;
}
}
static void Main(string[] args)
{
// Transition table.
// Each row is a state, each column is the new state given the column lexeme.
// State -1 is error. No need to define an Error row since we never transition from it.
// State 7 is end. We never transition from this either.
int[,] transition = {
// Err,EOF, Ws, H, E, L, O // Lexeme
{ -1, 7, 0, 1, -1, -1, -1 }, // 0 = Start
{ -1, -1, -1, -1, 2, -1, -1 }, // 1 = first H
{ -1, -1, -1, -1, -1, 3, -1 }, // 2 = first E
{ -1, -1, -1, -1, -1, 4, -1 }, // 3 = first L
{ -1, -1, -1, -1, -1, -1, 5 }, // 4 = second L
{ -1, 6, 6, -1, -1, -1, -1 }, // 5 = first O
{ -1, 7, 0, 1, -1, -1, -1 }, // 6 = 'HELLO'
};
int currentState = 0; // 0 = Start
while ((currentState >= 0) && (currentState != 7))
{
Lexeme t = LexemeOfIntChar(Console.Read());
currentState = transition[currentState, (int)t];
switch (currentState)
{
case -1: Console.WriteLine("Invalid character!"); break;
case 6: Console.WriteLine("Hello"); break; // 6 = saw 'HELLO' with terminal symbol
}
}
}
The proposed exercise is to extend this interpreter to accept a "HELP" command that will print out:
"usage 'HelloScript <scriptfile'
This can be done in about a half-dozen changes.
A co-worker I asked this about was able to complete it in under 15 minutes, but wanted to argue about terminology, implementation, et al.
The intent is for it to be a simple exercise only to see if interviewees can understand and maintain existing code. How understandable and maintainable is it?