Amazon 社招新OA

半年前朋友帮投的Amazon Alexa。 是一个SDE2的职位。 半年后联系我给的OA。认真复习地里所有Amazon社招OA。结果无一命中。不知道是OA题库变了 还是SDE2和SDE1 题库不一样。1.给字符串， 找出里面长度为N的， 并且里面字符只有一次重复的字串。
例子：s: asdfaghjkjqoiiii;N=5.  返回asdfa ghjkj

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
t.add(s.charAt(i));
    }
    if(set.size()==N-1){
            return true;
    }else{
            return false;
    }
}
然而 结果是跑对了8/16的test case。我是怎么也想不到那一半不对的 test case是啥。。然后系统不告诉你都有哪些test case。 估计跪了把。。。

lixin832500 发表于 2017-12-30 07:32
贡献一个sliding window 的答案

dupCount --的判断条件应该是 >= 2，不是== 2吧？比如这个用例"aaabbcccc", 4

贡献一个sliding window 的答案

1.    public List<String> Solution(String s, int N){
   
2.         List<String> res = new ArrayList<>();
   
3.         if(s == null || N <=0 || s.length() < N) return res;
   
4.         Map<Character, Integer> map = new HashMap<>();
   
5.         int left = 0, dupCount = 0, len = 0;
   
6.         for(int right = 0; right < s.length(); right++){
   
7.             len++;
   
8.             if(!map.containsKey(s.charAt(right))){
   
9.                 map.put(s.charAt(right), 1);
   
10.             }else{
    
11.                 map.put(s.charAt(right), map.get(s.charAt(right))+1);
    
12.                 dupCount++;
    
13.             }
    
14. 
    
15.             while(len == N){
    
16.                 if(dupCount == 1){
    
17.                     String subString = s.substring(left, left + N);
    
18.                     res.add(subString);
    
19.                 }
    
20.                 if(map.get(s.charAt(left)) == 2){
    
21.                     dupCount--;
    
22.                 }
    
23.                 map.put(s.charAt(left), map.get(s.charAt(left)) - 1);
    
24.                 len--;
    
25.                 ++left;
    
26.             }
    
27.         }
    
28. 
    
29.         return res;
    
30.     }

复制代码

楼主，你的代码里面没有去掉重复的字符串。肯定挂别想了。

估计还有其他问题，暂时还看不出更多

谢谢lz分享！lz这样做应该是O(N*n)复杂度，如果用双指针同时向前走并且maintain一个hashmap来记录多少unique char，可以优化到O(n)?

可以用sliding window

请问另外一道题是啥?

lz还记得另一道题吗

lz还记得另一道题吗?

请问lz是在哪儿读的？buffalo or sit or utd?

  if(set.size()==N-1) 这句应该是   if(set.size()<=N-1) 吧