JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
Question | Reply
I was asked these questions during a recent interview.

Q1: Given a 2 dimensional array of characters and a dictionary, extract all the meaningful words from the array. The words can be positioned horizontally, vertically or diagonally within the array. I was asked to come up with an efficient algorithm..

Q2: In a single nested for loop, determine if a filled in sudoku is a valid solution.

Ny ideas on how to go abt?
Re: Question (response to post by Nukem) | Reply
I'm not sure I want to spend brain power on that at the moment, but how can you have a "single nested for loop"?
Re: Question (response to post by Nukem) | Reply
For the second one, I would just have an outer for loop that increments from 0 to 3.

If the for loop value is 0, check all rows to see that each row uses the numbers 1-9 once.

If the for loop value is 1, check all columns to ensure that each column uses 1-9 once.

If the for loop value is 2, check each of the 9 3x3 subgrids to make sure that they use 1-9 only once.

IIRC, these are all the checks of a valid suduko placement.
Re: Question (response to post by EmperorofUnivrs) | Reply
But then, can't you just not use a loop at all? How is it helping here? Instead of
if (x == 0) {
  check case A
} else if (x == 1) {
  check case B
}  else {
  check case C
}

the code
check case A
check case B
check case C

seems a lot shorter.
Re: Question (response to post by Minilek) | Reply
My guess is they really are looking for something like
for (int i=0; i<3; i++)
  for (int j=0; j<3; j++) {
     int hor = 0;
     int vert = 0;
     int square = 0;
     for (int x=0; x<3; x++)
       for (int y=0; y<3; y++) {
         hor |= 1<< grid[3*i + j][3*x + y];
         vert |= 1<< grid[3*x+y][3*i+j];
         square |= 1<<grid[3*i+x][3*j+y];
       }
     }
     if (hor != 0x3FE || vert != 0x3FE || square != 0x3FE) 
       return false;
  }
}
return true;   


If they really wanted a single unnested loop, it's possible using
int hor = 0;
int vert = 0;
int square = 0;
for (int c = 0; c < 81; c++) {
  int x = c/27;
  int y = (c/9)%3;
  int i = (c/3)%3;
  int j = c%3;
  if (x+y==0) hor = vert = square = 0;
  hor |= 1<< grid[3*i + j][3*x + y];
  vert |= 1<< grid[3*x+y][3*i+j];
  square |= 1<<grid[3*i+x][3*j+y];
  if (x+y==4 && (hor != 0x3FE || vert != 0x3FE || square != 0x3FE)) 
       return false;
}
return true;


Edit: removed extra opening [ on the hor lines.
Re: Question (response to post by Minilek) | Reply
He said nested for loops... But I agree with you.

I don't like it when odd constraints are placed on my programming. I'd much rather have the interviewer say "do such and such with this time complexity"
Re: Question (response to post by Nukem) | Reply
On the first, what do you mean by "efficient algorithm"? The most trivial algorithm I can think is not that inneficient
Re: Question (response to post by Malkava) | Reply
The first I thought of was Aho-Corasick on each row/column/diagonal.
RSS