## 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.

## Recent Activity