Interview Questions 22

1. Given an integer array, sort the integer array such that the concatenated integer of the result array is max. e.g. [4, 94, 9, 14, 1] will be sorted to [9,94,4,14,1] where the result integer is 9944141

2. I have a card pack of 313 cards. I remove the topmost card from card pack and place it on desk and I remove the next one and put it below the pack of cards(that you are holding). keep doing this till all the cards are on desk. Pick up the card stack from desk and repeat these steps till you find retrieve the original cards order.

3. [Design + Graph Traversal] Assume you have a set of 1500 independent pieces of code. We’ll call them projects. Each project can either be:
1) completely independent
2) dependent on other projects
3) dependent on other projects and have other projects dependent on it
The combined build times of all 1500 projects is 24 hours(so build project 1, when it finished, build project 2, etc). A build consists of compiling and linking all the requisite code. You can assume you don’t have to worry about a budget. If there’s a tool that would help you out, you can use it if you can describe how it works. How would you speed up the build process?

4. Given a BST in a language where memory must be handled manually, how do you completely remove BST from memory? Recursion is not allowed. [O(N), O(1)]

5. [Don't vomit out TRIE] You are developing a system for a cell phone which will automatically predict what word a user is typing. Talk about the data structures and algorithms you would use to make this, keeping in mind that cell phones have limited memory/CPU power.

6. There are N web servers. Each web server has a huge file containing random 1 million numbers (numbers can repeat). Find the median of these N million numbers given that only 1 million numbers can be brought into memory at a time.

7. Many irregular shape objects are moving in random direction. provide data structure and algo to detect collision. Remember that objects are in million.

8. A complete ternary tree is a tree in which each and every node has either 0 or 3 children . Given preorder of a complete ternary tree , construct the tree . Preorder will be a string containing characterd i and l where i represents an internal node and l represent a leaf node .

9. [Math] Find the number of strings of length n having u distinct uppercase letters , l distinct lowercase letters and d distinct digits.

10. Given a sorting order string, sort the input string based on the given sorting order string.
Ex. sorting order string -> dfbcae
Input string -> abcdeeabc
output -> dbbccaaee

DP after a long time :)

At work it seems I will be shifting from Java to C++ now. I have never coded in C++ before, whenever I have it was solely for the purpose to use their beautiful vector, map, string and all libraries. So I guess I should start doing some C++ coding too. A step towards it, I wrote a C code after a looong time. Obviously, a DP problem to target . It is a typical interview problem, just that the O(n) is also possible, and I feel it’s the best one can do.

Problem: Given an array of integers, each element represents the max number of jumps can make forward. What is the minimum number of element selections to reach the end of the array (starting from the first element).
Example: arr = 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9
Here the min # of selections is : 3
with the sequence : 1-> 3 -> 8 ->9
First element is 1, so can only go to 3.
Second element is 3, so can make at most 3 jumps: eg to 5 or 8 or 9.
If an element is 0, then cannot make any jumps

PS: Have not checked for corner cases. Laziness again

#include<stdio.h>
#include<stdlib.h>

#define MAX 0x7fffffff

inline int min(int a, int b) {
  return a >= b ? b : a;
}

int find_min_steps(int const * const input, const int n) {
  int min_steps_dp[n], i, temp, next_vacant;
  for (i = 0; i < n; min_steps_dp[i++] = MAX);

  min_steps_dp[0] = 0;
  next_vacant = 1; // Is the index in the array whose min_steps needs to be updated
                   // in the next iteration.
  for (i = 0; i < n && min_steps_dp[n - 1] == MAX; i++) {
    temp = i + input[i];
    if (temp >= n) {
      min_steps_dp[n - 1] = min(min_steps_dp[n - 1], min_steps_dp[i] + 1);
      temp = n - 1;
    } else {
      printf("Updating min[%d] to %d \n", i + input[i], min_steps_dp[i] + 1);
      min_steps_dp[temp] = min(min_steps_dp[temp], min_steps_dp[i] + 1);
    }
    if (temp > next_vacant) {
      for (; next_vacant < temp; next_vacant++) {
        min_steps_dp[next_vacant]
          = min(min_steps_dp[temp], min_steps_dp[next_vacant]);
      }
    }
  }
  for (i=0;i<n;printf("%d ",min_steps_dp[i++]));printf("\n");
  return min_steps_dp[n-1];
}

int main() {
  int n, *input, i;
  scanf("%d",&n);
  if ((input = (int *)malloc(n * sizeof(int))) == NULL) {
    return -1;
  }
  for (i = 0;i < n; scanf("%d",&input[i++]));
  printf("Minimum steps: %d\n",find_min_steps(input, n));
  return 0;
}

Another Greedy solution provided by Abhishek in O(n) time and O(1) space.

#include <iostream>
#include <vector>

using namespace std;

int find_min_steps(vector<int>& input) {
   int start, end, next_start;
   vector<int> result;
   start = end = 0;
   int n = input.size();

   while (end < n-1) {
     int max = -1;
     for(int w = 0; start <= end ; w++, start++){
       if(input[start] + w > max) {
         max = input[start] + w ;
         next_start = start;
       }
     }
     start = end + 1;
     end = next_start + input[next_start];
     result.push_back(input[next_start]);
   }
   cout << endl << "steps are : ";
   for(int i =0; i< result.size(); ++i)
     cout << endl << result[i];
   cout << endl;
   return result.size();
}

int main() {
  vector<int> input;
  int t = -1;
  cout << endl << "enter input values.. (-1) to end" << endl;
  do {
   cin >> t;
   input.push_back(t);
  } while(t != -1);
  input.resize(input.size() -1); //remove last pushed -1.
  cout << endl << "Minimum steps: "<< find_min_steps(input) << endl;
  return 0;
}

Some more Dynamic Programming

I noticed that most people who visited my blog were particularly interested in Dynamic Programming section of my blog. The two posts which I see were quiet popular were the Programming Problem Solution 1 and Solution to Dynamic Programming Problems. The questions which were solved in the two posts were fairly good to provide a beginner insight into Dynamic Programming. So I just went through my collection and found some more resources of practice problems for Dynamic Programming.

• This is a very nice chapter for introduction to Dynamic Programming.
• This is a set of problems in Dynamic Programming.
• This is a second set of problems in Dynamic Programming with solutions.
• This is a nice article with solved examples in Dynamic Programming.

Hope you find the resources useful

Solution to Dynamic Programming Problems

In an earlier post I had given a set of Dynamic Programming problems which are a must do for every person interested in programming. I would like to share the solutions of them today. This is a link to all those problems and their solutions. The solutions are in swf format and can be viewed in the web browser.

I would suggest one should try to solve them first hand and go to the solutions only after digging deep enough

Programming Problem Solution 1

Change of plan. I figured, giving out questions is getting boring now. Above that noone has asked any doubt regarding any question. Either my blog is read only by me or the people who read my blog are too intelligent . Anyways, for a change I decided to solve a problem for you in this post. So, what can be a better problem/concept to provide to you than Dynamic Programming . So here is a problem which I have solved using dynamic programming and now I will show you the steps and code for the same.

The problem can be found here.

I chose this problem because it is a very good example of a problem where a Greedy Algorithm seems to be sufficient but it’s not . Now any standard textbook will provide you a decent enough background on how to go about solving a problem using DP. Following their legacy, I first propose to you to think of a recurrence relation for this problem and confirm to yourself whether that relation is valid or not.

I hope you have tried, if you have found it, awesum, if not, don’t worry I have the solution for you. The following program which solves the problem using the recurrence relation. It’s a recursive code, so obviously it’s uber low . You can figure out the recurrence relation easily from the program. I hope you’ve got the idea of the solution. Now, the job is not done yet, we need to improve upon the solution.

#include<stdio.h>
#include<stdlib.h>

int N = 0, *arr;

int max(int a,int b)
{
	return a>b?a:b;
}

int fun(int day, int start, int end)
{
	if (day > N)
		return 0;
	return max(fun(day+1,start+1,end) + day*arr[start],fun(day+1,start,end-1) + day*arr[end]);
}

int main()
{
	scanf("%d",&N);
	arr = (int *)malloc(sizeof(int)*(N+1));
	int start,end,day,i;
	for (i=1;i<=N;scanf("%d",&arr[i]),i++);
	start = 1;end = N;day = 1;
	printf("%d\n",fun(1,1,N));
	return 0;
}

The next step found in any standard textbook is to use Memoization. So we’ll do the process here too. You should find a way to store the precomputed results and use them for further calculations. Hope you will code it. The program which uses memoization for this problem. Have a look at it. Hope you get the idea .

#include<stdio.h>
#include<stdlib.h>

int N = 0, *arr;
int **table;

int max(int a,int b)
{
	return a>b?a:b;
}

int fun(int day, int start, int end)
{
	if (day > N)
		return 0;
	if (start >= end && table[end][start] != 0)
		return table[end][start];
	if ( start+1 <= N && table[start+1][end] == 0 )
		table[start+1][end] = fun(day+1,start+1,end);
	if (end-1 >= 0 && table[start][end-1] == 0 )
		table[start][end-1] = fun(day+1,start,end-1);
	return max(table[start+1][end] + day*arr[start],table[start][end-1] + day*arr[end]);
}

int main()
{
	scanf("%d",&N);
	arr = (int *)malloc(sizeof(int)*(N+1));
	table = (int **)malloc(sizeof(int *)*(N+2));
	int start,end,day,i,j;
	for (i=0;i<=N+1;i++)
	{
		*(table+i) = (int *)malloc(sizeof(int)*(N+2));
		for (j=0;j<=N+1;j++)
			table[i][j]=0;
	}
	for (i=1;i<=N;scanf("%d",&arr[i]),i++);
	start = 1;end = N;day = 1;
	printf("%d\n",fun(1,1,N));
	return 0;
}

Now is the time To Play THE GAME . It’s DP time . The last nail in the coffin??? We’ll see. Well by now you will have had an idea of how you are going to program this as a DP solution. Great !! go ahead. For newbies, try out. The DP code for this. Do notice the sizes of the codes I am providing, see how they change

#include<stdio.h>
#include<stdlib.h>

int max(int a,int b)
{
	return a>b?a:b;
}

int main()
{
	int N;
	scanf("%d",&N);
	int arr[N+1],i,j, table[N+1][N+1],tmp=0;
	for (i=1;i<=N;scanf("%d",&arr[i]),i++);
	for (i=1;i<=N;i++)
		table[i][i] = arr[i] * N;
	for (i=1;i<N;i++)
	{
		tmp++;
		for (j=1 ;j+tmp <= N;j++)
			table[j][j+tmp] = max(table[j+1][j+tmp] + arr[j]*(N-tmp), table[j][j+tmp-1] + arr[j+tmp]*(N-tmp) );
	}
	printf("%d\n",table[1][N]);
	return 0;
}

Now what ?? Is the game over ??? Not yet, for geeks, the memoization and DP solution will get uploaded on spoj, but to get to the best timing, you still have to do something special. Think about how this code can be optimized. Notice the way the table is being filled by the DP solution and which part of the table is being used to fill an entry in the table. Take some time to think. Just a hint, it can be done in O(N) space only . The following is my solution which is among the best which has been uploaded. It’s really fast . Analyze this, the pattern how the table has been filled was exploited to use only O(N) space rahter than O(N^2) space.

#include<stdio.h>
#include<stdlib.h>

int max(int a,int b)
{
	return a>b?a:b;
}

int main()
{
	int N;
	scanf("%d",&N);
	int arr[N+1],i,j,table[N+1],tmp=0;
	for (i=1;i<=N;scanf("%d",&arr[i]),i++);
	for (i=1;i<=N;i++)
		table[i] = arr[i] * N;
	for (i=1; i < N; i++)
	{
		tmp++;
		for (j=1;j <= N-i ;j++)
			table[j] = max(table[j+1] + arr[j]*(N-tmp), table[j] + arr[j+tmp ]*(N-tmp));
	}
	printf("%d\n",table[1]);
	return 0;
}

Hope you geeks had a good time.

Do post comments for anything or just compliments