Bloomberg LP Interview Question
InternsCountry: United States
Interview Type: In-Person
We will use a recursive algorithm to find the max score. The recursive function will take in the employee node, an n-ary node, and a Boolean parameter: bossIsGoing. Idea: At a node x, if boss is going, x won't go, recursively attempt to invite all his/her subordinate; if boss is not going, decide whether x will go or not using recursion.
public class InviteEmployees
{
public static int inviteEmployees(Node head)
{
boolean bossIsGoing = false;
return inviteEmployees(head, bossIsGoing);
}
private static int inviteEmployees(Node x, boolean bossIsGoing)
{
if (x==null) return 0;
if (bossIsGoing)
{
// My boss is going, I am not going
// Attempt to invite all my subordinate
int score = 0;
for(Node e : x.next)
score += inviteEmployees(e, false);
return score;
}
assert !bossIsGoing;
// Should I go?
int scoreIfGo = x.value;
int scoreIfDontGo = 0;
for(Node e : x.next)
{
scoreIfGo += inviteEmployees(e, true);
scoreIfDontGo += inviteEmployees(e, false);
}
return Math.max(scoreIfGo, scoreIfDontGo);
}
}
This problem seems too complex for being asked in an interview. But I may be wrong and there's a much simpler solution.
Construct a graph where nodes correspond to employees and edges connect employees that are not directly related (i.e. can attend the party together).
Employees with negative value can be discarded in this phase because there's no point in inviting them.
The problem now is to find which clique in the graph gives the highest sum of values. Since we only have positive values in the graph, we can consider only maximal cliques, given larger cliques are always better.
Bron-Kerbosch's algorithm enumerates maximal cliques in graphs, so there you have it.
Since the question didn't say about the return type, I am returning the max value that can be computed from this hierarchy for simplicity. If the invited employee list is required to be returned, it can be easily achieved with List.
public class Employee
{
int value;
List<Employee> subordinates;
public Employee(int newValue)
{
value = newValue;
subordinates = new List<Employee>();
}
public void AddSubordinate(Employee subordinate)
{
subordinates.Add(subordinate);
}
public List<Employee> Subordinates
{
get
{
return subordinates;
}
}
public int Value
{
get
{
return value;
}
}
}
public static int InviteEmployees(Employee head)
{
int sum = Int32.MinValue;
if (head == null)
{
return sum;
}
int sumOfSubordinates = Int32.MinValue;
foreach(Employee subordinate in head.Subordinates)
{
int currentSubordinate = InviteEmployees(subordinate);
if (sumOfSubordinates < 0)
{
sumOfSubordinates = Math.Max(sumOfSubordinates, currentSubordinate);
}
else
{
sumOfSubordinates += Math.Max(0, currentSubordinate);
}
}
Console.WriteLine("head is: " + head.Value);
Console.WriteLine("sumOfSubordinates is: " + sumOfSubordinates);
if (head.Value >= 0 && sumOfSubordinates >= 0)
{
sum = head.Value + sumOfSubordinates;
}
else
{
sum = Math.Max(head.Value, sumOfSubordinates);
}
return sum;
}
The thing that jumps out is "you cant invite an employee's immediate boss or subordinate". Being that it's a tree, every node will have a parent node (a boss of someone), except the leaf nodes. So correct me if I'm wrong but I think doing a BFS and returning all the leaf nodes should suffice for this problem.
Well, the problem will require taking those values which are +ve and leaving out negative values(+ separate handling for case when all values are -ve). Do a Depth first search recursively on subordinates and pass boolean value in recursion to indicate if node at this recursive level is available for consideration.
class Employee
attr_reader :subordinates
def initialize(children, val)
@subordinates= children
@val = val
end
def val
@val > 0 ? @val : 0
end
end
def party_val hierarchy
val = hierarchy.inject(0) { |v,e| v+=e.val; v }
val + hierarchy.map do |e|
e.subordinates.map { |s| s.subordinates }
end.flatten.inject(0) do |v,e|
v += e.val; v
end
end
def best_party hierarchy
[
party_val(hierarchy),
party_val(hierarchy.map { |e| e.subordinates }.flatten)
].max
end
if __FILE__ == $0
puts best_party [Employee.new(
[
Employee.new([Employee.new([],3),Employee.new([],-4),Employee.new([],12)], 999),
Employee.new([Employee.new([],3),Employee.new([],-4),Employee.new([],12)], 999),
Employee.new([Employee.new([],3),Employee.new([],-4),Employee.new([],12)], 999),
Employee.new([Employee.new([],3),Employee.new([],-4),Employee.new([],12)], 999),
],
200
)]
end
class Employee
attr_reader :subordinates
def initialize(children, val)
@subordinates= children
@val = val
end
def val
@val > 0 ? @val : 0
end
end
def party_val hierarchy
val = hierarchy.inject(0) { |v,e| v+=e.val; v }
val + hierarchy.map do |e|
e.subordinates.map { |s| s.subordinates }
end.flatten.inject(0) do |v,e|
v += e.val; v
end
end
def best_party hierarchy
[
party_val(hierarchy),
party_val(hierarchy.map { |e| e.subordinates }.flatten)
].max
end
if __FILE__ == $0
puts best_party [Employee.new(
[
Employee.new([Employee.new([],3),Employee.new([],-4),Employee.new([],12)], 999),
Employee.new([Employee.new([],3),Employee.new([],-4),Employee.new([],12)], 999),
Employee.new([Employee.new([],3),Employee.new([],-4),Employee.new([],12)], 999),
Employee.new([Employee.new([],3),Employee.new([],-4),Employee.new([],12)], 999),
],
200
)]
end
class Employee
attr_reader :subordinates
def initialize(children, val)
@subordinates= children
@val = val
end
def val
@val > 0 ? @val : 0
end
end
def party_val hierarchy
val = hierarchy.inject(0) { |v,e| v+=e.val; v }
val + hierarchy.map do |e|
e.subordinates.map { |s| s.subordinates }
end.flatten.inject(0) do |v,e|
v += e.val; v
end
end
def best_party hierarchy
[
party_val(hierarchy),
party_val(hierarchy.map { |e| e.subordinates }.flatten)
].max
end
if __FILE__ == $0
puts best_party [Employee.new(
[
Employee.new([Employee.new([],3),Employee.new([],-4),Employee.new([],12)], 999),
Employee.new([Employee.new([],3),Employee.new([],-4),Employee.new([],12)], 999),
Employee.new([Employee.new([],3),Employee.new([],-4),Employee.new([],12)], 999),
Employee.new([Employee.new([],3),Employee.new([],-4),Employee.new([],12)], 999),
],
200
)]
end
The following code returns the maximum value, searching throughout the hierarchy tree recursively. It starts from the boss and it might skip him or invite him. In the former case, it searches through his subordinates (inviting or skipping them as well) and adding the resulting values from each (valueWithout). In the latter case, it adds the value of the boss in the respective variable (valueWith) and searches at the subordinates of his subordinates, adding their values as well. Finally, it selects the maximum value between the choices of inviting or skipping him.
int maxValue(Tree boss){
if (boss == null) return 0;
int valueWithout = MIN_VALUE, valueWith = MIN_VALUE;
\\ Do not invite him, thus check his subordinates
for (subOrdinate sub: boss){
valueWithout += maxValue(sub));
}
\\ Invite him, thus check directly the subordinates of his subordinates
valueWith += bossValue;
for (subSubOrdinate subSub: boss){
valueWith += maxValue(subSub);
}
return Math.max(valueWithout,valueWith);
}
We can divide this problem in sub problems. For a particular sub-org, we compute maxIncl is the maximum value if we include the boss of the sub-org, maxExcl is the maximum value if we don't include him.
To compute maxInc: We start with the value of the current root. For each direct report add the sub-tree's maxExcl value if it's positive.
To compute maxExcl: We start with 0 (zero). For each direct report add the sub-tree's maxIncl value if it's positive.
struct Node;
using NodePtr = unique_ptr<Node>;
struct Node {
int value;
vector<NodePtr> children;
Node(int val)
: value(val) {
}
void addChild(NodePtr&& node) {
children.push_back(forward<NodePtr>(node));
}
};
void FindMaxValueRec(const NodePtr& root, int& maxIncl, int& maxExcl) {
maxIncl = 0;
maxExcl = 0;
if (root == nullptr) {
return;
}
maxIncl += root->value;
for (const auto& child : root->children) {
int maxChildIncl;
int maxChildExcl;
FindMaxValueRec(child, maxChildIncl, maxChildExcl);
if (maxChildIncl > 0) {
maxExcl += maxChildIncl;
}
if (maxChildExcl > 0) {
maxIncl += maxChildExcl;
}
}
}
int FindMaxValue(const NodePtr& root) {
int maxIncl;
int maxExcl;
FindMaxValueRec(root, maxIncl, maxExcl);
return max(maxIncl, maxExcl);
}
struct Node;
using NodePtr = unique_ptr<Node>;
struct Node {
int value;
vector<NodePtr> children;
Node(int val) : value(val) {}
void addChild(NodePtr&& node) {
children.push_back(forward<NodePtr>(node));
}
};
void FindMaxValueRec(const NodePtr& root, int& maxIncl, int& maxExcl) {
maxIncl = 0;
maxExcl = 0;
if (root == nullptr) {
return;
}
maxIncl += root->value;
for (const auto& child : root->children) {
int maxChildIncl;
int maxChildExcl;
FindMaxValueRec(child, maxChildIncl, maxChildExcl);
if (maxChildIncl > 0) {
maxExcl += maxChildIncl;
}
if (maxChildExcl > 0) {
maxIncl += maxChildExcl;
}
}
}
int FindMaxValue(const NodePtr& root) {
int maxIncl;
int maxExcl;
FindMaxValueRec(root, maxIncl, maxExcl);
return max(maxIncl, maxExcl);
}
package com.practice.algo.and.ds.Tree;
import java.util.HashMap;
import java.util.Map;
/*You are asked to plan the company party for a big company and the rst step is to choose who will be
invited. There are two factors to be considered: a) each person has a desirability ai; if this is high you
really want to invite the person to the party (think the funny guy); b) the company hierarchy is organized
as a rooted the tree. The root is the CEO of the company and everyone else is the child of their direct
boss in the tree. You should never invite someone and their direct boss to the party (that would make it
hard for them to have fun.)
Your job is to devise an algorithm that takes n, the number of people in the company, a1; : : : ; an and the
company hierarchy as input and outputs the set of people to invite. The way the company hierarchy is
given is as follows. You are given sets C1;C2; : : : ;Cn where Ci contains the direct subordinates of the ith
employee. You are guaranteed that these make a tree (each person except the CEO is in precisely one
of the Ci sets and there are no cycles.) To make your life easier we also know that the CEO is always
employee number 1 and that each person's subordinates have a higher number than themselves.
You should never invite a person and their direct boss at the same time and among all possible such
solutions you should output the one with the maximum total desirability. The total desirability of an
invitation list is the sum of the desirability of the people invited.
*/
public class CLRS15_6_PartyQuestion {
/**
* @param args
*/
static Map<Integer,int[]> subMap = new HashMap<Integer,int[]>();
static int[] willingness = {-2,1,1,4};
public static void main(String[] args) {
subMap.put(1, new int[]{2,3});
subMap.put(2, new int[]{4});
subMap.put(3, null);
subMap.put(4, null);
int n = getMax();
}
private static int getMax() {
int l = subMap.size();
int[] D = new int[l];
int[] DEx = new int[l];
for(int i = l;i>0;i--){
int sof = 0;
int sofe = 0;
int[] sub = subMap.get(i);
if(sub!=null)
for(int k=0;k<sub.length;k++){
sofe+=DEx[sub[k]];
sof+=D[sub[k]];
}
DEx[i] = sof;
D[i] = Math.max(willingness[i-1]+sofe, sof);
}
return D[1];
}
}
package com.practice.algo.and.ds.Tree;
import java.util.HashMap;
import java.util.Map;
/*You are asked to plan the company party for a big company and the rst step is to choose who will be
invited. There are two factors to be considered: a) each person has a desirability ai; if this is high you
really want to invite the person to the party (think the funny guy); b) the company hierarchy is organized
as a rooted the tree. The root is the CEO of the company and everyone else is the child of their direct
boss in the tree. You should never invite someone and their direct boss to the party (that would make it
hard for them to have fun.)
Your job is to devise an algorithm that takes n, the number of people in the company, a1; : : : ; an and the
company hierarchy as input and outputs the set of people to invite. The way the company hierarchy is
given is as follows. You are given sets C1;C2; : : : ;Cn where Ci contains the direct subordinates of the ith
employee. You are guaranteed that these make a tree (each person except the CEO is in precisely one
of the Ci sets and there are no cycles.) To make your life easier we also know that the CEO is always
employee number 1 and that each person's subordinates have a higher number than themselves.
You should never invite a person and their direct boss at the same time and among all possible such
solutions you should output the one with the maximum total desirability. The total desirability of an
invitation list is the sum of the desirability of the people invited.
*/
public class CLRS15_6_PartyQuestion {
/**
* @param args
*/
static Map<Integer,int[]> subMap = new HashMap<Integer,int[]>();
static int[] willingness = {-2,1,1,4};
public static void main(String[] args) {
subMap.put(1, new int[]{2,3});
subMap.put(2, new int[]{4});
subMap.put(3, null);
subMap.put(4, null);
int n = getMax();
}
private static int getMax() {
int l = subMap.size();
int[] D = new int[l];
int[] DEx = new int[l];
for(int i = l;i>0;i--){
int sof = 0;
int sofe = 0;
int[] sub = subMap.get(i);
if(sub!=null)
for(int k=0;k<sub.length;k++){
sofe+=DEx[sub[k]];
sof+=D[sub[k]];
}
DEx[i] = sof;
D[i] = Math.max(willingness[i-1]+sofe, sof);
}
return D[1];
}
}
package com.practice.algo.and.ds.Tree;
import java.util.HashMap;
import java.util.Map;
/*You are asked to plan the company party for a big company and the rst step is to choose who will be
invited. There are two factors to be considered: a) each person has a desirability ai; if this is high you
really want to invite the person to the party (think the funny guy); b) the company hierarchy is organized
as a rooted the tree. The root is the CEO of the company and everyone else is the child of their direct
boss in the tree. You should never invite someone and their direct boss to the party (that would make it
hard for them to have fun.)
Your job is to devise an algorithm that takes n, the number of people in the company, a1; : : : ; an and the
company hierarchy as input and outputs the set of people to invite. The way the company hierarchy is
given is as follows. You are given sets C1;C2; : : : ;Cn where Ci contains the direct subordinates of the ith
employee. You are guaranteed that these make a tree (each person except the CEO is in precisely one
of the Ci sets and there are no cycles.) To make your life easier we also know that the CEO is always
employee number 1 and that each person's subordinates have a higher number than themselves.
You should never invite a person and their direct boss at the same time and among all possible such
solutions you should output the one with the maximum total desirability. The total desirability of an
invitation list is the sum of the desirability of the people invited.
*/
public class CLRS15_6_PartyQuestion {
/**
* @param args
*/
static Map<Integer,int[]> subMap = new HashMap<Integer,int[]>();
static int[] willingness = {-2,1,1,4};
public static void main(String[] args) {
subMap.put(1, new int[]{2,3});
subMap.put(2, new int[]{4});
subMap.put(3, null);
subMap.put(4, null);
int n = getMax();
}
private static int getMax() {
int l = subMap.size();
int[] D = new int[l];
int[] DEx = new int[l];
for(int i = l;i>0;i--){
int sof = 0;
int sofe = 0;
int[] sub = subMap.get(i);
if(sub!=null)
for(int k=0;k<sub.length;k++){
sofe+=DEx[sub[k]];
sof+=D[sub[k]];
}
DEx[i] = sof;
D[i] = Math.max(willingness[i-1]+sofe, sof);
}
return D[1];
}
}
#include <list>
#include <string>
#include <vector>
#include <iostream>
using namespace std;
struct employee
{
string name;
int value;
vector<employee> children;
void add_child(employee &child)
{
children.push_back(child);
}
employee(string name_, int value_) : name(name_), value(value_) {}
employee() {}
};
struct get_guests_res
{
get_guests_res() : calculated_value_0(0), calculated_value_1(0) {}
int calculated_value_0;
list<employee*> guests_0;
int calculated_value_1; // best calculated value for subordinates
list<employee*> guests_1; // subordinate guests
};
get_guests_res get_guests_(employee *node)
{
get_guests_res ret;
if (!node)
return ret;
for (unsigned i = 0; i < node->children.size(); ++i)
{
get_guests_res r = get_guests_(&node->children[i]);
if (r.calculated_value_0)
{
ret.guests_1.splice(ret.guests_1.end(), r.guests_0);
ret.calculated_value_1 += r.calculated_value_0;
ret.guests_0.splice(ret.guests_0.end(), r.guests_1);
ret.calculated_value_0 += r.calculated_value_1;
}
else
{
list<employee*> guests_1 = r.guests_1;
ret.guests_1.splice(ret.guests_1.end(), r.guests_1);
ret.calculated_value_1 += r.calculated_value_1;
ret.guests_0.splice(ret.guests_0.end(), guests_1);
ret.calculated_value_0 += r.calculated_value_1;
}
}
if (node->value > 0 && ret.calculated_value_0 + node->value > ret.calculated_value_1)
{
ret.guests_0.push_back(node);
ret.calculated_value_0 += node->value;
}
else
{
ret.calculated_value_0 = 0; // parent one level up will skip two levels
}
return ret;
}
list<employee*> get_guests(employee &node)
{
get_guests_res r = get_guests_(&node);
return r.calculated_value_0 > 0 ? r.guests_0 : r.guests_1;
}
void main()
{
// init test data with values from cspat.googlecode.com/svn/trunk/Course/505%20Algorithm/HW/hw3/hwk-3-solution-archer.pdf
// President
employee top("BigShot", 5);
// Vice Presidents
top.add_child(employee("VP-1", 3));
top.add_child(employee("VP-2", 12));
top.add_child(employee("VP-3", 20));
// Middle Management
top.children[0].add_child(employee("MM-1", 6));
top.children[0].add_child(employee("MM-2", 3));
top.children[1].add_child(employee("MM-3", 7));
top.children[1].add_child(employee("MM-4", 9));
top.children[1].add_child(employee("MM-5", 8));
top.children[1].add_child(employee("MM-6", 11));
top.children[2].add_child(employee("MM-7", 4));
// Peons
top.children[0].children[1].add_child(employee("GTC-1", 28));
top.children[1].children[2].add_child(employee("Peon-1", 1));
top.children[1].children[2].add_child(employee("PG-1", 45));
list<employee*> invited = get_guests(top);
for (auto it = invited.begin(); it != invited.end(); ++it)
{
cout << (*it)->name << " is invited" << endl;
}
}
DP:
- Anonymous January 23, 2015f(node, canBeSelected)=
- if canBeSelected then max(node.value + f(node.child1, false) + ... + f(node.childN, false), 0 + f(node.child1, true) + ... + f(node.childN, true))
- otherwise f(node.child1, true) + ... + f(node.childN, true)
The result is f(root, true).