Answer: Uber | 15th October, 2022 | Recent Interview Questions

Solution to Problem 1 Analysis Let's first make a graph where the nodes are the jobs and the candidates, and if candidate i is a fit of job j add an edge of weight profit[j] between candidate i and job j. Note that this graph is bipartite as the only edges are from jobs to candidates. So now our problem reduces to finding a set of independent edges (i.e. edges that do not share a node) that has maximum weight ...