Amazon New Grad OA2 一道没在地里见过的题

回馈地里，两道题:

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

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

OA2 可以用Python了，真开心。

求大米！

bycfly 发表于 2018-9-6 07:36
请问楼主 第1题就是k distinct 吗？

是K distinct，但求的是子串总数。

第一题的“子串”打成了“字串”

第一题正确答案最多n方个，所以worse case time complexity不会更好。不过假设output size是k， sliding window应该可以 n + k，对于k比较小的情况还是远好于n方

求问楼主的timeline是怎样的？是内推的吗？

求问第二题DP怎么做，感觉后面对前面有影响不知道要怎么记呀

liu93ri 发表于 2018-9-1 23:40
求问楼主的timeline是怎样的？是内推的吗？

周四收到OA1周五收到OA2

ydtang 发表于 2018-9-2 00:15
求问第二题DP怎么做，感觉后面对前面有影响不知道要怎么记呀

从后往前DP

同求问第二题怎么用lc174的模型呀 想不出dp[i][j]表示什么

第一题不是用sliding window 吗

谢谢楼主分享！

第一题有最优解吧 用两个指针