【求大米】paypal哦噻

求大米
5轮，三轮design，一轮coding，一轮behavior

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

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

第四题，java做的话，用string.indxeOf找出两个str位置，然后更新长度: Math.max(indexOf(str1)+str1.length, indexOf(str2)+str2.length) - Math.min(indexOf(str1), indexOf(str2))。然后下一个循环从前面的index+1开始，直到indexOf返回-1。时间复杂度最坏可以到O(n*(n*m))(m是子串长度)。 如果扩展到k个子串，那么变成(O(n*(n*m*k)))。
另一种做法是先用O(n*m*k)找出每个字串在text里的所有位置，存在list里面(k个list存k个子串的位置,list里的位置是sorted)，然后用一个heap，读取每个list的一个元素放进heap，以heap中的最小值来更新text长度(heap中最小值是text长度最左端)，然后丢掉最小值补充新的位置进入heap继续循环，直到某个list为空。 后面这部分复杂度O(n*k*logk)。

cbtou1 发表于 2020-4-1 03:58
第四题，java做的话，用string.indxeOf找出两个str位置，然后更新长度: Math.max(indexOf(str1)+str1.lengt ...

想问下这个follow up 只有一个heap 的话， 不是只能找到最左端的边界吗？ 怎么确定右边界呢？

TiAmO723 发表于 2020-7-24 11:20
想问下这个follow up 只有一个heap 的话， 不是只能找到最左端的边界吗？ 怎么确定右边界呢？

题目我现在看不到了，你把楼主的第四题题目贴一下，我来跟你解释

cbtou1 发表于 2020-8-22 18:17
题目我现在看不到了，你把楼主的第四题题目贴一下，我来跟你解释

4. 给定一段text里面包含多份str1和str2，找出最短的一段text包含有这两个strings；写完后，问怎么解决k个strings

同问，求大神解答~

a_plus 发表于 2020-8-28 09:25
4. 给定一段text里面包含多份str1和str2，找出最短的一段text包含有这两个strings；写完后，问怎么解决k ...

可以用两个heap做这个题，minHeap存所有subStrings中最小index, maxHeap存所有subStrings中最大的index
1 找到每个subString的所有indexes，放在一个Map<String, List<Integer>>里
2 拿出每个子字符的第一个指数，装在Pair<String, Integer>里，把这个Pair分别扔进 minHeap 和 maxHeap， 需要注意的是堆的comparator， minHeap只要比较 index, 然而maxHeap要比较index + len(subString)，这是因为子字符串可能会很长很长。这样minHeap的堆顶元素给出目标子串的开始位置，而maxHeap的堆顶元素给出目标子串的终止位置
3 找到当前子串，比长短，更新答案
4 将minHeap的堆顶元素剔除，同时将其下一个index放入堆中（如果没有下一个index了就可以直接退出循环)，注意同时还要更新maxHeap, 把之前minHeap堆顶的元素剔除，把新元素加入

a_plus 发表于 2020-8-28 11:40
可以用两个heap做这个题，minHeap存所有subStrings中最小index, maxHeap存所有subStrings中最大的index
...

不需要用到maxHeap，因为你在maxHeap里面删除minHeap堆顶的元素时，由于minHeap的堆顶元素在maxHeap里不一定是堆顶，所以删除某个特定元素的复杂度是O(n)，这样造成总复杂度是O(n*k)，失去了heap的意义。
其实保持右边界只需要用一个int存就够了，每次更新minHeap元素时，将新增元素的终止位置和当前右边界比较，大于右边界则更新右边界，否则保持不变。总复杂度O(nlogk).

TiAmO723 发表于 2020-7-24 11:20
想问下这个follow up 只有一个heap 的话， 不是只能找到最左端的边界吗？ 怎么确定右边界呢？

保持右边界只需要用一个int存就够了，每次更新minHeap元素时，将新增元素的终止位置和当前右边界比较，大于右边界则更新右边界，否则保持不变。