Recovering a Hash Path?

Question

I tried to figure out how to find the O (n) time complexity algorithm to solve the following in Java :

We are given an input pair with a start point and an end point, and we must build such a path so that the beginning of one input matches the end of another input (in this case, in alphabetical order)

EX: if I have a list

PB
BM
OP
Mz

where PB or BM are pairs, P is the starting point, and B is the end

I have to create as output

OP
PB
BM
Mz

And, of course, I want to check the cycles - in this case, I just let you know if there is a cycle.

The first time I tried to do this, I used the swap algorithm, which was O (N ^ 2), basically replacing two entries if there was a match and moving down the list. There is definitely a faster way to do this, and I understand semi-intuitively how to do it, but I was wondering if anyone could clarify it a bit.

Basically, I assume that you need to create some type of hash / key of the structure, where you can refer to the value of the object itself using the key.

For example, you would save two collections, one from the start and one from the ends. You can take each input and create an object with a start and end field, and then add all the start and end values ​​to two arrays. Then you will need to basically find the end of [start] for each start and add its corresponding object to the list after they are searched.

My only thing, I cannot figure out exactly how to implement this in Java using a hash table or some similar data structure. Should I add start and end values ​​to separate hash tables and then use start points as search keys?

Pseudo code from looking at who solved it in python on github:

for inputs parse input add parse[1] to starts, add parse[2] to ends for starts find origin (a start not in ends) <--requires hash? if no origin cycle exists for inputs find ends[origin] <--requires hash? origin = ends[origin] <-- so we can find the next one 

I wonder if someone can help me translate this into an algorithm in Java (other effective solutions are very welcome, as I am interested in this type of problem solving) or more understandable in this regard from the point of view of data structure.

Answer 1

Here's a simple implementation using HashMaps in Java:

  String[][] paths = { {"P", "B"}, {"B", "M"}, {"O", "P"}, {"M", "Z"}, }; // create a single hash map, mapping start->end HashMap<String, String> end = new HashMap<>(); for(int i = 0; i < paths.length; i++) { end.put(paths[i][0], paths[i][1]); } // find if a cycle exists String origin = null; for (String key : end.keySet()) { if(!end.containsValue(key)) { origin = key; break; } } if(origin == null) { System.out.println("cycle exists"); return; // no origin found, cycle exists } // iterate over hash map: int count = 0; while(true) { if(!end.containsKey(origin)) break; String next = end.get(origin); System.out.println(origin + " " + next); origin = next; if(++count > paths.length) { System.out.println("cycle exists"); break; } } 

end saves the end point (value) based on the start point (key).

If a point exists as a start point, but not an end point, it will be the key in end , but not the value in end . Thus, iterating over the key set end and checking whether end contains each key, how the value will find the beginning. If there is no such origin, then there is a cycle. However, this is not enough to determine if a cycle exists, because a cycle may exist, even if there is an origin. Consider this set:

 PBBM OP MZ ZM 

There is a unique origin (O), but there is also a cycle M → Z → M. To discover this, you can walk around the set and follow what you have already visited, or, more simply, you can walk the set, and if you are in in the end, you visit more points than the input length, then there should be a cycle.

To go through the set, set the line to the origin. Then continue looking for the value at end indicated by origin as the key, and print the key, value pair (origin, end.get (origin)) as the beginning, the end. Then set end.get (origin) as the new source. The loop ends when there is no value for the current source at the end of the HashMap.

This algorithm fails if there are duplicate start or end positions in the list, for example:

 PBBM OP MZ BZ 

It is unclear whether you need to handle this case.

Answer 2

Although I would prefer to create a structure with a similar list with something like

 class Node { String name; Node prev; Node next; } 

nevertheless, you can do this only with the help of a map (only HashMap, if you want).

It is similar to the answer from @samgak, just with some tricks that can make your code look shorter (not necessarily faster, didn't test it):

 String[][] rawPaths = { {"P", "B"}, {"B", "M"}, {"O", "P"}, {"M", "Z"}, }; // 1. You can keep only one `Map<String, String> which keeps start as key and end as value. Map<String, String> pathMap = new HashMap<>(); for (String[] path : rawPaths) { pathMap.put(path[0], path[1]); } // 2. Some validity checks for data: // 2.1 No of entry in final Map should equals to number of lines in raw data, which means there is no duplicated "start" node. assert pathMap.size() == rawPaths.length; // 2.2 There should be no duplicate in "end", ie no partial cyclic path assert new HashSet<>(pathMap.values()).size() == rawPaths.length; // 2.3 there should be one and only one start value that does not exists in end values, ie no full cyclic path Set<String> startPoints = new HashSet<>(pathMap.keySet()); startPoints.removeAll(pathMap.values()); assert startPoints.size() == 1; //3. Then you can make up the path by getting the "head" which is the only value left in startPoints, and construct the full path String start= startPoints.iterator().next(); while (pathMap.contains(start)) { String end = pathMap.get(start); System.out.println(start + " " + end); start = end; } 

There may be times when there is a cyclic path on the island as follows:

 AB BC CD XY YX 

This can be easily verified by going through part 3, saving the counter, and the counter should be the same as pathMap.size() . If not, there is a cyclic island