# Interview Questions 10

August 3, 2010 3 Comments

1. Given a set of schedules with Start and End times, cluster the ones which have a collision in time. The clusters can have more than two schedules and have to be unique. Do it efficiently.

2. You are given a set of n points in a XY plane. Suggest an algorithm to determine if every point is at least separated by every other point by a Manhattan distance of 5 units. Return should be true or false. Better than O(n^2).

3. You have an array like ar[]= {1,3,2,4,5,4,2}. You need to create

another array ar_low[] such that ar_low[i] = number of elements lower

than or equal to ar[i] in ar[i+1:n-1].

So the output of above should be {0,2,1,2,2,1,0}

4. Generate all strings of length ‘n’, from a given string, which do not contain another given string as a substring.

5. Given an array of size n wherein elements keep on increasing monotically upto a certain location after which they keep on decreasing monotically, then again keep on increasing, then decreasing again and so on. Sort the array in place (ie. using only O(1) extra memory).

6. Given a input string find the longest substring which appears more than once in the string?

7. Write a function that takes an array of five integers, each of which is between 1 and 10, and returns the number of combinations of those integers that sum to 15. For example, calling the function with the array [1, 2, 3, 4, 5] should return 1, while calling it with [5, 5, 10, 2, 3] should return 4 (5 + 10, 5 + 10, 5 + 5 + 2 + 3, 10 + 2 + 3). You may assume that the input has already been validated. Show how you would test this function.

8. Given a array, find k increasing numbers whose summation will be maximum.

9. You are given an amount of work load k, which can be partitioned among m workers. Generate all the partitions.

10. A string S can contain just two symbols X and Y. The number of X symbols in S must be equal to the number of Y symbols. For each prefix of S, the number of X must be less than the number of Y.

What is the intepretation of the problem?

1.) Sort the schedules by their start dates (NLogN). For every end date now, find where does it lie w.r.t start dates(logN).

2.) Start filling the new array backwards, with the value of the current index depending on the next lowest value in the indexes which lie ahead.

i,e; ar_low[i] ar_low[j] + 1, where j is minimum such that a[j]i.

5.) Say there are a increasing sequences & b decreasing sequences. Reverse the b decreasing sequences. So, now we have a+b increasing sequences. Start merging them 2 at a time.

@oshin

1. Its almost correct, why dont you also specify (just for information sake) the criterion with which you divide clusters i.e. mark a cluster as end and start building another cluster.

2. I guess the solution is for qns. 3 than 2 ??

5. well, that is a very abstract answer. In this problem, the

exactsolution is very important. Idea is almost correct. But notice that you will have to merge n sorted listsin placewhich is a problem in its own 🙂5. how to merge n sorted lists inplace, i can merge them using extra space by making heap. but m not able to figure out inplace method. please help.