CareerCup

This is the "Reservoir Sampling" problem. There is an explanation of it here:
code-slim-jim.blogspot.com/2010/06/reservoir-sampling.html

That's correct! But you should implement something like this using the linked list instead of array as the base elements. Anyway, this won't be so hard.
0. verify if k < N, if not, exit would be a solution. :)
1. create a array of size k and copy the first k elements.
2. while(list not ended) // I don't know N but I know that the list has an end
get a random index from 0 to k - 1;
move current node index positions;
replace the array[index] with the new value from current node.

Hi... Just think u r given a doubly linklist

function::
for(i=0;i<k;i++)
{

}

Hi... Just think u r given a doubly linklist

function::
ll=head;
for(i=0;i<k;i++)
{
cnt = rand();
cnt = cnt % k;
j=0;
while(j<cnt)
{
if(ll->next != NULL)
{
ll=ll->next;
}
else
ll=ll->prev;
}
arr[i]=ll->value;
}


Every time this function will give you a new set of random nos from linklist :)

what if it is a singly linked list

Even in singly linked list, use while loop k(incremented starting from zero each time) time. Always choose node position at random place starting from head. Check for tail.

C# version

Node f(Node list)
{
  if(list==null) return null;
  Node p = list;
  int i=0;
  while(true)  
  {
    if(p.next==null)
    {
      return p;
    }

    Random rand = new Random(0,1);
    if(rand.next()<1/(i+1))
    {
      return p;
    }    
    else
    {
      p=p.next;
      i++;
    }
  }
}

vector<int> random(ListNode* head, int k)
{
      vector<int> ans(k);
      while (k-- && head) {
            ans.push_back(head->val);
            head = head->next;
      }
      int i = k, j ;
      while (head) {
              j = rand() % (i+1);
              if (j < k)
                      ans[j] = head->val;
              i++;
      }
      return ans;
       
      
}

@S
Step 1 second half part is not correct. It says any K random numbers. So why are you copying 'first' K numbers from the list to array?

What is if the random number does not occur in first K elements of the list?