CareerCup

if two people are known by every other of the group, they must know each other.
use an int array of n, where n is the number of people in the party, (0 for a, 1 for b, etc), whenever a person is known, +1 for it, then finally find out the index with number n-1.
e.g for the above situation:
[4,4,4,0,0]
so the answer is 0,1,2, which is a,b,c

Had to go back to my algorithms book. This isn't a popular problem, but it's the Clique problem (en.wikipedia.org/wiki/Clique_problem)

It's relatively well-studied, and graphs are the data structure to use. Specifically, I'm pretty sure that this is the maximum clique problem.

So, once you have your graph constructed, you would want to look at the set of nodes, that are all interconnected with each other, that have the highest degree.

I'm not going to describe a solution, since it's well studied. You'd be better off reading about it at the Wiki page (and other places), and understanding the problem, than looking at code here.


Kind of a bogus question, IMHO, since the "answer" is considered to be a (nontrivial tenet of computer science. I think the interviewer was probably looking for your knowledge of the problem space, identification of the Computer Science problem, choosing the right data structure, and then starting to work out the problem.

This is a NP-Hard problem, so some big brains have worked on this.

We can create stack for each grup memeber , i,e a know b ,c then stack for a contains a,b,c ..like this we create for each member. Now common elementsof all the stack we take and it forms a group which is favourite.
i.e for A : A,B,C
for B : B,A,C
for C: C,A,B
for D : D,A,B,C
for E : E,A,B,C

So
A,B,C is the group
OR
We can using hashing here also i.e after creating stack count for A goes in hash table as 5 , for B 5 etc ....take peope which has highest counts as popular group

We can create stack for each grup memeber , i,e a know b ,c then stack for a contains a,b,c ..like this we create for each member. Now common elementsof all the stack we take and it forms a group which is favourite.
i.e for A : A,B,C
for B : B,A,C
for C: C,A,B
for D : D,A,B,C
for E : E,A,B,C

So
A,B,C is the group
OR
We can using hashing here also i.e after creating stack count for A goes in hash table as 5 , for B 5 etc ....take peope which has highest counts as popular group

/*given class (my assumption)*/
class People{
  List<People> peopleIKnow;
  List<People> getPeopleIKnow();
}


/*my proposed DataStructure*/
HashMap<People, Integer>


algo
------

List<People> getFavoriteGroup(List<People> peoples){
  HashMap<People, Integer> map = new HashMap<People, Integer>();
  List<People> favoriteGroup = new List<People>();
  for(People p: peoples)
    map.put(p,0);

  for(People p: peoples){
    for(Peoples m: p.getPeopleIKnow()){
       map.put(m, (map.get(m)+1) );
    }
  }

  for(People p: map.keySet() )
     if(map.get(p) == peoples.length )
	favoriteGroup.add(p);

  return favoriteGroup;
}

#include<stdio.h>
#include<conio.h>

int main()
{
int n,i,j,m[10][10],count[10],f[10],c=0,z=0;
printf("Enter no. of persons: ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("Does Mr. %d know Mr. %d? ",i,j);
scanf("%d",&m[i][j]);
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("%d\t",m[i][j]);
}
printf("\n");
}

for(j=0;j<n;j++)
{
i=0;
c=0;
while(i<n)
{
if((m[i][j]==1))
{
i++;
c++;
}
else
break;
}
if(c==n)
{
f[z]=j;
z++;
}
}

for(i=0;i<z;i++)
{
printf("Mr. %d is celebrity\n",f[i]);
}
getch();
return 0;
}

Finding connected components in a graph, perhaps?

Relationships => This is a graph problem.
Represent persons with nodes.
Represent relations with edges.
Store graph as adjacency matrix/list

for all nodes in graph:
compute degree of the node (that is, number of edges on it, un-directional)

This will output the "person" who knows max persons (perhaps the host of the party ;))
BUT not the "group" of persons... (sub-graph).... Conceivably a similar algorithm that creates "cover" over more than one nodes can solve the problem... Perhaps O(nodes^2) complexity.

Keep array [5] and store count of people knowing each of them. if no one knows a person, count=1 as each person knows self.

find the max value in array, max_fav <= count of people

traverse through array and see when count == max_fav, put person is fav group.

Keep array [5] and store count of people knowing each of them. if no one knows a person, count=1 as each person knows self.

find the max value in array, max_fav <= count of people

traverse through array and see when count == max_fav, put person is fav group.

a directed graph.

(u,v) \in E iff u knows v.

then, simply count the edges incoming to each v.

whenever this count for a v is equal to |V|-1, add it to the result set.

Suppose we have a matrix
A B C D E
A 1 1 1 0 0
B 1 1 1 0 0
C 1 1 1 0 0
D 1 1 1 1 0
E 1 1 1 0 1

Here Mat[x][y]=1, represents x knows y. So, the vertical column of A, B and C, has all 1's so they are a favourite group. Instead of matrix we can represent this vertical columns by bitsets.

If a new person is added to the party simple, simply add his knowings to this bitset and compute the cardinality. If the cardinality is equal to the total no. of people in the party then this person is in favourite group.

Just check which of the nodes have indegree |V|-1

Just check which of the nodes have indegree |V|-1

#In JAVA

take a hashmap map<string,list>
Take everyone in the party to be the key and those who know them store in list.
Then find size of each list corresponding to every person. Club those people together who have size of list as (n-1). They are the most famous group.

adjacency matrix