Menu Sidebar
Menu

Interview Question

Minimize Hamming Distance After Swap Operations

给一个原数组和一个目标数组, 给一个2d数组表示可以交换原数组的index对, 求使用这些交换后, 原数组不能成为目标数组元素的个数. 这个题是典型并查集的题, 先预装一下所有的swap, 然后再找原数组中的index是否在某个集合中, 需要注意的还有一个是因为有重复元素, 所以还需要一个map记录并查集中每个小集合中元素的频率.

Average Waiting Time

给一个已经排序好的二维数组. 第一个数字表示顾客到达的时间, 第二个表示准备顾客order的时长, 求平均服务顾客的时间. 这个题就是分类讨论, 通过看例子, 知道如果前后两个人在同一时间到达, 那么后一个人的服务时间是要把给前边人准备的时间也算进去的. 然后再按照当前时间进行分类, 还是第二个例子, 能看出如果两个人不是同一时间到达, 但是两个人的准备时间不重叠, 那么只需要分别算服务时间, 如果重叠, 需要先找到上一个顾客的完成时间, 然后计算出当前顾客的服务时间, 所以还需要一个变量记录上一个顾客的完成时间.

Profitable Schemes

给一个数字n,表示n个人, 给一个数字p, 表示最小的收益, 给两个数组,表示工作和工作需要的人, 问最多使用n个人并且满足最小收益的工作一共有多少种组合? 这个题一眼肯定是动态规划, 但是因为是求多少种组合, 所以每个条件都单做一维. Let dp[i][g][p] to be the first i’th jobs (including) with exact g members used and having exact p profit. 首先要初始化这个dp, 那么dp[0][0][0]是1 从背包问题,宽泛考虑, 可以知道, 如果不选当前的i, 那么对应的g和p就不会增加, 所以这也是一种组合: 当决定了选i’th job, 就要考虑当前i是否满足限制人数(不满足则不选): 通过上面这行后, 确定了ith job肯定能干, 接着考虑下面的, 如果ith job的profit和当前profit加起来超过了P(最小profit), 因为其实超过了多少无所谓, 我们就把所有超过P的job放到P的位置上, 这样便于统计. 如果加起来还是没有超过p, 那么我们只能先存着, 因为当前的运算可能作为以后某个答案的子集. 以上就是dp的构建, 最后的答案因为我们的dp只迭代了包含前i个job的子问题, 子问题并没有对人数进行迭代, 人数从0到G都是满足题意的答案, 所以需要在dp的中找到这些答案并且加起来. 全代码:

Newer Posts
Older Posts

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.