狗家现场表演

第一轮：说是有一个music list, 让你随机选一首歌，如果这首歌已经出现了，则要相隔K次才能再出现，要求O(1) time complexity and O(1) s

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

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

耗1加仑汽油，问你到终点时如何保证加油花费最小。（完全没有思路）


求大米， 求大米

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

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

第五题是USACO的，觉得有用请加米！
http://www.usaco.org/current/data/sol_fuel.html

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

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

第一题能做到O(1)吗？

楼主第一题怎么做的？是每次随机数选一个下标然后跟list最后一个元素换过来，然后k次之后每次再从列表后面的元素中拉一个换到前面？
第五轮是不是dp[i][w]代表第i个加油站剩w升油的最小花费...

第一题的解法感觉和这个面经差不多： https://www.1point3acres.com/bbs ... ;page=1#pid16029108
第四题话，如果是利口871的DP解法， 是不是就改成dp[t+1] = Math.min(tankSize, Math.max(dp[t+1], dp[t] + stations[i][1]))就可以了？

第一题如果用一个size为k的queue存已经出现的歌，同时放在一个set里，新歌加进来把超过k的踢出去，感觉很像一个LRU，不同的是要搞一个randomness。
第五题我觉得每一个加油站的weight其实是上一个加油站到这个加油站的距离distance * 这个加油站的油价，然后Best First Search就可以了，注意俩个加油站距离不能超过tank size。

第五题的明显是要你用DP解决问题。dp[i][j] 代表第i个加油站的时候车子的油是j。每到一个加油站，加油 范围【0..K】, 确保加油的量足够到下一个加油站。

最终的结果是min(dp[n-1][j])   j is[0..K]

这种题目一出，面试官基本不会让你 BFS或者DFS解决

多谢LZ分享。第五题有点难。能分享下BQ问了什么问题吗？

csushin1992 发表于 2021-9-21 23:20
第一题的解法感觉和这个面经差不多： https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=799 ...

这个dp算的是最少的加油次数吧。如果算cost，不太行吧。

第五题歧义挺多的. 请问楼主题目中的路具体是什么结构呢? 比如是一排加油站列表, 还是有向图, 甚至无向图. 看到很多人说DP, 如果是无向图, DP是没法做的. 想到地里的高频加油站题, 我猜测可能是那道题的一个变种. 比如求起点到终点最短距离, 最少加油次数, 最少加油费用. 最通用的做法是用BFS额外保存油量和油费状态, 搜索所有可能的合法路径, 给出最少的油费.