发一个2月下旬骨骼昂塞

发个2月下旬的骨骼PhD onsite, 一共5轮，3轮coding，2轮research
r1: 白人大哥，coding. 问题本身不是很难，主要考察对数据结构的应用以及优缺点的比较。设计两个api，一个是updateRange(start, end, val), 一个是lookup(key)，lookup会用的比较频繁。updateRange 是将从start到end的这个范围的key对应的值都设为va

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

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

个问题，然后听我回答，不停地敲键盘做记录，没有几次眼神交流。回答完了没有反馈，继续问下一个问题。感觉比较生硬。

过了一周hr就约打电话，lz就知道挂了。本来想问问能不能透露下原因的，还没等lz开口，hr就说了没法提供更多的feedback，应该是挂的比较深沉。

r2刷题板块里高频题里有，看里面回复最佳做法确实是二分法最大匹配或者最大流。不过我看有人说用回溯法也过了。如果用回溯法最好做个word 中ch对应dice的map。这样处理起来会快一点。复杂度是O（m**n） m是word长度 n是dices个数，如果不预处理的话，判断char是否在dice中又需要k，k是dice面数，复杂度就会变的更高。

国人小哥这题如果没有要求o（1）空间复杂度啊之类的，确实放水了。哈哈哈

r2不用费用流，最大匹配(或者最大流)即可，然后匈牙利算法写起来其实和暴力回溯差不多，但是是多项式复杂度(其实能过的回溯大概就是写成了匈牙利了吧，这个算法思想特别朴实...)= =O(N^3)
左边每个骰子，右边单词的每个字母，骰子上有字母就给所有对应字母连边，判断最大匹配数量是否是单词长度，每个匹配边表示选择使用对应骰子表示单词的对应字母

第一题也不容易吧。。

我想不出很好的数据结构，除了线段树