CareerCup

>> Either way, one person is always eliminated.

if both know each other or they don't know each other, then both of them need to be eliminated.

See my argument above that precisely captures all the cases.

>> After asking n - 1 such questions, only one person will remain.

You actually need to ask 2n-2 questions. Also, there is no guarantee than only one person will remain. It can also be the case that no person remains in the end if there is no mayor. Again, see my argument above for precise details.

Your approach seems overcomplicated. Maybe we understand the problem differently?

Can you tell me what you think is wrong with my argument? I've given a precise argument why exactly one person will be eliminated with every question. To recap:

If A knows B, A cannot be the mayor, since the mayor knows no one.
If A doesn't know B, B cannot be the mayor, since everyone knows the mayor.
Therefore, we can always eliminate one person with every question.
We start with N people.
Therefore, once we ask N-1 questions, we'll be down to a single person.
If there exists a mayor, that person must by necessity be the mayor. If there is not a mayor, then we may have returned a bogus answer. Hence the validation step that I mention.

Yes, eugene.yarovoi is precise.

@Eugene

Yeah, your approach is correct and elegant. The solution does not need the verbosity I gave. I could have refined my elimination step to disregard one person at a time as a Mayor instead of bothering about two. That also reduces the number of questions to be asked. The final validation step is necessary as I too see it. Great answer!

Mayor is the sink node in topological sort of the graph.

@Varun: building the graph would involve O(n^2) API calls. Hence the use of the method I gave, which uses only O(n) calls.

sd that looks interesting, maybe you can explain it better
you said:

0
of 0 vote

Provided a 2*2 matrix is given as input, the below should take O(n+m).

How can it be O(n+m) ?

Building an adjacency matrix is n^2, even if you only set a few 1's in it. Who is going to 0 initialize your RAM locations for you?
1) interpreter/VM/JVM -> it will have to zero initialize the object
OR
2) If it's a compiled language, and your array is static in duration, the runtime code that loads your program will have to 0 initialize.
OR
3) If it's a compiled language and your array is off the heap or the stack, you have to 0 initialie it yourself

So it's O(n^2) to build the thing. And imagine a town with 1 million people, the array will require ~ c*10^12 bytes of memory

You are right. That's the reason I mentioned if the input itself is in form of adjacency matrix, then this can be done in O(n+m) time complexity.

n sorry I meant n*n matrix and not 2*2 matrix

ok :)

@sd: why cant we directly check for all 1's in all the columns in a adjacency matrix.What is the point of having this i++ and j++ magic?

That will be a O(N2) Solution

@anish: It will a O(n2) solution if we scan each and every element.

Correct me if i am wrong, but does this essentially mean that we are searching a row from a 2D array where every element except a[i][j] (where i=j) are O.

if P[i] does not know P[j] and P[j] does not know P[i]
then what happened ? infinite while loop!

for both the above conditions
P[i] doesnot know P[j] it will j--
&&
P[j] doesnot know P[i] it will i--

please read conditions carefully

your code is :

if(P[i].knows[P[j]])
      i++;
if(P[j].knows[P[i]])
      j--;

you have two if statement . if both of these are false then what?
you read carefully please!

paradigm that is being addressed here is that there is a mayor in the collection and thus the code. i haven't coded for at most one mayor scenario.
I will reiterate please read the details carefully

ehsan explained clearly 2 times why your code is shit and there is an infinite loop possible

and you keep responding telling him to check the details.. but you provide none yourself ("paradigm" is not a detail)

while( <something related to i, and j that starts off true> )  {
if(<some shit that might be false at start>)
      change i;
if(<some other shit that might be false at start>)
      change j;
}

What happens if both if statement get skipped, genius?

So you're trying to solve a MUCH easier problem than the one everyone else is solving? Good job.
Look at your post

public person findMayor(person[] P)
{
   if(P.length==0)
   return null;
  int i=0; int j=P.length-1;
  while(i<j)
  {
      if(P[i].knows[P[j]])
      i++;
      if(P[j].knows[P[i]])
      j--;
     
  }

  return P[i];
}

if it is given that there is >>>atmost<<< a mayor int he people that are present then 
loop through once more to identify if P[i] knows anyone else this gives us if the probable candidate is a mayor based on the conditions given in the question

What the fuck does atmost mean?

ok let me give you an "atmost" solution here -

public person findMayor(person[] P)
{
   if(P.length==0)
   return null;
  int i=0; int j=P.length-1;
  while(i<j)
  {
      if(P[i].knows[P[j]])  // if i knows j then he cannot be mayor based on the constraints
      i++;
       else
      j--; // if j is not known we can be sure that j can not be a mayor as mayor is known by every one
    
     if(P[j].knows[P[i]]) // if j knows i then he cannot be mayor based on the constraints
      j--;
     else
      i++;//  if i is not known we can be sure that i can not be a mayor as mayor is known by every one
  }
//  here  comes "atmost" scenario
  int k=i;
  for(int i=0;i<P.length;i++)
  {
   if(!P[i].knowsP[k])
     return -1; // this mean the prospective candidate was not mayor as there was an ith candidate who didn't knew the prospect mayor 
  }
  return P[i]; // the identified candidate was a mayor

}

assume that we are searching for president of U.S. and the community has 3 persons. you , me and the president of U.S.
p[0] is you
p[1] is president of U.S.
p[2] is me
you don't know me. and I don't know you. but both of us know the president.

in your code at first loop i =0 and j=2 ( p[0] is you and p[2] is me)
if(you know me)
i++; // it does not run because you do not know me.
if(I know you)
j++; // it does not run because I don't know you
then while loop runs again and again , it means there is an infinite loop

I did my best to simplify the problem and explain that your code does not work!

this is going in an infinite loop guys . I tried to explain the constraints also give us a divide and conquer oppurtunity which if you are not able to see i can not explain more.

Rohit,

#1) You have a much bigger ego than your skill can uphold.
#2) You do not discuss how you build the P[ ] data structures
#3) You mix up your preconditions (at most, at least) and do not solve the problem exactly. Code something that finds a mayor or returns Nil if it can't. No "at most" or "at least" solutions. Make 1 solution.
#4) You do not discuss the time and space complexity of your solution.

Stop talking about constraints. Read the original question.
Stop talking about paradigms and divide and conquer and blah blah (just because you read that chapter of the book recently).

The query would be O(n).

The query would be O(n)
but Creating the model takes O(n2)
so your solution is O(n2)

Yeah.
That is how I would model it for the best amortized performance over the lifetime of this community.. which I presume is forever :P

Wait, what do you mean n2?

Community graphs usually have m = O(n) .. m=#edges

So it takes O(m+n) with adj lists.
which is "usually" O(n) to build.

u check person i to know how many people he knows it takes O (n)
and you should check all person . so n*n is O(n2)

number of edges in your model is O(n2) in worst case!

p[0] knows n-1 people
P[1] knows n-1 people
.
P[n-2] knows n-1 people
P[n-1] does not know any one (he is mayor!)

number of edge in this case is (n-1)(n-1) ---> O(n2)

ehsan, you still denote the complexity as O(n+m). m is at most n^2, but the preferred big-O notation remains O(n+m) because it is a tighter bound than O(n^2)

ehsan.... community graphs are m=little_o(n)
no community graph is even m=theta(n)

Think of why.

So building it is O(m+n)
If your community is very small and everyone almost knows everyone else, then ok m can be n^2.

But everyone will model this problem using a graph if they want to continually update the community (inserts/deletes). If you are just asking for a 1 time answer, then just brute force on whatever data structure you already have. No need to build another data structure to get 1 query answer.

you mean you create the model in O(n) ?
could you write your pseudo code? I think you need two nested loop , each one from i to n

It is O(m+n).

But community graphs usually are m=O(n).
{Think about why... if your city has a few million people, n^2 edges roughly means each person knows around 1million }

Community graphs usually have m = O(n).

dear Bigphatkdawg,
If you have the graph for this community you can find the mayor in O(n) but you don't have community graph. you should create it then use it to find the possible mayor.

the creation time is O(n2) because you have to check all possible edges. It does not matter how many edges the community has. for creation you need two nested loop to check who knows who.

You can "strip out" the parts of the graph model you don't need and target it just for this query (which nobody will do in real life cuz it's a toy problem if we do this).

Create an array of "people"
and in each "person" object store
1) count of "how many that know the person" and
2) count of "how many how many people the person knows"

There are on the order of O(n) relationships usually.
Have an array of N "persons":

pseudocode:

for each relationship (a,b): //usually O(n) relationships
{
        person[a].outdegree++;
        person[b].indegree++;
}

for i from 1 to N (num persons): //check for possible mayor
{
      if( person[i].outdegree==0 && person[i].indegree==N-1)
          return person[i];
}
else return nil:

====================
For each relationship, you do 2 array accesses.
So if (a,b), means person a know person b.
Update person a's "num ppl i know" count, and update b's "num ppl who know me" count.

So it should be O(n) unless the town is sooo small and everyone knows everyone (in which case the interviewer can find the answer even using pen and paper).

Nice, but tricky to understand.

Hey, DFS has O(V+E) complexity, but note that to run DFS, you need to build the graph. Building a graph for this problem takes O(n^2) complexity as you need to compare a person with every other person to determine whether they know each other. In other words, you will have to try n_choose_2 possibilities to establish the directed edges between nodes.

@algo_buff, I agree! However, it is safe to assume that we are provided with the matrix of people relationship (otherwise we can argue that we should go door to door in that city to figure it out!). This matrix can serve the graph representation to run the DFS.

No ahead path....

Explain your code please.
#1 REASON for that is, if you cannot explain it, then it probably does not work.
#2 REASON, while explaining it, it forces you to understand your code.

If P[0].knows(P[0]), then you set isMayor=false. Then isMayor never has a chance to become true.

What does your function return if the for loop reaches it's ending } ?

etc. etc. etc.

yes you are right. I had some mistakes in my code.
now it works.
I use two nested loops to check is there any person that does not know any one. that's it.

By the way, you are modelling the problem with something that is roughly equivalent/isomorphic to a graph adjacency matrix.

Not a good idea for community graphs.

P[i].knows( )
~~> his implies that you can put any person in in the ( )

So you are modelling by graph adjacency.

It is better if you do it this way:

P[i].knowlist
~~> is the head of a linked list of everyone P[i] is related to

Now you can iterate over P[i].knowlist

And with that change, your code can be optimized for O(m+n) , where m is #edges( relationships / "knows ofs" ).

oops, the statement in the if condition should be

mayBeMayor = p[i];