PROGRAMMING INTERVIEWS

Question: There are n coins in a line. Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins. Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.

Answer: If we assume that n is even then there is simple strategy to ensure that you win. Find the sum of coins at even and odd positions say X and Y respectively. Now if X>Y, pick coins only at even positions else pick coins only at odd positions.

How to ensure that you pick coins only at even or odd positions:
Assume that n = 6 and value are {3, 2, 2, 3, 1, 2}. Then sum at even positions is 7 (2 +3 +2) and at odd positions is 6 (3 +2 +1). So you will always pick the coins at even positions to ensure wining. How to achieve it:

You first pick coin at position 6 (value 2). Now the opponent is forced to choose coin at either at position 1 or 5. If he picks coin at position 1, you choose coin at position 2. Else if he picks coin at position 5, you choose coin at position 4. Following this strategy you will always ensure picking even position coins (same for odd positions.)

An optimal Solution:
Since your opponent is as smart as you, so we need to take all the possible combinations in consideration before our move. Calculating all those moves will include repetitive calculations so this is the place where we can use Dynamic Programming to show its magic.

Say coins are in stored in array A and C(i, j) is the maximum sum possible when remaining coins are from i to j. Lets discuss the case when there are remaining coins from i to j (positions) and it’s your turn to pick the coin. Now there are 2 possibilities:

1. You pick coin A(i)
2. You pick coin A(j)

Case 1 - If you pick coin Ai : Then the opponent has the choice between A(i+1) and A(j). If the opponent takes A(i+1), the remaining coins are { A(i+2) … A(j)}, for which our maximum is denoted by C(i+2, j). On the other hand, if the opponent takes Aj our maximum is C(i+1, j-1). Since the opponent is as smart as you, he would have chosen the choice that yields the minimum amount to you.

Therefore, the maximum amount you can get when you choose Ai is:

C1 = Ai + min { C(i+2, j), C(i+1, j-1) }

Case 2 - If you pick coin Aj :
Similar to case 1, the maximum amount you can get when you choose Aj is:

C2 = Aj + min { C(i+1, j-1), C(i, j-2) }

Therefore

C(i, j)  = max { C1, C2 }   
= max { Ai + min { C(i+2, j),   C(i+1, j-1) },
        Aj + min { C(i+1, j-1), C(i,   j-2) } }

Now we have the recursive function in hand and the above recurrence relation could be implemented in few lines of code. But if we follow simple recursion, its complexity is exponential. The reason is that each recursive call branches into a total of four separate recursive calls, and it could be n levels deep from the very first call).

To reduce the time complexity, we need to store the intermediate values in a table and use them, when required. Memoization provides an efficient way by avoiding re-computations using intermediate results stored in a table.

If you notice, we do not need to build complete matrix but only need to build right (upper) triangular matrix. Also notice that C[i, i] (diagonal elements) will always be equal to A[i]. Below is the code which runs in O(n^2) time and takes O(n^2) space.

Code:

#define MAX 100

int maxMoney(int A[], int N) {
int C[MAX][MAX] = {0};
int x, y, z; //x = C[m+2][n], y = C[m+1][n-1], z = C[m][n-2]
for (int i = 0; i < N; i++) {
  for (int m = 0, n = i; n < N; m++, n++) {
      //calculate x, y, z
      x = (m+2 < N)                         ? C[m+2][n] : 0;
      y = (m+1 < N && n-1 >= 0)    ? C[m+1][n-1] : 0;
      z = (n-1 > 0)                            ? C[m][n-2] : 0;
      C[m][n] = max(A[m] + min(x,y),
                             A[n] + min(y,z));
      //For Debugging      
      cout << x << ", " << y << ", " << z << endl;
      cout << m << ", " << n << ", " << C[m][n] << endl;
  }
}
return C[0][N-1];
}

Question: A long array A[] is given to you. There is a sliding window of size w, which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position.

 
#include<deque>

void maxSlidingWindow(int A[], int n, int w, int B[])
{
   deque<int> Q;
  
   //Initilize deque Q for first window
   for (int i = 0; i < w; i++)
   {
       while (!Q.empty() && A[i] >= A[Q.back()])
           Q.pop_back();
       Q.push_back(i);
   }
  
   for (int i = w; i < n; i++)
   {
       B[i-w] = A[Q.front()];

       //update Q for new window
       while (!Q.empty() && A[i] >= A[Q.back()])
           Q.pop_back();

       //Pop older element outside window from Q    
       while (!Q.empty() && Q.front() <= i-w)
           Q.pop_front();
      
       //Insert current element in Q
       Q.push_back(i);
   }
   B[n-w] = A[Q.front()];
}

Question: Suppose you represent every number with a character like

1. Recursion will stop once we reach the last character in input string.
2. While we are combining 2 characters, we should take care that it doesn’t exceed 25.

//  1234 => 1-2-3-4, 12-2-4, 1-23-4 => bcde, mde, bxe

#include <iostream>
using namespace std;

char arr[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

char input[100];
int len;

void print_combination(int index, char out[], int outindex)
{
  if(index == len){
  out[outindex] = '\0';
  cout << out << endl;
  return;
 }
  
 if(index <= (len - 1)){
  out[outindex] = arr[int(input[index]) - 48];
  print_combination(index+1, out, outindex+1);
 }

  if(index <= (len - 2)){
  int num = (int(input[index])-48)*10 + (int(input[index+1])-48);  
    if (num <= 25){
   out[outindex] = arr[num];
   print_combination(index+2, out, outindex+1);
  }
 }
}

int main(int argc, char* argv[])
{
 char out[100] = {'\0',};
 
 if (argc < 2)
  exit(0);
 else 
  strcpy(input,argv[1]);
  
 len = strlen(input); 
 print_combination(0, out, 0);
}