pony.ai四轮挂经

第一轮：1. matrix里面有很多人和一个出口，问离出口最远的人的距离 2. 如何判断一个点是否在三角形内
第二轮：1. 给一个数组和一个阈值，问满足最大最小值之差在阈值内的subarray的最长长度。2. SQL，给了一个查询name的语句，问有什么问题
第三轮：1. 给了一堆含有起点和终点的pair，问这些pair是否能够构成二叉树 2.给了一堆点的横纵坐标，要求找到一个三角形，这个三角形不包含任何其他的点
第四轮: 基础知识，什么都有，计算机网络（三次握手，四次握手），OS（stack和heap），数据库（index），C++，还有系统设计，要求给五子棋设计API，并且还要求写出后端database具体有什么table，每个table有什么column
平常都用python，C++不太会。作为new grad，system design也没太接触过。只能说pony.ai的bar确实很高。
PS：求加大米！谢谢！

对于任意给定的一点P，判断其是否位于△ABC的内部，就是要计算其相对于△ABC的u、v值，只要这两个值满足u>0、 v>0、 u+v<1，那么可以确定点P位于三角形内, u+v=1，那么就在三角形内，u+v>1，那么就在三角形外。 AP=u∗AB+v∗AC。

求问楼主从电面到vo的timeline~

最后挂的原因是什么，面试题没答出来吗？

求问楼主:
第二轮第一题最优解法是什么？O(n)?暂时只想到了O(n^2)方法。
第三轮第一题再给详细说一下？没太明白什么意思。第二题是根据第一轮第二题吗？如果这样的化，枚举任何三点构成三角形，再判断其他店在不在内部，需要(n^3 * n) = O(n^4)复杂度，还有更好的解法吗？
谢谢啦！

knight0clk 发表于 2020-11-26 00:45
求问楼主:
第二轮第一题最优解法是什么？O(n)?暂时只想到了O(n^2)方法。
第三轮第一题再给详细说一下？没 ...

第二轮第一问应该是 https://leetcode.com/problems/lo ... -or-equal-to-limit/

第三轮“给了一堆点的横纵坐标，要求找到一个三角形，这个三角形不包含任何其他的点” ：按照横坐标排序，然后选择连续的三个点（保证三个点不在同一纵坐标）应该就可以吧。

Ethan.Z 发表于 2020-11-12 19:44
最后挂的原因是什么，面试题没答出来吗？

应该是系统设计没达到要求，还有一些多线程的问题没有答好

xiaoxiao0801 发表于 2020-11-27 12:30
第二轮第一问应该是 https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-le ...

是的是的，很可惜我当时面试的时候还没刷过。经过面试官提醒才做出来的。

请问第一轮的1要怎么做？只会遍历