# Interview Questions 8

May 22, 2010 12 Comments

Some more nice problems collected from Antonio Gulli’s Coding Playground

1. Find the longest common subsequence of given N strings each having length between 0 to M.

2. Partition a set of numbers into two sets such that the difference between their sum is mininum and they have equal num of elements.

3. Given a bst of n nodes, find two nodes whose sum is equal to a number k in O(n) time and constant space

4. We have N element array with k distinct keys. sort this array without using any extra memory.

5. You buy a newspaper and notice that page 8 and 21 are on the same sheet. Can you infer the total number of pages in the newspaper?

6. Given two sorted postive integer arrays A(n) and B(n) (let’s say they are decreasingly sorted), we define a set S = {(a,b) | a \in A and b \in B}. Obviously there are n^2 elements in S. The value of such a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs from S with largest values. in O(n).

5. 28

6. Will need a max-queue to keep the list of next possible elements and deriving out max from that. Still it isn’t O(n) if you consider max queue operations.

3. Two stacks, use one to traverse inorder, another to traverse reverse of inorder. Compare elements with sum and traverse either stack accordingly.

1. How about we divide them in pairs of two. Find out the LCS. Then divide the LCS found in pairs of two and find out thier LCS and so on till we have only one string left. The complexity is pretty high.

Will need to think about the rest…. 🙂

In soln 6 u mean

max heapI believe, still it needs a lot of improvement 🙂For soln 1, think a data structure based solution. String data structures are very handy many a times.

1. Counting chars should do it. Much less complexity O(mn) to be exact.

4. Without using extra memory? Can we use hashing with count for each bucket?

6. Yeah I meant max-heap. Still thinking abt the improvements though.

1. Counting chars ?? I dint get you. Also the complexity of LCS of 2 strings is itself O(n^2), so the solution will be of much higher one.

2. O(k*n) is trivial. Thus if k << n then the trivial method will be just fine. And if k is large then something like partitioning about the median and then solving the problem recursively till k for every section of the array is very small can do.

3. 🙂

2. Generating all subsets of size n/2 involves nC(n/2) set generation and storing the min difference. This is O(n!). :).

Another approach could be: Calculate the total sum. Divide it by 2. Solve it as a Modified bin packing problem where the elements used cannot be less than or greater than n/2. I am not sure it will work though. Any hints?

It is a modified Bin Packing Problem, but you need to do more than just checking for (a1+a2..+an)/2. Analyse the actual algorithm and keep track of number of elements forming a given sum ( from low limit to high limit) and then choosing the minimum. (lower limit is the minimum sum possible using a set of given numbers)

not getting any solution of last question… how it can be done in O(n)

6.

we can do this by having 3 indexes traversing the two arrays.

since first n values are required they would either of type greatest of A + some value in B or greatest of B + some value in A or addition of pair of numbers which are equidistant from start.

let i be index for A, j for B and r for the equidistant values

at start i=0,j=0,r=0

at each loop

calc max of ( A[0] + B[j+1], A[i+1]+ B[0], A[r] + B[r] ) and output it

if max is first increment j , if second increment i ,if third increment r

keep count of values output and stop at n

Hi, Avi for question 3, i have got two solutions O(nlogn) time,O(1) space and O(n) time and O(n) space.

Please tell me how to go about O(n) time and O(1) space

Priyanka,

I would really appreciate if you also post the solutions (in small detail) with the order statistics (which is a very good habit) 🙂

I guess your O(nlogn) solution is: for every node, perform a search for the (Sum – ).

And the O(n) time and O(n) space: put the elements in an array and use the standard 2 pointer solution to figure the 2 numbers, since the elements are already sorted.

A possible O(n) time and O(1) space (excluding the system stack space) could be, to convert the given BST into a doubly linked list and perform you algorithm 2 on it.

Another possibility is to use O(logn) space for storing pointers and use a variant of your algorithm 2. (think about this one)

hey Avi thanx a lot

Can u please post the O(N) solution for this problem 6 don’t seem to find it on any forum ?