amazon SDE 社招 phone-in 過經

total 45min = 15min bq + 30min codingvia amazon chime全程開camera但我看不到interviewer LOL


bq1: most challenge work experience
bq2: how to deal with conflicts with team members
bq3: how did u reject (tasks/features/whatever)

coding1:
find out the number of the pairs that each of the pair's sum is less than or equals to the target. (nums可以有負數的, 冇重覆, 每個num只可以用一次)

e.g.

nums = [1,3,5,7,9], target=10return 5
因為這些pairs
[1,3]
[1,5]
[1,7]
[1,9]
[3,5]
[3,7]
全部 <= 10


我先講brute force O(n^2),  到binary search O(nlogn), 之後我implement了binary search。說畢，我再說2pointers O(2n)應該也可以，ta說lets go to the followups

followup1(其實我覺得是另一題了，因為做法完全不同):
what if i want you to give me all the subsets(no redundant) and each of the subset's sum is less than or equals to the target? (nums可以有負數的，冇重覆, 每個num只可以用一次)

e.g.
nums = [1, 3, 5, 7, 9], target=10
return 13
因為這些subsets
[] <- empty, 0, 也是其中一個subset
[1]
[3]
[5]
[7]
[9]
[1,3]
[1,5]
[1,7]
[1,9]
[1,3,5]
[3,5]
[3,7]
全部 <= 10


這個我brute force recursion O(2^n)做了，想不到更快的，有大神說一下該如何優化嗎?

followup: nums有重覆，同樣每個num只可以用一次，但要給去重的result。類似利口肆拾，不過有負數

P.S.
1. 我一開始以為社招OA完之後就是VO, 想不到他先給我來一下phonein
2. 在地里，很多人都是被問LRU, longest palindrome, hashmap implementation...etc這些常見題。當我聽到subset，我呆了，當時只剩下15min，差點寫不出來。。。
3. 想再準備好一點，VO約了4個星期後哈哈


4. 我之前的OA 傳送門

jimmytzm 发表于 2019-5-4 02:09
Coding1楼主说用binary search, 你指的是two pointer吧？二分搜索不太适合吧………

补充内容 (2019-5-4 02 ...

haha對

雖然我implement了binary search，2pointers也可以。但因為2pointers也要先sort，所以也是O(nlogn)，只是後面是O(n)快一點

其實他說想理解我的thought process，對於一個問題會怎樣分析，可以有多少個方法解決。。。給我感覺implementation的是否最優好像不是重點（當是不是brute force）

1. def twoSumCombo(nums, target):
   
2.     nums = sorted(nums)
   
3.     res = 0
   
4.     for i in range(len(nums)):
   
5.         num = nums[i]
   
6.         idx = bsearch(nums, target-num)
   
7.         if idx > -1 and idx > i:
   
8.             res += idx - i #重點!!!
   
9.     return res
   
10. 
    
11. 
    
12. def bsearch(nums, target):
    .
13.     left = 0
    
14.     right = len(nums)-1
    
15.     while left <= right:
    
16.         mid = (left + right)/2
    
17.         if target < nums[mid]:
    
18.             right = mid - 1
    
19.         elif target > nums[mid]:
    
20.             left = mid + 1
    
21.         else:
    
22.             return mid
    
23.     # to find number that no larger than target
    
24.     return right

复制代码

subset就是2^n没办法优化了，因为结果就是那么多个，这道题的话能剪枝，但是最坏情况还是2^n，用一个linkedlist hashmap之前的target和对应的pair存起来，类似于带memo的DFS。

Coding1楼主说用binary search, 你指的是two pointer吧？二分搜索不太适合吧………

补充内容 (2019-5-4 02:10):
漏看了后面你说的two pointer

jimmytzm 发表于 2019-5-4 02:09
Coding1楼主说用binary search, 你指的是two pointer吧？二分搜索不太适合吧………

补充内容 (2019-5-4 02 ...

二分可以做的

hupei1991 发表于 2019-5-4 06:38
二分可以做的

對，其實有幾個解。我感覺這些基本題，ta其望看到candidates能想到多解及比較他們time&space

WarriorZ 发表于 2019-5-4 01:36
subset就是2^n没办法优化了，因为结果就是那么多个，这道题的话能剪枝，但是最坏情况还是2^n，用一个linked ...

這個其實當時我有想過，但不肯定怎樣implement。。。因為雖然說有部份相似，但其實有prefix，感覺有點像word break 2

hupei1991 发表于 2019/05/04 06:38:26


二分可以做的

发现了.  不过觉得直接二分的细节操作没有两个指针那么直观

jimmytzm 发表于 2019-5-8 05:49
发现了.  不过觉得直接二分的细节操作没有两个指针那么直观

如果用bisect的话 还更不容易错 何乐不为

数组是排好序的吗？