How to print a spiral of numbers 1 through N

Printing the numbers 1 through N in a spiral is asked on interviews sometimes and is a interesting puzzle to solve. The reverse process is also simple but I will not write it here.

The code here is quite simple, but it does not print the numbers thorough N in a spiral, instead it prints a matrix with size N in which numbers are arranged into a spiral. Assuming N is given (16 for example), identifying the matrix size is simply of matter of finding sqrt(n). The idea is to print the outer layer and move inward progressively until reaching the most inner layer.

   1:  #define N 4

   2:  int mat[N][N];

   3:   

   4:  void fillSpiral() {

   5:      int start = 0;

   6:      int end = N;

   7:      int k = 0;

   8:      while (end - start >= 1) {

   9:          for (int i = start; i < end; i++) {

  10:              mat[start][i] = k;

  11:              ++k;

  12:          }

  13:          for (int i = start + 1; i < end; i++) {

  14:              mat[i][end - 1] = k;

  15:              ++k;

  16:          }

  17:          for (int i = end - 2; i >= start; i--) {

  18:              mat[end - 1][i] = k;

  19:              ++k;

  20:          }

  21:          for (int i = end - 2; i >= start + 1; i--) {

  22:              mat[i][start] = k;

  23:              ++k;

  24:          }

  25:          ++start;

  26:          --end;

  27:      }

  28:  }

  29:   

  30:   

  31:  int main() {

  32:      memset(mat, 0, sizeof(mat));

  33:      fillSpiral();

  34:      for (int i = 0; i < N; i++) {

  35:          for (int j = 0; j < N; j++) {

  36:              cout << mat[i][j] << "\t";

  37:          }

  38:          cout << endl;

  39:      }

  40:      cout << endl << endl;

  41:      return 0;

  42:  }

And the result is something like this (notice the spiral):

0       1       2       3

11      12      13      4

10      15      14      5

9       8       7       6

How to hack daily puzzles on www.gameknot.com

What better way of wasting two hours of your life then hacking a website? :) Actually what I'm going to show here is just a simple example of javascript function overriding, it doesn't even deserve the name "hack". The site is not very secured, but the basic stuff (moves, canceling games etc.) is checked server side, so there's not much anybody could do.

You need Firefox with the extension "Firebug" installed. Now, assuming you like chess and you have an account at http://www.gamespot.com, notice that if you open a daily puzzle, then open the right-click menu and click "View source", the whole solution is encrypted. However the javascript files, which handle moving and verifying your moves, are not encrypted in any way. Pay attention to this line:
<script type="text/javascript" src="/js/chess-puzzle.js?122109"></script>
You can use the javascript formatter to make the file chess-puzzle.js a little more readable.
There are some interesting functions you can pay attention to. For example:

   1:  function show_move_hint() //this displays a hint if not in "contest mode"

   2:  function display_move_hint(countdown) //this one ensures the hint is displayed only once

   3:  function report_wrong_move() //this one tells the server you made a wrong move

   4:  function callback_record_move_solve() //this one records the puzzle as "unsolved" if you made more than 2 mistakes

What would happen if I would chose to override one of them? :) Or all, for that matter. Well, I could not try it myself since I would probably get my account deleted, but you could: just open Firebug, as in the screen-shot below, and edit the last <script> tag in the "head" section, to fit the following:

   1:  <script type="text/javascript"><!--

   2:  if (top.location!=location) { top.location.href = location.href; }

   3:   

   4:  function show_move_hint() {

   5:  //////if(contest_mode())return;

   6:  //////if(show_move_hint_count > 0)count_hints2++;

   7:  //////else count_hints1++;

   8:  //////if(!node_hints[cur_solution_node])node_hints[cur_solution_node] = 1;

   9:  //////else node_hints[cur_solution_node]++;

  10:  //////if(count_hints1 == 1 && count_hints2 == 0)report_solved(0);

  11:  //////show_move_hint_count++;

  12:     display_move_hint(5);

  13:  //////disable_hint_button();

  14:     }

  15:   

  16:  function display_move_hint(countdown) {

  17:  //////if(cur_mode != modes.SOLVE)return true;

  18:  //////if(cur_solution_node < 0 || cur_solution_node >= solution.length)return;

  19:     var sn = solution[cur_solution_node];

  20:     if(!sn.moves.length)return;

  21:     var cc = sn.moves[0].coords;

  22:     var mv = bob.chess_decode_move(cc);

  23:     var b_on = countdown % 2 ? 1 : 0;

  24:     bob.update_cell_image(mv[0], mv[1], b_on);

  25:     if(show_move_hint_count > 1)bob.update_cell_image(mv[2], mv[3], b_on);

  26:     countdown--;

  27:     if(countdown >= 0) {

  28:        display_hint_timer = window.setTimeout('display_move_hint(' + countdown + ')', 300);

  29:        }

  30:     }

  31:   

  32:  function report_wrong_move() {

  33:  //////   count_wrong_moves++;

  34:  //////   if(contest_mode(1)) {

  35:  //////      bob.b_allow_new_moves = 0;

  36:  //////      if(count_wrong_moves >= 4) {

  37:  //////         report_contest_wrong_move();

  38:  //////         alert('Sorry, you have failed to solve this puzzle.\nPlease check back tomorrow for the correct solution and\na new puzzle and another chance to win the Grand Prize!');

  39:  //////         top.location.href = location.href;

  40:  //////         return;

  41:  //////         }

  42:  //////      pop_msg('Processing, please wait...', 10000, 10000);

  43:  //////      setTimeout(function() {

  44:  //////         report_contest_wrong_move(); }

  45:  //////      , 1);

  46:  //////      return;

  47:  //////    }

  48:  //////    if(count_wrong_moves == 1 || count_wrong_moves == 6)report_solved(0);

  49:     var m = ['Wrong move', 'Not quite', 'Sorry', 'Incorrect'];

  50:     pop_msg(m[Math.floor(Math.random() * m.length)] + '. Try again!', 1000);

  51:     }

  52:   

  53:  function callback_record_move_solve() {

  54:     var sn = solution[cur_solution_node];

  55:     if(bob.b_checkmate) {

  56:        if(!report_solved(1))return;

  57:        var last_mv = split_move(bob.chess_get_last_move());

  58:        for(var i = 0; i < sn.moves.length; i++) {

  59:           var mv = sn.moves[i];

  60:           if(!same_move(mv, last_mv))continue;

  61:           cur_solution_node = mv.goto_node;

  62:           break;

  63:           }

  64:        start_solved_mode();

  65:        return;

  66:        }

  67:     if(bob.cur_to_move != puzzle_to_move) {

  68:        var last_mv = split_move(bob.chess_get_last_move());

  69:        var b_found = 0;

  70:        var best_mtc =- 1;

  71:        for(var i = 0; i < sn.moves.length; i++) {

  72:           var mv = sn.moves[i];

  73:           var mtc = solution[mv.goto_node].moves_to_checkmate;

  74:           if(best_mtc < 0)best_mtc = mtc;

  75:           if(best_mtc < mtc)break;

  76:           if(!same_move(mv, last_mv))continue;

  77:           b_found = 1;

  78:           break;

  79:           }

  80:        if(b_found) {

  81:           cur_solution_node = mv.goto_node;

  82:           sn = solution[cur_solution_node];

  83:           var best_move = decide_best_move(cur_solution_node);

  84:           mv = sn.moves[best_move];

  85:           cur_solution_node = mv.goto_node;

  86:           node_solution_moves[cur_solution_node] = 1;

  87:           make_move(mv.coords, mv.promo);

  88:           return;

  89:           }

  90:  /////////report_wrong_move();

  91:        bob.undo_last_move();

  92:  /////////if(!node_wrong_moves[cur_solution_node])node_wrong_moves[cur_solution_node] = 1;

  93:  /////////else node_wrong_moves[cur_solution_node]++;

  94:        }

  95:     bob.b_allow_new_moves = 1;

  96:     update_last_move_cell_cursor();

  97:     }

  98:  // --></script>

The lines prefixed with ////// need to be deleted. I just left them there so a comparison can be made: before and after. I wonder if the requests which go the server are as easily hacked as this.... Have fun!

How to find the missing number from an array

This is what I've been asked at an interview at Microsoft (over the phone): An array of length N (for example N = 6) is given, containing all the elements from 1 to N, except one which is duplicated. So instead of having:

   1:             1, 2, 3, 4, 5, 6

we have an array which has one number duplicated:

   1:             1, 2, 3, 4, 4, 6

(notice a duplicated "4"). One additional detail: the array is not ordered. This is an final example of such an array:

   1:             3, 4, 1, 6, 4, 2

The question is: how do you find the number which is missing?

There are multiple solutions:

1. We could order the array as the first step. This would have complexity O(n*log₂n) in the best case considering merge sort, or quick sort in the average case. Next step would be to iterate through the array once, and check which number is the same as the previous one. We have the answer.

2. Previous solution was O(n*log₂n) in time complexity and took no additional space to solve (depending on the sorting algorithm). A second solution would be to keep an extra array of boolean values, initialized with false. We can iterate through the array once, and switch the corresponding boolean value from false to true as we go. Once we find a value which is already true, we have the duplicated number. At the end, one of the values in the extra array will remain false. This is the answer. This solution is O(n) in time complexity (much better), but also has O(n) space complexity.

3. The last solution is the best but is a trick actually. Considering there are N numbers in the array, from 1 to N, it means their sum is (N*(N+1))/2. So if we do the sum in the array, it will be X, different than (N*(N+1))/2. Calculating the difference between the values gives us the answer to the questions in O(1) time complexity and O(1) space complexity.

How to find subsets of an array

The problem statement: given an array of integers, for example (2, 5, 8, 10), how do you print all the subsets of this array. By all the subsets, I mean:

   1:  empty set

   2:  10

   3:  8

   4:  8 10

   5:  5

   6:  5 10

   7:  5 8

   8:  5 8 10

   9:  2

  10:  2 10

  11:  2 8

  12:  2 8 10

  13:  2 5

  14:  2 5 10

  15:  2 5 8

  16:  2 5 8 10

Well the answer is simple recursively: for each number in the array, compute recursively all the subsets without including it. Then include it and compute again all the subsets.

   1:  void subsets_recursive(int* vec, int size, int index, vector<int>* subset) {

   2:      if (index == size) { //print if we reached the end

   3:          if (subset->size() == 0)

   4:              cout << "empty set";

   5:          for (int i = 0; i < subset->size(); i++)

   6:              cout << subset->at(i) << " ";

   7:          cout << endl;

   8:          return;

   9:      }

  10:      int n = subset->size();

  11:      //first print all the subsets without including the number

  12:      subsets_recursive(vec, size, index + 1, subset);

  13:      //clear the numbers that we added in the previous subsets

  14:      while (subset->size() != n)

  15:          subset->pop_back();

  16:      //add the number to the subset and print all subsets including it

  17:      subset->push_back(vec[index]);

  18:      subsets_recursive(vec, size, index + 1, subset);

  19:  }

Iteratively it's a different story. Complexity for this (both recursively and iteratively) is O(2ⁿ), where "n" is the size of the array. This means we have to iterate 2ⁿ times. As it turns out, there's a trick involved: take each number i from 0 to 2ⁿ and check each bit. If bit k from number i is 1, then consider array_k to be in the current subset. Too bad I didn't think of this during the interview. Here it is:

   1:  void subsets_iterative(int* vec, int size) {

   2:      int n = pow((double)2, (double)size);

   3:      vector<int> currentSubset;

   4:      for (int i = 0; i < n; i++) {

   5:          currentSubset.clear();

   6:          for (int j = 0; j < size; j++)

   7:              if (((i >> j) & 1) != 0)

   8:                  currentSubset.push_back(vec[j]);

   9:          if (currentSubset.empty())

  10:              cout << "empty set";

  11:          for (int i = 0; i < currentSubset.size(); i++)

  12:              cout << currentSubset.at(i) << " ";

  13:          cout << endl;

  14:      }

  15:  }

How to do the product trick on a array

The problem is: given an array of numbers, replace each number with the product of all numbers except itself, without using the divide operator "/".
Quite tricky. Of course the goal is to make the program as fast as possible.

First solution: O(n²) - having a temporary array, iterate through the array. At each iteration, iterate again through the array, skipping the current number and keeping the rest of the product in the temporary array. Kids stuff.

Second solution: O(n) - having two temporary arrays, iterate once through the array and keep the product of all numbers smaller (in index) than the current number. Iterate again in reverse and keep a product of all the numbers bigger (in index) than the current number. At the end, the answer is the product of these two vectors. Example:

   1:  array :  1  2  3  4

   2:  left  :  1  1  2  6 <--at each index is the product of all the previous numbers

   3:  rights: 24 12  4  1 <--at each index is the product of all the next numbers

   4:  final : 24 12  8  6 <--left[0]*right[0], left[1]*right[1]... etc.

The program is equally simple:

   1:  void product(int* vec, int size) {

   2:      int* left = new int[size]; //left products

   3:      int* right = new int[size]; //right products

   4:      int product = 1;

   5:      left[0] = 1;

   6:      right[size - 1] = 1;

   7:      for (int i = 1; i < size; i++) {

   8:          left[i] = product * vec[i - 1];//keep the product of prev numbers

   9:          product = left[i];

  10:      }

  11:      product = 1;

  12:      for (int i = size - 2; i >= 0; i--) {

  13:          right[i] = product * vec[i + 1];//keep the product of next numbers

  14:          product = right[i];

  15:      }

  16:      for (int i = 0; i < size; i++)

  17:          vec[i] = left[i] * right[i]; // compute the final results

  18:      delete[] left;

  19:      delete[] right;

  20:  }

How to use the two pointers trick in a linked list

A very simple trick which has multiple uses: finding the middle of a linked list, finding a certain node from the end (e.g. the 3rd node from the end back) or finding if a linked list has loops. I'll just post the code here, using the same structure as in the previous post. It has comments and it's really simple.

Finding the middle of a linked list:

   1:  int findMiddle(node* head) {

   2:      node* middle = head; // the middle will be here

   3:      while (head != 0 && head->next != 0) {

   4:          head = head->next->next; // advance the head by two positions forward

   5:          middle = middle->next; // advance the middle by only one position

   6:      }

   7:      return middle->data;

   8:  }

The solution is O(n) because the algorithm has to go through all the nodes once.

Finding if a linked list has loops (uses almost the same code):

   1:  bool hasLoops(node* head) {

   2:      node* slowPtr = head; //we'll move slower into the list using this pointer

   3:      while (head != 0 && head->next != 0) {

   4:          head = head->next->next; // advance the head by two positions forward

   5:          slowPtr = slowPtr->next; // advance the slowPtr by only one position

   6:          if (head == slowPtr) //these can never become equal unless one pointer loops

   7:              return true;     //back to a previous position, which means there's a loop

   8:      }

   9:      return false;

  10:  }

Again, the solution is O(n) in the worst case because the algorithm has to go through (potentially) all the nodes - it depends on where the loop is.