Google NYC Onsite 面经

回报地里，两周前的面试，凭借记忆写一下。（在 NYC 参加面试，并非 NYC 的岗位）
第一轮：校友小哥纯聊 research，非常友善，聊完以后还给了名片。

第二轮：号码牌倒置歧义问题：已知有 N 个运动员，每个人有一个号码牌，找出哪些号码上下颠倒以后会有歧义的。

第三轮：给定一个平面上许多点的坐标，找出以其中四个点为顶点可能组成的所有矩形中，最大的矩形的面积。这里矩形只考

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

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

告里。题目本身挺简单，给定一列已经排好序的数字，和一个二次函数 f(x) = ax^2 + bx + c 的三个参数 a, b, c，将序列中的每一个数字用二次函数计算后得到的结果有序输出出来。

tangalai 发表于 2017-11-1 12:48
楼主牛阿。。求稳矩形那个题是怎么做的？，谢谢。

我没有什么特别神奇的做法。大概就是定义两个从 X 到所有 Y，和从 Y 到所有 X 的列表。比如说这样：

1. Map<Integer, List<Integer>> xtoy = new HashMap<>();
   
2. Map<Integer, Set<Integer>> ytox = new HashMap<>();

复制代码

然后对于 xtoy 里每一个 xi 对应的每一对 (yi, yj)，在 ytox 里查找对应的 ytox.get(yi) 和 ytox.get(yj) 有没有比 xi
大的其他 x 的交集。如果有就计算一次面积。

franD 发表于 2017-11-5 13:05
请问LZ第五题什么思路呢? 就是扫一遍数组,把每个数当做x带入然后计算结果输出,然后排序吗

二次函数分两个单调区间，所以根据二次函数的开口方向，可以用双指针从两边依次取更小（大）的数，向中间挪动，并将新的数插入到结果的最后（前）面，扫描依次就可以了。
@siranjoy119 提到 generalize 到 n 阶多项式的情况，感觉思路也可以是求导数为 0 时 X 的值，将区间分为 K 段，每段分别求最小值并移动指针吧

第二题是Strobogrammatic Number吧
第三题可以用hashset把所有的点都存进去，然后任取两点作为矩形的对角点，然后check另一条对角线的两点在不在hashset中，在的话更新最大面积，O(n^2)
第四题 Word ladder I
第五题我电面也遇到了同样的题，他还说generalize到n阶多项式怎么办。原来这人是某组tech lead啊。。。失敬失敬。。

谢谢楼主分享。
第三轮 四点 要两两平行于坐标轴才能算矩形？

edyyy 发表于 2017-11-1 12:19
谢谢楼主分享。
第三轮 四点 要两两平行于坐标轴才能算矩形？

对的，这样把问题简化了不少。需要主动问这个 clarification question。

第二题不是非常理解意思。楼主能举个例子吗？谢谢！

大懒懒一休哥 发表于 2017-11-2 03:21
第二题不是非常理解意思。楼主能举个例子吗？谢谢！

假设有 800 个运动员，对于号码是 169 的人， 如果号码牌上下颠倒了，就是 691，所以是一个有歧义的号码。找出所有这样的号码。

要注意的是像 101 这样的数字是没有歧义的。然后 696 其实也不会有歧义，因为倒过来 969 超出 800 人这个范围了。

论坛匿名用户 发表于 2017-11-2 09:32
假设有 800 个运动员，对于号码是 169 的人， 如果号码牌上下颠倒了，就是 691，所以是一个有歧义的号码 ...

猴！谢谢楼主回复！

感谢LZ分享！
请问号码牌是等长的吗，还是没有前导0？