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

iyarik 发表于 2021-9-23 12:48
谢谢分享! 第二个问题是 LC828

还是不太一样，描述类似，但题意差了不少

谢谢楼主分享。
第二题O(n)应该可以做：
       public int passwordStrength(String s) {
        int n = s.length();
        int[] last = new int[26];
        Arrays.fill(last, -1);
        int ans = 0;
        int cur = 0;
        for (int i = 0; i < s.length(); i++) {
            int index = s.charAt(i) -'a';
            cur += i + 1 - (last[index] + 1);
            ans += cur;
            last[index] = i;
        }
        return ans;
    }
    dp[i]: number of distinct letters for all substring end at i
    last[i]: last index for each letter
    There are total (i + 1) substring at [0, i]. letter i add at most i + 1 new distinct letter in dp[i]
    also need to substract previous substring count which already having letter i, which is lastIndex + 1
     dp[i] = dp[i - 1] + i + 1 - (lastIndex + 1) => cur = cur + i + 1 - (lastIndex + 1)
    Time complexity: O(n)
    Space complexity: O(1)

第一题 python 代码，试了几个test cases 好像都是对的，如果有不对的地方，请大佬们指点

1. #####helper funciton don't delete or change

复制代码

kobegao 发表于 2021-10-17 19:24
第一题 python 代码，试了几个test cases 好像都是对的，如果有不对的地方，请大佬们指点

上个回复复制错了，不知道怎么改不了，再发下

1. class Node:
   
2.     def __init__(self,data,next = None):
   
3.         self.data = data
   
4.         self.next = next
   
5. 
   
6. def insert(root,val):
   
7.     if not root:
   
8.         root = Node(val)
   
9.     else:
   
10.         cur = root
    
11.         while cur.next:
    
12.             cur = cur.next
    
13.         cur.next=Node(val)
    
14.     return root
    
15. def listToNode(numbers):
    
16.     root = None
    
17.     for num in numbers:
    
18.         root = insert(root,num)
    .1point3acres
19.     return root
    
20. 
    
21. #####helper funciton don't delete or change
    
22. def reverseLinkedList(node):
    
23.     prev = None
    
24.     while node:
    
25.         next = node.next
    
26.         node.next = prev
    
27.         prev = node
    
28.         node = next
    
29.     return prev
    
30. 
    
31. def maxinumPages(head):
    
32.     slow = head
    
33.     fast = head.next
    
34.     while fast and fast.next:
    
35.         fast = fast.next.next
    
36.         slow = slow.next
    
37. 
    
38.     new_head = slow.next
    
39.     slow.next = None
    
40.     rev_head = reverseLinkedList(new_head)
    
41.     max_pages = 0
    
42.     while head or rev_head:
    
43.         if head:
    
44.             p1 = head.data
    
45.             head = head.next
    
46.         else:
    
47.             p1 = 0
    
48. 
    
49.         if rev_head:
    
50.             p2 = rev_head.data
    
51.             rev_head = rev_head.next
    
52.         else:
    
53.             p2 = 0
    
54.         max_pages = max(max_pages,p1+p2)
    
55. 
    
56.     return max_pages
    
57. # numbers = [1,4,3,2]
    
58. # numbers = [3,1,1,3]
    
59. numbers = [3,1,9,3,3]
    
60. head = listToNode(numbers)
    
61. print(maxinumPages(head))

复制代码

guiguia 发表于 2021-10-16 22:15
谢谢楼主分享。
第二题O(n)应该可以做：
       public int passwordStrength(String s) {

Good one!

iyarik 发表于 2021-9-23 12:48
谢谢分享! 第二个问题是 LC828

这题和828还不一样。感觉828比这题难不少。我们来看一个例子就知道了。
828的要求：
For example if s = "LEETCODE" then "L", "T", "C", "O", "D" are the unique characters since they appear only once in s, therefore countUniqueChars(s) = 5.
所以如果character在这个substring里重复，它是不能被记入最后结果的

再来看亚麻的OA：
test => 3
这道题里，t尽管重复了，但是它被记入了一次。所以这两道题对于 countUniqueChars()的定义是不同的。

naturalbeau 发表于 2021-9-24 15:24
第一题先用快慢指针分两半，然后把后半段reverse，然后再两个list相加。

大佬可以发一下sudo code嘛

SteinGate 发表于 2021-11-12 20:31
这题和828还不一样。感觉828比这题难不少。我们来看一个例子就知道了。
828的要求：
For example if s  ...

如果只记录一次，应该更简单
dp[ i ] 代表从0开始 以 i 坐标结尾的substring的所有substring的unique 和

dp[ i ] = dp[i - 1] + (i - last occurance of s.charAt( i ))  （meaning number of new uniques the new s.charAt( i ) can contribute to dp[ i - 1]）
一个长26的数组记录 并更新 last occurance of s.charAt( i )
dp只用两个数组不断更新就行

微信用户_b95b611 发表于 2021-11-26 21:35
大佬可以发一下sudo code嘛

用快慢指针找到中点的部分你可以参考 LC876

reverse list 的部分可以参考 LC206

之后就是双指针, 一个从开头, 另一个从中点, 相加取最大值就行

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