/*
4. 给你一串input，比如：
A -> B
B -> C
X -> Y
Z -> X
。
。
。
然后让你设计一个data structure来存这些关系，最后读完了以后呢要输出这些关系链：[A -> B -> C, Z -> X -> Y]
如果遇到invalid的case就直接raise error，比如你已经有了A->B->C，这时候给你一个D->C或者B->D就是invalid的。
followup我感觉就是他看你什么case没有cover就提出来然后问你怎么改你的代码和data structure
比如遇到A->B两次，再比如遇到环
这题相当开放，面试官说他遇到过4，5种不同的解法，总之就是最好保证insert是O(1), reconstruct是O(n)
补充内容 (2018-11-19 01:02):
第四题好像说是关系链有点误导大家，它题目的意思更像是directed graph，然后每次读进来的都是一条edge，要求是你的graph里只能有链条，不能有branch，不能有cycle，所以假设你有A->B->C，这时候又来了一个A->C算错
*/
public class Main {
public static void main(String[] args) {
String[] strs = {"A -> B", "B -> C", "X -> Y", "Z -> X"};
try{
Solution s = new Solution();
s.insert(strs);
s.reconstruct();
//System.out.println("Hello World!");
}
catch(Exception e){
e.printStackTrace();
}
}
}
class Solution{
class Node {
char val;
Node pre;
Node next;
public Node(char v){
val = v;
}
}
HashMap<Character, Node> map= new HashMap<>();
HashSet<Character> roots = new HashSet<>();
public void insertSingle(String str) throws Exception{
String[] strs = str.split(" -> ");
char parent = strs[0].charAt(0);
char child = strs[1].charAt(0);
//check parent side
Node pNode = null;
if(!map.containsKey(parent)){
pNode = new Node(parent);
map.put(parent, pNode);
roots.add(parent);
}
else{
if(map.get(parent).next != null && map.get(parent).next.val != child){
throw new Exception("multiple children!");
}
pNode = map.get(parent);
}
//check child side
Node cNode = null;
if(!map.containsKey(child)){
cNode = new Node(child);
map.put(child, cNode);
}
else{
if(map.get(child).pre != null && map.get(child).pre.val != parent){
throw new Exception("multiple parents!");
}
if(roots.contains(child)){
roots.remove(child);
}
cNode = map.get(child);
}
pNode.next = cNode;
cNode.pre = pNode;
}
public void insert(String[] strs) throws Exception{
for(String str : strs){
insertSingle(str);
}
}
//cycle will be detected here by adding an array to check if the node is visited or not.
public void reconstruct() throws Exception{
for(char root : roots){
Node node = map.get(root);
while(node != null){
System.out.print(node.val);
node = node.next;
}
System.out.println("");
}
}
}