Interview Questions 8

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

Advertisements

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

12 Responses to Interview Questions 8

  1. Amar says:

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

    • Avi Dullu says:

      In soln 6 u mean max heap I 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.

  2. Amar says:

    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.

    • Avi Dullu says:

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

  3. Amar says:

    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?

    • Avi Dullu says:

      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)

  4. jalaj says:

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

  5. nik says:

    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

  6. priyanka chatterjee says:

    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

    • Avi Dullu says:

      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)

  7. priyanka chatterjee says:

    hey Avi thanx a lot

  8. Nihil says:

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

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: