uber电面

comicrudy 发表于 2016-4-13 18:33
这个不太对吧，比如1 N 2, 2 S 3, 怎么判断1， 3？

我觉得1，3无法判断

我觉的根据例子2
(2)Input :  4 SE 5, 5 SW 3, 3 N 4
    Expected output: True

这个题可能是假设距离的单位都是1吧，要不然这个2）是没法判断true的。比如是4 在(0,0), 5 在（1，-1），3在(1,1), 那么3 N 4 是true，如果3在(2,2), 3和是4 关系是 3 NE 4?

hkc593 发表于 2016-4-14 02:07
我觉的根据例子2
(2)Input :  4 SE 5, 5 SW 3, 3 N 4
    Expected output: True

我觉得这个理解是对的！！应该相对距离，n,e,w,s距离都是1， ne,nw,se,sw的距离应该都是sqrt（2）。
对于1n2，3n2这种情况，我认为1，2，3的坐标应该是（0，0），（0，－1），（0，0）
具体方法，我觉得就是设置第一个出现的点的坐标为0，0，然后其他的点如果在hashmap里面没有出现过，那么就是hashmap其实是最好的做法

harryhu0705 发表于 2016-4-17 04:38
我觉得这个理解是对的！！应该相对距离，n,e,w,s距离都是1， ne,nw,se,sw的距离应该都是sqrt（2）。
对 ...

这个方法感觉是对的，必须假设东西南北距离是1，不然没法判断，TOPOLOGY SORT什么都没用

                • Construct two graphs, one for x-coordinate--Gx, one for y-coordinate--Gy. 
                • For Gx, If x1 < x2, then we have an edge from x1->x2, if x1 > x2, one edge x1<-x2. If x1 == x2, combine x1 and x2 together. 
                • In the end, we check whether there exists a cycle in Gx or Gy. If this is true, then the answer is impossible. 
                • To detect a back edge, we can keep track of vertices currently in recursion stack of function for DFS traversal. If we reach a vertex that is already in the recursion stack, then there is a cycle in the tree. The edge that connects current vertex to the vertex in the recursion stack is back edge. We have used recStack[] array to keep track of vertices in the recursion stack.

wangxinbo1123 发表于 2017-1-3 09:19
• Construct two graphs, one for x-coordinate--Gx, one for y-coordinate--Gy. 
                • ...

我觉得你的方法很好，但是
If x1 == x2, combine x1 and x2 together.
这个部分，岂不是要union find来实现，不过好想也真实没什么其他办法了