# Interview Questions 2

January 16, 2010 9 Comments

The solutions/approaches to the problems in this post are shared on Solutions to Interview Questions 2.

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.

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.

2. Write code for aligned malloc and free.

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.

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

5. Write a program to shuffle an pack of cards in the most efficient way.

6. Sort an array of 0s, 1s and 2s in O(n) time and O(1) space.

is there a time constraint for q1 ? If not, can’t I just sort the two arrays and form the solution.

U cannot sort it because the question mentions a “stable” merge. In stable algorithms ( see Sorting Algorithms page on wiki) you cannot change the relative order of elements. so in the merged array a1 SHOULD come before a2 and same for b1 and b2. Thus sorting cannot be done.

Just a hint, try to get a recursive solution ( DP ) 🙂

Q4. Can I have another array which will keep track of the cumulative sum and then use that to find the partition. I assume that we cannot shuffle the elements of the array to get the best partition possible,

Actually this also has a recursive approach. By your method you can get the solution, but it will run in exponential time. You should go through the problems on Dynamic Problems at https://avidullu.wordpress.com/2010/01/24/algorithm-problem-solving/

Here the text on DP has a collection of standard problems and this is one of them. 🙂

For question 6: Its a famous Dutch National Flag problem.

I haven’t heard of it, but it was a nice problem to code. A lot of care to be taken. Infact, people ask to do it in a single pass of the array.

Yeah it is done in one pass only using three pointers. This was first given by Dijkstra (He was a dutch, so the name of the problem). This problem can be generalized to sorting an array of 0,1,2, .., n in one pass. But it becomes extremely difficult to write code.

Here’s a nice article on this: http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/

Pingback: Solutions to Interview Questions 2 « Avi Dullu's Code Arena

Great post you have here with good info 🙂 Thanks for sharing 🙂