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 generate random numbers in [1...7] from random numbers in [1...5]

Well known as a Google/Microsoft interview question, the following problem is actually really complicated to solve correctly, although it looks easy:

Given a function which produces a random integer in the range 1 to 5, write another function which uses it and produces a random integer in the range 1 to 7.

I'm going to modify this a little and make it generic:
Given a function which produces a random integer in the range 1 to 5(M), write another function which uses it and produces a random integer in the range 0 to 7(N).

Of course it's easy to do it without generating a uniform distribution so I'm not going to spend time on that.
What needs to be done is generate a uniform distribution. But consider this example:
If we add random(5) + random(5), assuming random(5) generates numbers from 0 to 4, we have:

   1:  0+0

   2:  0+1, 1+0

   3:  0+2, 2+0, 1+1

   4:  0+3, 3+0, 1+2, 2+1

   5:  0+4, 4+0, 1+3, 3+1, 2+2

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

   7:  2+3, 3+2, 3+3

   8:  3+4, 4+3

   9:  4+4

This obviously is not a uniform distribution because we have more chances of generating the number 4 than the number 8. So whatever algorithm is needed, it cannot simply use operations involving random(5). Or, actually it can, with some complicated math behind. Read about Box–Muller transformations and Rejection sampling.

What I think is a simpler algorithm is the following: since every number can be represented in X bits, generate X numbers from 1 to 5, and depending on the generated number, set bit X to 1 or 0. Number from 0 to 7 can be represented with 3 bits. Let me know what you think.

   1:  int genRandom1to5() {

   2:      return (rand() % 5) + 1;

   3:  }

   4:   

   5:  int genRandom1to7() {

   6:      int rand17 = 0;

   7:      for (int i = 0; i < 3; i++) {

   8:          int rand15 = 3;

   9:          while (rand15 == 3) {

  10:              rand15 = genRandom1to5();

  11:          }

  12:          if (rand15 < 3)

  13:              rand17 |= (1 << i);

  14:      }

  15:      return rand17;

  16:  }

Momentary break

M64FT7ZUTGK4

Been very busy the last few weeks. I will resume posting soon.

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 do integer partitioning

The problem statement: given a number N, for example 5, print all the partitions of this number, meaning: the sum of all possible number that add up to N. In this example:

   1:          1+1+1+1+1

   2:          1+1+1+2

   3:          1+1+2+1

   4:          1+1+3

   5:          1+2+1+1

   6:          1+2+2

   7:          1+3+1

   8:          1+4

   9:          2+1+1+1

  10:          2+1+2

  11:          2+2+1

  12:          2+3

  13:          3+1+1

  14:          3+2

  15:          4+1

  16:          5

The answer is obviously recursive, and the complexity is, of course O(2^{n - 1}), exponential.

   1:  void doPartitions(int n, vector<int>* partition) {

   2:      if (n <= 0) { //the number cannot be partitioned further, so print

   3:          for (int i = 0; i < partition->size() - 1; i++)

   4:              cout << partition->at(i) << "+";

   5:          cout << partition->at(partition->size() - 1) << endl;

   6:          return;

   7:      }

   8:      int size = partition->size();

   9:      for (int i = 1; i <= n; i++) {

  10:          //add the current no to the partitions

  11:          //and generate partitions from the leftover number

  12:          partition->push_back(i);

  13:          doPartitions(n - i, partition);

  14:          while (partition->size() > size)

  15:              partition->pop_back(); //reset the partitions each iteration

  16:      }

  17:  }

What's left here is to find a way to print only the distinct solutions, but this is a simple exercise.

How to find all possible words from a phone number

The problem statement: Most phone numbers these days are like 1-800-COOLSTUFF, which means you have to type 1-800-266578833 on your phone to dial. Given an array of numbers like "266578833" above, find all the words which could be formed from them. The problem is obviously exponential in complexity. Assuming each phone key holds 3 letters and having the array "266578833", there are 3*3*3*3*3*3*3*3*3 possible combinations, which means 3⁹. So any algorithm has to be at least O(3ⁿ), where n is the size of the array of numbers.

The problem is easily solved in a recursive way: take each number and see which letters are assigned to it. Take each letter in turn, and each turn generate all possible combinations with the other letters:

   1:  //keep here the vector of letters

   2:  //like on position 5, the letters "jkl", which are on key 5 of a phone

   3:  vector<string> words;

   4:   

   5:  void generateWords(int* vec, int size, int index, vector<char>* currentWord) {

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

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

   8:              cout << currentWord->at(i);

   9:          cout << endl;

  10:          return;

  11:      }

  12:      //otherwise take each letter from the current key and add it to the stack

  13:      //then generate combinations with the other keys

  14:      for (int i = 0; i < words[vec[index]].size(); i++) {

  15:          currentWord->push_back(words[vec[index]][i]);

  16:          generateWords(vec, size, index + 1, currentWord);

  17:          currentWord->pop_back();

  18:      }

  19:  }

To call this, "words" needs to be initialized, like this:

   1:      words.push_back("");    //0

   2:      words.push_back(".,'"); //1

   3:      words.push_back("abc"); //2

   4:      words.push_back("def"); //3

   5:      words.push_back("ghi"); //4

   6:      words.push_back("jkl"); //5

   7:      words.push_back("mno"); //6

   8:      words.push_back("pqrs");//7

   9:      words.push_back("tuv"); //8

  10:      words.push_back("wxyz");//9

  11:      int size = 3;

  12:      int vec[] = { 2, 5, 8 };

  13:      vector<char> currentWord;

  14:      generateWords(vec, size, 0, &currentWord);

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 generate permutations of an array or string

I've been asked this on interviews a number of times, so I think it counts as "common questions". The answer is simple.

It can be done recursively in a logical way: having a function which takes an array, swap the first element with all the others, in turn, and at each turn, call the function again for the rest of the array (skipping the first position):

   1:  //head is the original array, unchanged between functions calls

   2:  //this is so that we can print the full array

   3:  //first is the "partial" array, which is being permuted now

   4:  void permutations(int* head, int totalLen, int* first, int len) {

   5:      if (len == 1) {//we reached the end of the array

   6:          for (int i = 0; i < totalLen; i++)

   7:              cout << head[i] << " ";

   8:          cout << endl;

   9:          return;

  10:      }

  11:      //first do all the permutations

  12:      //without swaping the first element with all the others

  13:      permutations(head, totalLen, first + 1, len - 1);

  14:      int temp = first[0];

  15:      for (int i = 1; i < len; i++) {

  16:          first[0] = first[i]; //swap the first element

  17:          first[i] = temp; //with all the others, in turn

  18:          permutations(head, totalLen, first + 1, len - 1);

  19:          first[i] = first[0]; //each turn generate permutations for

  20:          first[0] = temp;// the rest of the array, then swap back the first elem

  21:      }

  22:  }

The function is called like this:

   1:      int size = 4;

   2:      int vec[] = { 1, 2, 3, 4 };

   3:      permutations(vec, size, vec, size);

How to implement Dijkstra's algorithm

Dijkstra's algorithm is a graph search algorithm, often used in routing. For a given node in the graph, the algorithm finds the path with lowest cost between that node and every other node. It can also be used for finding costs of shortest paths from a single node to a single destination node by stopping the algorithm once the shortest path (lowest cost) to the destination node has been determined.

The algorithm is described on-line fairly good, so I won't spend time describing it again here. The main ideas are that we need to keep a list with all the nodes that we visited and another list with all the nodes that we still haven't visited. At each iteration we take the unvisited node with the lowest distance from the source (calculated so far) and calculate the distance from the source to each of it's neighbors. We stop when there are no unvisited nodes.

I'm just going to print the algorithm since it does all the talking by itself. Some comments are available in the code which should explain everything.

   1:  #include <iostream>

   2:  #include <vector>

   3:  #include <string>

   4:  #include <set>

   5:  #include <queue>

   6:  using namespace std;

   7:   

   8:  const int SIZE = 5; //number of nodes

   9:  int graph[SIZE][SIZE];//the graph itself

  10:  int d[SIZE]; //distances from the source to each node

  11:  int pi[SIZE];//contains the predecessor node for each node

  12:  vector<int> s;//list of nodes which were already visited

  13:  vector<int> vs;//list of nodes which were not visited yet

  14:   

  15:  void sort(vector<int>* vec) {

  16:      //sorts the vector of nodes according to 

  17:      //distances from the source to each node

  18:      for (unsigned int i = 0; i < vec->size(); i++)

  19:          for (unsigned int j = i; j < vec->size(); j++)

  20:              if (d[vec->at(i)] > d[vec->at(j)]) {

  21:                  int temp = vec->at(i);

  22:                  vec->at(i) = vec->at(j);

  23:                  vec->at(j) = temp;

  24:              }

  25:  }

  26:   

  27:  void relax(vector<int>* vec, int u) {

  28:      //updates the distances from the source to each node

  29:      //and the predecessor for each node

  30:      for (unsigned int i = 0; i < vec->size(); i++) {

  31:          int vi = vec->at(i);

  32:          if (graph[u][vi] == SHRT_MAX)

  33:              continue;

  34:          if (d[vi] > d[u] + graph[u][vi]) {

  35:              d[vi] = d[u] + graph[u][vi];

  36:              pi[vi] = u;

  37:          }

  38:      }

  39:  }

  40:   

  41:  void printShortestPathTo(int v) {

  42:      //this simply prints the vector of predecessors

  43:      //for the requested node (v)

  44:      cout << "Distance to " << v << " is " << d[v] << endl;

  45:      cout << "Shortest path: ";

  46:      int x = pi[v];

  47:      while (x != -1) {

  48:          cout << x << "<-";

  49:          x = pi[x];

  50:      }

  51:      cout << endl << endl;

  52:  }

  53:   

  54:  int main() {

  55:      //initialize all the costs in the graph

  56:      for (int i = 0; i < SIZE; i++)

  57:          for (int j = 0; j < SIZE; j++)

  58:              graph[i][j] = SHRT_MAX;

  59:   

  60:      graph[0][1] = 20;

  61:      graph[0][4] = 40;

  62:      graph[1][4] = 50;

  63:      graph[2][3] = 30;

  64:      graph[2][4] = 60;

  65:      graph[4][2] = 20;

  66:      graph[4][3] = 100;

  67:   

  68:      for (int i = 0; i < SIZE; i++) {

  69:          for (int j = 0; j < SIZE; j++) {

  70:              cout << graph[i][j] << "\t";

  71:          }

  72:          cout << endl;

  73:      }

  74:      for (int i = 0; i < SIZE; i++) {

  75:          vs.push_back(i);//initialize all the variables

  76:          d[i] = SHRT_MAX;//all distances to infinite

  77:          pi[i] = -1;//nodes have no predecesors 

  78:      }

  79:      d[0] = 0; //the distance of the source is 0

  80:      sort(&vs); //we sort the nodes according to the distance

  81:   

  82:      while (vs.size() > 0) {

  83:          int x = vs.front();//take the node with the shortest distance

  84:          for (unsigned int i = 0; i < vs.size() - 1; i++) {

  85:              vs.at(i) = vs.at(i + 1);

  86:          }

  87:          vs.pop_back();

  88:          s.push_back(x);//mark it as visited

  89:          relax(&vs, x);//update the distances

  90:          sort(&vs); //sort the nodes according to the new distances

  91:      }

  92:   

  93:      printShortestPathTo(4);//choose any node

  94:      return 0;

  95:  }

How to find the longest continuous increasing sequence

How to find the longest continuous increasing sequence in a array of numbers is one of the questions I was asked in a interview at Microsoft, Copenhagen. The solution I provided then was not the best one, since I wasn't so well prepared (I gave a O(n*log₂n) solution which is better than the basic O(n²) solution, but still not the optimum one). This can be done with O(n) time complexity. Hopefully writing these things here will help me in my future interviews.

The idea for the O(n) solution is to keep track of the start of the longest continuous increasing sequence and it's length. At each item, if it's bigger than the previous, then we have a sequence. If it's longer then the current maximum length, then we have a new longest increasing sequence, longer than the previous one.

The same principle can be applied to similar problem which I'll post later. Until then, here's the algorithm:

   1:  void longestContinuousIncrSeq(int* a, int size) {

   2:      int maxstart = 0;

   3:      int max = 1;

   4:      int start = 0;

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

   6:          if (a[i] > a[i - 1]) {

   7:              if (i - start + 1 > max) {

   8:                  max = i - start + 1;

   9:                  maxstart = start;

  10:              }

  11:          } else {

  12:              start = i;

  13:          }

  14:      }

  15:      cout << "Longest sequence starts at " << maxstart << " and is " << max << " numbers long." << endl;

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

  17:          cout << a[maxstart + i] << " ";

  18:      }

  19:      cout << endl;

  20:  }

How to reverse the order of words in a sentence but also each word

This is a common trick which can be done using pointers in C/C++, but the principle is the same for other languages: first reverse the whole sentence, disregarding the words, then reverse each word by itself (words are separated by whitespace).

The method to reverse a string is easy:

   1:  void reverseWord(char*& word, int len) {

   2:      for (int i = 0; i < len / 2; i++) {

   3:          char temp = word[i];

   4:          char temp2 = word[len - i - 1];

   5:          *(word +i) = temp2;

   6:          word[len - i - 1] = temp;

   7:      }

   8:  }

So we could use the above function to reverse the order of words in a sentence and also the letters in each word:

   1:      string s = "This is a test run";

   2:      char* str = const_cast<char*>(s.c_str());

   3:      int size = s.size();

   4:      cout << "Initial string is: ";

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

   6:          cout << str[i];

   7:      cout << endl;

   8:      reverseWord(str, size);

   9:      cout << "Whole string reversed is: ";

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

  11:          cout << str[i];

  12:      cout << endl;

  13:      // do stuff here

  14:      int k = 0;

  15:      int start = 0;

  16:      char* tmp = str;

  17:      while (k <= size) {

  18:          if (str[k] == ' ' || str[k] == '\0') {

  19:              reverseWord(tmp, k - start);

  20:              tmp = str + k + 1;

  21:              start = k + 1;

  22:          }

  23:          ++k;

  24:      }

  25:      //

  26:      cout << "After processing, string is: ";

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

  28:          cout << str[i];

  29:      cout << endl;

The complexity is... O(n) ?

How to do merge sort

Merge sort is a O(n*log₂n) complexity algorithm which is why it's preferred in various interviews. It is also a divide and conquer algorithm and the best way to sort linked lists, which I discussed in my previous post. The Java implementation of sorting collections (linked lists) is done using merge sort.

So here is how it's done. It's quite a lot of code, but it's easy to understand:

   1:  void mergeSort(int arr[], int first, int last) {

   2:      int SIZE = last - first;

   3:      if (SIZE <= 1)

   4:          return;

   5:      //if only 2 elements exist, just swap if necessary

   6:      if (SIZE == 2) {

   7:          if (arr[first] > arr[last - 1]) {

   8:              int tmp = arr[first];

   9:              arr[first] = arr[last - 1];

  10:              arr[last - 1] = tmp;

  11:          }

  12:          return;

  13:      }

  14:      //otherwise find the middle 

  15:      //and apply merge sort for each half

  16:      int half = first + SIZE / 2;

  17:   

  18:      mergeSort(arr, first, half);

  19:      mergeSort(arr, half, last);

  20:   

  21:      int i = first;

  22:      int j = half;

  23:      int* temp = new int[SIZE];

  24:      memset(temp, 0, sizeof(int) * SIZE);

  25:      int k = 0;

  26:      //after both halfs are sorted

  27:      //merge them together in one big sorted list

  28:      while (i < half || j < last) {

  29:          if (i < half && j < last) {

  30:              if (arr[i] < arr[j]) {

  31:                  temp[k] = arr[i];

  32:                  i++;

  33:              } else {

  34:                  temp[k] = arr[j];

  35:                  j++;

  36:              }

  37:          } else if (i < half) {

  38:              temp[k] = arr[i];

  39:              i++;

  40:          } else {

  41:              temp[k] = arr[j];

  42:              j++;

  43:          }

  44:          ++k;

  45:      }

  46:      //overrite the original array with the sorted elements

  47:      for (int m = 0; m < SIZE; m++)

  48:          arr[first + m] = temp[m];

  49:      delete[] temp;

  50:  }

How to do string matching

There are numerous algorithms for finding matches between strings and patterns, see wikipedia for detailed explanations. In the example implementation below, I chose a simpler variation of the Boyer-Moore algorithm, just because it's fast to implement and understand, and good enough in practice. The algorithm is called Boyer–Moore–Horspool algorithm or Horspool's algorithm.

It uses only the first table from Boyer-Moore, which is why it's easy to implement.
First, here's the function which build the table:

   1:  const int SIZE = 255;

   2:   

   3:  void computeTable(int arr[], char* pattern, int len) {

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

   5:          arr[i] = len;

   6:      }

   7:      for (int i = 0; i < len - 1; i++) {

   8:          arr[pattern[i]] = len - i - 1;

   9:      }

  10:  }

And the actual string matching uses the table which we build above:

   1:  int findOccurences(char* pattern, int patternLen, char* str, int strLen, int* table) {

   2:      int i = 0;

   3:      int pos = 0;

   4:      int last = patternLen - 1;

   5:      while (patternLen <= strLen) {

   6:          for (i = last; str[i] == pattern[i] && i >= 0; i--);

   7:          if (i == -1)

   8:              //return pos;

   9:              cout << "found one at position: " << pos << endl;

  10:          if (strLen <= table[str[last]])

  11:              return -1;

  12:          int offset = table[str[last]];

  13:          str += offset;

  14:          strLen -= offset;

  15:          pos += offset;

  16:      }

  17:      return -1;

  18:  }

You can use it simply by typing this:

   1:  int main() {

   2:      char pattern[] = "gcagagag";

   3:      char str[] = "gcatcgcagagagtatacagtacg";

   4:      int patternSize = sizeof(pattern) - 1;

   5:      int strSize = sizeof(str) - 1;

   6:      int arr[SIZE];

   7:      computeTable(arr, pattern, patternSize);

   8:      cout << "Finding occurences... " << endl;

   9:      cout << findOccurences(pattern, patternSize, str, strSize, arr) << endl;

  10:      return 0;

  11:  }

How to sort an array using heap sort

Heap-sort means using the heap structure and heap operations, as defined in my previous post, to sort a container such as an array. The complexity for heap sort is O(n * log₂n), explained next.

Take each element from the unsorted array and put it into a heap, restoring the heap property each time. Restoring the heap property is O(log₂ n) complexity and you have to multiply that for each element of the array, meaning O(n*log₂n). After you finish, remove one element at a time from the heap (the root each time, because it's the biggest element), restoring the heap property after each removal. Again, this is O(n*log₂n).

The full algorithm also requires O(n) additional space.
Here it is:

   1:  template <class T>

   2:  void sortArray(vector<T>* vec) {

   3:      vector<int>* heap = new vector<T>();

   4:      for (unsigned int i = 0; i < vec->size(); i++) {

   5:          addToHeap(heap, vec->at(i));

   6:      }

   7:      vec->clear();

   8:      T elem = deleteFromHeap(heap);

   9:      while (elem != -1) {

  10:          vec->push_back(elem);

  11:          elem = deleteFromHeap(heap);

  12:      }

  13:      delete heap;

  14:  }

How to implement a heap

Doing basic operations on a heap is a more complicated than implementing a binary tree, but is a good thing to know just in case. The easiest and most efficient way to implement a heap is using an array.

Inserting to a heap means adding a new element to the last position, than restoring the heap property, by moving up the tree. The child of a node k in the array is at positions 2k+1 and 2k+2, so moving up the tree is just basic arithmetic.

Deleting from the heap simply means replacing the root (the element at position k 0) with the last element, delete the last element, and restore the heap property.
Without further delays, here's the code.

For insertion:

   1:  template <class T>

   2:  void addToHeap(vector<T>* heap, T val) {

   3:      heap->push_back(val);

   4:      int pos = heap->size() - 1;

   5:      if (pos == 0)

   6:          return;

   7:      bool fixingHeap = true;

   8:      do {

   9:          int parent = 0;

  10:          if (pos % 2 == 0)

  11:              parent = (pos - 2) / 2;

  12:          else

  13:              parent = (pos - 1) / 2;

  14:          if (heap->at(parent) < heap->at(pos)) {

  15:              T temp = heap->at(pos);

  16:              heap->at(pos) = heap->at(parent);

  17:              heap->at(parent) = temp;

  18:              pos = parent;

  19:          } else {

  20:              fixingHeap = false;

  21:          }

  22:      } while (fixingHeap && pos != 0);

  23:  }

For deleting:

   1:  template <class T>

   2:  T deleteFromHeap(vector<T>* heap) {

   3:      int size = heap->size();

   4:      if (size == 0) {

   5:          return -1;

   6:      }

   7:      T ret = heap->front();

   8:      if (size == 1) {

   9:          heap->clear();

  10:          return ret;

  11:      }

  12:      if (size == 2) {

  13:          heap->at(0) = heap->at(size - 1);

  14:          heap->pop_back();

  15:          return ret;

  16:      }

  17:      heap->at(0) = heap->at(size - 1);

  18:      heap->pop_back();

  19:      size--;

  20:      bool fixingHeap = true;

  21:      int pos = 0;

  22:      do {

  23:          int child1 = 2 * pos + 1;

  24:          int child2 = 2 * pos + 2;

  25:          int switchPosition = 0;

  26:          T max = 0;

  27:          if (child2 < size) {

  28:              //2 children

  29:              if (heap->at(child1) > heap->at(child2)) {

  30:                  switchPosition = child1;

  31:                  max = heap->at(child1);

  32:              }

  33:              else {

  34:                  switchPosition = child2;

  35:                  max = heap->at(child2);

  36:              }

  37:              if (heap->at(pos) < max) {

  38:                  T temp = heap->at(pos);

  39:                  heap->at(pos) = heap->at(switchPosition);

  40:                  heap->at(switchPosition) = temp;

  41:                  pos = switchPosition;

  42:              } else {

  43:                  fixingHeap = false;

  44:              }

  45:          } else if (child1 < size) {

  46:              //1 child

  47:              if (heap->at(pos) < heap->at(child1)) {

  48:                  T temp = heap->at(pos);

  49:                  heap->at(pos) = heap->at(child1);

  50:                  heap->at(child1) = temp;

  51:                  pos = child1;

  52:              } else {

  53:                  fixingHeap = false;

  54:              }

  55:          } else {

  56:              //0 children;

  57:              fixingHeap = false;

  58:          }

  59:      } while (fixingHeap);

  60:      return ret;

  61:  }

How to find the sub-array with the maximum sum

Suppose you have an array of integers, and you want to find the sub-array with the maximum sum. One obvious solution would be to take each index, go through the rest of the numbers, find the local sub-array with the maximum sum and compare with the global found. But that would mean O(n²), which although polynomial, is time expensive.

There is a O(n) solution: go through each index of the array, remembering what the max sum is until now, from where it starts and where it ends. At each step, remember a local sub-array and check if it's larger than the maximum. If it is, the maximum becomes the current sub-array. If the local sum ever becomes <0, just restart the sub-array with the next index. Here's the algorithm:

   1:      int arr[10] = {3, 1, 6, -1, -7, 3, 10, -5, 0, 1};

   2:      int maxsum = arr[0];

   3:      int maxstart = 0;

   4:      int maxend = 0;

   5:      int sum = arr[0];

   6:      int start = 0;

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

   8:          sum += arr[i];

   9:          if (sum > maxsum) {

  10:              maxsum = sum;

  11:              maxend = i;

  12:              maxstart = start;

  13:          }

  14:          if (sum < 0) {

  15:              sum = 0;

  16:              start = i + 1;

  17:          }

  18:      }

  19:      cout << "maxsum=" << maxsum << endl;

  20:      cout << "sequence: ";

  21:      for (int i =  maxstart; i <= maxend; i++) {

  22:          cout << arr[i] << " ";

  23:      }

  24:      cout << endl;

Here's what this prints:

   1:        maxsum=15

   2:        sequence: 3 1 6 -1 -7 3 10

How to convert a number from little endian to big endian

Converting from little endian to big endian means actually reversing the bits in a number, like in a mirror. This can be done iteratively, by removing one bit at a time and building another number with the bits reversed. I don't know any other version, but I don't think there's a better solution.

   1:      //little endian to big endian

   2:      unsigned char littleEndianN = 5;

   3:      cout << (unsigned int)littleEndianN << "(size=" << sizeof(littleEndianN) * 8 << ") little endian is ";

   4:      unsigned char bigEndianN = 0;

   5:      for (int i = 0; i < sizeof(littleEndianN) * 8; i++) {

   6:          cout << (littleEndianN & 1);

   7:          bigEndianN |= (littleEndianN & 1);

   8:          littleEndianN >>= 1;

   9:          if (i < (sizeof(littleEndianN) * 8 - 1))

  10:              bigEndianN <<= 1;

  11:      }

  12:      cout << " meaning " << (unsigned int)bigEndianN << " in big endian" << endl;

Here's what this prints:

   1:  5(size=8) little endian is 10100000 meaning 160 in big endian

What happens if the number is negative? Well, if we change all the unsigned char's to char's, the program prints this:

   1:  -5(size=8) little endian is 11011111 meaning -33 in big endian

Do you know why?
Also since we're on the subject, how do you tell if the computer representation is little endian or big endian? Spoiler below :)

   1:  bool isLittleEndian = ((1 << 1) == 2);

How to check if a number is a power of 2 (Google phone screening)

This is actually one of the questions I was asked in my Google first phone screening, and it's really easy, because there's a trick for that: given a number N, you can check if it's a power of two if N & (N-1) == 0.

   1:  int n = 1024;

   2:  cout << n << " is " 

   3:      << ((n & (n-1)) ? "NOT " : "" )

   4:      << "power of 2" << endl;

You could also do the iterative version, where you repeatedly check the first byte (N & 1), then shift to the right (N >> 1), and again, for all 32 bits (assuming it's a 32bit integer). If the total number of bits with value 1 is just one, it means it's a power of two. I gave this as an alternative to the trick above and everything was fine.

How to print all the paths from the root to a leaf in a tree

Consider the following tree:

   1:             10

   2:            /   \

   3:           25    7

   4:               /   \

   5:              8     2

There are three paths from the root to a leaf, in this tree:
10 -> 25
10 -> 7 -> 8
10 -> 7 -> 2
Some programming questions I found on the net, and are useful to know, are how to print all these paths, given a tree in a structure as below, and another one, how to find if one of these paths has a certain given sum. Both are solved using recursion.
To print all the paths recursively, we need the current node, and a way to know what path reaches till that node. Therefore we could write something like this:

   1:  void printPaths(struct node* node) { 

   2:      struct node* prevPaths[100];

   3:      int pathLen = 0;

   4:      printPaths(node, prevPaths, pathLen);

   5:  }

So we start out with the root node and an empty list (no paths before the root node). Replacing the array prevPaths[100] with something reasonable is left as a challenge to the reader.

   1:  void printPaths(node* head, node** prevPaths, int pathLen) {

   2:      if (head == 0) { //we have reached the end, print the existing path

   3:          cout << "path: ";

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

   5:              cout << prevPaths[i]->data << " ";

   6:          cout << endl;

   7:          return;

   8:      } //otherwise

   9:      prevPaths[pathLen] = head; //add the current node to the path

  10:      pathLen++; //increase the path length

  11:      if (head->left == 0 && head->right == 0) //if it has no children then call the function one more time to print the paths

  12:          printPaths(head->left, prevPaths, pathLen);

  13:      else if (head->left == 0 && head->right != 0) //if it has one child, continue to it

  14:          printPaths(head->right, prevPaths, pathLen);

  15:      else if (head->left != 0 && head->right == 0)

  16:          printPaths(head->left, prevPaths, pathLen);

  17:      else {

  18:          printPaths(head->left, prevPaths, pathLen);//if it has both children, search both

  19:          printPaths(head->right, prevPaths, pathLen);

  20:      }

How about if you would want to find out if a certain path has a give sum? Following the same principle we get:

   1:  int hasPathSum(struct node* node, int sum) { 

   2:      if (node == 0) //we reached a dead end

   3:          if (sum == 0)

   4:              return 1;

   5:          else

   6:              return 0;

   7:      sum -= node->data; //otherwise continue to each child with the remaining sum

   8:      return max(hasPathSum(node->left, sum), hasPathSum(node->right, sum));    

   9:  }

So we go through each path, removing the current value of the node from the existing sum. If at the end, the sum is 0, then the values from that path add up to exactly the inital sum, otherwise not.

How to mirror a binary tree

Easy, but you have to be prepared for anything :) Mirroring means switching the pointers around, inside of the tree, so that the resulting tree looks like it's mirror copy of the original tree. Here's an example.
So the tree:

   1:             10

   2:            /   \

   3:           7     25

   4:         /   \

   5:        2     8

becomes:

   1:             10

   2:            /   \

   3:           25    7

   4:               /   \

   5:              8     2

The solution has to be O(n) because it has to change all the pointers from all the nodes, so it can't be done faster.

   1:  void mirror(struct node* head) {

   2:      if (head == 0)

   3:          return;

   4:      node* temp = head->left;

   5:      head->left = head->right;

   6:      head->right = temp; // switch left child with right child

   7:      mirror(head->left); // then repeat the process with each child

   8:      mirror(head->right);

   9:  }

This can be easily expanded for generic trees with more than two children, the basic idea remains the same.

How to do BFS/BFT and DFS/DFT in a tree

Another one of the classic interview questions is how to do BFT (breadth-first traversal) and DFT (depth-first traversal) in a tree of some kind. For this purpose I'm going to consider a binary tree, just because the algorithm is shorter to write and easier to understand. It can be applied on any kind of tree.
The structure of a tree node should look like this, resembling the node of a linked list:

   1:  struct node {

   2:      int data;

   3:      struct node* left;

   4:      struct node* right;

   5:  };

The recursive solution for DFT is really easy so I'm not going to write it here. For BFT it's a little more complicated, but I want to focus here on the iterative solutions for both, since they also involve two frequently used data structures, a stack and a queue. In the examples below, I use std::queue and std::stack.

For BFT:

   1:  void bfs(node* head) {

   2:      queue<node*> q;

   3:      q.push(head);

   4:      while (!q.empty()) {

   5:          node* n = q.front();

   6:          q.pop();

   7:          cout << n->data << " ";

   8:          if (n->left != 0)

   9:              q.push(n->left);

  10:          if (n->right != 0)

  11:              q.push(n->right);

  12:      }

  13:      cout << endl;

  14:  }

DFT simply exchanges the queue with a stack:

   1:  void dfs(node* head) {

   2:      stack<node*> q;

   3:      q.push(head);

   4:      while (!q.empty()) {

   5:          node* n = q.top();

   6:          q.pop();

   7:          cout << n->data << " ";

   8:          if (n->left != 0)

   9:              q.push(n->left);

  10:          if (n->right != 0)

  11:              q.push(n->right);

  12:      }

  13:      cout << endl;

  14:  }