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

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