CareerCup

1)
here is how it can be done

int count=0;
char *winner="none";
char *curName="";
while(curName=readNextNameFromFile()!=EOF){
  count++;
  int random=getRandom(1,count) // in the range of 1 .. count
  if(random == count) winner=curName;
}

the idea is, at every new name read, pick either current winner or new name as winner, with probabilities in proportion to (n-1/n):1/n

this will ensure that all the names read till count = n will have equal chance (1/count) of getting picked as winner.

2) i would go for HashSet.

3) XOR would be fastest.

don quite agree with the first. This alogrithm may generate no winners at all.

count=1;
while(end of the file)
{
//get one record at a time
if((random(count)+1 == count))winner = current record;
count++;
}

For third, can we go for...
Compare first 3 numbers, see which is occuring 3 or 2 times.
If one number is occuring 2 times, other number is the one.
Else if all 3 numbers are same, scan through array to find a number different than the current one.
Worst time complexity is O(n) and average case is O(n/2) and best case is O(1).