狗狗家

电面
二叉树多了一条边 找到这条边 删掉

onsite
1. 蠡口 易武巴， 伞斯舞
2. 蠡口 散酒久 变了一

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

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

的工资最少。

先大概写一下 之后再来更新细节。
祝大家面试顺利！

FTD2014 发表于 2018-6-20 00:34
我刚用DP推了一下你这个例子，没什么问题。
本来想回答你的，但有个人问他问题跟问空气一样，不想让他看 ...

不好意思~我早上有点忙，回了一条就有急事出去了。~~~我刚才又想了想，觉得DP的n并不能直接从n-1推演（当然也有可能是我的DP状态错了）。比如A工作10小时，每小时rate $1, B工作也是10小时，每小时rate 也是$1，C工作 5小时，每小时rate $3，D工作3小时，每小时rate $4。那么选两个人应该选A和B，但是选三个人应该是A，C，D或者B，C，D。三个人的解并不等于两个人的最优解加额外一个人。（当然，再说一遍，我的DP公式可能是错的）。

补充内容 (2018-6-20 01:19):
另外，我也在论坛上问很多问题，但是我自己是从来不觉得别人obligated to回答我的问题，尤其别人是没有义务第一时间内去回答我的问题。论坛上有很多好心的大牛，我都从他们身上受益良多，比如tinylic, Ramily

补充内容 (2018-6-20 01:24):
还有其他人，我就不一一列举了。我自己的看法: 在这里别人帮你解惑，我很感激。但是对方没有义务去帮我，我也问很多问题得不到回答，但我从来不会想要去指责别人。Nobody gets paid to help you.

我面过最后一道题，这里给解释一下，比如有小王 工作6h, 工资6块，小李工作3h,工资15块，小赵工作3h,工资9块，每个人的平均工资是1块／h, 5块／h, 3块／h
最后选择的人根工作时间没有任何关系，只要求选k个人，付的工资最少，要求给每个人pay选择的k个人中最高的平均工资
如果选3个人，就必须给每个人pay5块／h, 总的就是（8 + 2 + 3） * 5 = 65
若果选2个人，
选小王和小李就是 5 * （6 + 3） = 45
选小李和小赵就是5 * （3+ 3） = 30
选小王和小赵就是3 * （3 + 6） = 27
所以如果选择两个人，最优应该选小王和小赵
最优答案是啥，我也不知道，如果面到了就看运气吧

补充内容 (2018-6-19 21:17):
6 + 3 + 3 改正一下

hankok 发表于 2018-6-19 08:34
感觉可以先把所有人按时薪高低排序用一个priorityqueue存起来，遍历所有情况（dfs, k就是dfs的深度），从选 ...

错了是 n*k^n

补充内容 (2018-6-20 02:09):
想不出怎么用DP.. 感觉和利口八二六比较像,用排序+2pointer，一会研究一下它的greedy解法

最后一轮是DP嘛……伤脑筋

多谢分享！最后一道题是不是还有一些其他的限制条件？比如每个小时必须有至少K个工人同时在工作？

楼主，最后一题，是不是说每个工人都有自己离散的工作时间段？然后问题是在指定的时间段内选k个人？如果这样的话，那我每次找到指定时间段内available的工资最低的k个人不就行了？或者如果低工资人的时间段小于我的时间段，那我也可以把总时间段切片？

感觉可以先把所有人按时薪高低排序用一个priorityqueue存起来，遍历所有情况（dfs, k就是dfs的深度），从选定一个工人（以他的时薪为准）开始，遍历其他所有时薪更低的，每次遍历完存一个total，然后取最小值。复杂度似乎是n*3^n。

byrlhb 发表于 2018-6-19 08:05
我面过最后一道题，这里给解释一下，比如有小王 工作6h, 工资6块，小李工作3h,工资15块，小赵工作3h,工资9 ...

多谢！请问三个人时总小时数为什么是8+2+3呢？

补充内容 (2018-6-19 11:22):
应该是6+3+3？

有谁能说一下第四题什么意思啊，没看明白题意

idatascience 发表于 2018-6-19 10:58
多谢！请问三个人时总小时数为什么是8+2+3呢？

补充内容 (2018-6-19 11:22):

我也觉得是6+3+3, 老哥能说一下第四题是啥意思吗

最后一题把所有工人按时薪从小到大排序，然后用背包问题的模型求解。