IBM Interview Question Software Engineer / Developers
Country: United States
package myProject;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;
public class resolveIssues {
public static void main(String[] args) {
HashMap<String,String> map = new HashMap<String,String>();
String inputString = "Frank->Mary,Mary->Sam,Mary->Bob,Sam->Katie,Sam->Pete,Bob->John,Sam,Katie";
String mgr = createEmployeeManagerDictionary(map,inputString);
System.out.println("Mgr who will resolve the issue is: " + mgr);
}
private static String createEmployeeManagerDictionary(HashMap<String, String> map, String inputString) {
StringTokenizer tokens = new StringTokenizer(inputString,",");
StringBuffer sb = new StringBuffer();
String emp1 = null;
String emp2 = null;
while (tokens.hasMoreElements()) {
String token = tokens.nextToken();
if(token.contains("->")){
map.put(token.split("->")[1], token.split("->")[0]);
}else{
sb.append(token + ",");
}
}
tokens = new StringTokenizer(sb.toString(),",");
while (tokens.hasMoreElements()) {
emp1 = tokens.nextToken();
emp2 = tokens.nextToken();
}
String mgr = resolveIssue(emp1,emp2,map);
return mgr;
}
private static String resolveIssue(String emp1, String emp2, HashMap<String, String> map) {
ArrayList<String> sb1 = getTree(emp1,map);
ArrayList<String> sb2 = getTree(emp2,map);
if(sb1.size()==0 && sb2.size()!=0){
int i = sb2.size();
return sb2.get(i-1);
}
if(sb2.size()==0 && sb1.size()!=0){
int i = sb1.size();
return sb1.get(i-1);
}
if(sb1.size()>sb2.size()){
return sb2.get(0);
}else{
return sb1.get(0);
}
}
private static ArrayList<String> getTree(String emp, HashMap<String, String> map) {
ArrayList<String> stringArray = new ArrayList<String>();
while(map.containsKey(emp)){
stringArray.add(map.get(emp));
emp = map.get(emp);
}
return stringArray;
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace conflictResolver
{
class Program
{
static void Main(string[] args)
{
Dictionary<string, Employee> employees = new Dictionary<string, Employee>();
string ip1 = "Frank->Mary,Mary->Sam,Mary->Bob,Sam->Katie,Sam->Pete,Bob->John,Ron->Frank,Bob,Katie";
string ip2 = "Sam->Pete,Pete->Nancy,Ram->Katie,Mary->Bob,Frank->Mary,Mary->Sam,Bob->John,Mary->Ram,Pete,Katie";
var inputData = ip2.Split(',');
for (int i = 0; i < inputData.Length - 2; i++)
{
var employeeManager = inputData[i].Replace("->", "-").Split('-');
if (employees.Keys.Any(key => key == employeeManager[0]) && employees.Keys.Any(key => key == employeeManager[1]))
{
Employee manager = employees.FirstOrDefault(item => item.Key == employeeManager[0]).Value;
Employee employee = employees.FirstOrDefault(item => item.Key == employeeManager[1]).Value;
manager.DirectReports.Add(employee);
employee.Manager = manager;
}
else if (employees.Keys.Any(key => key == employeeManager[0]))
{
Employee manager = employees.FirstOrDefault(item => item.Key == employeeManager[0]).Value;
Employee employee = new Employee(employeeManager[1], manager);
manager.DirectReports.Add(employee);
employees.Add(employeeManager[1], employee);
}
else if (employees.Keys.Any(key => key == employeeManager[1]))
{
Employee employee = employees.FirstOrDefault(item => item.Key == employeeManager[1]).Value;
Employee manager = new Employee(employeeManager[0], null);
manager.DirectReports.Add(employee);
employee.Manager = manager;
employees.Add(employeeManager[0], manager);
}
else
{
// Employee managersManager = employees.FirstOrDefault(item=> item.Key == e)
Employee mananager = new Employee(employeeManager[0], null);
Employee employee = new Employee(employeeManager[1], mananager);
mananager.DirectReports.Add(employee);
employees.Add(employeeManager[1], employee);
employees.Add(employeeManager[0], mananager);
}
}
RankEmployees(employees);
Employee emp1 = employees.First(item => item.Key == inputData[inputData.Length - 2]).Value;
Employee emp2 = employees.First(item => item.Key == inputData[inputData.Length - 1]).Value;
string conflitResolver = FindCommonManger(emp1, emp2);
}
private static string FindCommonManger(Employee emp1, Employee emp2)
{
if (emp1.Rank < emp2.Rank)
{
return emp1.Manager.Name;
}
else if (emp2.Rank < emp1.Rank)
{
return emp2.Manager.Name;
}
else
{
if (emp1.Manager == emp2.Manager)
return emp1.Manager.Name;
else
return FindCommonManger(emp1.Manager, emp2.Manager);
}
}
private static void RankEmployees(Dictionary<string, Employee> employees)
{
Employee ceo = employees.FirstOrDefault(item => item.Value.Manager == null).Value;
AddRank(ceo, 1);
ForEachdirectReorts(ceo, ceo.Rank + 1);
}
private static void ForEachdirectReorts(Employee emp, int rank)
{
foreach (var item in emp.DirectReports)
{
AddRank(item, rank);
ForEachdirectReorts(item, item.Rank + 1);
}
}
private static void AddRank(Employee ceo, int v)
{
ceo.Rank = v;
}
}
public class Employee
{
public string Name { get; set; }
public Employee Manager { get; set; }
public int Rank { get; set; }
public List<Employee> DirectReports { get; set; }
public Employee(string employee, Employee manager)
{
this.Name = employee;
this.Manager = manager;
DirectReports = new List<Employee>();
}
}
}
import java.util.*;
public class Main{
public static String test1 = "Frank->Mary,Mary->Sam,Mary->Bob,Sam->Katie,Sam->Pete,Bob->John,Katie->Steve, Steve,Bob";
public static String test2 = "Sam->Pete,Pete->Nancy,Sam->Katie,Mary->Bob,Frank->Mary,Mary->Sam,Bob->John,Pete,John";
public static Map <String, ArrayList<String>> mp = new HashMap<String, ArrayList<String>>();
public static void main(String [] args){
ArrayList<String> allPeople = new ArrayList<String>();
String [] temp = test1.split(",");
//System.out.println(Arrays.toString(temp));
for(int x = 0; x<temp.length-2; x++){
String pair = temp[x];
String [] pairS = pair.split("\\s*(->)\\s*");
//System.out.println(Arrays.toString(pairS));
ArrayList<String> tz;
if(mp.get(pairS[0]) == null) {
tz = new ArrayList<String>();
tz.add(pairS[1]);
mp.put(pairS[0], tz);
}else{
tz = mp.get(pairS[0]);
tz.add(pairS[1]);
mp.put(pairS[0], tz);
}
if(!allPeople.contains(pairS[0])) allPeople.add(pairS[0]);
}
String person1 = temp[temp.length-1].replace(" ", "");
String person2 = temp[temp.length-2].replace(" ", "");;
if(!allPeople.contains(temp[temp.length-1])) allPeople.add(temp[temp.length-1]);
if(!allPeople.contains(temp[temp.length-1])) allPeople.add(temp[temp.length-2]);
for(int x = 0; x<allPeople.size(); x++){
ArrayList<String> tez = mp.get(allPeople.get(x));
System.out.println(allPeople.get(x) + ", " + tez);
}
for(int x = 0; x<allPeople.size(); x++){
ArrayList<String> tez = mp.get(allPeople.get(x));
if(tez.size() == 1) continue;
if (tez.contains(person1)) {
//System.out.println("FOUND 1: " + person1);
int place = tez.indexOf(person1);
tez.remove(place);
boolean xz = checkChildren(tez, person2, allPeople.get(x));
if(xz) return;
}else if(tez.contains(person2)){
//System.out.println("FOUND 1: " + person2);
int place = tez.indexOf(person2);
tez.remove(place);
boolean xz = checkChildren(tez, person1, allPeople.get(x));
if(xz) return;
}
else{
continue;
}
}
//System.out.println(allPeople);
/*
Set set = mp.entrySet();
// Get an iterator
Iterator i = set.iterator();
// Display elements
while(i.hasNext()) {
Map.Entry me = (Map.Entry)i.next();
System.out.print(me.getKey() + ": ");
System.out.println(me.getValue());
}
*/
}
public static boolean checkChildren(ArrayList<String> tez, String toFind, String curr){
//System.out.println(tez + ",TO FIND(" + toFind + ")");
if(tez.contains(toFind)) {
System.out.println("FOUND: " + curr);
return true;
}
for(int y = 0; y < tez.size(); y++){
ArrayList<String> tez2 = mp.get(tez.get(y));
if(tez2 != null) checkChildren(tez2, toFind, curr);
}
return false;
}
}
import java.util.HashMap;
import java.util.Map;
/**
* Created by NoOne on 18/10/16.
*/
public class Main {
static String s = "Frank->Mary,Mary->Sam,Mary->Bob,Sam->Katie,Sam->Pete,Bob->John,Bob,Katie" ;
static Map<String,String> createDict(String[] items){
Map<String,String> m = new HashMap();
for ( int i = 0 ; i < items.length - 2 ; i++ ){
String[] pair = items[i].split("->");
m.put( pair[1], pair[0] );
}
return m;
}
static String[] pathToRoot( String employee, Map<String,String> tree){
StringBuffer buf = new StringBuffer();
while ( tree.containsKey( employee ) ){
buf.append( employee ).append( "\t") ;
employee = tree.get( employee );
}
buf.append( employee );
return buf.toString().split( "\t" );
}
static void doIBM( String s ){
String[] values = s.split(",");
Map<String,String> tree = createDict( values );
String emp1 = values[ values.length -2 ] ;
String emp2 = values[ values.length -1 ] ;
String[] path1 = pathToRoot( emp1 , tree ) ;
String[] path2 = pathToRoot( emp2 , tree ) ;
int len = path1.length > path2.length ? path1.length : path2.length ;
String resolver = "" ;
for ( int i = 0; i < len ; i++ ){
if ( !path1[ path1.length - 1 - i ].equals( path2[ path2.length -1 - i] ) ) {
break;
}
resolver = path1[ path1.length - 1 - i ];
}
System.out.println(resolver);
}
public static void main(String[] args){
doIBM(s);
}
}
From the same Java Code. My first code is a sham, and should be avoided.
This, on the other hand is very concise. Abhinav, note that 1-1 mapping with ZoomBA land and Java island are possible, see code in both the languages :
def path_2_root( emp, tree ){
path = ''
while ( emp @ tree ){
path += ( emp + '\t' )
emp = tree[emp]
}
path += emp
return path.split('\t')
}
def do_ibm( s ){
values = s.split(",")
tree = dict ( [0: size(values) - 2 ] ) -> {
pair = values[ $.item ].split('->')
[ pair[1] , pair[0] ]
}
emp1 = values[-2]
emp2 = values[-1]
path1 = path_2_root( emp1 , tree )
path2 = path_2_root( emp2 , tree )
len = size( path1 ) > size( path2 ) ? size( path1 ) : size( path2 )
resolver = fold( [1:len] , '' ) -> {
break ( path1[ - $.item ] != path2[ - $.item ] )
$.prev = path1[ - $.item ]
}
}
Didn't take the challenge so I took a stab at it myself. This is my result, all test cases succeeded, not sure if there are any edge cases I am missing, I tried to follow thru with them but the concept is there.
int main()
{
static const string test1 = "Frank->Mary,Mary->Sam,Mary->Bob,Sam->Katie,Sam->Pete,Bob->John,Katie->Steve,Steve,Bob"; //answer = Mary
static const string test2 = "Sam->Pete,Pete->Nancy,Sam->Katie,Mary->Bob,Frank->Mary,Mary->Sam,Bob->John,Pete,John"; // answer = Mary
static const string test3 = "Frank->Mary,Mary->Sam,Mary->Bob,Sam->Katie,Sam->Pete,Bob->John,Pete,Katie"; // answer = Mary
static const string test4 = "Sam->Pete,Pete->Nancy,Sam->Katie,Mary->Bob,Frank->Mary,Mary->Sam,Bob->John,Sam,John"; //answer = Mary
static const string test5 = "Tom->Mary,Mary->Bob,Mary->Sam,Bob->John,Sam->Pete,Sam->Kate,Pete,Kate"; // answer = Sam
//we will reverse the relationship since each employee can have only one manager, we will use a hashmap to represent this
unordered_map<string, string> myMap;
string stringToTest = test3;
string employee1, employee2;
size_t posNext = 0;
size_t posLast = 0;
//parse thru the string
while ((posNext = stringToTest.find(",", posLast)) != string::npos) {
string tmpString = stringToTest.substr(posLast, posNext-posLast);
size_t pos;
string employee, manager;
if ((pos = tmpString.find("->")) != string::npos) {
manager = tmpString.substr(0, pos);
employee = tmpString.substr(pos + 2);
myMap.emplace(employee, manager);
}
else {
if (employee1.empty()) {
employee1 = tmpString;
}
}
posLast = ++posNext;
}
employee2 = stringToTest.substr(posLast);
//use this set to keep track of which nodes were visited
unordered_set<string> visited;
//traverse with employee1 and mark all nodes as visited unless its employee1 or employee2
auto it = myMap.find(employee1);
while (it != myMap.end()) {
if (it->second != employee1 || it->second != employee2) {
visited.emplace(it->second);
}
it = myMap.find(it->second);
}
//continue searching with employee2 and find traces of employee1's footsteps, ignore instances of employee1 or employee2
string result;
it = myMap.find(employee2);
while (it != myMap.end() ||
it->first == employee1 &&
it->first == employee2) {
//if its visited, we know we found a match
if (visited.find(it->second) != visited.end()) {
result = it->second;
break;
}
it = myMap.find(it->second);
}
cout << result << endl;
return 0;
}
Went back and redid the challenge. This is working code and I tested many cases. Should be good to go.
int main()
{
static const string test1 = "Frank->Mary,Mary->Sam,Mary->Bob,Sam->Katie,Sam->Pete,Bob->John,Katie->Steve,Steve,Bob"; //answer = Mary
static const string test2 = "Sam->Pete,Pete->Nancy,Sam->Katie,Mary->Bob,Frank->Mary,Mary->Sam,Bob->John,Pete,John"; // answer = Mary
static const string test3 = "Frank->Mary,Mary->Sam,Mary->Bob,Sam->Katie,Sam->Pete,Bob->John,Pete,Katie"; // answer = Mary
static const string test4 = "Sam->Pete,Pete->Nancy,Sam->Katie,Mary->Bob,Frank->Mary,Mary->Sam,Bob->John,Sam,John"; //answer = Mary
static const string test5 = "Tom->Mary,Mary->Bob,Mary->Sam,Bob->John,Sam->Pete,Sam->Kate,Pete,Kate"; // answer = Sam
//we will reverse the relationship since each employee can have only one manager, we will use a hashmap to represent this
unordered_map<string, string> myMap;
string stringToTest = test3;
string employee1, employee2;
size_t posNext = 0;
size_t posLast = 0;
//parse thru the string
while ((posNext = stringToTest.find(",", posLast)) != string::npos) {
string tmpString = stringToTest.substr(posLast, posNext-posLast);
size_t pos;
string employee, manager;
if ((pos = tmpString.find("->")) != string::npos) {
manager = tmpString.substr(0, pos);
employee = tmpString.substr(pos + 2);
myMap.emplace(employee, manager);
}
else {
if (employee1.empty()) {
employee1 = tmpString;
}
}
posLast = ++posNext;
}
employee2 = stringToTest.substr(posLast);
//use this set to keep track of which nodes were visited
unordered_set<string> visited;
//traverse with employee1 and mark all managers as visited unless its employee1 or employee2
auto it = myMap.find(employee1);
while (it != myMap.end()) {
if (it->second != employee1 || it->second != employee2) {
visited.emplace(it->second);
}
it = myMap.find(it->second);
}
//continue searching with employee2 and find traces of employee1's footsteps, ignore instances of employee1 or employee2
string result;
it = myMap.find(employee2);
while (it != myMap.end() ||
it->first == employee1 &&
it->first == employee2) {
//if its visited, we know we found a match
if (visited.find(it->second) != visited.end()) {
result = it->second;
break;
}
it = myMap.find(it->second);
}
cout << result << endl;
return 0;
}
Went back and redid the challenge. This is working code and I tested many edges cases. Should be good to go.
int main()
{
static const string test1 = "Frank->Mary,Mary->Sam,Mary->Bob,Sam->Katie,Sam->Pete,Bob->John,Katie->Steve,Steve,Bob"; //answer = Mary
static const string test2 = "Sam->Pete,Pete->Nancy,Sam->Katie,Mary->Bob,Frank->Mary,Mary->Sam,Bob->John,Pete,John"; // answer = Mary
static const string test3 = "Frank->Mary,Mary->Sam,Mary->Bob,Sam->Katie,Sam->Pete,Bob->John,Pete,Katie"; // answer = Mary
static const string test4 = "Sam->Pete,Pete->Nancy,Sam->Katie,Mary->Bob,Frank->Mary,Mary->Sam,Bob->John,Sam,John"; //answer = Mary
static const string test5 = "Tom->Mary,Mary->Bob,Mary->Sam,Bob->John,Sam->Pete,Sam->Kate,Pete,Kate"; // answer = Sam
//we will reverse the relationship since each employee can have only one manager, we will use a hashmap to represent this
unordered_map<string, string> myMap;
string stringToTest = test3;
string employee1, employee2;
size_t posNext = 0;
size_t posLast = 0;
//parse thru the string
while ((posNext = stringToTest.find(",", posLast)) != string::npos) {
string tmpString = stringToTest.substr(posLast, posNext-posLast);
size_t pos;
string employee, manager;
if ((pos = tmpString.find("->")) != string::npos) {
manager = tmpString.substr(0, pos);
employee = tmpString.substr(pos + 2);
myMap.emplace(employee, manager);
}
else {
if (employee1.empty()) {
employee1 = tmpString;
}
}
posLast = ++posNext;
}
employee2 = stringToTest.substr(posLast);
//use this set to keep track of which nodes were visited
unordered_set<string> visited;
//traverse with employee1 and mark all managers as visited unless its employee1 or employee2
auto it = myMap.find(employee1);
while (it != myMap.end()) {
if (it->second != employee1 || it->second != employee2) {
visited.emplace(it->second);
}
it = myMap.find(it->second);
}
//continue searching with employee2 and find traces of employee1's footsteps, ignore instances of employee1 or employee2
string result;
it = myMap.find(employee2);
while (it != myMap.end() ||
it->first == employee1 &&
it->first == employee2) {
//if its visited, we know we found a match
if (visited.find(it->second) != visited.end()) {
result = it->second;
break;
}
it = myMap.find(it->second);
}
cout << result << endl;
return 0;
}
My above solution doesn't work. Here is my fixed one that finds all grandchildren or underling of each person. Then, it finds which person has both of the conflict employees as grandchildren.
import java.util.*;
public class Main{
public static String test1 = "Frank->Mary,Mary->Sam,Mary->Bob,Sam->Katie,Sam->Pete,Bob->John,Katie->Steve, Steve,Bob";
public static String test2 = "Sam->Pete,Pete->Nancy,Sam->Katie,Mary->Bob,Frank->Mary,Mary->Sam,Bob->John,Pete,John";
public static Map <String, ArrayList<String>> mp = new HashMap<String, ArrayList<String>>();
public static Map <String, ArrayList<String>> grandmp = new HashMap<String, ArrayList<String>>();
public static ArrayList<String> allPeople = new ArrayList<String>();
public static ArrayList<String> visited = new ArrayList<String>();
public static ArrayList<String> managers = new ArrayList<String>();
public static String person1;
public static String person2;
public static boolean found = false;
public static void main(String [] args){
String [] temp = test2.split(",");
//System.out.println(Arrays.toString(temp));
for(int x = 0; x<temp.length-2; x++){
String pair = temp[x];
String [] pairS = pair.split("\\s*(->)\\s*");
//System.out.println(Arrays.toString(pairS));
ArrayList<String> tz;
if(mp.get(pairS[0]) == null) {
tz = new ArrayList<String>();
tz.add(pairS[1]);
mp.put(pairS[0], tz);
}else{
tz = mp.get(pairS[0]);
tz.add(pairS[1]);
mp.put(pairS[0], tz);
}
if(!allPeople.contains(pairS[0])) allPeople.add(pairS[0]);
}
person1 = temp[temp.length-1].replace(" ", "");
person2 = temp[temp.length-2].replace(" ", "");;
if(!allPeople.contains(temp[temp.length-1])) allPeople.add(temp[temp.length-1]);
if(!allPeople.contains(temp[temp.length-1])) allPeople.add(temp[temp.length-2]);
for(int x = 0; x<allPeople.size(); x++){
ArrayList<String> tez = mp.get(allPeople.get(x));
System.out.println(allPeople.get(x) + ", " + tez);
}
for(int x = 0; x<allPeople.size(); x++){
if(found) break;
if(visited.contains(allPeople.get(x))) continue;
ArrayList<String> tez = mp.get(allPeople.get(x));
//System.out.println("ADDING FOR: " + allPeople.get(x));
visited.add(allPeople.get(x));
addChildren(allPeople.get(x), tez, allPeople.get(x));
}
if(managers.size()>1) {
System.out.println("Managers: " + managers);
String cManager = "";
int leastleaves = 0;
for(int i = 0; i< managers.size(); i++){
if(leastleaves == 0) {
leastleaves = grandmp.get(managers.get(i)).size();
cManager = managers.get(i);
}
else if(grandmp.get(managers.get(i)).size() < leastleaves) {
leastleaves = grandmp.get(managers.get(i)).size();
cManager = managers.get(i);
}
}
System.out.println("cManager: " + cManager);
}
}
public static void addChildren(String root, ArrayList<String> tez, String current){
//if(found) return;
//System.out.println("Adding children for root: " + root + " with Children: " + grandmp.get(root) + ", current: " + current + " with Children: " + mp.get(current));;
if(tez == null) return;
if(mp.get(root).contains(person1) && mp.get(root).contains(person2)){
System.out.println("BOSS FOUND: " + root);
if(!managers.contains(root)) managers.add(root);
return;
}
for(int i = 0; i<tez.size();i++){
if(found) return;
//System.out.println("Current check: " + tez.get(i));
if(!mp.get(root).contains(tez.get(i))){
ArrayList<String> tz;
tz = mp.get(root);
tz.add(tez.get(i));
grandmp.put(root, tz);
}
addChildren(root, mp.get(tez.get(i)), tez.get(i));
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace InterviewQuestions.September2016
{
//Programming Challenge Description:
//Develop a service to help a client quickly find a manager who can resolve the conflict between two employees.When there is a conflict between two employees, the closest common manager should help resolve the conflict.The developers plan to test the service by providing an example reporting hierarchy to enable the identification of the closest common manager for two employees.Your goal is to develop an algorithm for IBM to efficiently perform this task.To keep things simple, they just use a single relationship "isManagerOf" between any two employees. For example, consider a reporting structure represented as a set of triples:
//
//Tom isManagerOf Mary
// Mary isManagerOf Bob
//Mary isManagerOf Sam
// Bob isManagerOf John
//Sam isManagerOf Pete
// Sam isManagerOf Katie
//
//The manager who should resolve the conflict between Bob and Mary is Tom(Mary's manager). The manager who should resolve the conflict between Pete and Katie is Sam(both employees' manager). The manager who should resolve the conflict between Bob and Pete is Mary(Bob's manager and Pete's manager's manager).
//
//Assumptions:
//There will be at least one isManagerOf relationship.
//There can be a maximum of 15 team member to a single manager
//No cross management would exist i.e., a person can have only one manager
// There can be a maximum of 100 levels of manager relationships in the corporation
//
//Input:
//R1, R2, R3, R4...Rn, Person1, Person2 R1...Rn - A comma separated list of "isManagerOf" relationships.Each relationship being represented by an arrow "Manager->Person". Person1, Person2 - The name of the two employee that have conflict
// Output:
//The name of the manager who can resolve the conflict Note: Please be prepared to provide a video follow-up response to describe your approach to this exercise.
//
//Test 1:
//Test Input
//Frank-> Mary,Mary->Sam,Mary->Bob,Sam->Katie,Sam->Pete,Bob->John,Bob,Katie
//
//Expected Output
//Mary
//
//Test 2:
//Test Input
//Sam-> Pete,Pete->Nancy,Sam->Katie,Mary->Bob,Frank->Mary,Mary->Sam,Bob->John,Sam,John
//
//Expected Output
//Mary</p>
public class ReportTreeNode
{
public string Name { get; set; }
public List<ReportTreeNode> Reports { get; set; }
public ReportTreeNode Manager { get; set; }
public ReportTreeNode(string name, ReportTreeNode manager)
{
Reports = new List<ReportTreeNode>();
Name = name;
Manager = manager;
if (Manager != null)
{
Manager.AddReport(this);
}
}
public void AddReport(ReportTreeNode toAdd)
{
toAdd.Manager = this;
Reports.Add(toAdd);
}
}
public class ReportTree
{
public ReportTreeNode Root { get; set; }
public ReportTree(ReportTreeNode root)
{
Root = root;
}
public ReportTree(string toParse)
{
Parse(toParse);
}
public ReportTreeNode Find(string name)
{
return Find(name, Root);
}
public ReportTreeNode Find(string name, ReportTreeNode root)
{
ReportTreeNode r = null;
if (name == root.Name)
{
r = root;
}
else
{
foreach (var item in root.Reports)
{
r = Find(name, item);
if (r != null)
{
break;
}
}
}
return r;
}
public ReportTreeNode FindFirstCommonManager(string name1, string name2)
{
ReportTreeNode r = null;
ReportTreeNode first = Find(name1);
if (first != null)
{
if (first.Manager == null)
{
//this guy is the root
r = first;
}
else
{
ReportTreeNode manager = first;
while (manager != null)
{
ReportTreeNode isReport = Find(name2, manager);
if (isReport != null)
{
if (manager == first)
{
r = manager.Manager;
}
else
{
r = manager;
}
break;
}
else
{
manager = manager.Manager;
}
}
}
}
return r;
}
//Sam-> Pete,Pete->Nancy,Sam->Katie,Mary->Bob,Frank->Mary,Mary->Sam,Bob->John,Sam,John
public void Parse(string listOfReports)
{
string[] reports = listOfReports.Split(',');
foreach (var item in reports)
{
string[] relation = item.Split("->".ToArray(),StringSplitOptions.RemoveEmptyEntries);
if (relation.Count() != 2)
{
throw new FormatException();
}
string manangerName = relation[0].Trim();
string reportName = relation[1].Trim();
if (Root == null)
{
Root = new ReportTreeNode(manangerName, null);
ReportTreeNode node = new ReportTreeNode(reportName, Root);
}
else
{
//find manager
ReportTreeNode manager = Find(manangerName);
if (manager == null)
{
//create manager reporting to root
manager = new ReportTreeNode(manangerName, Root);
}
ReportTreeNode report = Find(reportName);
if (report == null)
{
report = new ReportTreeNode(reportName, manager);
}
else
{
report.Manager = manager;
}
}
}
}
}//class
}
def find_manager(rels, emp1, emp2):
for manager,employees in rels.iteritems():
if emp1 in employees:
manager1 = manager
if emp2 in employees:
manager2 = manager
if manager1 == emp2:
return manager1
if manager2 == emp1:
return manager2
if manager1 == manager2:
return manager1
return find_manager(rels, manager1, manager2)
def parse(str):
rels = dict()
for rel in str.split(','):
m,e = rel.split('->')
if m not in rels:
rels[m] = e
else:
rels[m] += ',' + e
return rels
class Hierarchy(object):
class Node:
def __init__(self, token, parent):
self.token = token
self.parent = parent
def get_parents(self, l=None):
l = l or []
if self.parent:
l.append(self.parent.token)
self.parent.get_parents(l)
return l
def __repr__(self):
return "(%s, %s)" % (self.parent, self.token)
def __init__(self, tokens):
self.node_dict = {}
for parent, child in tokens:
if parent not in self.node_dict:
self.node_dict[parent] = self.Node(parent, None)
if child not in self.node_dict:
self.node_dict[child] = self.Node(child, None)
self.node_dict[child].parent = self.node_dict[parent]
def lcp(self, t1, t2):
t1_parents = self.node_dict[t1].get_parents()
for p in self.node_dict[t2].get_parents():
if p in t1_parents:
return p
def __repr__(self):
return repr(self.node_dict)
ip = "Frank->Mary,Mary->Sam,Mary->Bob,Sam->Katie,Sam->Pete,Bob->John,Bob,Katie"
employee1, employee2 = ip.split(',')[-2:]
relationships = [x.split('->') for x in ip.split(',')[:-2]]
print Hierarchy(relationships).lcp(employee1, employee2)
ip = "Sam->Pete,Pete->Nancy,Sam->Katie,Mary->Bob,Frank->Mary,Mary->Sam,Bob->John,Sam,John"
employee1, employee2 = ip.split(',')[-2:]
relationships = [x.split('->') for x in ip.split(',')[:-2]]
print Hierarchy(relationships).lcp(employee1, employee2)
class Hierarchy(object):
class Node:
def __init__(self, token, parent):
self.token = token
self.parent = parent
def get_parents(self, l=None):
l = l or []
if self.parent:
l.append(self.parent.token)
self.parent.get_parents(l)
return l
def __repr__(self):
return "(%s, %s)" % (self.parent, self.token)
def __init__(self, tokens):
self.node_dict = {}
for parent, child in tokens:
if parent not in self.node_dict:
self.node_dict[parent] = self.Node(parent, None)
if child not in self.node_dict:
self.node_dict[child] = self.Node(child, None)
self.node_dict[child].parent = self.node_dict[parent]
def lcp(self, t1, t2):
t1_parents = self.node_dict[t1].get_parents()
for p in self.node_dict[t2].get_parents():
if p in t1_parents:
return p
def __repr__(self):
return repr(self.node_dict)
ip = "Frank->Mary,Mary->Sam,Mary->Bob,Sam->Katie,Sam->Pete,Bob->John,Bob,Katie"
employee1, employee2 = ip.split(',')[-2:]
relationships = [x.split('->') for x in ip.split(',')[:-2]]
print Hierarchy(relationships).lcp(employee1, employee2)
ip = "Sam->Pete,Pete->Nancy,Sam->Katie,Mary->Bob,Frank->Mary,Mary->Sam,Bob->John,Sam,John"
employee1, employee2 = ip.split(',')[-2:]
relationships = [x.split('->') for x in ip.split(',')[:-2]]
print Hierarchy(relationships).lcp(employee1, employee2)
#Develop a service to help a client quickly find a manager who can resolve the conflict between two employees. When there is a conflict between two employees, the closest common manager should help resolve the conflict. The developers plan to test the service by providing an example reporting hierarchy to enable the identification of the closest common manager for two employees. Your goal is to develop an algorithm for IBM to efficiently perform this task. To keep things simple, they just use a single relationship "isManagerOf" between any two employees. For example, consider a reporting structure represented as a set of triples:
#
#Tom isManagerOf Mary
#Mary isManagerOf Bob
#Mary isManagerOf Sam
#Bob isManagerOf John
#Sam isManagerOf Pete
#Sam isManagerOf Katie
#
#The manager who should resolve the conflict between Bob and Mary is Tom(Mary's manager). The manager who should resolve the conflict between Pete and Katie is Sam(both employees' manager). The manager who should resolve the conflict between Bob and Pete is Mary(Bob's manager and Pete's manager's manager).
#
#Assumptions:
#There will be at least one isManagerOf relationship.
#There can be a maximum of 15 team member to a single manager
#No cross management would exist i.e., a person can have only one manager
#There can be a maximum of 100 levels of manager relationships in the corporation
#
#Input:
#R1,R2,R3,R4...Rn,Person1,Person2 R1...Rn - A comma separated list of "isManagerOf" relationships. Each relationship being represented by an arrow "Manager->Person". Person1,Person2 - The name of the two employee that have conflict
#Output:
#The name of the manager who can resolve the conflict Note: Please be prepared to provide a video follow-up response to describe your approach to this exercise.
#
#Test 1:
#Test Input
#Frank->Mary,Mary->Sam,Mary->Bob,Sam->Katie,Sam->Pete,Bob->John,Bob,Katie
#
#Expected Output
#Mary
#
#Test 2:
#Test Input
#Sam->Pete,Pete->Nancy,Sam->Katie,Mary->Bob,Frank->Mary,Mary->Sam,Bob->John,Sam,John
#
#Expected Output
#Mary
ip1="Sam->Pete,Pete->Nancy,Sam->Katie,Mary->Bob,Frank->Mary,Mary->Sam,Bob->John,Sam,John"
ip2="Frank->Mary,Mary->Sam,Mary->Bob,Sam->Katie,Sam->Pete,Bob->John,Bob,Katie"
def conflict(conflict_1,conflict_2,book):
if(book.get(conflict_1)== conflict_2):
return conflict_2
if(book.get(conflict_2)== conflict_1):
return conflict_1
if(book.get(conflict_1)== None):
return conflict_1
if(book.get(conflict_2)== None):
return conflict_2
if(book.get(conflict_1)== book.get(conflict_2)):
return book[conflict_1]
else:
return conflict(book[conflict_1],book[conflict_2],book)
def main(ip1):
sets=ip1.split(',')
l=len(sets)
conflict_1=sets[l-2]
conflict_2=sets[l-1]
i=0
book={}
for i in range(l-2):
[temp1,temp2]=sets[i].split('->')
book[temp2]=temp1
manager=conflict(conflict_1,conflict_2,book)
print(manager)
main(ip1)
main(ip2)
#Develop a service to help a client quickly find a manager who can resolve the conflict between two employees. When there is a conflict between two employees, the closest common manager should help resolve the conflict. The developers plan to test the service by providing an example reporting hierarchy to enable the identification of the closest common manager for two employees. Your goal is to develop an algorithm for IBM to efficiently perform this task. To keep things simple, they just use a single relationship "isManagerOf" between any two employees. For example, consider a reporting structure represented as a set of triples:
#
#Tom isManagerOf Mary
#Mary isManagerOf Bob
#Mary isManagerOf Sam
#Bob isManagerOf John
#Sam isManagerOf Pete
#Sam isManagerOf Katie
#
#The manager who should resolve the conflict between Bob and Mary is Tom(Mary's manager). The manager who should resolve the conflict between Pete and Katie is Sam(both employees' manager). The manager who should resolve the conflict between Bob and Pete is Mary(Bob's manager and Pete's manager's manager).
#
#Assumptions:
#There will be at least one isManagerOf relationship.
#There can be a maximum of 15 team member to a single manager
#No cross management would exist i.e., a person can have only one manager
#There can be a maximum of 100 levels of manager relationships in the corporation
#
#Input:
#R1,R2,R3,R4...Rn,Person1,Person2 R1...Rn - A comma separated list of "isManagerOf" relationships. Each relationship being represented by an arrow "Manager->Person". Person1,Person2 - The name of the two employee that have conflict
#Output:
#The name of the manager who can resolve the conflict Note: Please be prepared to provide a video follow-up response to describe your approach to this exercise.
#
#Test 1:
#Test Input
#Frank->Mary,Mary->Sam,Mary->Bob,Sam->Katie,Sam->Pete,Bob->John,Bob,Katie
#
#Expected Output
#Mary
#
#Test 2:
#Test Input
#Sam->Pete,Pete->Nancy,Sam->Katie,Mary->Bob,Frank->Mary,Mary->Sam,Bob->John,Sam,John
#
#Expected Output
#Mary
ip1="Sam->Pete,Pete->Nancy,Sam->Katie,Mary->Bob,Frank->Mary,Mary->Sam,Bob->John,Sam,John"
ip2="Frank->Mary,Mary->Sam,Mary->Bob,Sam->Katie,Sam->Pete,Bob->John,Bob,Katie"
def conflict(conflict_1,conflict_2,book):
if(book.get(conflict_1)== conflict_2):
return conflict_2
if(book.get(conflict_2)== conflict_1):
return conflict_1
if(book.get(conflict_1)== None):
return conflict_1
if(book.get(conflict_2)== None):
return conflict_2
if(book.get(conflict_1)== book.get(conflict_2)):
return book[conflict_1]
else:
return conflict(book[conflict_1],book[conflict_2],book)
def main(ip1):
sets=ip1.split(',')
l=len(sets)
conflict_1=sets[l-2]
conflict_2=sets[l-1]
i=0
book={}
for i in range(l-2):
[temp1,temp2]=sets[i].split('->')
book[temp2]=temp1
manager=conflict(conflict_1,conflict_2,book)
print(manager)
main(ip1)
main(ip2)
Using an n-ary tree where each node has both a parent pointer as well as a list of children.
import java.util.*;
public class ManagerResolveConflicts {
public static void main(String[] args) {
//String x = "Frank->Mary,Mary->Sam,Mary->Bob,Sam->Katie,Sam->Pete,Bob->John,Katie,Bob";
String x = "Sam->Pete,Pete->Nancy,Sam->Katie,Mary->Bob,Frank->Mary,Mary->Sam,Bob->John,Nancy,Katie";
// Parse the string and create a HM. Also create unique nodes at the same time.
// Go through the HM and for that particular name, find the nodes and set up associations
String[] spl = x.split(",");
String emp1 = spl[spl.length - 2];
String emp2 = spl[spl.length - 1];
Map<String, List<String>> hm = new HashMap<String, List<String>>();
List<String> uniqNames = new ArrayList<String>();
for (String p: Arrays.copyOfRange(spl, 0, spl.length - 2)) {
String mgr = p.split("->")[0];
String emp = p.split("->")[1];
List<String> vals = null;
if (!hm.containsKey(mgr)) {
vals = new ArrayList<String>();
} else {
vals = hm.get(mgr);
}
vals.add(emp);
hm.put(mgr, vals);
if (!uniqNames.contains(mgr)) {
uniqNames.add(mgr);
}
if (!uniqNames.contains(emp)) {
uniqNames.add(emp);
}
}
List<TreeNode> uniqNodes = new ArrayList<TreeNode>();
for (String uniq: uniqNames) {
uniqNodes.add(new TreeNode(uniq));
}
System.out.println("HM: " + hm);
for (TreeNode n: uniqNodes) {
// For each node, put all children in n.children.
List<String> childNames = hm.get(n.name);
if (childNames != null) {
for (String c: childNames) {
n.children.add(new TreeNode(c));
}
}
}
for (TreeNode n: uniqNodes) {
// For each node, traverse the keys to see which key is the parent for n. n.parent is that node.
Set<String> keys = hm.keySet();
for (String k: keys) {
if (hm.get(k).contains(n.name)) {
TreeNode pNode = null;
for (TreeNode tn: uniqNodes) {
if (tn.name.equals(k)) {
pNode = tn;
}
}
n.parent = pNode;
}
}
}
// uniqNodes now has a fully updated list of nodes.
// Traverse this list based on data and see if it matches emp1. Also find emp2.
// 2 situations:
// emp1 and emp2 have a distinct common mgr. Then easy LCA problem.
// One of emp1 and emp2 is in the manager hierarchy. Then, choose that mgr's parent.
// First, check if emp1 is an ancestor of emp2. Then check if emp2 is an ancestor of emp1.
// In these two cases, return the ancestor's parent if not null, as the output.
// If the above check fails, keep checking parent pointers for the node with emp1 and node with emp2.
// If they are equal, return that node's name.
TreeNode e1 = null;
for (TreeNode t: uniqNodes) {
if (t.name.equals(emp1)) {
e1 = t;
}
}
TreeNode e2 = null;
for (TreeNode t: uniqNodes) {
if (t.name.equals(emp2)) {
e2 = t;
}
}
if (e1 == null || e2 == null) {
return;
}
TreeNode temp1 = e1;
while (temp1 != null) {
if (temp1.name.equals(emp2)) {
if (temp1.parent != null) {
System.out.println(temp1.parent.name);
} else {
System.out.println(temp1.name);
}
return;
}
temp1 = temp1.parent;
}
TreeNode temp2 = e2;
while (temp2 != null) {
if (temp2.name.equals(emp1)) {
if (temp2.parent != null) {
System.out.println(temp2.parent.name);
} else {
System.out.println(temp2.name);
}
return;
}
temp2 = temp2.parent;
}
TreeNode te1 = e1;
TreeNode te2 = e2;
List<String> emp1Parents = new ArrayList<String>();
List<String> emp2Parents = new ArrayList<String>();
while (te1.parent != null) {
te1 = te1.parent;
emp1Parents.add(te1.name);
}
while (te2.parent != null) {
te2 = te2.parent;
emp2Parents.add(te2.name);
}
for (String i: emp1Parents) {
if (emp2Parents.contains(i)) {
System.out.println(i);
return;
}
}
return;
}
}
class TreeNode {
String name;
public List<TreeNode> children;
TreeNode parent;
public TreeNode(String name) {
this.name = name;
this.parent = null;
this.children = new ArrayList<TreeNode>();
}
}
Using an n-ary tree with each node having both a parent pointer and a list of children.
import java.util.*;
public class ManagerResolveConflicts {
public static void main(String[] args) {
//String x = "Frank->Mary,Mary->Sam,Mary->Bob,Sam->Katie,Sam->Pete,Bob->John,Katie,Bob";
String x = "Sam->Pete,Pete->Nancy,Sam->Katie,Mary->Bob,Frank->Mary,Mary->Sam,Bob->John,Nancy,Katie";
// Parse the string and create a HM. Also create unique nodes at the same time.
// Go through the HM and for that particular name, find the nodes and set up associations
String[] spl = x.split(",");
String emp1 = spl[spl.length - 2];
String emp2 = spl[spl.length - 1];
Map<String, List<String>> hm = new HashMap<String, List<String>>();
List<String> uniqNames = new ArrayList<String>();
for (String p: Arrays.copyOfRange(spl, 0, spl.length - 2)) {
String mgr = p.split("->")[0];
String emp = p.split("->")[1];
List<String> vals = null;
if (!hm.containsKey(mgr)) {
vals = new ArrayList<String>();
} else {
vals = hm.get(mgr);
}
vals.add(emp);
hm.put(mgr, vals);
if (!uniqNames.contains(mgr)) {
uniqNames.add(mgr);
}
if (!uniqNames.contains(emp)) {
uniqNames.add(emp);
}
}
List<TreeNode> uniqNodes = new ArrayList<TreeNode>();
for (String uniq: uniqNames) {
uniqNodes.add(new TreeNode(uniq));
}
System.out.println("HM: " + hm);
for (TreeNode n: uniqNodes) {
// For each node, put all children in n.children.
List<String> childNames = hm.get(n.name);
if (childNames != null) {
for (String c: childNames) {
n.children.add(new TreeNode(c));
}
}
}
for (TreeNode n: uniqNodes) {
// For each node, traverse the keys to see which key is the parent for n. n.parent is that node.
Set<String> keys = hm.keySet();
for (String k: keys) {
if (hm.get(k).contains(n.name)) {
TreeNode pNode = null;
for (TreeNode tn: uniqNodes) {
if (tn.name.equals(k)) {
pNode = tn;
}
}
n.parent = pNode;
}
}
}
// uniqNodes now has a fully updated list of nodes.
// Traverse this list based on data and see if it matches emp1. Also find emp2.
// 2 situations:
// emp1 and emp2 have a distinct common mgr. Then easy LCA problem.
// One of emp1 and emp2 is in the manager hierarchy. Then, choose that mgr's parent.
// First, check if emp1 is an ancestor of emp2. Then check if emp2 is an ancestor of emp1.
// In these two cases, return the ancestor's parent if not null, as the output.
// If the above check fails, keep checking parent pointers for the node with emp1 and node with emp2.
// If they are equal, return that node's name.
TreeNode e1 = null;
for (TreeNode t: uniqNodes) {
if (t.name.equals(emp1)) {
e1 = t;
}
}
TreeNode e2 = null;
for (TreeNode t: uniqNodes) {
if (t.name.equals(emp2)) {
e2 = t;
}
}
if (e1 == null || e2 == null) {
return;
}
TreeNode temp1 = e1;
while (temp1 != null) {
if (temp1.name.equals(emp2)) {
if (temp1.parent != null) {
System.out.println(temp1.parent.name);
} else {
System.out.println(temp1.name);
}
return;
}
temp1 = temp1.parent;
}
TreeNode temp2 = e2;
while (temp2 != null) {
if (temp2.name.equals(emp1)) {
if (temp2.parent != null) {
System.out.println(temp2.parent.name);
} else {
System.out.println(temp2.name);
}
return;
}
temp2 = temp2.parent;
}
TreeNode te1 = e1;
TreeNode te2 = e2;
List<String> emp1Parents = new ArrayList<String>();
List<String> emp2Parents = new ArrayList<String>();
while (te1.parent != null) {
te1 = te1.parent;
emp1Parents.add(te1.name);
}
while (te2.parent != null) {
te2 = te2.parent;
emp2Parents.add(te2.name);
}
for (String i: emp1Parents) {
if (emp2Parents.contains(i)) {
System.out.println(i);
return;
}
}
return;
}
}
class TreeNode {
String name;
public List<TreeNode> children;
TreeNode parent;
public TreeNode(String name) {
this.name = name;
this.parent = null;
this.children = new ArrayList<TreeNode>();
}
}
def main():
dict = {'frank':['mary'],'mary':['sam','bob'],'sam':['katie','pete'],'bob':['john']}
n1 = 'john'
n2 = 'pete'
flag = 0
while flag != 1:
for k,v in dict.items():
if n1 in v:
n1_man = k
break
for k,v in dict.items():
if n2 in v:
n2_man = k
break
if n1_man == n2_man:
print ('Manager is : {}'.format(n1_man))
flag = 1
elif (n1_man in dict[n2_man]):
print ('Manager is : {}'.format(n2_man))
flag = 1
elif (n2_man in dict[n1_man]):
print ('Manager is : {}'.format(n1_man))
flag = 1
else:
n1 = n1_man
n2 = n2_man
if __name__ == '__main__':
main()
def main():
dict = {'frank':['mary'],'mary':['sam','bob'],'sam':['katie','pete'],'bob':['john']}
n1 = 'john'
n2 = 'pete'
flag = 0
while flag != 1:
for k,v in dict.items():
if n1 in v:
n1_man = k
break
for k,v in dict.items():
if n2 in v:
n2_man = k
break
if n1_man == n2_man:
print ('Manager is : {}'.format(n1_man))
flag = 1
elif (n1_man in dict[n2_man]):
print ('Manager is : {}'.format(n2_man))
flag = 1
elif (n2_man in dict[n1_man]):
print ('Manager is : {}'.format(n1_man))
flag = 1
else:
n1 = n1_man
n2 = n2_man
if __name__ == '__main__':
main()
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
public class IBM_Q2{
public class Graph{
private HashMap<String, ArrayList<String>> adjacent = new HashMap<>();
public void addEdge(String emp, String manager){
ArrayList<String> empList = getList(emp);
empList.add(manager);
}
public ArrayList<String> getList(String vertex){
ArrayList<String> list = null;
if(adjacent.containsKey(vertex))
list = adjacent.get(vertex);
else{
list = new ArrayList<>();
adjacent.put(vertex, list);
}
return list;
}
public String BFS(String v1, String v2){
HashMap<String, Boolean> visit1 = new HashMap<>();
Queue<String> queue1 = new LinkedList<>();
HashMap<String, Boolean> visit2 = new HashMap<>();
Queue<String> queue2 = new LinkedList<>();
queue1.add(v1);
visit1.put(v1, true);
queue2.add(v2);
visit2.put(v2, true);
String collision = null;
while(!queue1.isEmpty() && !queue2.isEmpty()){
collision = search(queue1, visit1, visit2);
if(collision != null)
return collision;
collision = search(queue2, visit2, visit1);
if(collision != null)
return collision;
}
return null;
}
public String search(Queue<String> queue, HashMap<String, Boolean> primary, HashMap<String, Boolean> secondary){
String vertex = queue.poll();
if(secondary.containsKey(vertex))
return vertex;
primary.put(vertex, true);
for(String friend : adjacent.get(vertex))
if(!primary.containsKey(friend))
queue.add(friend);
return null;
}
}
public String findCommonManager(String relations){
Graph graph = new Graph();
String[] tokens = relations.split(",");
for(int i = 0; i < tokens.length - 2; i++){
if(tokens[i].contains("->")){
String[] edges = tokens[i].split("->");
graph.addEdge(edges[1], edges[0]);
}
}
String name1 = tokens[tokens.length - 1];
String name2 = tokens[tokens.length - 2];
return graph.BFS(name1, name2);
}
public static void main(String[] args){
IBM_Q2 tmp = new IBM_Q2();
String relations = "Frank->Mary,Mary->Sam,Mary->Bob,Sam->Katie,Sam->Pete,Bob->John,Bob,Katie";
System.out.println(tmp.findCommonManager(relations));
}
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
public class IBM_Q2{
public class Graph{
private HashMap<String, ArrayList<String>> adjacent = new HashMap<>();
public void addEdge(String emp, String manager){
ArrayList<String> empList = getList(emp);
empList.add(manager);
}
public ArrayList<String> getList(String vertex){
ArrayList<String> list = null;
if(adjacent.containsKey(vertex))
list = adjacent.get(vertex);
else{
list = new ArrayList<>();
adjacent.put(vertex, list);
}
return list;
}
public String BFS(String v1, String v2){
HashMap<String, Boolean> visit1 = new HashMap<>();
Queue<String> queue1 = new LinkedList<>();
HashMap<String, Boolean> visit2 = new HashMap<>();
Queue<String> queue2 = new LinkedList<>();
queue1.add(v1);
visit1.put(v1, true);
queue2.add(v2);
visit2.put(v2, true);
String collision = null;
while(!queue1.isEmpty() && !queue2.isEmpty()){
collision = search(queue1, visit1, visit2);
if(collision != null)
return collision;
collision = search(queue2, visit2, visit1);
if(collision != null)
return collision;
}
return null;
}
public String search(Queue<String> queue, HashMap<String, Boolean> primary, HashMap<String, Boolean> secondary){
String vertex = queue.poll();
if(secondary.containsKey(vertex))
return vertex;
primary.put(vertex, true);
for(String friend : adjacent.get(vertex))
if(!primary.containsKey(friend))
queue.add(friend);
return null;
}
}
public String findCommonManager(String relations){
Graph graph = new Graph();
String[] tokens = relations.split(",");
for(int i = 0; i < tokens.length - 2; i++){
if(tokens[i].contains("->")){
String[] edges = tokens[i].split("->");
graph.addEdge(edges[1], edges[0]);
}
}
String name1 = tokens[tokens.length - 1];
String name2 = tokens[tokens.length - 2];
return graph.BFS(name1, name2);
}
public static void main(String[] args){
IBM_Q2 tmp = new IBM_Q2();
String relations = "Frank->Mary,Mary->Sam,Mary->Bob,Sam->Katie,Sam->Pete,Bob->John,Bob,Katie";
System.out.println(tmp.findCommonManager(relations));
}
}
def closestManager(string):
# split the string into the manager/employee pairs and the two conflicting employees
sepValues = string.split(",")
emp1 = sepValues[-2]
emp2 = sepValues[-1]
# get dictionary of employee and their manager
empManagers = {}
for pair in sepValues[:-2]:
splitPair = pair.split("->")
empManagers[splitPair[1]] = splitPair[0]
# find the closest common manager
orig_emp2 = emp2
while emp1 in empManagers.keys():
manager1 = empManagers[emp1]
emp2 = orig_emp2
while emp2 in empManagers.keys():
manager2 = empManagers[emp2]
if manager1 == manager2:
return manager1
else:
emp2 = manager2
emp1 = manager1
closestManager("Sam->Pete,Pete->Nancy,Sam->Katie,Mary->Bob,Frank->Mary,Mary->Sam,Bob->John,Sam,John") gives the answer "Mary"
The basic is trivial. Here is how to solve it.
- NoOne October 17, 2016// ZoomBA ip1 = "Frank->Mary,Mary->Sam,Mary->Bob,Sam->Katie,Sam->Pete,Bob->John,Bob,Katie" ip = "Sam->Pete,Pete->Nancy,Sam->Katie,Mary->Bob,Frank->Mary,Mary->Sam,Bob->John,Sam,John" values = ip.split(",") mgr = dict( [0: #|values| - 2 ] ) ->{ #(k,v) = values[$.item].split('->') // mgr : employee if ( k @ $.partial ){ $.partial[k] += v }else{ $.partial[k] = list(v) } [k, $.partial[k] ] } emp = [ values[-2] , values[-1] ] //root, the employee who never comes as value as managed rs = mgr.keys - fold ( mgr.values , list() ) -> { $.partial += $.item } assert ( size(rs) == 1 ,'How come multiple Organizations?' ) root = for ( rs ){ $ } // idiomatic extraction of root def get_path (emp, node, path ){ if ( emp == node ) return path if ( !(node @ mgr) ) return '' for ( c : mgr[node] ){ r = get_path ( emp, c, path + '/' + c ) if ( !empty(r) ) return r } return '' } // now find paths and compare :: because every time tree changes x = get_path (emp.0, root, root ) println(x) y = get_path (emp.1, root, root ) println(y) x = x.split('/') ; y = y.split('/') #(n,M) = minmax( #|x| , #|y| ) i = index ( [0:n] ) :: { x[ $.item ] != y[ $.item ] } println ( x[i-1] )