Skyscanner HackerRank questions - Oct 2015 - Backend Developer

question1.md

Find the Most Popular Destination:

Your task is to find the most popular holiday destination from a list of destinations searched for by users. You are given as standard input the integer size of the list, followed by the names of the destinations themselves. The input has the following format:

• on the first line, the count of items in the list
• on the subsequent lines, the name of each destination searched for, one per line (each destination is a single word with no spaces, destinations can be searched for and appear more than once) The input is correct. There is at least one destination in the input. Write a program that reads the input from stdin and then outputs out the name of the most searched for destination i.e. the destination that appears most in the list. One destination is guaranteed to be the outright winner in the input.

Examples:

• Input:

    6
    Barcelona
    Edinburgh
    Barcelona
    Miami
    Miami
    Barcelona

• Output:

    Barcelona

• Input:

    5
    Singapore
    Bangkok
    Singapore
    Bangkok
    Singapore

• Output:

    Singapore

question2.md

Find the Common Manager

You are given as standard input the number of employees in a company, the first names of two selected employees in a company, and the direct line management relations between every employee. Each person in the company can directly line manage a maximum of 2 other employees. The input has the following format: * on the first line, the number of unique employees in the company * on the second line, the name of the first selected employee (a first name only without spaces) * on the third line, the name of the second selected employee (a first name only without spaces, guaranteed to be different from the first selected employee) * on the subsequent lines, the line management relations in the format "EmployeeX EmployeeY" - meaning EmployeeX manages EmployeeY (first names without spaces and spaces are used to separate the two names)

The input is correct (there are only direct line management relations, no cycles, all employees appear in the input). For simplicity, the first line after the selected employees (line 4) always contains the manager at the top of the hierarchy. Write a program that reads the input from stdin and then outputs out the name of the single employee at the lowest point in the hierarchy to which the two selected employees report, either directly or indirectly. If one employee reports to the other, either directly or indirectly, print out the name of the highest of the two selected employees.

Examples:

• Input:

    6
    Hilary
    James
    Sarah Fred
    Sarah Paul
    Fred Hilary
    Fred Jenny
    Jenny James

• Output:

    Fred

• Input:

    4
    Simon
    Claudiu
    Sarah Claudiu
    Sarah Paul
    Claudiu Simon

• Output:

    Claudiu 

• Input:

    5
    Gareth
    Alex
    June Alex
    June Qing
    Qing Paul
    Qing Gareth

• Output:

    June

Is it possible that the second example is wrong?
Sara is the manager of Claudiu and the result have to be Sara, because as the exercise say "print out the name of the highest of the two selected employees."

The first one is easy, I used Counter from Collections, then used the most_common() to return the common item.

@redbass it is correct, because it also says: "If one employee reports to the other, either directly or indirectly, print out the name of the highest of the two selected employees."

Simple Solution to Common Manager Problem

/*

• Solution:
• 1. Build an adjacency list while nabigating from bottom to top
• i.e HashMap<String,String> where key = employee and value = manager
• key->value => employee->manager i.e employee is managed by manager
• 2. No build a parent chain starting from personA till top i.e ceo
• and another starting from personB till top i.e ceo
• 3. check common elements in these two parent chains.
• 4. The first common element will be the nearest common manager. Note that we are using LinkedList
• to build the chain and hence on the leftMost we will always have the nearest manager to each employee

*/

import java.util.*;
public class sky_FindCommonManager {
	
	static HashMap<String,String> adjacencyList = new HashMap<String,String>();
	
	public static void addToAdjacencyList(String a , String b){
		
		if(adjacencyList.isEmpty()){
			adjacencyList.put(a, null); // top employee ceo is managed by nobody
		}
		
		//A to B is A manager B . A manages multiple people
		//But we will create directional Adjacency list B to A i.e B is managed by A
		//B is always managed by directly one person only i.e A
		//Add B to A
		adjacencyList.put(b, a);
	}
	
	public static void buildParentChain(String employee, LinkedList<String> list){
		if(employee==null){ // parent of ceo reached
			return;
		}
		String manager = adjacencyList.get(employee);
		list.add(manager);
		buildParentChain(manager, list); // call for manager to current employee to build chain upto top i.e ceo
	}
	
	public static void findCommonManger(String personA , String personB){
		
		if(adjacencyList.containsKey(personA) && adjacencyList.get(personA).equals(personB)){
			System.out.println(" Result = " + personB);
			return;
		}else if(adjacencyList.containsKey(personB) && adjacencyList.get(personB).equals(personA)){
			System.out.println(" Result = " + personA);
			return;
		}
		
		LinkedList<String> personAParentChain = new LinkedList<String>();
		LinkedList<String> personBParentChain = new LinkedList<String>();
		
		buildParentChain(personA,personAParentChain);
		buildParentChain(personB,personBParentChain);
		
		personAParentChain.retainAll(personBParentChain);
		
		System.out.println(" Result = " + personAParentChain.peek());

	}
	
	public static void main(String[] args) {
		
		Scanner scanner = new Scanner(System.in);
		int numElements = scanner.nextInt();
		scanner.nextLine(); // Move pointer to next Line as nextInt doesn't stops/looks at new line
		String personA = scanner.nextLine();
		String personB = scanner.nextLine();
		while(scanner.hasNextLine()){
			String str = scanner.nextLine();
			if(str.length()>0){
				String a = str.split(" ")[0];
				String b = str.split(" ")[1];
				addToAdjacencyList(a,b);
			}else{
				break; // last line will be empty (after enter symbol a blank line)
			}
		}
		findCommonManger(personA,personB);
	}
}

Looks good. It is supposed to be an exercise in the Tree structure manipulation.

Find the lowest common ancestor:
0) Build the Binary Tree.

1. Find path from root to Person A and store it in an array.
2. Find path from root to Person B and store it in an array.
3. Traverse both paths until the values in the arrays are the same.

mayank5211 answer was good. You skipped the step 0. I like it.

these are my solutions for both Questions: C#
https://github.com/mou2ayad/HackeRrank/tree/master/Dynamic

An even simpler solution

• Uses a map to store the children (reports) of each manager
• Uses another map to store the parent of each manager

After filling them, will start from one of the two, if it has the other among the descendants ok found, otherwise go to the parent and search again.

static boolean contains(Map<String, List<String>> tree, String parent, String descendant) {
        if (parent.equals(descendant)){
            return true;
        }
        List<String> children = tree.get(parent);
        if (children == null){
            return false;
        }
        if (children.contains(descendant)) {
            return true;
        } else {
            for (String child : children) {
                if (contains(tree, child, descendant)) {
                    return true;
                }
            }
            return false;
        }
    }

    public static void main(String args[]) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        bufferedReader.readLine();
        String firstEmployee = bufferedReader.readLine().trim();
        String secondEmployee = bufferedReader.readLine().trim();

        Map<String, List<String>> tree = new HashMap<>();
        Map<String, String> parentMap = new HashMap<>();

        String line;
        while ((line = bufferedReader.readLine()) != null && !line.isEmpty()) {
            String[] pieces = line.trim().split(" ");
            String parent = pieces[0].trim();
            String employee = pieces[1].trim();

            List<String> managed = tree.getOrDefault(parent, new LinkedList<>());
            managed.add(employee);
            tree.put(parent, managed);

            parentMap.put(employee, parent);
        }

        String manager = firstEmployee;
        while (!contains(tree, manager, secondEmployee)){
            if (parentMap.containsKey(manager)) {
                manager = parentMap.get(manager);
            }else{
                System.out.println("not found");
                return;
            }
        }
        System.out.println(manager);
    }

Are the questions still similar/the same in 2019?

The best solution can be done by using something like I did in here, a different problem with similar setting:

static class GraphNode {

        public GraphNode(int content) {
            this.content = content;
        }

        int content = -1;
        List<GraphNode> children = new ArrayList<>();
    }

public static int findCommonAncestor(GraphNode root, int one, int two) {
        List<Integer> list1 = new ArrayList<>();
        trail(root, one, list1);
        List<Integer> list2 = new ArrayList<>();
        trail(root, two, list2);

        int len = Math.min(list1.size(), list2.size());
        int best = -1;
        for (int i = 0; i < len && list1.get(list1.size() - 1 - i) == list2.get(list2.size() - 1 - i); i++) {
            best = list1.get(list1.size() - 1 - i);
        }

        return best;
    }

    private static boolean trail(GraphNode node, int elem, List<Integer> trailList) {
        if (node.content == elem) {
            trailList.add(node.content);
            return true;
        } else {
            if (node.children.stream().anyMatch(n -> trail(n, elem, trailList))) {
                trailList.add(node.content);
                return true;
            } else {
                return false;
            }
        }
    }