Two I've used for interview purposes:

- Given an array of 100 numbers, work out how to calculate the min, max and average.
- Given an array of 9 values representing a Tic Tac Toe game (or Noughts and Crosses, depending on where you're from) where the values are -1, 0 or 1, figure out who, if anyone, has won.

Yes, I realize these are very simple and we could all knock them off very quickly, but I'm not testing for the end product and I don't want them sitting down for two hours trying to nut out something complicated.

I want to see the process followed to arrive at a result (so I get them to white-board the entire thing, explaining as they go). It's more to see if they have problem solving ability. That's far more important than knowing the algorithms off the top of their head.

I really don't care if they can code up a bubble sort (it's a crappy sort algorithm for large data sets anyway and, if you need some sort code, you'll be using something built in to the language, pulled out of Wikipedia or found with Google, not writing your own - I'm not going to be happy paying you to re-invent the wheel).

The problem with asking someone to come up with a complicated algorithm is that they won't be doing that on the job. Most code is very simple stuff so you may as well just ask them to code up a for-loop. By all means ask them about algorithms and see what they know. For example, ask them how they would sort an array. I wouldn't hire anyone who coded up a bubble sort (or even a quick sort, for that matter). I *would* consider hiring them if they knew that different sort algorithms have different properties depending on the data set.

The best response in my view to a question like "Can you implement an array in Perl which uses a string as an index?" is not "Yes". It's either "Perl already has those, they're called associative arrays" or "No, but I know how to find code that's freely available to use on the net". Of course, if they come up with an O(n) or O(1) sort algorithm, I'll hire them on the spot :-).

As an aside, one guy answered the Tic Tac Toe question by transferring the board to the center of a 7-by-7 matrix (with the outer squares set to 0), then looping on the inner squares, checking for three of the same value in every direction to "simplify the algorithm" as he put it (not needing to worry about crossing over the boundaries of the array). Something like (and I kid you not, the amount of comments was the same as shown here):

```
int board[7][7];
for (col = 2; col < 5; col++) {
for (row = 2; row < 5; row++) {
board[row][col] = 0
}
}
board[2][2] = arr[0];
board[2][3] = arr[1];
board[2][4] = arr[2];
board[3][2] = arr[3];
board[3][3] = arr[4];
board[3][4] = arr[5];
board[4][2] = arr[6];
board[4][3] = arr[7];
board[4][4] = arr[8];
for (col = 2; col < 5; col++) {
for (row = 2; row < 5; row++) {
for (coldir = -1; coldir < 2; coldir++) {
for (rowdir = -1; rowdir < 2; rowdir++) {
if ((coldir != 0) || (rowdir != 0)) {
sum = 0;
for (i = 0; i < 3; i++) {
sum = sum + board[row+i*rowdir][col+i*coldir];
}
if (sum == -3) return -1;
if (sum == 3) return 1;
}
}
}
}
}
return 0;
```

It was an innovative approach but way too complicated compared to the 8 if-statements that most people came up with. Still I gave him a chance to explain his reasoning and, in his "Thanks but no thanks" letter, I let him know why he didn't get the job (this code was just one of the reasons) so hopefully, he's improved himself and is now gainfully employed.

And, before anyone asks, the 8 if statements are:

```
if ((arr[0] != 0) && (arr[0] == arr[1]) && (arr[0] == arr[2])) return arr[0];
if ((arr[3] != 0) && (arr[3] == arr[4]) && (arr[3] == arr[5])) return arr[3];
if ((arr[6] != 0) && (arr[6] == arr[7]) && (arr[6] == arr[8])) return arr[6];
if ((arr[0] != 0) && (arr[0] == arr[3]) && (arr[0] == arr[6])) return arr[0];
if ((arr[1] != 0) && (arr[1] == arr[4]) && (arr[1] == arr[7])) return arr[1];
if ((arr[2] != 0) && (arr[2] == arr[5]) && (arr[2] == arr[8])) return arr[2];
if ((arr[0] != 0) && (arr[0] == arr[4]) && (arr[0] == arr[8])) return arr[0];
if ((arr[6] != 0) && (arr[6] == arr[4]) && (arr[6] == arr[2])) return arr[6];
return 0;
```

But you knew that already, I'm sure.

To generalize it, we can also use this pseudo-code:

```
const SIZE=3
// cells_array is a sized SIZE*SIZE array
function cell(x,y)
return(cells_array(x+y*SIZE))
function get_winner(z)
result=0
if abs(z)=SIZE then result=sign(z)
return(result)
for i = 0 to SIZE-1
sumrow=0; sumcol=0; sumd1=0; sumd2=0
for j = 0 to SIZE-1
sumrow=sumrow+cell(i,j)
sumcol=sumcol+cell(j,i)
if (i==0) then // We only need diagonals calculated once!
sumd1=sumd1+cell(j+j)
sumd2=sumd2+cell(j+SIZE-j-1)
winner=0
if (winner==0) then winner=get_winner(sumrow)
if (winner==0) then winner=get_winner(sumcol)
if (winner==0) && (i==0) then winner=get_winner(sumd1)
if (winner==0) && (i==0) then winner=get_winner(sumd2)
```