CareerCup

one approach is using modified heap data structure .
1> the node will contain three information server no, index of list and value.
2> first i will create the min heap of first element of all M sorted list.
3> Now we can get the minimum element from the top of heap than extract the next item from the server which belong to deleted item.
4> for finding the k'th smallest we need to follow the 3'rd step K times.

We need get next number from those server that give min current element while don't gathering K smallest numbers. For select min number we can use min-heap datastructure size of O(M).

1. Get one number for every server and insert those numbers and server names of every numbers in min-heap.
2. From 1 to K
    2.1. remove top(smallest) item in min-heap. 
    2.2. get new number from that server whose item was removed.
    2.3. insert new item into min-heap.
3. The top of min-heap is kth smallest element.

There are M server with each is having sorted list of N number.
consider 2-D array of size S[M][N] (m= server Id, N= number of elements)
and consider 1-D array sid[M] to maintain list index and initialized to 0.

void findKthMin( int S[][], int sid[])
{
min = INT_MAX;
int j = 0;
while ( j < k) {
for( int i = 0 ; i< M ; i++) {
if (min > S[i][sid[i]] ) {
min = S[i][sid[i]];
sid[i] = sid[i]+1;

}
if (j < k)
min = INT_MAX;
j++;
}
}

return min;
}

Let say M = 3
startindex and endindex of each server { s1 s2 s3 } and { e1 e2 e3 }
for first server find the Median..it will tell u position and value let say position is x and value is v
now for remaining M-1 servers find position of a number just smaller of val v
let say those are y and z from second and third server.

if (x + y + z < k) modify end index for all servers
if (x + y + z > k) modify start index for all servers
if (x + y + z == K) choice is between values at y and z postions

all this is running at client side.

can there be repetition of elements in and across the server

int ReturnKthSmallestNo(int servers, int listSize, int k)
{    
    int[] numbers = new numbers[k];
    int index = 0;
    // create an initial list of k numbers starting from the first number of each array
    for(int i=0;i<k;i++)
    {
        for(int j=0; j<servers; j++)
        {
            int num = GetNumberFromServer(j , i);     // an API which returns ith number from jth server
            numbers[index++] = num;
            if(index==k) // k might be smaller or greater than server size
                break;
        }
    }

    CreateHeap(ref numbers, k); // Create a MAX-HEAP of the first k values
    
   // a boolean array to determine if we would want to search the server for values
    bool[] serverDone = new bool[servers];
    // set all the values to false;    
    
    for (int j = i; j< listSize ; j++ ) // loop for the entire list of numbers
    {
        for(int m = 0; m< servers; m++)        
        {
            if(!serverDone[m]) // if the smallest element in the list on the server is not greater than root of heap
            {
                int num = GetNumberFromServer(m, j);  // Assumption of an API
                if(num < numbers[0])  // the incoming element is smaller than the kth smallest element in the heap
                {
                    numbers[0] = num;
                    Heapify(ref numbers,0);  // heapify from the root
                }
                else // the smallest element in the list is larger than kth smallest element in the heap, no need to check this list further
                {
                    serverDone[m] = true;
                }                
            
            }
        
        }
        
    }
    
    
    return numbers[0];
    
}