/*
# Suppose we have a series of people relationships that looks something like this:
# [ ['Bart', 'brother', 'Lisa' ],
# ['Bart', 'son', 'Homer' ],
# ['Marge', 'wife', 'Homer' ],
# ['Lisa', 'daughter', 'Homer' ] ]
#
# i.e. inner lists have len == 3 and are in form name1, relationship, name2
#
# Given a series of relationships as a list of lists, and given two names, return
# all known "sequences" of relationships from name1 to name2
#
# e.g. with the lists above as input, with input names 'Bart' and 'Homer', you should return:
# ['Bart son Homer', 'Bart brother Lisa daughter Homer']
#
*/
给你一堆string 都是relationship 然后给你两个名字 找出两个人之间的所有关系 通过别人也好
follow up1:
follow up2:
follow up3:
今天recruiter告诉我 move forward with onsite
public class Solution {
public static void main(String args[] ) throws Exception {
List<List<String>> rel = new ArrayList<>();
rel.add(Arrays.asList("Bart", "brother", "Lisa"));
rel.add(Arrays.asList("Bart", "friend", "Lisa"));
rel.add(Arrays.asList("Bart", "son", "Homer"));
rel.add(Arrays.asList("Marge", "wife", "Homer"));
rel.add(Arrays.asList("Lisa", "daughter", "Homer"));
getRel(rel, "Bart", "Homer").forEach(x -> System.out.println(x));
}
private static List<String> getRel(List<List<String>> relations, String first, String second) {
List<String> res = new ArrayList<>();
if (relations == null || relations.size() == 0 || first == null ||first.length() == 0|| second == null || second.length() == 0) return res;
if (first.equals(second)) return Arrays.asList(first+" self "+second);
Map<String, List<String[]>> graph = new HashMap<>();
for (List<String> rel: relations) {
if (rel.get(0).equals(rel.get(2))) continue;
graph.computeIfAbsent(rel.get(0), x -> new ArrayList<>()).add(new String[] {rel.get(2), rel.get(1)});
}
if (!graph.containsKey(first)) return res;
dfs(first, second, graph, res, new StringBuilder(), new HashSet<>(), new HashMap<>());
return res;
}
private static void dfs(String first, String second, Map<String, List<String[]>> graph, List<String> res, StringBuilder sb, Set<String> visited, Map<String, List<String>> cached) {
if (!visited.add(first)) return; //if this person has been visited, means there is a loop
if (cached.containsKey(first)) {
int n = sb.length();
for(String no: cached.get(first)) {
res.add(sb.append(" "+no).toString());
sb.setLength(n);
}
return;
}
if (first.equals(second)) {
visited.remove(first);
res.add(sb.append(first).toString());
String[] arr = sb.toString().split(" ");
for (int i = 0; i < arr.length;i+=2) {
int ind = sb.indexOf(arr[i]);
cached.computeIfAbsent(arr[i], x-> new ArrayList<>()).add(sb.toString().substring(ind, sb.length()));
}
return;
}
List<String[]> next = graph.get(first);
if (next == null) return;
sb.append(first);
int len = sb.length();
for (String[] n: next) {
sb.append(" "+n[1]+" ");
dfs(n[0], second, graph, res, sb, visited, cached);
sb.setLength(len);
}
visited.remove(first);
}
}
Xavier
21 August 2019 23:02
6
这题用DFS的话有个complication，如果你到了已经visited的node，因为我们并不是找最短路径，我们还需要加上这个path，举个例子
起点是A，终点是G
然后我们通过 A -> E -> F -> H -> D, 这个时候我们已经visited过D了，那么，A -> E -> F -> H -> D -> G 是否算到结果里呢？
visited.remove(first);
Xavier
21 August 2019 23:33
10
你这样感觉还是有问题，等于visited 过的，就忘了（全局）
就是要忘了，你要找出所有relationship 从a 到 b啊
e.g. with the lists above as input, with input names ‘Bart’ and ‘Homer’, you should return:
[‘Bart son Homer’, ‘Bart brother Lisa daughter Homer’]
Xavier
21 August 2019 23:39
15
你这个visited set不是global的，你再想想我说的例子
起点是A，终点是G
然后我们通过 A -> E -> F -> H -> D, 这个时候我们已经visited过D了，那么，A -> E -> F -> H -> D -> G 是否算到结果里呢？
A->B->C->D->G
第一次走完D的时候 我已经把D从visited里面去掉了啊
A -> B -> C ->D -> G VISITED: A B C D G
Xavier
21 August 2019 23:52
18
再改复杂一点
A -> B -> C ->D -> J -> G
上次到D的时候，你其实知道D到 G的路径了
love
22 August 2019 21:18
20
也报一个二面。内推的。