狗VO

六月中HR找，无OA，约七月初4轮VO(1*BQ + 3*technical)，题有点不常规move on，单纯分享看看大家对于难度看法，顺便求米

1.BQ 常规

2.有一个整数数据流，实现一个数据结构，有init方法，add方法和一个get方法
ini

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

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

ght三种行动之一，求unique paths数量

4.给一个m和n，放置0和1，放0没有要求，放1的要求是：上下左右至少有一个0，问最多能放多少个1

第二题我的想法是，已知输入的是个整数，那么我们可以开辟一个数组，所有数初始化为0，每个数放入下标i的counter，其中2^i <= nun < 2^(i+1)。如果考虑负数的话就再加一个list。每次get的时候计算中位数位置即可。
因为int有4个字节，所以数组长度固定32，这样每次操作都是O(1)

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

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

july2020 发表于 2022-07-19 01:21:56
第四题说了数据量吗。 看起来比较像 状态压缩dp

我没有问，但应该问一下吧，感觉复杂度降不下来

第二题

“....返回[4, 8]之间任意一个整数即可，包含4， 8..."

那么直接返回中位数“5”行不行？  “5”是在[4,8]的范围内

同问直接return 中位数能不能过呢？

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

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

小亩_fa72728 发表于 2022-7-18 22:10
同问直接return 中位数能不能过呢？

直接return中位数复杂度降不下来，不是O(1)

小亩_fa72728 发表于 2022-7-18 22:10
同问直接return 中位数能不能过呢？

valid但不能过，这样add和get复杂度不能同时降到O(1)，所以这题很不常规

第二题分段储存count，然后记一个中位数的位置和leftCount， rightCount。然后每次就去更新这些可以做到O(1)
第三题 这个dp还算简单。
第四题想了下完全不会。感觉是一个特别难的dp

第二题最后要求是add，get同时做到O(1)

第四题…可不可以backtracking 每次check condition 改成1， 之后再改回去， 然后有个 check board is down 作为stop condition， 就是看有没有3*3个0

jinl00 发表于 2022-7-18 22:45
第四题…可不可以backtracking 每次check condition 改成1， 之后再改回去， 然后有个 check board is down ...

backtrack思路应该是对的，就是复杂度降不下来，而且实现挺麻烦