Interview Questions 2

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.

Advertisements

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

9 Responses to Interview Questions 2

  1. translator says:

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

    • Avi Dullu says:

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

  2. translator says:

    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,

  3. spsneo says:

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

    • Avi Dullu says:

      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.

  4. spsneo says:

    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/

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

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

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: