# Solutions to Interview Questions 2

May 17, 2010 20 Comments

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.

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.

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

constructedarray 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. 🙂

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

Yes and No actually. It depends on the choice which was selected from the

maxcondition. If B[j]*B[j+] was max then yes j will be j+=2 else by 1 or 0 depending on other two conditions.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.

yes ..

Do you find some issue in it ?

nope just confirming.

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;

What is

cthat you are referring to?Can you give your complete DP solution?

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

Your

cis myS[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 thei+j-1th value to calculatei+jth value. You are suggesting the same thing. Just go over it again 🙂in question 4 , are the two parts contagious?

Yes

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

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!!!

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!!!

@vipul

You can see the code and logic now. I have updated the post.

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

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?

I Think vipul is right..