Thumbtack new grad 电面

国人小哥面试官，上来自我介绍，介绍完项目实习都没问直接上题，online coding pad (hackerrank)
利特扣得 356, 给一组2D平面上的点，找是否存在一条平行于y轴的线可以镜像分割2侧的点

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

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

恭喜楼主过了店面，关于follow up 1和2我各有一个问题，误差e的范围（比如说0.0002的误差都可以看成相等)，但是没有理解“把每个数round到最近的e之内“，比如当前x=0.9999, 那么应该是找[0.9997， 1.0001] 范围的点的x存不存在。第二个follow up里面如果对称轴不是平行于x或者y轴的直行，那么原问题的答案思路就没法套用，因为此时对称点的x值和y值都会不一样，而且他们之间的对称规律不是简单的x=max+min-current_x,而是相似三角型的规律，即如果P1(x1, y1), P2(x2,y2)对称，P3(x3, y3), P4(x4, y4)对称，则有：|x1-x2|/|y1-y2| = |x3-x4|/|y3-y4|

follow up 1我后面仔细想想确实有点问题，round的意思是比如1之内都能看成相等，那1.2和1.8都round到最近的1之内则是1&2，这样就有问题了, 但当时我没想那么多，面试官也没在意就直接follow up 2了。follow up 2的话首先你能确定n - 1种可能的slope, 知道slope之后套用原题，确实不能照搬，但思路是差不多的，针对这个slope确定min和max然后公式就generalize到整个2d平面。不过你不需要担心那么多。。他2个follow up总计没讲过8分钟，这种不可能让你写code的，只是想知道你的思路细节不重要的

hahahazgz 发表于 2019-10-18 13:30
请问楼主昂塞题目难吗？

签了NDA不敢细说，1个面经题，1个很简单的图论，最后栽在白人manager那一轮coding上了，题不难但是很烦很难理解，思路讲清楚3个loop嵌套，但每个的terminate condition都很不一样而且很复杂，当时脑子一抽就没写出来，再加上面试官脚翘在桌子上什么话也不说一句，最后就因为这轮fail了

楼主最后过了吗？另外楼主没被问到过calender的那道题吗

torez 发表于 2019/10/02 09:16:14
楼主最后过了吗？另外楼主没被问到过calender的那道题吗

在等消息，onsite被问了calendar

请问followup3，这种做法为什么不是n的立方时间复杂度。
因为有n方的可能性划分线，然后每种要用n来检验。
乘起来应该是立方啊

Katherine_ME 发表于 2019-10-10 05:05
请问followup3，这种做法为什么不是n的立方时间复杂度。
因为有n方的可能性划分线，然后每种要用n来检验。 ...

假设你有n个点[1, 2 ... n], 你可以fix随便一个点k, 那所有slope就是剩下n - 1个点和k本身pair出来的结果，再套第一问所以是(n -1) * n = O(n^2)

请问楼主昂塞题目难吗？

bukbuk 发表于 2019-10-18 13:37
签了NDA不敢细说，1个面经题，1个很简单的图论，最后栽在白人manager那一轮coding上了，题不难但是很烦很 ...

谢谢楼主！！！希望楼主继续求职顺利！！！