Google Intern Conversion Onsite Interview

8.15 google intern return的两轮背靠背 白板coding interview

第一题：
有一个显示屏，给定长度和宽度。同时有一行只含字母的字符串，每个字符的大小与其对应的font-size有关，font-size范围从0到100。
Question: fon

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

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

没米了没米了没米了没米了没米了没米了没米了没米了没米了没米了没米了没米了没米了没米了没米了没米了没米了没米了没米了没米了没米了没米了没米了没米了没米了没米了没米了没米了没米了没米了没米了没米了

812015941 发表于 2019-8-31 15:52
第二题bfs+dp+backtrack?想知道带parent的bfs怎么做的

带parent的意思就是在你bfs对一个node的所有邻居进行扩张的时候，用一个parent map去记住每一个新node的来源node。

带parent的意思就是在你bfs对一个node的所有邻居进行扩张的时候，用一个parent map去记住每一个新node的来源node。

请问楼上，node的所有邻居的parent不就是node本身吗？

记录了parent map请问要怎样使用呢？

论坛匿名用户 发表于 2019-9-2 06:25
带parent的意思就是在你bfs对一个node的所有邻居进行扩张的时候，用一个parent map去记住每一个新node的 ...

这样就直接根据目标地点的parent找祖先们，找到了最后的路径？

楼主牛X！（DCGG tql了！！ 我也要去GG!!!
在上课时间会这个帖子的我怕不是铁憨憨

mattaysm 发表于 2019-8-29 03:41
楼主牛X！（DCGG tql了！！ 我也要去GG!!!
在上课时间会这个帖子的我怕不是铁憨憨

你也真的是个大天才

第一题二分？
第二题带parent的BFS？

楼主第一题啥方法做的呀

bwbwbw 发表于 2019-8-30 10:36
第一题二分？
第二题带parent的BFS？

没错！！！zszszszs

oyster 发表于 2019-8-31 00:22
楼主第一题啥方法做的呀

第一题就先做一个check函数看一行字符串能不能放进屏幕，然后二分找到最大的font-size

论坛匿名用户 发表于 2019-8-31 04:11
第一题就先做一个check函数看一行字符串能不能放进屏幕，然后二分找到最大的font-size

好的 谢谢 开始理解成字符串不同字母也可以不同font size了

第一题感觉是个二分。第二题bfs，followup 最短路（n>0)的话。

第二题bfs+dp+backtrack?想知道带parent的bfs怎么做的