Google NG VO 大概率挂经

今天刚面的， 一轮BQ+三轮Coding。感觉自己还是刷的不够多（只有两百多道），答题还比较生疏。因为个人原因自己压力也比较大可能只能去icc了。第一轮：BQ
第二轮：定义一个add(x, y) 添加一个点到平面上，返回是否有其余三个点能与之组成正方形。
这道题还是很简单的，直接DFS就OK了， 面试官是个很好的白人，也提前说了没有follow up。

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

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

解后不了了之了。


补充内容 (2022-06-09 06:24 +8:00):
06/08 Update: Recruiter 通知我可以team match了。。。

最后一题想了一下 可以用BFS 最多只有24*60= 1440的node需要visit
栗子的话23:59 = 1439， 00:02 = 2
从0开始
step = 0: { 0 }
step = 1: { 1439, 2 }
step = 2: { 1438, 1, 4}
step = 3: { 1437, 3, 6}
-------------------------
所以返回3

努力奋斗的小乔 发表于 2022-5-27 14:55
求问第三轮和第四轮题目的具体描述，第三轮那个同学描述的有点抽象，楼主可以给个例子吗？
第四轮follow u ...

第三轮的题目就是相当于给你一个log history， 每一条history 记录 三个东西: LogID, timestamp, Start/End. 记录是按照timestamp排序的。差不多是这个样子:
LogID    timestamp   Start/End1          1                   Start
2           2                 Start
1           3                 End
2           7                 End
3         8                  Start
3         9                 End
这里假如timeout 是 4 的话 log 2就timeout了，返回true。
第四轮 那个follow up 的意思是现在button 数量不固定了，不是像原题那样写死的。他给的例子第一个button 是advance 23小时59分， 第二个button是advance 2分钟，要求往后调3分钟。最优解肯定是往后调两分钟两次之后再往后调23小时59分 一次（等于往前调一分钟）。还有一个例子就是[0, 3] [0, 4] 要往后调6分钟，这个的最优解就是按第一个button两次

求问第三轮和第四轮题目的具体描述，第三轮那个同学描述的有点抽象，楼主可以给个例子吗？
第四轮follow up的例子调三分钟为什么是第一个按钮两次第二个按钮一次呀？第一个和第二个按钮是1分钟和5分钟没错吧,意思是这个follow up是时钟还可以往前调了么？而且说add button的数量不定是指什么意思呢？原始问题求最小操作数add button的数量不相当于也没定吗？感谢！

最后一题有点像蠡口Coin Change那道题 用dp做

可以问一下第二轮用dfs怎么做吗

请问一下第二题有没有例子呀，也想问一下DFS的思路，感谢~

匿名用户 发表于 2022-05-26 00:38:01
请问一下第二题有没有例子呀，也想问一下DFS的思路，感谢~

枚举与add的点同边的点就行了吧，两点之间的距离就是正方形的边长.然后根据add点是正方形的4个顶点的情况就能直接算出剩下点的位置

Pyy12134 发表于 2022-5-26 06:47
枚举与add的点同边的点就行了吧，两点之间的距离就是正方形的边长.然后根据add点是正方形的4个顶点的情况 ...

正方形可能有角度啊。

www熙 发表于 2022-5-25 17:52
最后一题有点像蠡口Coin Change那道题 用dp做

可以展开讲一下吗？

能问下楼主电话面试后多久约VO吗？

匿名者 发表于 2022-5-26 05:28
正方形可能有角度啊。

遍历O（n2)的解法，任选2个点，满足 （dotproduct（(x,y) - (x1,y1）,  (x,y)-(x2,y2)), 如果==0, and distance相同，再找有没有  第四个点。

匿名者 发表于 2022-5-26 05:28
正方形可能有角度啊。

interviewer 说只考虑没有角度的情况