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) ?