Background

This is the most interesting puzzle I've seen till date and It was asked in campus interview of NIT Kurukshetra by Microsoft India Development Center. Luckily my friend could solve it and get into Microsoft.

Problem Definition

There are 5 Racing Tracks in a Ranch and you are given 25 horses. You have to find 3 fastest horses (considering there is no tie between any two horses) by conducting minimum number of races.

Solution:

This problem has interesting solution because to reach to the conclusion of this problem you only have to solve it to few steps and then analyzing the data from those steps you can easily come to conclusion. Let us discuss how to do so.

Divide 25 horses in five groups (A, B, C, D, E) with 5 Horses each. Now conduct the races of 5 Groups.

Number of Races Till Now: 5

After this you can arrange the top three horses from all the groups in following order

A - A1 A2 A3
B - B1 B2 B3
C - C1 C2 C3
D - D1 D2 D3
E - E1 E2 E3

Let us conduct a race among all the winners of a group i.e. A1, B1, C1, D1, E1

Number of Races Till Now: 6

Now sort the groups (A-E) from second table such that winner's group is placed first. For explanation let us assume that C1 is winner of 6th race with E1 as second winner and B1 as third, A1 fourth and D1 fifth.

Arrange the horses like this

C - C1 C2 C3
E - E1 E2 E3
B - B1 B2 B3
A - A1 A2 A3
D - D1 D2 D3

Now let us analyze these results to find three fastest horses.

1. Without doubt C1 is the fastest (Right? It has won from C2, C3 as well as A1, B1, D1, E1)
2. Second Fastest is Either E1 or C2 (Because all other are slower than these two. Agreed?)
3. Third Fastest will be among C2, C3, E1, E2, B1 (Why not E3?? It has two winners from it- E1, E2 so it can be at the max fourth.)

So we need to conduct a final race amond - C2, C3, E1, E2, B1 to determine second and third winner.

Number of Races Till Now (And Finally): 7 is the answer!!

For more such problems simply visit http://CodeBoat.blogspot.com
If you have any query/question or feedback. Feel free to send them over to codeboat@gmail.com

Background
This is a question which usually gets asked in many programming interviews. One of my friends was asked this question in his Microsoft Interview and he answered it. Here is his experience in my words.
Tip!! When you face such question in interview, never hesitate to mention the solution that seems obvious to you.

Obvious Solution
Starting with first character of string, keep comparing this with all other characters in the string unless you find a non-repetitive one. But tell your interviewer that it is most trivial and Although you can optimize this solution by either comparing a character with the characters to the right of it, because this way you are removing redundant comparisons. But in both the cases, worst case complexity is going to be O(n^2). So tell your interviewer that you are looking for a better solution.

Maintaining a Count Array
A good solution may be if we can have an array which maintains count for number of times a character appears in the string and this array can be filled in O(n) by going once through the string. And once we are done with it, we can again parse whole string and find the first character that has count 1. Wow!!! This one requires two passes through whole string so it will take 2n time. Which is obviously O(n). If your interviewer is impressed with this approach then proceed further with the implementation of the algorithm.

int charCount[128];

char firstNonRepeatingChar(const char* string)
{
  int i=0;

  //Keep count
  while(string[i]!='\0')
  {
      charCount[string[i]] += 1;
      i++;
  }

  i=0;

  //Find Character
  while(string[i]!='\0')
  {
      if(charCount[string[i]] == 1)
          return string[i];
      i++;
  }

  return '-'; 
}

Special Note: Ask interviewer what does he want if all characters are repeated? In my case, interviewer told me, your function should return '-' in that case as they don't expect '-' to be one of the characters in the string.
But this is not where a tough interviewer will stop. Why??
Extra Space: Because you are using an array to store count of characters which will be of size 128 as there are 128 ASCII characters but if you are dealing with Unicode then this length will be 65536.
Optimize: Interviewer may ask you if you can make it n from 2n?