Skyscanner Interview Question Software Engineers
Country: United Kingdom
I started using a btree for this like the solution above, but since we are limited to two employees per manager, it is easier to just create a list of managers with two employees.
class Manager
{
String name;
String firstEmployee = "";
String secondEmployee = "";
Manager(name, firstEmployee)
{
this.name = name;
this.firstEmployee = firstEmployee
}
Manger(name)
{
this.name = name;
}
}
main()
{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String s;
while (s= in.ReadLine() != null and s.length >0 )
{
int numPairs = Integer.parseInt(s);
List<Manager> managers = new ArrayList();
Manager man = null;
for (int i=0; i<numPairs; i++)
{
s = in.readLine();
String[] names = s.split(" ");
if (man == null || !(man.name).equal(names[0]))
{
if (man != null)
{
managers.add(man);
}
man = new Manager (names[0], names[1]);
}
else ((man.name).equal(names[0])
{
man.secondEmployee = name[1];
}
if (i == numPairs-1)
{
managers.add(man);
}
}
for(Manager man: managers)
{
System.out.println(man.Name);
if (man.firstEmployee.length >0)
{
System.out.println(man.firstEmployee + " " + man.secondEmployee);
}
}
}
}
I don't think you need a btree since this is only one level deep and you can only have two employees per manager. A btree seems like a bit of an overkill
class Manager
{
String name;
String firstEmployee = "";
String secondEmployee = "";
Manager(name, firstEmployee)
{
this.name = name;
this.firstEmployee = firstEmployee
}
Manger(name)
{
this.name = name;
}
}
main()
{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String s;
while (s= in.ReadLine() != null and s.length >0 )
{
int numPairs = Integer.parseInt(s);
List<Manager> managers = new ArrayList();
Manager man = null;
for (int i=0; i<numPairs; i++)
{
s = in.readLine();
String[] names = s.split(" ");
if (man == null || !(man.name).equal(names[0]))
{
if (man != null)
{
managers.add(man);
}
man = new Manager (names[0], names[1]);
}
else ((man.name).equal(names[0])
{
man.secondEmployee = name[1];
}
if (i == numPairs-1)
{
managers.add(man);
}
}
for(Manager man: managers)
{
System.out.println(man.Name);
if (man.firstEmployee.length >0)
{
System.out.println(man.firstEmployee + " " + man.secondEmployee);
}
}
}
}
For some reason I couldn't get this to accept my code, but the solution above is a bit complex. Since you have the restrictions of only one level deep with a two employee limit per manager. Just create a list of Manager object with strings of firstEmployee and secondEmployee. Figure out whether you need a new manager and what string to write to. After you finish the first list print that list and start with the second list (you know exactly how many are in each list).
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
import static treeproblems.Solution.getHierarchy;
public class Solution {
static class Node
{
String data;
Node left;
Node right;
Node() {}
Node(String data)
{
this.data=data;
}
}
static Node rootNode = null;
public static void levelOrderTraversal(Node startNode) {
Queue<Node> queue=new LinkedList<Node>();
Queue<Node> nextLevel=new LinkedList<Node>();
queue.add(startNode);
while(!queue.isEmpty())
{
Node tempNode=queue.poll();
System.out.print(tempNode.data + " ");
if(tempNode.left!=null)
nextLevel.add(tempNode.left);
if(tempNode.right!=null)
nextLevel.add(tempNode.right);
if(queue.isEmpty()) {
System.out.println();
while(!nextLevel.isEmpty()) queue.add(nextLevel.poll());
}
}
}
static void treeInsert(Node node, String name1, String name2){
if(node == null) return;
if(node.data.equals(name1))
{
if(node.left == null) {
node.left = new Node(name2);
return;
} else {
node.right = new Node(name2);
return;
}
}
treeInsert(node.left, name1, name2);
treeInsert(node.right, name1, name2);
}
static void getHierarchy(int n, Scanner in) {
rootNode = new Node();
for(int i= 0; i< n; i++) {
String line = in.nextLine();
String[] names = line.split(" ");
if(i ==0) rootNode.data = names[0];
treeInsert(rootNode, names[0], names[1]);
}
levelOrderTraversal(rootNode);
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int _n;
_n = Integer.parseInt(in.nextLine());
getHierarchy(_n, in);
}
}
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
import static treeproblems.Solution.getHierarchy;
public class Solution {
static class Node
{
String data;
Node left;
Node right;
Node() {}
Node(String data)
{
this.data=data;
}
}
static Node rootNode = null;
public static void levelOrderTraversal(Node startNode) {
Queue<Node> queue=new LinkedList<Node>();
Queue<Node> nextLevel=new LinkedList<Node>();
queue.add(startNode);
while(!queue.isEmpty())
{
Node tempNode=queue.poll();
System.out.print(tempNode.data + " ");
if(tempNode.left!=null)
nextLevel.add(tempNode.left);
if(tempNode.right!=null)
nextLevel.add(tempNode.right);
if(queue.isEmpty()) {
System.out.println();
while(!nextLevel.isEmpty()) queue.add(nextLevel.poll());
}
}
}
static void treeInsert(Node node, String name1, String name2){
if(node == null) return;
if(node.data.equals(name1))
{
if(node.left == null) {
node.left = new Node(name2);
return;
} else {
node.right = new Node(name2);
return;
}
}
treeInsert(node.left, name1, name2);
treeInsert(node.right, name1, name2);
}
static void getHierarchy(int n, Scanner in) {
rootNode = new Node();
for(int i= 0; i< n; i++) {
String line = in.nextLine();
String[] names = line.split(" ");
if(i ==0) rootNode.data = names[0];
treeInsert(rootNode, names[0], names[1]);
}
levelOrderTraversal(rootNode);
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int _n;
_n = Integer.parseInt(in.nextLine());
getHierarchy(_n, in);
}
}
And in Python..
import sys
# Get input
num_employees = int(sys.stdin.readline())
select1 = sys.stdin.readline().strip()
select2 = sys.stdin.readline().strip()
connections = list(map(lambda s: s.strip(), sys.stdin.readlines()))
root = connections[0].split()[0]
def parentof(node):
for line in connections:
parent, child = line.split()
if node == child:
return parent
def child_to_root_chain(child):
line = ' %s' % child
current = child
while current != root:
parent = parentof(current)
line += ' %s' % parent
current = parent
return line.lstrip()
def common_string(s1, s2):
s1_reversed = s1[::-1]
s2_reversed = s2[::-1]
for i in range(min(len(s1), len(s2))):
if s1_reversed[i] != s2_reversed[i]:
return s1_reversed[:i-1][::-1]
if len(s1) > len(s2):
return s2
else:
return s1
# Get hierarchy chains from selected nodes to root
line1 = child_to_root_chain(select1)
line2 = child_to_root_chain(select2)
print(common_string(line1, line2).split()[0])
private static void lineManagement(String[][] input) {
Map<String, List<String>> whoManagesWhom = new HashMap<>();
for (int i = 0; i < input.length; i++) {
whoManagesWhom.computeIfAbsent(input[i][0], (na) -> new ArrayList<>(2))
.add(input[i][1]);
}
String boss = input[0][0];
List<String> current = Collections.singletonList(boss);
while (!current.isEmpty()) {
System.out.println(current);
current = current.stream()
.flatMap(name -> whoManagesWhom.getOrDefault(name, Collections.emptyList()).stream())
.collect(toList());
}
}
private static void lineManagement(String[][] input) {
Map<String, List<String>> whoManagesWhom = new HashMap<>();
for (int i = 0; i < input.length; i++) {
whoManagesWhom.computeIfAbsent(input[i][0], (na) -> new ArrayList<>(2))
.add(input[i][1]);
}
String boss = input[0][0];
List<String> current = Collections.singletonList(boss);
while (!current.isEmpty()) {
System.out.println(current);
current = current.stream()
.flatMap(name -> whoManagesWhom.getOrDefault(name, Collections.emptyList()).stream())
.collect(toList());
}
}
Construct a map and find roots
Use BFS to traverse
- kn February 03, 2015public class EmployeeHierarchy { public static void main(String[] args) throws IOException, URISyntaxException { List<String> lines = Files.readAllLines(Paths.get(new URI("file:/home/ketav/Workspaces/careercup/Test/src/careercup/coding/EmployeeList.txt"))); Map<String, Set<String>> tree = new HashMap<>(); Set<String> employees = new HashSet<>(); Set<String> roots = new HashSet<>(); for(int i=1;i<lines.size();i++){ String arr[] = lines.get(i).split(" "); if(!tree.containsKey(arr[0])){ tree.put(arr[0], new HashSet<>()); } tree.get(arr[0]).add(arr[1]); if(!employees.contains(arr[1])) { employees.add(arr[1]); } if(!employees.contains(arr[0])){ roots.add(arr[0]); } else { roots.remove(arr[0]); } } //thus roots contain root elements .. now you can use BFS (using queue to) to print employees at each level. printBFS(tree, roots); } public static void printBFS(Map<String, Set<String>> graph, Set<String> roots){ Queue<String> queue = new LinkedList<>(roots); Set<String> visitedNodes = new HashSet<>(); printBFS(graph, queue, visitedNodes); } private static void printBFS(Map<String, Set<String>> graph, Queue<String> queue, Set<String> visitedNodes){ int size = queue.size(); if(size==0) return; for(int i=0; i<size; i++){ String name = queue.poll(); if(!visitedNodes.contains(name)){ System.out.print(name+" "); if(graph.get(name)!=null) queue.addAll(graph.get(name)); visitedNodes.add(name); } } System.out.println(""); printBFS(graph, queue, visitedNodes); } }