Heights of Cats

Question

I have an assignment to solve this problem. However, I have exceeded the time limit required, can anyone suggest where to improve my code?

Cats like to sit in high places. It is not uncommon to see cats climbing trees or furniture in order to lie on the top-most area within their feline reach. Rar the Cat is no exception. However, he does not know how high is one area relative to another.

Height can be measured in centimeters (cm) above sea level but Rar the Cat does not know the absolute height of any place. However, he knows that area B_i will be higher than area A_i by H_i centimetres because he needs to jump H_i to get from area A_i to B_i There will be N areas in total with N-1 such descriptions. Areas are labelled from 1 to N and 0 < A, B ≤ N where A ≠ B. Also, all H_i will satisfy the following range 0 ≤ H_i ≤ 1,000,000.

Rar the Cat also has Q queries, each consisting 2 integers X and Y. He wants to know the height of area Y with respect to area X. Do note that 0 < X, Y ≤ N but X can be equal to Y. In the event that area Y is lower than area X, please output a negative number. Otherwise, output a positive number.

It is guaranteed that the relative heights of all pairs of areas can be computed from the data provided in the input. To be precise, the graph provided will be connected and has N-1 edges connecting N vertices in total.

Input

The first line of input will contain 1 integer, N.

The following N-1 lines of input will contain 3 integers each, with the i-th line containing A_i, B_i and H_i. The next line will contain a single integer, Q.

The following Q lines will contain 2 integers each, X and Y.

Output

For each line of query, you are supposed to output the relative heights of area Y compared to area X, in centimeters, one line per query.
Limits

• 0<N≤100,000 and 0 ≤Q≤100,000

Test Case 1

5
2 3 5
4 2 2
4 1 3
5 2 10
3
1 2
3 5
1 3

Output

-1
-15
4

Explanation for Test Case Area 1 is 3 centimeters above Area 4 while Area 2 is 2 centimeters above Area 4. Hence, Area 2 is 1 centimeters below Area 1.

Area 2 is 10 centimeters above Area 5. Area 3 is 5 centimeters above Area 2 and hence 15 centimeters above Area 5. As such, Area 5 is 15 centimeters below Area 3.

From the first query, Area 2 is 1 centimeters below Area 1. Area 3 is 5 centimeters above Area 2. As such, Area 3 is 4 centimeters above Area 1.

My attempt

import java.util.*;
import java.util.stream.*;

public class Height {
    private void run() {

        Scanner sc = new Scanner(System.in);
        int end = sc.nextInt();
        String clear = sc.nextLine();

        int count; 


        HashMap<Integer,HashMap<Integer,Integer>> map = new HashMap<>();
        //searches the location of all edge using ends in O(1)

        while (true) {//infinite loop because it seems to be waiting on a count command on the new line
            String line = sc.nextLine();
            String[] parts = line.split(" ");


            if (parts.length==1) {//this is a count command to do bfs
                count = Integer.parseInt(parts[0]);
                break;
            }
            int src = Integer.parseInt(parts[0]);
            int dst = Integer.parseInt(parts[1]);
            int dist = Integer.parseInt(parts[2]);

            map.putIfAbsent(src,new HashMap<>());
            HashMap<Integer,Integer> accessed = map.get(src);
            accessed.put(dst,dist);

            map.putIfAbsent(dst,new HashMap<>());
            accessed = map.get(dst);
            accessed.put(src,-dist);
        }



        for (int i=0;i<count;i++) {
            int src = sc.nextInt();
            int dst = sc.nextInt();
            bfs(map,src,dst);
        }


    }


    public static void bfs(HashMap<Integer,HashMap<Integer,Integer>> map, int src, int dst) {

        HashSet<Integer> visited = new HashSet<>();
        visited.add(src);
        Queue<Integer> frontier = new LinkedList<>();
        frontier.add(src);
        Queue<Integer> weights = new LinkedList<>();
        weights.add(0);


        while (!frontier.isEmpty()) {
            src = frontier.poll();
            int beforeMove = weights.poll();//get all weights accumulated so far
            if (src==dst) {
                System.out.println(beforeMove);
                return;
            }

            for (int neighbour : new ArrayList<>(map.get(src).keySet())) {


                if (!visited.contains(neighbour)) {//checks if node is travelled in O(1)
                    visited.add(neighbour);
                    frontier.add(neighbour);

                    weights.add(beforeMove+map.get(src).get(neighbour));
                }


            }
        }
    }



    public static void main(String[] args) {
        Height newHeight = new Height();
        newHeight.run();
    }
}

Answer 1

Code to the interface, not the implementation. It should be very rare to see HashMap or HashSet other than immediately following the keyword new.

        Queue<Integer> frontier = new LinkedList<>();

is good.

        HashMap<Integer,HashMap<Integer,Integer>> map = new HashMap<>();

should be changed to

        Map<Integer,Map<Integer,Integer>> map = new HashMap<>();

---

run is not static: bfs is static. Why?

I would favour making the code more OO: make map a field of the class; add a method addEdge to do the updates to map; make bfs non-static and remove map from its parameters; and rename bfs to something which tells you what it does rather than how it does it, such as processQuery.

---

The input parsing is quite ugly because it doesn't take into account the clear statement of the specification that there will be N-1 edges in the graph. With the refactors suggested in my previous point, it can be as simple as

    private void run() {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        for (int i=0;i<n-1;i++) {
            int src = sc.nextInt();
            int dst = sc.nextInt();
            int dist = sc.nextInt();
            addEdge(src,dst,dist);
        }

        int count = sc.nextInt();
        for (int i=0;i<count;i++) {
            int src = sc.nextInt();
            int dst = sc.nextInt();
            processQuery(src,dst);
        }
    }

---

        Queue<Integer> frontier = new LinkedList<>();
        frontier.add(src);
        Queue<Integer> weights = new LinkedList<>();
        weights.add(0);

As far as I can see, this is a brittle implementation of

Queue<Pair<Integer,Integer>> frontierWithWeights = new LinkedList<>();

Implementing a pair class would be worthwhile for the improved clarity; even abusing Map.Entry<Integer,Integer> would make the code easier to understand.

But actually that's unnecessary. Provided that you store the number of vertices, weights could be an int[].

visited is completely unnecessary because the spec guarantees that the edges form a spanning tree.

---

An alternative approach, which would be faster for some use cases, would be to run the search to completion once such that each query can be processed in constant time.

Answer 2

Your biggest mistake is running the search for every query, a separate query phase almost always means you have to build an intermediate data structure, e.g. an array of height for this problem.

When building a spanning tree, or doing an equivalent operation, use DFS. Do a depth first traversal, starting with node 1 and calculating relative heights as you go. Record these heights in an array. During the query phase look up heights from the array and return their difference.

DFS to BFS is like quicksort to mergesort, don't use BFS unless you have a reason to. Even when traversing infinite graphs DFS with iterative deepening provides better performance.

Note you should use a stack and not recursion for more than a few thousand (a few hundred really) nodes.