Google Youtube Onsite面经

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

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

sophietian1024 发表于 2018-1-20 10:21
是不是应该，对每一块板，对于前面的板子，如果他们有overlap, 就更新加上板长，然后得到最小值，没有ove ...

嗯嗯是这样，字数字数

请问楼主第二题的follow up是怎么答的呀？

还想请教楼主第四题是不是只需要考虑一种字体，每个字符的高度宽度可能不同，求出可能的最大字号？

请问楼主第二轮的worse case的优化怎么答得

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)， 其实就换了个判断的思路。

RebortZhang 发表于 2018-1-20 14:10
请问楼主第二轮的worse case的优化怎么答得

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

619899442 发表于 2018-1-20 13:28
还想请教楼主第四题是不是只需要考虑一种字体，每个字符的高度宽度可能不同，求出可能的最大字号？

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

最后一题不是每一种都试一下或者先按照string的大小来算最大可以是什么字体就好了吗？有木有什么特别要注意的地方咩？

Seventh 发表于 2018-1-20 17:19
最后一题不是每一种都试一下或者先按照string的大小来算最大可以是什么字体就好了吗？有木有什么特别要注意 ...

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