完全被虐死了,中间恨不得把电话给扔了。
下面说说过程,首先说明,全程面试官从来没说过我的任何回答是对还是错,我下面的
回答可能很多是错的。
一个西亚或者印度(口音不太像)面试官 A,一开始聊了一下background,然后丫说先
给你一道简单题做做吧,就是一楼的题。
一开始,听到二维平面,最多点,斜率,还以为是那到最多点共线的问题呢?心中一喜
,然后自己重复问题的时候,A 感觉完全不知道我在说什么。丫又重复了一遍问题,这
时才听懂。
当时第一反应是对一个维度排序,然后DP,说给A听了。
A:时间复杂度是多少?
me: O(n^2)
A: 不行,要nlog(n)。
me: (心理一紧,完蛋了,DP都不行)嘴上说好像可以剪枝。
A: How?
me: (心理说我怎么知道),胡说半天,说什么用tree啦,找parent啦,连我自己都不知
道在说什么。
A: 好吧,假设你有2维的nlogn的算法了,3维怎么办?
me: 先找一个2维最多的点集,再对这个点集的第3维在做一次这个算法。
A: M维怎么办?
me: 依次类推。
A: 时间复杂度多少?
me: 大概是最坏是m*n*logn吧。
A: 太慢了,你能不能再想办法提高速度。
me: (心理想,我连nlogn的算法都不知道,怎么提高速度,刚想回答不知道,突然想
到)可以并行。
A: 怎么并行?
me: 比如3维 (x0,x1)和(x0,x2)分别找,然后求交集。
A: M维的时候,怎么办?
me: 一样啊,(x0, x1),(x0, x2), (x0, x3)....(x0, xm),然后求交集。
A: 你要多少个并行?
me: M-1个。
A: 用什么design pattern?
me: boss/employer, peer, blablabla。
A: 要减少并行规模,你有什么方法吗?
me: (想了半天)可以减到M/2个,比如(x0, x1), (x2, x3).... ,然后再交集。
A: 还是太高了,还有什么方法?
me: (想了半天)可以((x0,x1),x2),((x3,x4),x5)之类的,
A: 用的什么design pattern?
me: pipeline(废话,唯一一个没说的)。
A: 如果处理过程中,突然加一个维度,怎么办?
me: 再多做一遍呗。
A: 如果处理过程中,突然想drop掉其中一维不用,怎么办?
me: (想扔电话了)那部分的job重新做。
A: 如果n太大,不能一次读入,怎么办?
me: 分块读入,然后再做。
A: 说的具体点....
me: (想把电话扔到丫脸上去)blabla,我都不知道自己胡说些什么。
然后又聊了一下别的,就结束了。