uber电面

发一道uber的电面，之前好像没有在网上看到过

题目是在二维平面上给定一组两个点的相对位置，需要判断这组相对位置是否可以被满足

一共

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

, 3 N 4
    Expected output: True

我觉的根据例子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?

这题我觉得沿着南北和东西方向做两次topological sort就可以了，只要没发现loop就是true

                • 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.

是不是拿hashmap 存一个point的object, 每个point存相对x,y

请问楼主，内推之后等了多久拿到面试？ 需要自己去找组吗？

感觉复杂点的做法就是每进来一条数据，更新所有点对于点的相对位置？有更好的方法么

这个题就是将第一个位置设定0, 0,然后给每个点根据信息设定坐标，并且放到Hashmap吧，如果发现坐标都在hashmap中，就判断位置是不是合理

gavinzhang 发表于 2016-1-30 05:02
是不是拿hashmap 存一个point的object, 每个point存相对x,y

嘿嘿 小伙 你也要面uber啦?进去了吗？

detect loop只能解决critical error，但是如果出现A NE B 和 C NE B， A和C的位置可能是 A N/S/E/W/NE/SE/NW/SW C的任意一种，这是一个问题，不知道楼主有没有问面试官？

其实最简单的就是存点的相对距离
比如 a （0，0）
a n b
那么b 就是（-1，0）
最后判断是否相对位置正确即可
至于是否出现loop 看新生成的位置是否与set里的位置一致 否则false

traceroute_su 发表于 2016-4-12 11:16
其实最简单的就是存点的相对距离
比如 a （0，0）
a n b

这个不太对吧，比如1 N 2, 2 S 3, 怎么判断1， 3？