Skip to content

[Graphs] Find Most Common Title from a Social Network

Daisho Komiyama edited this page Jul 6, 2021 · 1 revision
const list = [
  {
    id: 1, name: 'Joe', title: 'Manager', connections: [3,5]
  },
  {
    id: 2, name: 'Yang', title: 'Dev', connections: [1,4]
  },
  {
    id: 3, name: 'Eric', title: 'Manager', connections: [2,5]
  },
  {
    id: 4, name: 'Serge', title: 'Tester', connections: [1]
  },
  {
    id: 5, name: 'Louis', title: 'Manager', connections: [3,4,5]
  },
]

const getUser = id => list[id-1]

const findMostCommonTitle = (id, getUser, degreesOfSeparation) => {
  let queue = [id]
  const seen = new Set() // Creates a values only object e.g. {1,3,5}. They are guaranteed to be unique.
  const jobs = {}

  for (let _ = 0; _ <= degreesOfSeparation; _++) {
    queue = queue
      .filter(id => !seen.has(id))
      .map(getUser)
      .map(user => {
        jobs[user.title] = jobs[user.title] ? jobs[user.title] + 1 : 1
        seen.add(user.id)
        return user.connections
      })
      .reduce((acc, connections) => [...acc, ...connections], []) // Flattens [[1,3],[2,3]] to [1,3,2,3]
  }

  // jobs { 'Dev': 1, 'Manager': 3, 'Tester': 1 }
  return Object.keys(jobs) 
    .map(job => [job, jobs[job]]) // Makes tuples out of an object e.g.[['Dev', 1]...] so that we can sort it by the number
    .sort((a, b) => b[1] - a[1])[0][0]// high to low, then title
}

findMostCommonTitle(2, getUser, 2) // 'Manager'
Clone this wiki locally