World of BROCK

More info :D

noreply@blogger.com (Unknown) — Sun, 05 Jun 2011 13:20:00 +0000

Again, I'd like to share another website I'm working on. I've designed it to post reviews for different hardware and software stuff which I find interesting. Here's a link to my first post! :) Enjoy! Patriot XPorter XT Boost review

Forex trading

noreply@blogger.com (Unknown) — Tue, 02 Nov 2010 20:11:00 +0000

Hi everyone!!! Sorry for the lack of posts, I know it looks like this blog was abandoned, but it's not (not completely :) ).

I've been busy with trying out some online Forex trading with some degree of success.
If anyone out there is interested, please make sure to check out this awesome MetaTrader 4 indicator that I wrote (using my full expertise as a software developer):

http://www.intelligentsoftware.info/

I took these algorithms to the next level by using neural networks to build the ultimate indicator which tells you if the price goes up or down.

Good luck and have fun!

How to print a spiral of numbers 1 through N

noreply@blogger.com (Unknown) — Sat, 13 Mar 2010 15:54:00 +0000

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

Data structures

noreply@blogger.com (Unknown) — Sat, 27 Feb 2010 09:55:00 +0000

What is a linked list?
What is the structure like?
See my first post.

What is the complexity of finding a specific element in a linked list?
Hint: It's O(n).
• An excellent answer will discuss implementation, structure, operational complexity of common operations, and examples of usage.
• A good answer will discuss an example implementation or usage, but will fail to include internal details or complexity analysis.
• A poor answer would be not knowing about linked lists or confusing them with another data structure.

Compare a linked-list to a vector.
Hint: A vector is a single contiguous memory block containing all the elements whereas a linked list is made up of several memory blocks (elements) linked together through the "next" pointer. Access to an element of the array can be made directly in O(1) but in a list, to find the n^th element, you must iterate over the previous n elements, therefore the complexity is O(n). An array is fixed in size so to extend it you must reallocate a different memory block and copy all the existing data to the new allocated block; in a linked list you can simply add a new element which is linked to the last element, so it's much faster.
• An excellent answer will discuss the implementation differences, different pattern of memory usage and access, and mention some use cases where one is more appropriate than the other.
• A good answer will discuss the implementation differences and elaborate on some examples.
• An acceptable answer will merely mention the access time differences.
• A poor answer will make a technical mistake or not know one or both data structures.

What is a hash table? What is it used for?
Hint: The following description applies for all questions about maps. A hash table is a structure which uses hash functions to store and read items. When a key-value pair is inserted, the key is transformed through a hash function into an integer which represents the index in an array where the key-value pair will be stored. Because of this hash function, the insertion and deletions are O(1) in complexity. Therefore, most hash tables are implemented using an array. Hash tables are particularly efficient when the maximum number of entries can be predicted in advance, so that the array can be allocated once with the optimum size and never resized. If hash collisions occur, one usual solution is to store a list of items at each index in the array. This list will contains key-value pairs for which all the keys have the same hash value.
• An excellent answer will describe an O(1) read and write data structure with scaling memory usage and give several examples of where it is useful (e.g. caching, lookup tables with irregular keys).
• A good answer will describe an O(1) read and write data structure and give an example of where it is useful.
• An acceptable answer will mention constant-time access.
• A poor answer will give the access time as something other than constant-time, or confuse it with a tree or other structure.

How can a Map data structure be implemented? (By following the question regarding hash tables, this should be a gimme.)
• An excellent answer will cite at least the hash table-backed and the tree-backed implementations and note the different performance characteristics of each, possibly mentioning that the tree-backed implementation can provide some features not available in a hash-backed implementation (e.g. sorting).
• A good answer will cite both hash table and tree implementations.
• An acceptable answer will cite either the hash table or tree implementation.
• Being unable to answer this question is unacceptable.

What is a binary tree?(This question follows the Map question to allow people who forgot non-hash table solutions to realize and revise their omission. It is good for candidates who only mentioned the hash table implementation of a map to point out that a tree is also an alternative implementation after this question is asked.)
• An excellent answer will describe a binary tree as distinct from a ternary or general tree, and will note that a binary search tree or balanced tree are distinct sub-categories of the generic binary tree.
• A good answer will describe a generic tree where every node has no more than two children and will cite the O(log N) access time where N is the depth/height of the tree.
• An acceptable answer will describe a tree where every node has no more than two children.
• A poor answer will respond by describing a binary search tree or a non-binary tree, and will not respond to gentle hinting or prodding back to the specific question that was asked.

What is the operational complexity of inserting an element into a hash table?
• An excellent answer will correctly cite O(1) complexity and then consider details include about cases in which a collision occurs and common methodologies for resolving hash collisions (i.e. chaining, linear or quadratic probing, secondary hash functions, etc.) are needed.
• A good answer will cite O(1) complexity but will not include collision considerations.
• A poor answer will be incorrect.

How is a hash table implemented?
• An excellent answer will discuss selecting a hashing algorithm, dividing the address space into buckets and tuning the number of buckets to the use-case, hash collisions and bucket overflow/conflict resolution (possibly mentioning several strategies for dealing with collisions), dynamic resizing of the hash table, and might even discuss performance optimizations and interactions with hardware caching.
• A good answer will note the use of a hashing algorithm on the keys and an array or vector of buckets, and will identify hash collisions as a problem and may cite at least one method of dealing with them. The candidate will be able to answer a follow-up about dynamic resizing.
• An acceptable answer will mention an array of buckets and using a hashing function on the key to index into the array.
• A poor answer will be technically incorrect or impossible, or will be for a different data structure than a hash table.
What is the operational complexity of (various operations) on a binary tree?If the candidate already answered this as part of the first phone screen, this question may be skipped. It may also be asked to ensure the candidate is consistent in responding correctly.

What is operational complexity?
Hint: These notations describe different kinds of bounds on asymptotic growth rates. Search the web. You really should know what they all mean, if you want to work at GOOGLE.
• An excellent answer will distinguish between Big Oh, Big Omega, and Big Theta notations and describe each in detail, including how they relate to measures of run-time and space trade-offs.
• A good answer will describe Big Oh notation and how it relates to run-time of algorithms and common operations of abstract data types (ADTs).
• A poor answer will include vague or incorrect ideas regarding Big Oh notation and usage.

What is the operational complexity of inserting an element into a linked list? (Asking a clarifying question about singly-linked lists versus doubly-linked lists is unnecessary in this case, but clarifying requirements is always a good thing.)
• An excellent answer will correctly cite O(N) and note the edge cases such as empty lists and the beginning/ending of the list.
• An acceptable answer will correctly cite O(N).
• A poor answer will be incorrect.

Verbal communication tips

noreply@blogger.com (Unknown) — Fri, 26 Feb 2010 18:59:00 +0000

Why are you leaving your current position?
• A good answer will be generally positive, seeking better challenges or goals. Contract expirations and familial obligations are also common.
• A poor answer would be ranting against the current employer or generally being negative. Honesty is not necessarily negativity. The key is how they view their departure, whether they seek self-improvement whatever the situation.

Why do you want to work for GOOGLE?
• An excellent answer will be enthusiastic about GOOGLE and its business and problem space, demonstrating knowledge of our sites and familiarity with its use.
• A good answer will be enthusiastic about GOOGLE and show a desire to work in this environment and on our sorts of problems.
• A mediocre answer will demonstrate a lack of knowledge of our site and operations

Tell me about a recent project that you have worked on.
• An excellent answer will discuss an in-depth project involving a complicated problem, have a clear description of the problem that explains why it was difficult, describe the solution chosen, and reference how the candidate was involved in the entire process and implementation.
• A good answer may involve a small project that was well-executed, or a large project working on a simple problem, or a complex problem for which a sub-optimal solution was chosen.
• An acceptable answer will describe a project in detail from problem to implementation.
• A poor answer will not give a clear explanation of what the purpose of the project was, or will neglect to mention a solution at all, or will say the candidate was not actually involved in the project being described.

How to hack daily puzzles on www.gameknot.com

noreply@blogger.com (Unknown) — Tue, 22 Dec 2009 09:38:00 +0000

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]

noreply@blogger.com (Unknown) — Sat, 12 Dec 2009 17:40:00 +0000

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

noreply@blogger.com (Unknown) — Wed, 25 Nov 2009 18:15:00 +0000

M64FT7ZUTGK4

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

How to find the missing number from an array

noreply@blogger.com (Unknown) — Sat, 31 Oct 2009 17:48:00 +0000

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

noreply@blogger.com (Unknown) — Fri, 30 Oct 2009 14:45:00 +0000

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

noreply@blogger.com (Unknown) — Mon, 26 Oct 2009 19:03:00 +0000

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

noreply@blogger.com (Unknown) — Fri, 23 Oct 2009 19:21:00 +0000

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

noreply@blogger.com (Unknown) — Mon, 19 Oct 2009 17:08:00 +0000

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

noreply@blogger.com (Unknown) — Sun, 18 Oct 2009 17:09:00 +0000

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

noreply@blogger.com (Unknown) — Sat, 10 Oct 2009 15:28:00 +0000

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

noreply@blogger.com (Unknown) — Sat, 03 Oct 2009 16:02:00 +0000

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

noreply@blogger.com (Unknown) — Fri, 02 Oct 2009 15:47:00 +0000

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

noreply@blogger.com (Unknown) — Sun, 27 Sep 2009 10:59:00 +0000

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

noreply@blogger.com (Unknown) — Sat, 26 Sep 2009 11:42:00 +0000

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

noreply@blogger.com (Unknown) — Sat, 26 Sep 2009 08:34:00 +0000

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

noreply@blogger.com (Unknown) — Tue, 22 Sep 2009 14:46:00 +0000

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

noreply@blogger.com (Unknown) — Mon, 07 Sep 2009 17:48:00 +0000

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

noreply@blogger.com (Unknown) — Sun, 06 Sep 2009 15:30:00 +0000

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)

noreply@blogger.com (Unknown) — Sun, 06 Sep 2009 08:33:00 +0000

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.

World of BROCK

More links :D

More info :D

Forex trading

How to print a spiral of numbers 1 through N

Data structures

Verbal communication tips

How to hack daily puzzles on www.gameknot.com

How to generate random numbers in [1...7] from random numbers in [1...5]

Momentary break

How to find the missing number from an array

How to do integer partitioning

How to find all possible words from a phone number

How to find subsets of an array

How to do the product trick on a array

How to generate permutations of an array or string

How to implement Dijkstra's algorithm

How to find the longest continuous increasing sequence

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

How to do merge sort

How to do string matching

How to sort an array using heap sort

How to implement a heap

How to find the sub-array with the maximum sum

How to convert a number from little endian to big endian

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