CareerCup

If we make the assumption about there is always one and only one celebrity in the group,

c = -1; // celebrity index
   for i in 0..n-1
     if c == -1
       c = 0
     else 
       if knows(a[c], a[i]) && !knows(a[i], a[c])
         c = i

Its almost like finding the max from a list, by assuming the first element as the max and as you are iterating updating the current max.

In the end we need to verify if the celebrity even exists or not. (Consider a scenario where no-one knows each other). If it does not exist, return -1.

public int findCelebrity() {
		int celebrity = 0;
		for (int i = 1;  i < N; i++) {
			if (knows(celebrity, i)) {
				celebrity = i;
			}
			else if (knows(i, celebrity)) {
				// No need to do anything here.
			}
			else if (i + 1 < N) {
				// None of them are celebrity, lets select a new one.
				celebrity = i + 1;
				i++; // Increment the counter as none of these two are celebrity.
			}
		}
		boolean noCelebrity = false;
		// We need to confirm if the celebrity is correct or not.
		for (int i = 0; i < N; i++) {
			if (!knows(i, celebrity) || (i != celebrity && knows(celebrity, i))) {
				noCelebrity = true;
			}
		}
		if (noCelebrity) {
			return -1;
		}
		return celebrity;
	}

That is a classic problem. If A knows B, we can eliminate A, otherwise we can eliminate B. We can eliminate one person after each time we call knows(i, j), so it will take O(n) to find the celebrity.

if A doesn't know B how do you eliminate B?

//Assumed that there is only one celebrity in the group
Person function FindTheCeleb(List<Person> persons)
{
    Stack stk = new Stack(persons);
    Person theCeleb = new Person();
    
    theCeleb = stk.pop();
    while(stk.size)
    {
        Person tmpPerson;
        tmpPerson = stk.peek();
        if(knows(theCeleb, tmpPerson) || !knows(tmpPerson, theCeleb))
        {
            theCeleb = stk.pop(); //The new celeb is the tmpPerson(the next person in the stack)
        }
        else
        {
            stk.pop();
        }
    }
    
    return theCeleb;
}

I believe this can be solved using graphs.
Lets say we have N nodes in directed graph. Each node represents a person. If a node sees only incoming edges, then its a celebrity. If a node sees both incoming and outgoing, then its a normal person. For the sake of simplicity, we wont draw self edges (to convey that a person knows himself and since its same for all). Thus we would need to traverse all node edges (Adjacency list) once to find out number of celebrities in the event. This would be O(n).

I am new to this topic. Please suggest if the solution above seems doable.

my 2 cents.
lets model the problem as a adjacency matrix one.
lets define int arr[][] and for each arr[i][j] is 1 <=> i knows j.

so we acutally need to find 2 thing:
1. all of the k rows that follow this rule: (arr[k][i]==0 iff k!=i) for (0<=i<=arr.length)
2. all of the m colums that follow this rule: (arr[i][m]==1) for (0<=i<=arr.length)

the 1's rule checks if the person k doesn't know no one else but himself.
the 2's rule checks if all the other person know who person m is.

we need to find k such as (k==m), meaning both of the conditions are followed.

for i.e. this is a matrix that has person with index 3 (starting from 0) as a celebrity:

1 0 0 1 1
1 1 1 1 1
0 0 1 1 0
0 0 0 1 0
0 0 0 1 1

note that there can be no more than one k and no more the one m.

we can travel in a manhattan distance path from the first line until we encouter the last line or column of the matrix fo find the celebrity (we are actully finding k which is unique and can only be equal to m).

1-0-0 1 1
1 1 1 1 1
0 0 1 1 0
0 0 0-1-0
0 0 0 1 1

and the code:

package findCelebs;

import java.util.HashSet;
import java.util.Set;

public class FindCelebrity {
	static int knows[][];

	public static void main(String[] args) {
		knows = new int[][] { 
				{ 1, 0, 1, 1, 1 }, 
				{ 1, 1, 1, 1, 1 },
				{ 0, 0, 1, 1, 0 }, 
				{ 0, 0, 0, 1, 0 }, 
				{ 0, 0, 0, 0, 1 } };
		
		Set<Integer> people = new HashSet<Integer>();

		for (int i = 0; i < 5; i++) {
			people.add(i);
		}

		System.out.println(findCelebrity(people));
	}

	public static int findCelebrity(Set<Integer> group) {
		return isCelebrity(group, 0);
	}

	public static int isCelebrity(Set<Integer> group, int personInKRow) {
		if (personInKRow >= group.size()) {
			return -1;
		}

		// a celebrity must knows himself
		if (!knows(personInKRow, personInKRow)) {
			// so check the next person in line
			return isCelebrity(group, personInKRow + 1);

		}
		for (int j = personInKRow + 1; j < group.size(); j++) {

			if (knows(personInKRow, j)) {
				// personInKRow is not the celebrity - knows some one else but
				// himslef
				// so check the person in line j
				return isCelebrity(group, j);
			} else {
				// personInKRow does not know j -j is not the celebrity
			}
		}
		return personInKRow;
	}

	private static boolean knows(int i, int j) {
		return (knows[i][j] == 1);
	}
}

string FindCelebrity(vector<string> persons)
{
	if (persons.empty())
	{
		return NULL;
	}

	if (persons.size() == 1)
	{
		return persons[0];
	}

	// First find the person that might be a celebrity because he doen't know anyone else
	string celebrity = persons[0];
	for (int i = 1; i < persons.size() - 1; i++)
	{
		if (Knows(celebrity, persons[i]))
		{
			celebrity = persons[i];
		}
	}

	// Now we can check if the candidate is known by everyone else
	for (int i = 0; i < persons.size() - 1; i++)
	{
		if (!Knows(persons[i], celebrity))
		{
			return NULL;
		}
	}

	return celebrity;
}

In this problem, there will either be only one celebrity or no celebrity.

Now iterate over list of people picking two at a time say A & B. Check function knows(A,B). If A knows B, then eliminate A (as it knows someone else, so not a celebrity) and pick next person C. If A does not know B, then eliminate B (as celebrity should be known by all) and pick next person C. This will be O(n) and at the end only one person will remain (as we are eliminating one at each step) say P.

Now either this person is celebrity or none is celebrity. So again iterate over all elements picking each element once (say E) and check knows(P,E) & knows(E,P). If any of the E returns knows(P,E) as true or knows(E,P) as false, then return no celebrity found. Else return P as celebrity.

This will take O(3n) steps ie. O(n).

Based on the henrywang's suggested solution I implemented this quickly. Ideally you would want to use a set implementation that can return n distinct objects randomly but efficiently. Here I'm converting the set to an array each time and taking the first two objects. This might be efficient in a Ruby set, not sure.

require 'set'

def knows(i, j)
  #
end

def celebrity(set)
  while set.length > 1
    # ideally use a set that can
    # return any two distinct objects
    array = set.to_a
    a = array[i]
    b = array[i + 1]
    
    if knows(a, b)
      set.delete(a)
    else
      set.delete(b)
    end
  end
  
  set.to_a[0]
end

Go implementation

package main 
import "fmt" 

func main() {
	arr := []string {
		"Selena",
		"Miley",
		"Justin",
		"Katy",
		"Taylor",
	}

	findCelebrity(arr)
}

func findCelebrity(arr []string) {
	index := 0
	for i := 1; i < len(arr); i++ {
		if knows(index, i) || !knows(i, index) {
			index = i
		}
	}

	for i := 0; i < index; i++ {
		if knows(index, i) || !knows(i, index) {
			fmt.Println("No celebrity found")
			return
		}
	}

	fmt.Println(arr[index], "is the celebrity")
}

func knows(a, b int) bool {
	arr := [][]uint8{
		{ 1, 0, 1, 1, 0 },
		{ 1, 1, 0, 1, 0 },
		{ 0, 0, 1, 1, 0 },
		{ 0, 0, 0, 1, 0 },
		{ 1, 0, 0, 1, 1 },
	}

	return arr[a][b] > 0
}

public static Person FindCelebrity(IEnumerable<Person> P)
{
	if(P == null) return null;
	
	// Creating a working list
	P = new List<Person>(P);
	int pos = 0;
	while(P.Count > 1)
	{
		int p1 = pos;
		int p2 = pos + 1;
		bool p1kp2 = Knows(P[p1], P[p2]);
		bool p2kp1 = knows(P[p2], P[p1]);

		if(p1kp2 && !p2kp1)
		{
			P.Remove(p2);
		}
		else if(!p1kp2 && p2kp1)
		{
			P.Remove(p1);

			if(pos != 0)
				pos--;
		}
		else if(p1kp2 && p1kp2)
		{
			P.Remove(p2);
			P.Remove(p1);
		}
		else
		{
			pos++;
		}
	}
	
	// There is no celebrity
	if(P.Count == 0)
		return null;

	return P[0];
}

By the requirement, Celeb is someone who only knows himself.

Thus solution can be very simple:

for(i = 1 to n)
if (knows(i,i))
return celeb;

Thats it.

From the given info:

Celeb is someone who only knows himself, everyone else knows the celeb.

So here, we find someone who only knows himself, rather than finding someone whom everyone knows.

for (i = 1 to n)
	if (knows(i,i)==true)
		return (i is celeb);

import groovy.transform.EqualsAndHashCode

/**
Given a set of n people, find the celebrity.
Celebrity is a person who:
1. Knows only himself and no one else
2. Every one else knows this person

You are given the following helper function:
bool knows(i, j);
Returns:
True: If i knows j
False: otherwise

I proposed the O(n2) algorithm at first but he wanted me to improve on it. He wanted an O(n) algorithm

Ex: A->B->C
A->C<-D

A->C means A knows C
C<-A means C is Known for A
C is celebrity

* Created by Felipe on 21/03/2015.
*/

class Celebrity {

    static class Person {
        private String name
        List<Person> knows = new ArrayList<>()
        List<Person> isknown = new ArrayList<>()

        // the ideal would be a structure that was a list and set together
        //private static Set<Person> friendsSet = new TreeSet<Person>([compare:{a,b->  b.knows.size() <=> a.knows.size() }] as Comparator)
        private static Set<Person> friendsSet = new LinkedHashSet<Person>()
        private static List<Person> friendsList = new ArrayList<>()

        Person know(Person p) {
            knows << p
            p.isknown << this
            addFriends(p)
            addFriends(this)
            p
        }

        Person isKnown(Person p) {
            isknown  << p
            p.knows << this
            addFriends(p)
            addFriends(this)
            p
        }

        private void addFriends(Person p) {
            if (friendsSet.add( p )) {
                friendsList.add( p )
            }
        }

        boolean knows(i, j) {
            if (i>=0 && j>=0 && i < friendsSet.size() && j < friendsList.get(i).knows.size()) {
                friendsList.get(i).knows.get(j) != null
            }
            false
        }

        Person findCelebrity() {

            // with java 7 using the TimSort Average case performance  O(n log n)
            //def cmp =  [compare:{a,b->  b.knows.size() <=> a.knows.size() }] as Comparator
            friendsSet = friendsSet.sort {a,b->  a.knows.size() <=> b.knows.size() }

            friendsSet.find { Person p ->
                // Every one else knows this person
                (p.isknown.size() == friendsSet.size() -1) && (p.knows.size() == 0) //Knows only himself and no one else
            }

        }
    }

    static void main (String[] args) {
        def personA = new Person(name: "a")
        def personC = new Person(name: "c")
        def a = personA
                    .know(new Person(name:"b"))
                    .know(personC)
                    .isKnown(new Person(name:"d"))
        personA.know(personC)

        println "Celebrity is Person ${personA.findCelebrity()?.name}"

    }
}

seeing the problem , i am not sure whether we have to find only one celebrity or there exist more than one. but in any case, the simpler means is the true value return for knows(i,i) ...as celebrity only has self loop. i am thinking interviewer was not iterated in knowing data structure skill but simple common sense or how well we try understanding the question.

When i see the problem i thought this as a graph and with the assumption that there is only one celebrity , in that case the graph Vertex whose adjust size is n-1 is the celebrity.

Here is C++ version of solution.
DFS was used to search the relationship.

Running complexity is O(N) based on the assumption that there isn't anyone knows nobody.

#include <iostream>
using namespace std;

bool relation[5][5];


bool knows(int knower, int knowee)
{
	return relation[knower][knowee];
}

void dfs(int * visited, int pos, int len)
{
	for (int i = 0; i<len; i++)
	{
		if (pos != i && visited[i] !=1)
		{
			if (knows(pos, i))
			{
				visited[pos] = 1;
				dfs(visited, i, len);
			}
		}
	}
}
int find_celebrity(int len)
{
	int * visited = new int[len];

	for (int i = 0; i <len; i++)
	{
		visited[i] = 0;
	}

	for (int i = 0; i < len; i++)
	{ 
		if (visited[i] != 1)
			dfs(visited, i, len);
	}

	for (int i= 0; i<len; i++)
	{
		if (visited[i] ==0)
			return i;
	}
	return -1;
}



int main()
{
	relation[0][1]= true;
	relation[0][4] = true;
	relation[1][4] = true;
	relation[2][1] = true;
	relation[2][4] = true;
	relation[3][2]  = true;
	relation[3][4] = true;

	int pos = find_celebrity(5);
	cout << "celebrity is = " << pos <<endl;
}

This is like finding a sink in a directed acyclic graph which is O(n)

We can use union-find to find the highest ranking candidate, and use union find to create disjoint set, the node in the union-set doesnt know anyone, but everyone knows the root node.

This is impossible to solve it in O(n). Assume everyone is celebrity, i.e., nobody knows any one. In that case, you have to make (n-1)*(n-1) comparison, this is O(n^2) complexity. This is the worse case. The best case would be
- 1 knows 2, eliminate 1
- 2 knows 3, eliminate 2
- (n-1) knows n, eliminate (n-1)

this is the only corner case that would result in O(n). Otherwise, it will be between O(n) to O(n^2), thus O(n^2).