Solutions to Interview Questions 2

This post provides the solutions/approaches to the problems provided by me in the Interview Problems 2.

If you have better approaches do share as comments.

Question 1: You are given 2 arrays of size ‘n’ each. You need to stable-merge these arrays such that in the new array sum of product of consecutive elements is maximized and the relative ordering of elements of A and B in C is not reversed.
eg
A= { 2, 1, 3}
B= { 3, 7, 9}
Stable merging A and B will give an array C with ’2n’ elements say C={c1, c2, c3, c4, c5, c6}
You need to find a new array C by merging (stable) A and B such that sum= c1*c2 + c3*c4 + c5* c6….. n terms is maximum.

Solution 1: A simple DP problem with the following recurrence
Condition : S[i+j-1] + max ( A[i] * A[i+1], A[i] * B[j], B[j]*B[j+1])
If in the above condition, the max is due to A[i]*A[i+1], then the merged array will have A[i] in (i+j)th place and A[i+1] at (i+j+1)th place and i will be i+=2, similarly if max is due to A[i]*B[j], then merged array will have A[i] in (i+j)th place and B[j] in (i+j+1)th place and same for the third one.
i is the index of the elements in A array and j in B array and S[i+j-1] is the max sum upto the current state.

A code is worth a million explanations, so here is it.

const int Max = 1000;
vector<int> a,b;
int n;

int memo[Max][Max];


int solve(int i,int j) {

   if(i == n) {
      int ret = 0;
      for (int k=j;k<n;k++) {
	 ret += b[k] * b[k+1];
	 ++k;
      }
      return ret;
   }
   if(j == n) {
      int ret = 0;
      for (int k = i; k < n; k++) {
	 ret += a[k] * a[k+1];
	 ++k;
      }
      return ret;
   }

   int&ret = memo[i][j];
   if(ret != -1) return ret;

   ret = -INF;
   // Three possibilities.
   // (i,i+1) ; (j,j+1) ; [(i,j) == (j,i)]
   if(i + 1 < n) {
      ret = max(ret, a[i] * a[i+1] + solve(i+2,j));
   }
   if(j + 1 < n) {
      ret = max(ret, b[j] * b[j+1] + solve(i,j+2));
   }
   ret = max(ret, a[i]*b[j] + solve(i+1,j+1));
   return ret;
}
int main() {


   scanf("%d",&n);
   a.resize(n); b.resize(n);

   for (int i=0;i<n;i++) scanf("%d",&a[i]);
   for (int i=0;i<n;i++) scanf("%d",&b[i]);

   memset(memo, -1, sizeof memo);
   printf("%d\n",solve(0,0));
   return 0;

}

Question 2: Write code for aligned malloc and free.
Solution 2: See The C programming Language by Brian Kernighan and Dennis Ritchie. It has the implementation of malloc and free. But for this question you will need to make an additional structure and record the actual starting address returned by the malloc call and you will return the aligned pointer. When the call to aligned_free is made, you only pass the recorded address as argument to the actual free function. [I’ll code this only on request :lazy]

Question 3: Our cell phones have T9 dictionary embedded for message writing…How this dictionary is implemented? State any other way to optimize complexity.Mechanism of Addition of new words in that dictionary.
Solution 3: See T9 Dictionary and the tutorial on the DS used is here, here and this is a tutorial on the best DS (optimized for better performance) used for this type of situation. [Tries and Compressed Tries]

Question 4: Given an array of integers(both positive and negative) divide the array into two parts(sub-arrays) such that the difference between the sum of elements in each array is minimum?
Solution 4: A simple interview problem on O(n) space and O(n) time 🙂

Question 5: Write a program to shuffle an pack of cards in the most efficient way.
Solution 5: Knuth Shuffle is the best.

Question 6: Sort an array of 0s, 1s and 2s in O(n) time and O(1) space.
Solution 6: Here is my code for the problem and this is a link shared by spsneo in the comments.

#include<stdio.h>

int main()
{
	int n, i;
	scanf("%d",&n);
	int arr[n];
	for (i=0;i<n;i++)
		scanf("%d",&arr[i]);
	int p_0 = 0, p_2 = n-1, p_1 = -1;
	while (p_1 < p_2 )
	{
		while (p_0 < p_2 && arr[p_0] == 0)
			p_0++;
		while (p_0 < p_2 && arr[p_2] == 2)
			p_2--;
		if (arr[p_0] == 2 || arr[p_2] == 0)
		{
			arr[p_0]^=arr[p_2]^=arr[p_0]^=arr[p_2];
			continue;
		}
		if (p_1 == -1 )
			p_1 = p_0 + 1;
		while (p_1 <= p_2 && arr[p_1] == 1 )  p_1++;
		if (p_1 > p_2)
			break;
		if ( arr[p_1] == 0 )
		{
			arr[p_1]^=arr[p_0]^=arr[p_1]^=arr[p_0];
			p_0++;
		}
		else if ( arr[p_1] == 2 )
		{
			arr[p_1]^=arr[p_2]^=arr[p_1]^=arr[p_2];
			p_2--;
		}
	}
	for (i=0;i<n;i++)
		printf("%d ",arr[i]);
	return 0;
}

Another trivial solution can be to just count the number of 0s,1s and 2s and create the array again.

Advertisements

About Avi Dullu
Jaako rakhe saiyan, maar sake na koi!

20 Responses to Solutions to Interview Questions 2

  1. andy says:

    i think in solution 1 it should be:
    S[i+j-1] = S[i+j-1] + max ( A[i] * A[i+1], A[i] * B[j], B[j]*B[j+1]);

    and not:
    S[i+j-1] + max ( A[i] * A[i+1], A[i] * B[j], B[j]*B[j+1])

    ryt.

    • Avi Dullu says:

      I forgot to type S[i+j] there, it actually is

      S[i+j] = S[i+j-1] + max ( A[i] * A[i+1], A[i] * B[j], B[j]*B[j+1]),

      The logic will work for (i+j)th element in the constructed array using the ith and jth element from the given 2 arrays respectively. It is a global maximization so you will need the S[i+j-1]th value also.

      Let me know if this doesn’t make it clear. 🙂

  2. spandan says:

    shouldn’t we increment j by 2 also for every case.

    • Avi Dullu says:

      Yes and No actually. It depends on the choice which was selected from the max condition. If B[j]*B[j+] was max then yes j will be j+=2 else by 1 or 0 depending on other two conditions.

  3. spandan says:

    correct me if i am wrong….

    if max is due to a[i],a[i+1] increment i by 2 only.

    if max is due to a[j],a[j+1] increment j by 2 only.

    if maxis due to a[i],a[j] increment i and j both by 1.

    is this correct.

  4. spandan says:

    nope just confirming.

  5. andy says:

    i am still not getting why
    S[i+j] = S[i+j-1] + max ( A[i] * A[i+1], A[i] * B[j], B[j]*B[j+1])

    and not simply..

    c = c + max ( A[i] * A[i+1], A[i] * B[j], B[j]*B[j+1]),

    and return c;

  6. andy says:

    Its the same as your soln..

    we r just initializing c=0 —>where is sum found utill now..

    and we keep on updating c as per

    c = c + max ( A[i] * A[i+1], A[i] * B[j], B[j]*B[j+1])

    • Avi Dullu says:

      Your c is my S[i+j-1]. When you formulate a DP you are supposed to indicate the previous result ( if you are using it). I do it by using the value from the array I am constructing. So I use the i+j-1th value to calculate i+jth value. You are suggesting the same thing. Just go over it again 🙂

  7. nik says:

    in question 4 , are the two parts contagious?

  8. John's dad says:

    Hey Avi, are you also known as John. I’m looking for my misbehaved son.

  9. vipul says:

    Q4— for the input given in question…using ur recurrence i m getting…3*7+2*9+1*3

    but actually the ans. is …2*1+3*3+9*7…correct me if i m interpretting wrong here!!!

  10. vipul says:

    Q1— for the input given in question…using ur recurrence i m getting…3*7+2*9+1*3

    but actually the ans. is …2*1+3*3+9*7…correct me if i m interpretting wrong here!!!

  11. Divya says:

    sir i m unable to solve Q4.. please give the solution for it..

  12. beginner says:

    4. i can think of brute force approach for it. Take 1st element alone n rest of array. then first two element and so on and compare.
    Any hints for better soln?

  13. aman says:

    I Think vipul is right..

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: