CareerCup

Gosh!!! Why don't you guys read the question properly.
If nobody knows anybody else other than the celebrity it becomes all the more easier.

If a doesnt know b (b defn is not the celeb)
and b doesnt know a (a defn is not the celeb)

Then a and b both aren't celebrities. You can always eliminate people. READ THE QUESTION CAREFULLY!

Gosh!!! Why don't you guys read the question properly.
If nobody knows anybody else other than the celebrity it becomes all the more easier.

If a doesnt know b (b defn is not the celeb)
and b doesnt know a (a defn is not the celeb)

Then a and b both aren't celebrities. You can always eliminate people. READ THE QUESTION CAREFULLY!

plz read the comments for the correct solution before posting your's..Not to be rude or anything, but im tired of having to explain time and over again how the solution is O(n) for absolutely all situations!

Use a hash table.
Iterate through every character in the string and insert into the hash table with key = character and value = count.

No re-iterate through the string checking the values in the hash table for each character. The first element with count = 1 should be your first non-repeated character.

// Assume you have an ASCII coded string
char first_non_rep(char* string, int length)

{
    static int hash_table[256];
    int i=0;
    
    for (i = 0;i<length;i++)
    {
        hash_table[string[i]]++;
    }

    for (i=0;i<length;i++)
    {
        if (hash_table[string[i]]==1)
            return string[i];
    }
    return '\0'
}

I think this is an overly complicated solution to a simple problem.

A lot of the details you've mentioned overlooks the coding complexity involved. Heres how:

1) Lets say Im making my graph, before I even start constructing the graph I(as a coder) need to all information about who knows whom. This information can get stored in a confusion matrix. So if I need to code this, I would have an extra memory requirement to store this information.

2) When you talk about iterating through the graph, you need to ensure that given a particular node, you should be able to reach every other node. What happens if no individual knows anybody else in the room other than the celebrity. How do you iterate through your graph then?

3) Considering directed graphs, you need to consider the possibility of having loops in them. If they do, you could easily end up in a typical infinite recursion scenario. Sure, you could maintain a visited flag variable for each node, but that again adds to your memory. Not asymptotically, but practically for small n.

4) If I give you this problem to solve in place, your graph method wont work.

5) My solution when implement in code, requires just one fuction bool knows(a,b) which simply returns true if a knows b and false otherwise. Your solution requires way more.

Your solution is valid, but you need to take the above points into consideration. As I said, this problem looks for an efficient algorithm, not your data structure manipulation skills.

Thanks.

Valid point santosh but you fail to understand the logic here. We are not looking at two people knowing each other, we are interested in knowing if one knows the other or not.(a knows b doesnt mean b knows a).

If a and be dont know each other, they both will eventually get eliminated. Try this out, trust me it works!

sure, because drawing graphs and finding the node with the maximum number of incoming nodes is what people do when a celebrity is in a room right!!!!

Ok heres the solution. SantiagoYMG is pretty close.
The solution is O(n) in time complexity.

Make all of them stand in a row.
Lets say the people are a,b,c,d,e,f,g,h,i,j,.......n

Compare a and b.
if a knows b => a is certainly not the celebrity. Probable celebrity = b
if a doesnt know b => b is certainly not the celebrity. Probable celebrity = a

In either case compare the probable celebrity to the next person in line ie 'c' and repeat the process. Each comparison should eliminate 1 person and have another as the probable celebrity. At the end, the probable celebrity who survives is the certain celebrity.

Complexity = O(n)

Guys this a pretty cool algorithmic problem. Give it a shot.

In the previous case char*c is a const char*. Lets say we change it to be char* const c, which makes it a constant pointer to a character. SO by definition you should now be able to change the value but you cant make c point to anything else right?
The below code doesnt print c either.
char* const c = "assa";
*c ="ghj";
printf("%s",c);

Also as far as I know, when you declare an array or a pointer to an array, it is basically a constant pointer to a int/char whatever. There's no reason why it shouldn't allow you to change the value being pointed to. This thing is driving me nuts. Can some explain please?