Interview Questions 21

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?

Advertisements

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

13 Responses to Interview Questions 21

  1. Ashwani Sindhu says:

    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)

  2. Ashwani Sindhu says:


    printf("Test statement");

  3. Ashwani Sindhu says:
    printf("Test statement");
    
  4. Ashwani Sindhu says:

    Finally, i got how to print souce code 🙂
    Code for problem 1:

    
    #include<stdio.h>
    
    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<k-1;i++)
    	{
    		s1 = A[sA] + B[indexB];
    		s2 = A[indexA] + B[sB];
    
    		if(s1 >= 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};
    	int j;
    	for(j=1;j<=30;j++){
    	printf("%d \n",k_sum(A,B,5,6,j));
    	} 
    	return 0;
    }
    
    
  5. Divya says:

    2 trie tree

  6. Avi Dullu says:

    @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/utilize the fact that you are asked to store phone numbers ? How is this different from a pure dictionary storage?

    • Divya says:

      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?

      • Avi Dullu says:

        when u give a solution be precise about it. Compressing is a standard technique u shud point out to your optimizations. 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.

  7. Prateek Caire says:

    5.

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: