# Programming Problems 11

March 15, 2010 23 Comments

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.

2.

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.

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.

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 🙂

how to do with trees?

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

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?

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

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.

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 🙂

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

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

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

You just have to tell whether a given set of strings can

allbe chained or not. You areNOTexpected to give the ordering, just a yes/no. Still if you want, there can be many orderings possible. Find any one of them 🙂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

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

Another try 🙂

(1) Count the appearances of all the first and last chars

(2) If at most 2 different chars have odd number of appearances, they are chainable

It’s not that simple

Think Graphs 🙂

looks like a version of travelling salesman problem…..

Don’t worry Amar, I won’t give you guys an

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

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

Yes, that is it. It was just a graph mapping and euler path finding problem.

shdnt it be “make a edge between a node1 with node2 if the value of last character of node1 is same as value of “1st” character of node2..”

plz correct me if i am wrong..

@divya

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