google 电面

分享一个这周进行的google 电面。
在client端需要进行一些annotation的排版，可以对server端call api getAnnotation(),返回数据类型是List<Tuple>, 每个tuple代表了一个annotation，样本如下：
{id:"annotation description, start :34, e

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

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

tions的请求， 如何存储数据，如何加入load balancer，如何加入cache之类的。

刚收到了email说进入下一阶段，结果是第二轮的phone interview，不知道是不是因为题目没有答的太好，加面了一轮，还是现在是两轮电面。

PocketOffer 发表于 2021-4-17 12:53
楼主，这个{id:"annotation description, start :34, end :56}里面的34 56是啥意思哦？是代表列数？？

可以理解成每一行的列数。比如下面的例子。
----          --------
   ------
有三个annotation，其中的两个可以放在同一行，然后最后一个因为和第一个有重叠，只能重新开一行。

感觉好像是meeting room 2 的变种。 用PriorityQueue?

楼主，这个{id:"annotation description, start :34, end :56}里面的34 56是啥意思哦？是代表列数？？

sqzhang17 发表于 2021-4-17 05:03
感觉好像是meeting room 2 的变种。 用PriorityQueue?

有些类似吧，不仅需要最少需要几个房间，还需要知道每个会议是在哪个房间开的。

请问楼主是因为面的是senior以上才被问的系统设计吗？

嗨，楼主，面试官有要求行数最少吗？如果没有行数最少要求的话，每个ANNOTATION都占一行不就好了？

PocketOffer 发表于 2021-4-18 05:44
嗨，楼主，面试官有要求行数最少吗？如果没有行数最少要求的话，每个ANNOTATION都占一行不就好了？

是的，确认的时候问出来的，需要行数最少。

是来一个安排一个吗，还是一次请求完所有的之后再安排？

kobebyrant 发表于 2021-4-17 13:45
有些类似吧，不仅需要最少需要几个房间，还需要知道每个会议是在哪个房间开的。

可以使用一个freeLines集合存储可用的line id，添加一个新的annotation前，先回收可用的line id。处理当前annotation的时候，可能会回收多个line id。

大概流程如下：
1. 根据start对annotations排序
2. 遍历annotations，把每个annotation加入一个最小堆，堆顶的end最小
    2.1 如果堆顶的end 小于当前annotation的start，回收该行的line id
    2.2 如果freeLines为空，需要开一个新的line，freeLines.insert(maxLineId++);
    2.3 从freeLines里面选取一个free line，具体怎么选可以和面试官确定。
    2.4 更新结果，放入哈希表