Neil Fraser's Vietnam Problem

Google's Neil Fraser took a trip in Vietnam, where he was surprised to find computer science had been incorporated into public school curricula, despite severe resource constraints. In Vietnam, pils start learning computer science from second grade. They started real programming in their 4th grade. Where Neil made a comparison to students in the US struggling on HTML img tags, by 'students in the US', Neil was referring to 11th grade 'gifted and talented' students enrolled in magnet program in science and mathematics.

Intuitively, Neil was curious on what would a 11th grade Vietnamese student do for programming. He walked into a random school's programming class. This is the problem he found. Students have 45 minutes to design and work out a solution with PASCAL. Nearly all students in that classroom completed on time.

Google's recruitment team rated this question top one third. Neil estimated at least half of those students would pass Google interview.

This is a sad day. The Seagull estimate that in any college level computer science class at any university (with few exceptions such as MIT, CMU and Stanford) around the world, at most 10-20% 3rd year computer science students will be able to finish the task in 45 minutes. If his observance is accurate, then Neil's careless walk may have proved all the education in CS has been all wrong. In other words, as in the learning process of any other natural spoken language, it should be started in a child's early age.

Although an adult can learn a foreign language, it usually takes way longer time, and most likely will never reach the point he will be able to use it naturally. If it is not a natural process, it is hard. And that is what we have seen most computer science students doing in college, and in their programmer career: floundering and withering.

The question is actually a well known problem among programming enthusiasms. It is a variation of an ACM programming contest archive, maintained by the University of Valladolid in Spain, aka UVA 705 Slash Maze. There are some more involved solutions available from Google, but here is a most elegant solution with the Vietnamese problem's data file.

/* 
 * Vietnamese Problem - Neil Fraser - 11th Grade - Rosemont
 */
#include <iostream>
#include <fstream>

const int row(17);
const int col(25);
bool goal(true);
int count(0);

using namespace std;

void cal(char** mat, int i, int j) {
  if (mat[i][j] != '1') {
    mat[i][j] = '1';
    if ((i==0)||(i==row-1)||(j==0)||(j==col-1)) goal = false;
    if (goal) count++;
    if ( (i!=0)&&(j!=col-1) && (mat[i-1][j+1]!='1') ) cal(mat, i-2, j+2);
    if ( (i!=0)&&(j!=0) && (mat[i-1][j-1]!='1') ) cal(mat, i-2, j-2);
    if ( (i!=row-1)&&(j!=0) && (mat[i+1][j-1]!='1') ) cal(mat, i+2, j-2);
    if ((i!=row-1)&&(j!=col-1) && (mat[i+1][j+1]!='1')) cal(mat, i+2, j+2);
  }
}

int main() {

  int maxarea = 0;
  char **mat = new char* [row];
  for (int i=0; i<row; i++) mat[i] = new char[col];

  ifstream fin("data1.txt");
  for (int i=0; i<row; i++)
    for (int j=0; j> mat[i][j];
  fin.close();

  for (int i=0; i<row; i++)
    for (int j=0; j<col; j++)
      if ( (i%2==0) && (j%2==0) && !( (i%4==0) && (j%4==0) ) ) {
        cal(mat, i, j);
        if (count > maxarea) maxarea = count;
        count = 0, goal = true;
      }

  for (int i=0; i<row; i++) delete[] mat[i];
  delete [] mat;
  cout << "the largest enclosed area is: " << maxarea/2 << endl;
}

data.txt:

1000000010001000100000001
0100000100010100010000010
0010001000100010001000100
0001010001000001000101000
1000100010001000100010000
0100000100010001010001000
0010001000100010001000100
0001010001000100000100010
0000100010001000000010001
0001000101000100000101000
0010001000100010001000100
0100010000010001010000010
1000100010001000100010001
0100000101000001000100010
0010001000100010001000100
0001010000010100010001000
0000100000001000100010000