Bloomberg LP Interview Question for Interns


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
2
of 2 vote

DP:
f(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).

- Anonymous January 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you please explain the solution.

- Rocky January 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your case always adds up alternate tree level. It is possible to skip multiple levels.

- prodigy January 19, 2016 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This is CLRS 15-6

- itabe January 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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);
    }
}

- t4k9 January 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Victor January 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- akiremi January 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Xerox January 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Correct me if i am wrong , it says not immediate manager that is just one level above so just leaves doesnt suffice

- Sunil Vp January 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Prashant February 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Andrew March 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous March 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- anon March 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- zisuperman April 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- Anonymous May 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- marius May 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
}

}

- Anonymous July 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
	}
	
}

- Anonymous July 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
	}
	
}

- Saurabh July 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Its a dynamic programming where you begin from root and every parent selects max (parent + grandchildren , sum of children). That with a couple of conditions here and there
like negative child you don't want to count.

- Hk October 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This question is straight out of CLRS. There is a dynamic programming solution, similar to this recursive one here but utilizing memoization to avoid duplicate work.

- Anonymous November 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
	}
}

- pavelp May 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

dfd

ddssd dffdfd

- Anonymous July 23, 2017 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More