wish 店面

Job Hunting Interview
, , , ,
1

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 relatipnships as a list of lists, and given 2 names, return all known “sequances” of relationships from name1 to name2.

Example:
Input: relationships =[[“Bart”, “brother”, “Lisa”], [“Bart”, “son”, “Homer”], [“Marge”, “wife”, “Homer”],[“Lisa”, “daughter”, “Homer”]], name1 = “Bart”, name2 = “Homer”
Output: [“Bart son Homer”, “Bart brother Lisa daughter Homer”]

2

看起来是个graph的问题，类似 evaluate division

3

更像 BFS 的 word ladder

参考

4

试着写了下代码

import java.util.*;

public class relation {

	public static List<String> relationship(String[][] relationships, String name1, String name2, Set<String> visited) {
		Map<String, Map<String, String>> reMap = new HashMap<>();
		List<String> result = new ArrayList<>();
		for (String[] re : relationships) {
			reMap.computeIfAbsent(re[0], k -> new HashMap<>()).put(re[2], re[1]);
		}
		if (!reMap.containsKey(name1)) {
			return result;
		}	
		else {
			visited.add(name1);
			Map<String, String> valMap = reMap.get(name1);
			for (String k : valMap.keySet()) {
				if (visited.contains(k) && k != name2) {
					continue;
				} else {
					visited.add(k);
					if (k.equals(name2)) {
						result.add(name1 + " " + valMap.get(k) + " " + name2);
					} else {
						for (String str: relationship(relationships, k, name2, visited)) {
							result.add(name1 + " " + valMap.get(k) + " " + str);
						}
						
					}
				}	
			}
		}	
		return result;
	}

	public static void main(String[] args) {
		String[][] rel = {
			{"Bart", "brother", "Lisa"},
			{"Bart", "son", "Homer"},
			{"Marge", "wife", "Homer"},
			{"Lisa", "daughter", "Homer"},
			{"Lisa", "daughter", "Marge"},
			{"Marge", "daughter", "Mary"},
			{"Mary", "mother-in-law", "Homer"},
			{"Mary", "grandaughter", "Lisa"}
		};
		String name1 = "Bart";
		String name2 = "Homer";
		Set<String> visited = new HashSet<String>();

		for (String s : relationship(rel, name1, name2, visited)) {
			System.out.println(s);
		}
               
 
		/*output
		Bart son Homer
		Bart brother Lisa daughter Marge wife Homer
		Bart brother Lisa daughter Marge daughter Mary mother-in-law Homer
		Bart brother Lisa daughter Homer
		*/
	}
}
5

同意

6

你用的是DFS

7

这行是多余的，而且你不应该调用 relationship 方法两次

2 Likes
8 
                if (k.equals(name2)) {
					result.add(name1 + " " + valMap.get(k) + " " + name2);
				} else {
					for (String str: relationship(relationships, k, name2)) {
						result.add(name1 + " " + valMap.get(k) + " " + str);
					}
				}

这段代码是说你找到终点就停止尝试了吗？题目意思是说即使有更长的path到终点，还是需要尝试的

9

个人觉得这种dfs写法不是很对，可能有bug
你dfs就存一个visited的set，并放一个trace back的map - 存的是 <to, from>，就是每次往前走的 from 和 to
这是标准的dfs写法

10

这题其实就是经典的graph traversal，亚麻高频的从机场A 去 机场B的路径也是一样的做法

11

这里的意思是回溯找出所有非直接的关系，k是一个中间节点，所有的结果之前加上name1以及name1 和k的关系

12

是有bug，没有判断是否存在loop

13

嗯，我还是建议你用标准的DFS traversal 写法，一个visited的set + 一个trace back的map
这也是面试官熟悉的

1 Like
14

最终打印出路径就用这个trace back的map，从终点往起点走

参考word ladder里这段代码

	private List<List<String>> generateList(String start, String end, Map<String, List<String>> map, List<String> sol,
			List<List<String>> res) {
		if (start.equals(end)) {
			sol.add(start);
			res.add(new ArrayList<>(sol));
			sol.remove(sol.size() - 1);
			return res;
		}

		List<String> words = map.get(start);
		if (words == null) {
			return res;
		}

		sol.add(start);
		for (String word : words) {
			generateList(word, end, map, sol, res);
		}
		sol.remove(sol.size() - 1);
		return res;
	}
15

我觉得bug出现在if else， 即使是true的情况下，else里的逻辑也还是需要执行的

16

之前没有把visited set 作为参数传入recursive function, 所以一直 stack overflow, 现在好像对了

1 Like
17

这题用DFS的话有个complication，如果你到了已经visited的node，因为我们并不是找最短路径，我们还需要加上这个path，举个例子

起点是A，终点是G
DFS 先找到一个可行路径
A -> B -> C -> D -> G

然后我们通过 A -> E -> F -> H -> D, 这个时候我们已经visited过D了，那么，A -> E -> F -> H -> D -> G 是否算到结果里呢？

18

这里visited不是一个全局变量，它只是用来保证每条路径上不出现loop， A --> B 和 A --> E 是两个不同的路径上的recursive function, 彼此visited变量相互独立，所以我认为没有影响。另外我例子里面Marge这个节点就类似D那样的地位

19

全局还是需要判断是否有visited过吧，我记得这是亚麻那道高频题的followup
你可以存每个node的哪些neighbor已经visit过了（从这个node出发），这样避免再次访问

20

嗯我再想想这个问题，多谢了！