Amazon Online Assessment OA 刚做完，把题目分享给大家，换点大米

cxq920423 发表于 2021-09-23 10:55:30
感谢分享，第二题的时间复杂度是多少呢？

补充内容 (2021-09-24 02:02 +08:00):

我的想法是先loop一遍找maximum distinct character 然後再k in［1,max] 用sliding window找exact k，这样时间复杂度应该是 n？ 我也不知道行不行

samdee 发表于 2021-9-23 12:58
我的想法是先loop一遍找maximum distinct character 然後再k in［1,max] 用sliding window找exact k，这样 ...

赞，应该可以，get your point。good solution!!  我在想k in [1, max] 可能也是O(N^2) ?

感谢楼主分享！！刚收到OA正到处找面经
祝楼主找工顺利！

第一题是不是每次都需要从head 一直搜到tail，然后把tail提取出来？ 这样也是O(n^2)有没有更好的办法呢？

cxq920423 发表于 2021-09-23 13:58:45
赞，应该可以，get your point。good solution!!  我在想k in  可能也是O(N^2) ?

如果是限定a-z的话distinct character只有26个 就是说max最多是26 sliding window每个iteration是n所以最后总的还应该是n

samdee 发表于 2021-9-23 14:53
如果是限定a-z的话distinct character只有26个 就是说max最多是26 sliding window每个iteration是n所以最 ...

赞！good solution!

感谢楼主！祝找到满意的工作！

感谢楼主，祝找工顺利！我第一题只想到每次遍历去掉首尾，请问大佬们还有更加优化的解法吗？

FridaW 发表于 2021-9-24 00:36
感谢楼主，祝找工顺利！我第一题只想到每次遍历去掉首尾，请问大佬们还有更加优化的解法吗？

第一题先用快慢指针分两半，然后把后半段reverse，然后再两个list相加。

第2个拔而巴好像n平方的办法在刷题网上会超时哎，不知道实际oz能过吗？