Pony.ai onsite new grad面经

已经不太记得了,现在写下。

  1. 给你几个质数,他们作为分母的所有分数,然后找出第k小的分数,大概就是比如质数2,3,5。那么就有1/2, 1/3, 2/3, 1/5, 2/5, 3/5, 4/5, 那么第2小就是1/3。然后还有follow up就是如果k很大的时候,怎么解。
  2. 维护一个中位数。先要支持add和get。做完后要支持remove。remove真的难想,就一直靠面试官提示。
  3. 给一堆(x, y)的二维坐标,每一个坐标对应一个整形的score。以原点为圆心的,会有很多圆存在。需要找出一个圆,使得这个圆内的(包括圆上)所有score的和最大。
  4. 最后一面,上来先出了一个概率题,是在一个圆上随机取三个点,连起来是个钝角三角形的概率。然后是给我一个int数组,让我最后把奇数index的值都比偶数位的大。实在想不出O(n)的解,就直接说我不会,然后出了个islands的变种。dfs就可以解决。

四轮,题贼难,还带病面试,希望能有好结果。

这原点,很多点在一个圆内,score有正有负,我也不知道所有情况

补充内容 (2018-11-6 03:20):
特么这都能有2个踩,???

1 Like

第四题可以quick select找中间的数,然后就可以o(n)了

高产似母猪hh

like [1,2,3,4,5,6,7,8]要变成[1,5,2,6,3,7,4,8]这种形式,但是我也不知道是不是我理解错了

这里是写C++?

大多数人用C++,我用JAVA面的

这家onsite真少,lz 牛逼~

1题 n sorted list 找kth?2题对复杂度什么要求?

2题 two priority queue 再加一个multiset存删除的数字可以试一下

4题 int数组那个没看懂

谢谢分享~

第四题 利口 散而思?

不太是。。