3
\$\begingroup\$

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?

\$\endgroup\$
  • 3
    \$\begingroup\$ Not sure what this will tell you about the candidate. If you asked me to maintain it I would delete it and replace it with a Lex and Yacc file. \$\endgroup\$ – Martin York Sep 28 '11 at 19:52
4
\$\begingroup\$

If I were a candidate, I'd judge what I think the quality of your code looks like based on this simple, and I'd have some concerns:

  1. Your transition table depends on the values of the Lexeme enum not changing (say by inserting additional values). If this is the case I'd like there to be a comment on enum saying order is significant or having the values explicitly given orders. Otherwise I'd expect the actual numbers to not matter.
  2. Your code contains a transition table. That's hard to read and hard to modify. Why would you do that?
  3. You've two extra sets of parens here:

    while ((currentState >= 0) && (currentState != 7))
    
  4. Your states and done via magic numbers and not an enum.
  5. The check for -1 feels like it's in the wrong place. It is handling an error condition. But the other element of the switch isn't an error condition.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.