findCeleb.js

const knowsData = [
  {id: 1, knows: [4,2,10] },
  {id:2, knows: [4,10]},
  {id:3, knows: [10,2,1]},
  {id:4, knows:[10,8,9]},
  {id:5, knows:[10,6,7]},
  {id:6, knows:[10,1,2,3,4,5]},
  {id:7, knows:[10, 3,4,5]},
  {id:8, knows:[10,9,7,1]},
  {id:9, knows: [10]},
  {id:10, knows: []},
]


//return true if person 1 knows person 2
function knows(person1, person2) {
  return person1.knows.includes(person2.id)
}



// question - find the celebrity of the dataset - the person that knows no one but everyone knows them
//final solution took ~ 22 minutes

function find(data) {
  var iterationCount = 0;
  // my first iteration I was just looking through the list and finding someone that idnd't know anyone else I then realize a better solution...
  /*
  let dataIndex = 0;
  // step 1 - find out if the person knows anyone
  
  while(data.length > 2) {
      var knowsSomeone = false;
      for(var i = dataIndex+1; i < data.length; i++) {
        iterationCount++;
        if(knows(data[dataIndex],data[i])) {
          knowsSomeone = true;
          dataIndex++; //theyre now dead to us, there is no longer any point comparing them  
          break; //exit early
        }
      }
      if(knowsSomeone === false) { 
        console.log("iteration count:", iterationCount);  
        return data[dataIndex];
      }
  }
  
  */
  
  //the better solution is to use the first iterations list of people they know, and then only search that from then on.  This actually results in a significantly lower data set, closer to log n
  
  while(true) {
    var found = [];
    for( var i = 1; i < data.length; i++) {
      iterationCount++;
      if(knows(data[0], data[i])){
        found.push(data[i]);   
      }
    }
  
    //if we have a result of "knows no one" then we found the celebrity
    if(found.length === 0) { 
      console.log("iteration count:", iterationCount);  
      return data[0];
    } else {
     data = found; 
    }
  }
  
}
  
  console.log("CELEBRITY?:" , find(knowsData));