一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1740|回复: 10
收起左侧

Uber电面,非常规题,求解答……

[复制链接] |试试Instant~ |关注本帖
neostar2008 发表于 2016-2-14 05:50:30 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Uber - 猎头 - 技术电面 |Fail在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
最近面Uber Pool team(应该翻译成拼车组?),遇到了非常诡异的一道电面题,看版上貌似没有帖出来过,放出来和大家讨论一下,希望大牛们给个高效的解法
.1point3acres缃
面试题背景包装的非常复杂,我尽量简洁叙述,就是刚开始有第一个乘客requester要搭车,给出发点original point的[latitude, longitude] 和 destination的[latitude, longitude]。于是就有了这趟行程current route最初的两个点 Point_start 和 Point_end。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

然后现在有一个List<Requester>, 每一个Requester都有一个起始点original point和destination point。要求把符合要求的requester加入到current route里去。比如现在有个Requester  r1 起点和终点是 P_start_1, P_end_1, 而且P_start_1, P_end_1都在 [P_start, P_end]之间,所以加入r1后,current route 就变成了[ P_start, P_start_1, P_end1, P_end]

.1point3acres缃
注意:这个list里所有requester都是想carpool,加赛的,所以规定后来的Requester的起点和目的地都在Point1 和Point2之间。


然后给了一个API。int  QueryEngine.getDistance(Point p1, Point p2).   这个API返回任意两个点之间所花费的用时, 用时O(1)。


-google 1point3acres然后问题是: 给了初始乘客Requester r0 (知道他的起点, 终点), 然后给一个 List<Requester>, 问这个list里的requester可以有多少人加入到current route里来?按顺序返回最终的route里的point

. From 1point 3acres bbs
. 鍥磋鎴戜滑@1point 3 acres




. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
然后我就和面试官讨论,虽然List<Requester> 里的人已经事先确定在[P_start, P_end] 之间,但是加入的requester多了,原先的近直线路线会变得越来越曲折,花费时间会越来越多,所以定个要求,加入新requester后如果花费总时间小于等于原来的150%,就确认加入,否则放弃(150%是个例子,可以configurable)。. 1point 3acres 璁哄潧
.鏈枃鍘熷垱鑷1point3acres璁哄潧
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
然后对于每一个Requester r_i,他有起始点 P_start_i 和目的地 P_end_i,  我的方法是对于current route [P_start, P_start_1, P_end1, ....., P_end], 计算P_start_i 和 P_end_i  距离出发点P_start的距离,按照这个距离用类似binary search的方法插入到对应到位置去,同时保证P_start_i 要在P_end_i 前面。. 1point3acres.com/bbs




我也觉得这个方法很不好,但当时想不出更好的方法,于是便毫无疑问的挂了…… 挂的倒挺不甘心的,很不常规的一道题,大家有什么思路吗?  




评分

2

查看全部评分

wwk55551111 发表于 2016-2-14 08:37:16 | 显示全部楼层
而且P_start_1, P_end_1都在 [P_start, P_end]之间. more info on 1point3acres.com
是指?
回复 支持 反对

使用道具 举报

 楼主| neostar2008 发表于 2016-2-14 09:32:09 | 显示全部楼层
wwk55551111 发表于 2016-2-14 08:37
而且P_start_1, P_end_1都在 [P_start, P_end]之间
是指?

就是P_start_1, P_end_1 不会离 P_start, P_end 太远。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
可以理解为P_start_1, P_end_1 在 以P_start, P_end为对角线两端点围成的矩形里面。
回复 支持 反对

使用道具 举报

guixi107 发表于 2016-2-14 09:34:21 | 显示全部楼层
hmm, 可以把每次request算作一个一维的Interval, 新来的request(interval)被最开始的interval完全覆盖才加进来, 然后把所有的合法的request按照其实时间排序?

不知道可不可以把request当作1d interval?
回复 支持 反对

使用道具 举报

guixi107 发表于 2016-2-14 09:36:03 | 显示全部楼层
neostar2008 发表于 2016-2-14 09:32
就是P_start_1, P_end_1 不会离 P_start, P_end 太远。 . 1point 3acres 璁哄潧

可以理解为P_start_1, P_end_1 在 以P_start ...

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷P_Start和P_End是2个点,怎么构建矩形?
回复 支持 反对

使用道具 举报

 楼主| neostar2008 发表于 2016-2-14 10:15:42 | 显示全部楼层
guixi107 发表于 2016-2-14 09:36
P_Start和P_End是2个点,怎么构建矩形?
. From 1point 3acres bbs
以这两个点为 对角线上两个顶点,可以构建一个矩形
回复 支持 反对

使用道具 举报

guixi107 发表于 2016-2-14 11:10:26 | 显示全部楼层
neostar2008 发表于 2016-2-14 10:15
以这两个点为 对角线上两个顶点,可以构建一个矩形

hmm, 矩形有多大呢?
2点没法确定一个矩形啊
回复 支持 反对

使用道具 举报

a6219221 发表于 2016-2-14 12:00:48 | 显示全部楼层
想到两个点:
1. 如果是要你排出最短的路径感觉是变形的TSP问题
2. 另外一辆车上可以同时坐3个乘客 所以是不是也要考虑一下同时有三个人在车上的问题 不然就不是car pool了
回复 支持 反对

使用道具 举报

3angFeng945 发表于 2016-3-3 03:57:07 | 显示全部楼层
I think the returned list length should be limited to 4 or 5, becourse there only 4 or 5 seats in a car.

If original requester is R1(P1st, P1ed)

The added requester R2(P2st, P2ed) should meets these requirements:. more info on 1point3acres.com

1 QueryEngine.getDistance(Point p1st, Point p2st) < QueryEngine.getDistance(Point p1st, Point p1ed)
2 QueryEngine.getDistance(Point p2st, Point p1ed) < QueryEngine.getDistance(Point p1st, Point p1ed)
3 QueryEngine.getDistance(Point p2ed, Point p1ed) < QueryEngine.getDistance(Point p1st, Point p1ed). 鍥磋鎴戜滑@1point 3 acres
4 QueryEngine.getDistance(Point p2st, Point p2ed) < QueryEngine.getDistance(Point p1st, Point p1ed). Waral 鍗氬鏈夋洿澶氭枃绔,

You can go through the arraylist of requester, and compare every requester with the first requester. If the new requester meets the requirements, add it to the list. This is O(n).

Before outputing the list, we need to sort the request by the distance between the p1st and pnthst. I think this should be a constant time, because the length of the returned list is 4 or 5.
回复 支持 反对

使用道具 举报

Fustang 发表于 2016-3-25 21:25:23 | 显示全部楼层
楼上的方法可能有些过于constrained了 我有一个思路,是对夹角和距离分别排序
Intuitively, 第一个人是(start_0, end_0); 如果pool的人(start_i, end_i)也是去同一个方向,并且start_i和start_0, 以及end_i和end_0离的都不太远,那么就是适合拼车的。. 鍥磋鎴戜滑@1point 3 acres
best situation就是拼车人的start,end之间的斜率等于start_0, end_0之间的斜率;也就是在start, end组成的直线上。

用一下点乘的方法可以从pool available point中得到和start_0的夹角并对其排序 - 取出前几个夹角小的(方向相近)
然后对|start_i-start| + |end_i-end|进行排序 - 选取这个measure最小的几名乘客
回复 支持 反对

使用道具 举报

traceroute_su 发表于 2016-4-8 12:28:43 | 显示全部楼层
首先向请问楼主一个问题
如果两个requester
1. requester1 (p1,p2)
2. requester2(p3,p4)
如果出现 p1<p2<p3<p4 意思是p2在p1和p3之间 p3在p2和p4之间 那么 我们需要不要加入requester2 这是第一个问题
第二个问题,我们如何知道p2,p3在p1,p4之间,需要我们自己写方法还是给了API

solution:  这道题于lc上max point on line非常像 不同的是我上面提出的两个问题如何解决
lc上max point on line是基于斜率 而现在我们的标准基于是否点在矩形面积内(左上与右下两点可确定矩形)。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
知道了上两个问题的答案就知道 到底如何解决这个问题

所以归根结底 我认为这题的核心在于考矩阵是否相交,或者矩阵是否包含的意思 当然根据题意不同 结果也不同
这仅是我个人观点 欢迎讨论
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 13:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表