# Interview Questions 21

December 26, 2010 13 Comments

1. You are given 2 arrays A, B sorted in decreasing order of size m and n respectively and a number k, such that 1 <= k <= m*n. You need to fine the kth largest sum(a+b) possible where a in A, and b in B.

2. Store 100 million phone numbers, with minimal memory space. Search must be efficient.

3. [Pure Math] You have a set of ants moving on an horizontal segment of length n. Each ant can randomly move either right or left. When an ant takes a direction, she stays in that direction until she either drops out of the segment or it bumps with another ant. In this case, the ant changes her direction. Can you formalize the system and describe what will happen after t iterations?

4. Given an unsorted array arr[0..n-1] of size n, find the minimum length subarray arr[s..e] such that sorting this subarray makes the whole array sorted.

5. Given n distinct elements, how many Young tableaus can you make?

Hi Avi,

Solution for the

problem 1:#include

int k_sum(int A[],int B[],int m,int n,int k){

int indexA = 1;

int indexB = 1;

int i,s1,s2,sA=0,sB=0;

int maxsum = A[0] + B[0];

for(i=0;i= s2){

if(indexB == n-1){

indexB = sB + 1;

++sA;

}

else{

++indexB;

}

maxsum = s1;

}

else{

if(indexA == m-1){

indexA = sA + 1;

++sB;

}

else{

++indexA;

}

maxsum = s2;

}

}

return maxsum;

}

int main(){

int A[5]= {12,9,7,5,2};

int B[6] = {16,15,14,12,8,6};

printf("%d \n",k_sum(A,B,5,6,1));

return 0;

}

Complexity:

O(m*n)printf("Test statement");

Finally, i got how to print souce code 🙂

Code for problem 1:

@aswini can u write the logic of the program ?

reply asap , will appreciate your help ??

Thanks In Advance

This is obviously wrong!

2 trie tree

@divya .. there is a lot more to it than just a trie

radix tree ( compressed trie tree) or ternary search tree will take lesser space..

@divya

what will you compress the trie at? How will the compression save you space? How would the search complexity increase by compressing? What is your search complexity anyways ? Did you even

observe/utilizethe fact that you are asked to storephone numbers? How is this different from a pure dictionary storage?well compressing will reduce space complexity. as in case of trie every node will be having a pointer to ten other nodes (as their are 10 digits) but since there can be cases like their are nos 9898111111, 9898122222, 9898211111, etc ie all nos are starting from 9898 so instead of making a node which has 9 as info and has 10 pointers of which 9 are pointing to null and a single one to a node containing 8 and 9 null pointers and a pointer to 9 and so on.. we can compress the trie so that if there are nodes which point to a single node then we caqn compress them such that we make a new node with 9898 in it and this node now has 10 poitners to all 10 digits.. this will save space and not search complexity..

and my search complexity is the length of numbers..

is there any other approach?

when u give a solution be

preciseabout it. Compressing is a standard technique u shud point out toyouroptimizations. eg. u can use a bit array of size 10 at all levels of trie rather than an integer/char array. etc.there might be a better solution, will think and update the thread.

5.

a(n) = a(n-1) + (n-1)a(n-2)