9.26新鲜热乎的狗狗昂塞

1小时前结束的面试。第一题愣是没写出来。挂得不怨。

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

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

seanhfyz 发表于 2018-9-27 09:02
我的思路是把List分别按start和end排序，放进ListSortByStart和ListSortByEnd的两个list里
取ListSortBy ...

只需要sortByEnd，取第K个，return所有跟它相交的interval

Lego0o0 发表于 2018-9-27 08:45
楼主第二题怎么解决的？greedy吗？

我的思路是把List<interval>分别按start和end排序，放进ListSortByStart和ListSortByEnd的两个list里
取ListSortByStart.get(K)和ListSortByEnd.get(K)的交集intervalK，再扫一遍log，把和intervalK有交集的用户全返回出来。
面试官没给hint，没时间确认我的算法是否正确，但目前手头的testcase结果都是对的。希望哪位大佬给标答

wsx247 发表于 2018-9-27 15:57
怎么dp啊
可以解释一下吗

Step1. Sum all elements, eg.[2,5,1], sum = 8, construct a 2D array boolean[i][j] = boolean[3 + 1][8  + 1], means whether a certain sum j can be formed by front i elements
Step2. update dp[i][j] = dp[i - 1][j] || dp[i - 1][j - arr[i]]
Step3. record all j where dp[arr.length][j] = true

楼主第二题怎么解决的？greedy吗？

第一题除了暴力dfs还有好点的解法不？

mark狗家面经

第一题duplicate numbers要考虑么？

很详细的面筋

楼主每道题都够分量！如果沟通还可以，只是第一轮没写出code，结果未必fail。祝好运！

gaotianhang1022 发表于 2018-9-27 10:01
第一题duplicate numbers要考虑么？

[2,3,5]
返回[0,2,3,5,7,8,10]

seanhfyz 发表于 2018-9-27 11:31
[2,3,5]
返回[0,2,3,5,7,8,10]

请问比如 [2,2,3] 就返回 [0, 2, ,3,  4, 5, 7] ?
既然是subset， 两个相同的 2 也算不同的elements吧？