## IBM Interview Question for Software Engineer / Developers

Country: United States

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

The basic is trivial. Here is how to solve it.

``````// 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] )``````

Comment hidden because of low score. Click to expand.
0

Hello NoOne,

Thank you very much for your response. Could you please post the answer either in Java or Python???

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

``````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)){
emp = map.get(emp);
}
return stringArray;
}

}``````

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

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

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;
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);
}
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);
employee.Manager = manager;
}
else
{
// Employee managersManager = employees.FirstOrDefault(item=> item.Key == e)
Employee mananager = new Employee(employeeManager[0], null);
Employee employee = new Employee(employeeManager[1], 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;
ForEachdirectReorts(ceo, ceo.Rank + 1);
}

private static void ForEachdirectReorts(Employee emp, int rank)
{
foreach (var item in emp.DirectReports)
{
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>();
}
}

}

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

``````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>();
mp.put(pairS[0], tz);
}else{
tz = mp.get(pairS[0]);
mp.put(pairS[0], tz);
}
}
String person1 = temp[temp.length-1].replace(" ", "");
String person2 = temp[temp.length-2].replace(" ", "");;

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

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

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

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

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

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

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

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

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

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

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

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

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>();
mp.put(pairS[0], tz);
}else{
tz = mp.get(pairS[0]);
mp.put(pairS[0], tz);
}
}
person1 = temp[temp.length-1].replace(" ", "");
person2 = temp[temp.length-2].replace(" ", "");;

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));
}
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);
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);
grandmp.put(root, tz);
}
}
}
}``````

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

``````using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

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

{
}
}

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

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

``````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``````

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

``````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)``````

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

``````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)``````

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

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

``````#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)``````

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

#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)

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

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);
}
hm.put(mgr, vals);
if (!uniqNames.contains(mgr)) {
}
if (!uniqNames.contains(emp)) {
}
}

List<TreeNode> uniqNodes = new ArrayList<TreeNode>();
for (String uniq: uniqNames) {
}
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) {
}
}
}
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;
}

while (te2.parent != null) {
te2 = te2.parent;
}

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

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

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);
}
hm.put(mgr, vals);
if (!uniqNames.contains(mgr)) {
}
if (!uniqNames.contains(emp)) {
}
}

List<TreeNode> uniqNodes = new ArrayList<TreeNode>();
for (String uniq: uniqNames) {
}
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) {
}
}
}
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;
}

while (te2.parent != null) {
te2 = te2.parent;
}

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

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

``````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()``````

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

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()

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

``````import java.util.ArrayList;
import java.util.HashMap;
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);
}
public ArrayList<String> getList(String vertex){
ArrayList<String> list = null;
else{
list = new ArrayList<>();
}
return list;
}
public String BFS(String v1, String v2){
HashMap<String, Boolean> visit1 = new HashMap<>();
HashMap<String, Boolean> visit2 = new HashMap<>();

visit1.put(v1, true);
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);
if(!primary.containsKey(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("->");
}
}

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

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

``````import java.util.ArrayList;
import java.util.HashMap;
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);
}
public ArrayList<String> getList(String vertex){
ArrayList<String> list = null;
else{
list = new ArrayList<>();
}
return list;
}
public String BFS(String v1, String v2){
HashMap<String, Boolean> visit1 = new HashMap<>();
HashMap<String, Boolean> visit2 = new HashMap<>();

visit1.put(v1, true);
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);
if(!primary.containsKey(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("->");
}
}

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

}

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

``````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``````

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.

### 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.

### 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.

### 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.