# Interview Question 14

September 5, 2010 9 Comments

1. Given a line segment of length n. You need to cut it into m pieces specified by position[n] array. The price of cutting a segment of length len in two parts is always len (irrespective of cut position). Give a dynamic programming solution to minimize the cost of cutting.

2. Given a BST, print all the values >=vmin and <=vmax. Time complexity should be better than O(n). O(logn + (vmax-vmin)) in worst case.

No parent pointers are available.

3. You have a huge graph of cities and cost of flight between them. Find the cheapest path from A to B. **The graph doesn’t fit in memory**.

4. Write a function

int count_div(int a,int b,int k);

That given three integer numbers a, b and k return number of integers from range [a..b] divisible by k, i.e.:

For example, for a=6, b=11, and k=2, your function should return 3, because there are 3 numbers divisible by 2 in the range [6..11], namely 6, 8 and 10.

You can assume that , and k>0.

5. Given is an array of integers. Element is called an extreme if no other element’s value is more distant from the average. Write a function

int extreme(int[] A);

That given an array of integers returns the index of an extreme (any one of them if there are many).

If no extreme exists, the function should return -1.

A[0]=9, A[1]=4, A[2]=-3, A[3]=-10

the index of an extreme is 3, because the average of the array is

(9 + 4 + (-3) + (-10)) / 4 = 0

and in this array no value is further from 0 than -10

6. Say you need to design a web application which needs to support friends of friends function(like in linked in, when you search a person, it will show you if this person is linked with you, your connection or your connections’ conection…), we expect to have millions of users and each user may have thousands of friends, how would you design/implement this function to make it scalable.

7. Given two n digit prime numbers, change the first number to the second by changing one digit at a time. The resulting intermediate numbers should also be prime.

8. Given an input array of integers of size n, and a query array of integers of size k, find the smallest window of input array that contains all the elements of query array and also in the same order.

9. There is an array

A[N][M] =

1 2 3

4 5 6

The array is rotated so that

A'[M][N] =

3 6

2 5

1 4

is obtained.

Establish the relation between A and A’ by using i, j, M, N

A[i][j] = A'[_][_]

10. Given a list of strings say N, how would you write a perfect hash function and ensure 0 collissions?

8. Isn’t this like string search? Rabin Karp or KMP or Boyre-Moore would do.

No, its not.

How is it different then? Can you please explain?

Main string: aadebdcbdacbggcde

Query string: abc

Can you tell me the solution window for this? And how could Rabin Karp find it out?

8. *And also in the same order* – This is what your question states. I assume this means something like a substring search. Creating a proper hash function with a base of 26 (or 36 if you consider alphanumeric characters), will yield the proper result.

There is no window in the string that you have given.

No, it is not a

substringsearch...in the same orderimplies that the window should have all the characters of the given string in the same orderBUTmay have some other characters in middle too.Also the solution window of the above problem is

acbggcbecause it hasabcin order i.e. a followed by b followed by c and it is the smallest window of this nature.Hope you understand the problem now ?

okkk … got it .. 🙂 … you had posted a similar problem and solution in your previous blog.

Thnx for the explanation though.

ya .. that question is slightly different from this one hence the solution too 🙂

Hi,

for question 1, I have the basic recursive solution. But I am not getting the dynamic programming solution. Can you give some hints ?

int min_cost(int a[],int start,int end,int ps,int pe)

{

int sum=INT_MAX,temp=0;

int seg_len = end-start,k;

if(ps > pe){

return 0;

}

if(ps==pe && (a[ps]==start || a[ps]==end))

{

return 0;

}

for(k=ps;k<=pe;k++)

{

// choose a[k] as partition point

if(end==a[k])

continue;

temp = seg_len + min_cost(a,start,a[k],ps,k) + min_cost(a,a[k],end,k+1,pe);

if(temp < sum)

{

sum = temp ;

}

}

return sum;

}