Interview Question 14

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?


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

9 Responses to Interview Question 14

  1. Amar says:

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

  2. Amar says:

    How is it different then? Can you please explain?

  3. Amar says:

    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.

    • Avi Dullu says:

      No, it is not a substring search. the same order implies that the window should have all the characters of the given string in the same order BUT may have some other characters in middle too.
      Also the solution window of the above problem is acbggc because it has abc in 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 ?

  4. Amar says:

    okkk … got it .. 🙂 … you had posted a similar problem and solution in your previous blog.
    Thnx for the explanation though.

  5. guest says:

    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;
    // choose a[k] as partition point
    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;

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s

%d bloggers like this: