Programming Problems 11

1. There is an array of odd and even numbers. Now, sort them in such a way that the top portion of the array contains odd numbers, bottom portion contains even numbers. The odd numbers are to be sorted in descending order and the even numbers in ascending order. You are not allowed to use any extra array and it has to use a conventional sorting mechanism and should not do any pre or post processing.

Array1 :4,1,6,2,8,9,5,3,2,9,8,4,6
Array2 :6,1,2,9,8

Second array contains elements which are in first array in consequetive locations but may be in any order.Find their starting and ending indexes in array1 most efficiently.
(Be careful of duplicate numbers).

3. Given a set of integers S, rearrange them so that the same number does not occur in a window of n numbers.

when n= 2 and S = [1,1,1,2,2,3] one possible solution is [1,2,1,2,1,3]

4. You have 3 arrays containing 200 integers each. Given that there is one and only one common element in these 3 arrays. Find the common element.

5. Given n points on a 2D coordinate system . What is the most efficient way of finding nearest point for each point? How can we find all the points at a distance k from a given point efficiently?

6. String A can be chained with string B , if the last letter of A matches with the first letter of B. For example “GIRI” can be chained with “IDLE”. This can be generalized to a list of strings, string1 chains with string2 which in turn chains with string3 and so on.

Now, Given a list of n strings find if they can be chained together? Note that this is YES/NO question, i.e. you need not come up with the actual order of chaining.


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

23 Responses to Programming Problems 11

  1. Amar says:

    2. Sum up the 2nd array. Let it be S. Take the sum of same number of consecutive elements in 1st array. If not same reduce first element from sum and add the next element and move on till you find the matching sum. Then you can verify individual elements. Just to add better check, you can compare the XORed value and the product of the 2nd array as well.
    If there is a better method, Pls let me know.

    • Avi Dullu says:

      Your approach will work, but it can be shown that this approach runs in O(n * m) time. There is a better way to do it in O(n * log(m) ) time and O(m) space complexity. Trees might help you, but do take care of duplicates 🙂

      • Divya says:

        how to do with trees?

      • Sreekar says:

        1. Sort the second array in O(K log K). Say second array is of length ‘K’
        2. Take O(K) space array temp[], Count = 0
        3. For each element ‘j’ in first array
        a. Do Binary Search in the second array and try to find an element with index ‘i’
        i. If Found, Update the temp[i] = j. If count =0, startIndex = j, If count ==k then print the startIndex and ‘j’ as the end index
        ii. If Not found, update startIndex = j+1, count =0

  2. Amar says:

    4. The first thing that came to my mind.

    1.Sort all 3 arrays (nlogn)
    2.For every element in first array search 2nd array
    3. If found search the same in 3rd array (n logn * logn)

    Hence total complexity n*logn*logn.

    Is there a better soln?

    • Avi Dullu says:

      yes, infact there is a better solution which taken only (N * log(n) )
      Don’t try to search the elements after sorting, try with a linear scan and look for some property. 🙂

      • ims_china says:

        Just my two cents:

        (1)Sort 3 arrays respectively
        (2) Linear scan 3 arrays,
        Get one element from each,

        (3) Compare 3 elements
        if all same
        found it
        if not
        get the max of them
        keep the array corresponding to the max stay,
        progress the other two to next elements >= max
        goto (3)

        Not sure if it’s the right solution.

      • Avi Dullu says:

        yes, that’s pretty much it. But while you increase the elements of rest 2 arrays, you have to be careful in making sure you do not skip any element. That’s why increasing only the minimum of all the three elements will suffice. Increase it until it is no more the min. of all three. At equality, elements will be found 🙂

  3. Amar says:

    5. Cover trees or a K-d tree. Involves dividing the plane into various regions and forming a tree from that. Then finding the nearest neighbor by searching through that tree. Actually implementing this scheme is another matter altogether. 🙂

    • Avi Dullu says:

      yes .. I just put it up for people to get acquainted with the problem. Actually, heaps are very useful in some such situations. I’ll try to put up some good codable question sometime 🙂

  4. Amar says:

    6. In any order or do we need to check the given order of strings?

    • Avi Dullu says:

      You just have to tell whether a given set of strings can all be chained or not. You are NOT expected to give the ordering, just a yes/no. Still if you want, there can be many orderings possible. Find any one of them 🙂

      • ims_china says:

        just my two cents

        (1) Collect the first and last chars from all the strings into an array. For a last char c, save it as -c

        (2) Then add all the elements in the array to say if the sum is 0. If 0, means chainable, otherwise not

        Not sure if I missed something

  5. ims_china says:

    Sorry, after a second thought, I realized my solution was wrong 🙂

  6. Avi Dullu says:

    For problem 6,

    Try to reduce the problem into finding an Eulerian Path in a directed graph. Check for connectivity and conditions of existence of Euler Path.

    If somebody would like to suggest a method to map the problem onto a Directed Graph, it would be great 🙂

    • vipul says:

      make a edge between a node1 with node2 if the value of last character of node1 is same as value of 1st character of this for each string…O(n*n)…now find the Euler path in this graph…..correct me if i am wrong anywhere

  7. Avi Dullu says:

    yes it was a typo. I’ve edited vipul’s comment

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your 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: