G家VO挂经

6月底的VO

第一轮： 全程BQ第二轮： 第一问,给一个页码宽度和一段文字，输出文字放进去要放多少行。第二问，把两段文字放入excel表的两列，问中间的分隔在什么位置两列的文字高度最相近。其实利用第一问的function就很简单，优化就是binary search
第

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

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

。第二题很简单的一个BFS。面试官小哥很nice，说最后一轮不要搞得太累，后面就聊天吹水。

最后hc通知算法没过。题其实都不算难，主要还是中间两轮没把握好，只能明年再战了

scheduler那个设计其实蛮常规的，做过的自然是知道。
首先最简单的方法就是一个job一直跑着，可以用daemon thread做，定期去poll数据库里全部记录，到时间了就取出来。

其次就是用java delay queue，具体API自己查一下，如果需要多线程的话还有给你封装好了的库，叫DelayedExecutorService (好像是这个名字），直接创建thread pool就行了 （如果你这个开始就都不知道，那基本就挂了）
、
第三种方式是使用时间轮， 这是我个人最喜欢的一个数据结构，非常优雅。英文叫TimingWheel，不知道的也是自己查一下。

第四种方式是用rabbitMQ的TTL加delivery Queue机制，维护两个message queue，用户产生schedule的时候把job放进第一个queue，过期时间设置为用户的timing，这样用户的job过期（到时间）以后会自动转移到第二个queue（注意这个功能只有RabbitMQ提供），你通过设置可以让rabbitMQ直接push给你的worker达到实时启动的目的。


最后一种方式是多线程，分布式，大数据环境下常用的，Redis Zset，加分布式锁。

f0rest77 发表于 2020-7-24 03:36
这题面试官说不用考虑多线程，没搞太懂

我感觉面试官会不会只是在考比较简单的algo idea而不是多线程。。比如说maintain一个min heap记录接下来需要执行的task的时间，然后可以peek也可以开一个计时event，每次加入task就insert，拿出task就再heapify

第三题感觉是dijistra变体

[010101E,
0000000,
0010010,
10S0010
]
把每个点到最近的狮子距离算出来 (O(N^2))
然后从start开始往周边走，把周边都按照距离存heap里，下一步走离狮子最远的，maintain一个global min 直到到达END (应该是O(N))

第二轮的第一问是 四幺八？还是溜霸？ 第二问“中间的分隔在什么位置”是什么意思是呀？“两段文字放入excel表的两列”是指两个不同的sentence分别各自放在两列？
第三轮题目是啥意思呀？
第四轮第一题是酒令零？

旧未来 发表于 2020-7-14 10:27
第二轮的第一问是 四幺八？还是溜霸？ 第二问“中间的分隔在什么位置”是什么意思是呀？“两段文字放入exce ...

跟四幺吧有点像，但是sentence是一整个string，需要自己手动parse word。第二问就是页码总宽度是固定的，把中间的分隔往左移的话第一个column宽度就变小，第二个column宽度变大了，最后的返回可以是最终第一个column的宽度。 第三轮我也很懵逼，面试官口述就是这么说的，我的理解是找所有路径里最危险的点里相对最安全的点，但他也没说是对的。。第四轮第一题是的，但input没给任何条件，需要自己validate

f0rest77 发表于 2020-7-14 11:48
跟四幺吧有点像，但是sentence是一整个string，需要自己手动parse word。第二问就是页码总宽度是固定的， ...

第一题第二问我看你在原帖里面提到了binary search，想问一下这个search的判断条件是啥（就是比如说让search区间的right end 变成mid)，左边的行数 - 右边的行数 大于/小于啥？

旧未来 发表于 2020-7-14 12:22
第一题第二问我看你在原帖里面提到了binary search，想问一下这个search的判断条件是啥（就是比如说让sea ...

我觉得是对第一列column的宽度进行搜索，搜索范围left是0，right是两列总宽度，然后二分搜索：在设定第一列宽度为mid的情况下，求出左右两列的高度，如果左高>右高，right = mid - 1，否则left = mid + 1

LeiTian 发表于 2020-7-14 14:12
我觉得是对第一列column的宽度进行搜索，搜索范围left是0，right是两列总宽度，然后二分搜索：在设定第一 ...

是这个意思，不过你的结论好像说反了

f0rest77 发表于 2020-7-15 07:25
是这个意思，不过你的结论好像说反了

Agree 说反了
总体上来说就是二分找左边>右边的临界点，然后再看看左边<右边的差值，比较一下选个差最小的就OK了..

第四轮task scheduler 我猜要的是conditional variable,

一个thread run task，while True: check prioty queue for next item (eg, 5s from now), condition (wait for sleeping period)
别的thread可以加task，condition.notify

alpaca1234 发表于 2020-7-23 21:45
第三题感觉是dijistra变体

[010101E,

应该是这个思路，那轮面试官英语不好，communication很捉急