楼主: wjxtank2010
跳转到指定楼层
上一主题 下一主题
收起左侧

Google Youtube Onsite面经

全局:
wjxtank2010 发表于 2018-1-20 14:03
可能的,挡板位置不固定,你这么一说我想了下binary search好像确实有点问题,那就只能一个一个往 ...

是不是应该,对每一块板,对于前面的板子,如果他们有overlap, 就更新加上板长,然后得到最小值,没有overlap的话就是Integer.MAX_VALUE,最后直接更新为高度,因为最优情况肯定是没有overlap直接跳到平地的?
回复

使用道具 举报

🔗
 楼主| wjxtank2010 2018-1-21 02:39:41 | 只看该作者
全局:
sophietian1024 发表于 2018-1-20 10:21
是不是应该,对每一块板,对于前面的板子,如果他们有overlap, 就更新加上板长,然后得到最小值,没有ove ...

嗯嗯是这样,字数字数
回复

使用道具 举报

🔗
619899442 2018-1-21 05:02:31 | 只看该作者
全局:
请问楼主第二题的follow up是怎么答的呀?
回复

使用道具 举报

🔗
619899442 2018-1-21 05:28:33 | 只看该作者
全局:
还想请教楼主第四题是不是只需要考虑一种字体,每个字符的高度宽度可能不同,求出可能的最大字号?
回复

使用道具 举报

🔗
RebortZhang 2018-1-21 06:10:23 | 只看该作者
全局:
请问楼主第二轮的worse case的优化怎么答得
回复

使用道具 举报

🔗
 楼主| wjxtank2010 2018-1-21 08:55:16 | 只看该作者
全局:
619899442 发表于 2018-1-20 13:02
请问楼主第二题的follow up是怎么答的呀?

假设event的总数为N, 我最开始的思路是用queue, 每当有新的event的时候就放到queue尾,然后从queue的头部开始比对event是不是outdated, 如果是就pop出去,最后判断下queue的长度是不是长于n, 这样的话amortized时间复杂度是O(1),但是worst case下时间和空间均可能为O(N), 优化完的思路为每次把新的event放到队尾后,如果queue的长度大于n,就一直pop到n个为止,然后判断queue的头有没有outdated, 这样space不会超过n, worst case时间复杂度也是O(1), 其实就换了个判断的思路。

评分

参与人数 1大米 +3 收起 理由
saveria + 3 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
 楼主| wjxtank2010 2018-1-21 08:55:33 | 只看该作者
全局:
RebortZhang 发表于 2018-1-20 14:10
请问楼主第二轮的worse case的优化怎么答得

参见我楼上的回复,字数字数
回复

使用道具 举报

🔗
 楼主| wjxtank2010 2018-1-21 08:56:50 | 只看该作者
全局:
619899442 发表于 2018-1-20 13:28
还想请教楼主第四题是不是只需要考虑一种字体,每个字符的高度宽度可能不同,求出可能的最大字号?

对于每种字体都会有不同的宽度和高度,这个会有辅助API, 基本思路就是用binary search选定一种字体看能不能fit, 然后调大或者调小
回复

使用道具 举报

🔗
Seventh 2018-1-21 09:19:03 | 只看该作者
全局:
最后一题不是每一种都试一下或者先按照string的大小来算最大可以是什么字体就好了吗?有木有什么特别要注意的地方咩?
回复

使用道具 举报

🔗
 楼主| wjxtank2010 2018-1-21 09:23:10 | 只看该作者
全局:
Seventh 发表于 2018-1-20 17:19
最后一题不是每一种都试一下或者先按照string的大小来算最大可以是什么字体就好了吗?有木有什么特别要注意 ...

最后一题会给定个可用的最大最小字体先,在这个范围内找到最大的就行
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表