Mock interview problem: "Detect Connect 4 winner" - tim-hr/superprep GitHub Wiki

Setup

  • Make a Codestitch pad at codestitch.io.
    • If you don't have access privileges, ask Muhammad.
  • Paste the problem statement into the Codestitch pad.
  • Make sure they know that they can ask questions of the interviewer.
  • Make sure they know that this is "open book" -- they look stuff up on the Internet (preferably staying on the MDN site).

Problem statement

image

/*
Are you familiar with the game of Connect Four? 

It's that tabletop game with a vertical grid of 7 columns across and 6 rows down. You drop colored chips into each column to stack them. If you are able to get 4 chips of your color to form a sequence in any direction (horizontal, vertical, or diagonal) then you win the game.

Assume that you have already written most of a Connect 4 implementation. You now need to write a function that accepts an sequence of grid cells and determines who has a winning "run" of cells.

This specification is intentionally incomplete. It's up to you to (quickly) determine and decide a number of key features of how this function will work, in collaboration with your interviewer.
*/

Interviewer notes

Decisions that the interviewee must make

  1. The name of the function
  2. Data type for the sequence
  3. Values to represent the 3 possible states of each cell
  4. Return value type(s)

Don't let them take more than 2 minutes to make these decisions (they aren't very hard to make).

If they do go over 2 minutes, just start feeding them suggestions.

The name of the function

A good name for the function in question would be: detectWin or detectWinner, findWinningRun or similar. Make sure that they pick a function name that follows the coding style guidelines.

Note: if you are an HIR or volunteer new to Prep and have not gone through the Learn articles, please read all those articles, and pay particular attention to the Coding Style Guide for prep students.

Data type for the sequence

The sequence can either be a string or an array, it doesn't really matter. The latter is cleaner and more reasonable, really, but you don't have to push too hard about it. The problem can be solved well either way.

Note that this problem statement contains an intentional mild false lead. An un-careful reading might lead the interviewee to try to represent the entire grid, even though the specification only requires dealing with a sequence.

If they do that, have them re-read the problem carefully and warn them about making assumptions.

Representing cell states

Numbers are fine to represent moves by each player: 0 and 1.

Letters are also fine: 'o' and 'x'.

However, it's likely that the interviewee will forget the "empty" state for cells. If necessary, prompt them, and warn them to be thorough and avoid making assumptions.

For the empty state: a blank, a null, -1, or similar would all be fine.

Return value

The return value should be one of the 3 cell states.

Some interviewees will want to return true or false to represent whether or not someone won. In that case you can ask them how they will know who won.

If they reply that the surrounding program will keep track of that state because the program always knows who made the last move, and the win detection occurs right after a valid move has been made, then you can let that go and allow a boolean return value. That would be an impressively thoughtful answer.

However most of the time people will simply not have thought through the problem sufficiently, in which case you can warn them about making assumptions and reading the problem statement carefully.

Sample answer

As usual, there are a number of ways to approach this problem.

Below I have provided one sample answer based on reduce.

My decisions about problem setup (these are not canonical, they just happen to be what I picked):

  1. Function name: findWinningRun
  2. Data type for the sequence: array
  3. Cell values: X, O, and null
  4. Return value: X, O, or false if no winner.

Reference pseudocode

function findRunOfMoves(sequence) {
  return sequence.reduce(function(currentRun, currentMove) {
  // reduce the sequence to a "run" with these rules:
  // 1) if this value is different from the run, restart the run
  // 2) blanks always restart a run 
  // 3) otherwise add the value to the run
  }, []);
}

function findWinningRun(sequence) {
  var run = findRunOfMoves(sequence);
  // if run is 4 cells long then return tail, else return false
}

Reference implementation

var WIN_LENGTH = 4;

function peek(arr) {
  return arr.slice(-1)[0];
}

function findRunOfMoves(sequence) {
  return sequence(function(currentRun, currentMove) {
    if (currentRun.length !== WIN_LENGTH) {
      if (peek(currentRun) !== currentMove) {
        currentRun = [];
      }

      if (currentMove === null) {
        currentRun = [];
      } else {
        currentRun.push(currentMove);
      }

    }
    return currentRun;
  }, []);
}

function findWinningRun(sequence) {
  var run = findRunOfMoves(sequence);
  return run.length === 4 && peek(run);
}

Reference tests

var output = findRunOfMoves(['X', 'X', 'X', null, 'X', null, 'O', null]);
assertObjectsEqual(output, [], 'blank cell in middle interrupts run');

var output = findRunOfMoves([null, 'X', 'X', 'X', 'X', null, 'O', null]);
assertObjectsEqual(output, ['X', 'X', 'X', 'X'], 'blank cell on either side does not interrupt run');

var output = findRunOfMoves([null, 'X', 'X', 'X', 'O', 'O', 'O', 'O']);
assertObjectsEqual(output, ['O', 'O', 'O', 'O'], 'return correct run despite preceding run of opponent moves');

var output = findRunOfMoves([null, null, null, 'O', 'O', 'O', 'O']);
assertObjectsEqual(output, ['O', 'O', 'O', 'O'], 'does not return a partial run of blanks');

var output = findRunOfMoves([null, null, null, null, 'O', 'O', 'O']);
assertObjectsEqual(output, ['O', 'O', 'O'], 'does not return a full (4-move) run of blanks');

var output = findWinningRun([null, null, null, null, 'O', 'O', 'O'], 'does not detect a winner from a partial run');
assertObjectsEqual(output, false);

var output = findWinningRun(['X', 'X', 'X', 'O', 'O', 'O', 'O'], 'detects the winner despite a partial run from the opponent');
assertObjectsEqual(output, 'O');

var output = findWinningRun(['X', 'X', 'X', 'O', 'X', 'O', 'O'], 'detects the winner despite a partial run from the opponent');
assertObjectsEqual(output, false);


function assertObjectsEqual(actual, expected, testName) {
  actual = JSON.stringify(actual);
  expected = JSON.stringify(expected);
  if (actual !== expected) {
    console.log('FAILED ' + testName + ': expected ' + expected + ', but got ' + actual);
  } else {
      console.log('passed');
  }
}