Doordash 新鲜面经

Doordash新鲜面经，leetcode上没有但是是道原题:
讨论的开始讲了下n^2的思虑，但是面试官要求优化，利用PriorityQueue进行

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

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

优解挺难的，做着做着思路容易被自己搅混，最后没有把code写完，但是思路讲清楚了。目前还没有出结果。

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

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

贴一个面完以后自己写的完整代码。代码本身还有很多值得优化，简化的地方。勉强能被accept.

1. import java.util.*;
   
2. 
   
3. class Solution {
   
4.     public int[] solve(int[] nums) {
   
5.         int resultIndex = 0;
   
6.         int[] result = new int[nums.length];
   
7.         boolean[] visited = new boolean[nums.length];
   
8. 
   
9.         PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
   
10.         Map<Integer, List<Integer>> neighbors = new HashMap<>();
    
11.         for (int i = 0; i < nums.length; i++) {
    
12.             if (i - 1 >= 0 && i + 1 <= nums.length - 1) {
    
13.                 if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
    
14.                     queue.add(new int[]{nums[i], i});
    
15.                 }
    
16.                 neighbors.put(i, new ArrayList<>(Arrays.asList(i - 1, i + 1)));
    
17.             } else if (i - 1 >= 0) {
    
18.                 if (nums[i] > nums[i - 1]) {
    
19.                     queue.add(new int[]{nums[i], i});
    
20.                 }
    
21.                 neighbors.put(i, new ArrayList<>(Arrays.asList(i - 1)));
    
22.             } else if (i + 1 <= nums.length - 1) {
    
23.                 if (nums[i] > nums[i + 1]) {
    
24.                     queue.add(new int[]{nums[i], i});
    
25.                 }
    
26.                 neighbors.put(i, new ArrayList<>(Arrays.asList(i + 1)));
    
27.             } else {
    
28.                 queue.add(new int[]{nums[i], i});
    
29.             }
    
30.         }
    
31. 
    
32.         while (!queue.isEmpty()) {
    
33.             result[resultIndex++] = queue.peek()[0];
    
34.             int currIndex = queue.poll()[1];
    
35. 
    
36.             visited[currIndex] = true;
    
37. 
    
38.             List<Integer> neighbor = neighbors.get(currIndex);
    
39.             if (neighbor != null) {
    
40.                 List<Integer> neighborsToConsider = new ArrayList<>();
    
41.                 for (int n : neighbor) {
    
42.                     if (visited[n]) {
    
43.                         continue;
    
44.                     }
    
45.                     neighborsToConsider.add(n);
    
46.                 }
    
47.                 if (neighborsToConsider.size() == 1) {
    
48.                     int neighborIndex = neighborsToConsider.get(0);
    
49.                     boolean isPeak = true;
    
50.                     List<Integer> m = neighbors.get(neighborIndex);
    
51.                     if (m != null) {
    
52.                         for (int k : m) {
    
53.                             if (!visited[k] && nums[k] > nums[neighborIndex]) {
    
54.                                 isPeak = false;
    
55.                                 break;
    
56.                             }
    
57.                         }
    
58.                     }
    
59.                     if (isPeak) {
    
60.                         queue.add(new int[]{nums[neighborIndex], neighborIndex});
    
61.                     }
    
62.                 } else if (neighborsToConsider.size() == 2) {
    
63.                     int index1 = neighborsToConsider.get(0);
    
64.                     int index2 = neighborsToConsider.get(1);
    
65.                     int indexToAdd = nums[index1] > nums[index2] ? index1 : index2;
    
66. 
    
67.                     boolean isPeak = true;
    
68.                     List<Integer> m = neighbors.get(indexToAdd);
    
69.                     if (m != null) {
    
70.                         for (int k : m) {
    
71.                             if (!visited[k] && nums[k] > nums[indexToAdd]) {
    
72.                                 isPeak = false;
    
73.                                 break;
    
74.                             }
    
75.                         }
    
76.                     }
    
77.                     if (isPeak) {
    
78.                         queue.add(new int[]{nums[indexToAdd], indexToAdd});
    
79.                     }
    
80. 
    
81.                     // There should be a better way to optimize this so that we don't keep adding the neighbors but update properly.
    
82.                     neighbors.get(index1).add(index2);
    
83.                     neighbors.get(index2).add(index1);
    
84.                 }
    
85.             }
    
86.         }
    
87. 
    
88.         return result;
    
89.     }
    
90. }

复制代码

Time: O(nlgn),  Space: O(2n) 求大米

1. /*Remove-Smallest-Peaks-in-Order
   
2. Input: arr[] = {1, 9, 7, 8, 2, 6}
   
3. Output: [6, 8, 9, 7, 2, 1]
   
4. Explanation:  
   
5. First min peak = 6, as 2 < 6.
   
6. The array after removing min peak will be [1, 9, 7, 8, 2].                  
   
7. Second min peak = 8, as 7 < 8 > 2.
   
8. The array after removing min peak will be [1, 9, 7, 2]
   
9. Third min peak = 9, as 1 < 9 > 7.
   
10. The array after removing min peak will be [1, 7, 2]
    
11. Fourth min peak = 7, as 1 < 7 > 2.
    
12. The array after removing min peak will be  [1, 2]
    
13. Fifth min peak = 2, as 1 < 2.
    
14. The array after removing min peak will be  [1]
    
15. Sixth min peak = 1.
    
16. Therefore, the list of minimum peak is [6, 8, 9, 7, 2, 1].
    
17. */
    
18. class Node {
    
19. public:
    
20.     Node *pre =NULL, *nxt = NULL;
    
21.     int val;
    
22.     Node(int v){
    
23.         val = v;
    
24.     }
    
25. };
    
26. 
    
27. Node* tail = NULL;
    
28. set<int> findPeaks(vector<int>& a){
    
29.     set<int> ret;
    
30.     int n = a.size();
    
31.     if(n==1) return set<int>{a[0]};
    
32.     for(int i = 0; i < n; i++){
    
33.         if(i == 0 && a[i] > a[i+1]){
    
34.             ret.insert(a[i]);
    
35.         }else if(i == n-1 && a[i] > a[i-1]){
    
36.             ret.insert(a[i]);
    
37.         }else if(a[i] > a[i+1] && a[i] > a[i-1]){
    
38.             ret.insert(a[i]);
    
39.         }
    
40.     }
    
41.     return ret;
    
42. }
    
43. 
    
44. Node* addNode(int v){
    
45.     auto n = new Node(v);
    
46.     if(tail != NULL){
    
47.         tail->nxt = n;
    
48.         n->pre = tail;
    
49.     }
    
50.     tail = n;
    
51.     return n;
    
52. }
    
53. 
    
54. void removeNode(Node* n){
    
55.     if(n->pre != NULL && n->nxt != NULL){
    
56.         n->pre->nxt = n->nxt;
    
57.         n->nxt->pre = n->pre;
    
58.     }else if(n->pre != NULL){
    
59.         n->pre->nxt = NULL;
    
60.     }else if(n->nxt != NULL){
    
61.         n->nxt->pre = NULL;
    
62.     }
    
63.     delete(n);
    
64. }
    
65. 
    
66. bool isPeak(Node* n){
    
67.     if(n == NULL) return false;
    
68.     if(n->pre != NULL && n->nxt != NULL)
    
69.         return n->pre->val < n->val &&  n->nxt->val < n->val;
    
70.     if(n->pre != NULL)
    
71.         return n->pre->val < n->val;
    
72.     if(n->nxt != NULL)
    
73.         return n->nxt->val < n->val;
    
74.     return true;
    
75. }
    
76. 
    
77. vector<int> removePeaks(vector<int>& a){
    
78.       auto peaks = findPeaks(a);
    
79.       // (9, 8) -> (8, 9) -> asc -> true -> a.first > b.first;
    
80.       // (9, 8) -> (9, 8) -> desc -> false -> a.first < b.first;
    
81.       auto cmp = [](pair<int, Node*>& a, pair<int, Node*>& b){
    
82.           return a.first > b.first;
    
83.       };
    
84.       priority_queue<pair<int, Node*>, vector<pair<int, Node*>>, decltype(cmp)> q(cmp);
    
85.       for(auto n : a){
    
86.           auto node = addNode(n);
    
87.           if(peaks.count(n)){
    
88.               q.push({n, node});
    
89.           }
    
90.       }
    
91.       vector<int> res;
    
92.       while(!q.empty()){
    
93.           auto elem = q.top();
    
94.           res.push_back(elem.first);
    
95.           q.pop();
    
96.           auto pre = elem.second->pre;
    
97.           auto nxt = elem.second->nxt;
    
98.           removeNode(elem.second);
    
99.           if(isPeak(pre)) q.push({pre->val, pre});
    
100.           if(isPeak(nxt)) q.push({nxt->val, nxt});
     
101.       }
     
102.       return res;
     
103. }
     
104. 
     
105. 
     
106. int main() {
     
107.     vector<int> a {1, 9, 7, 8, 2, 6};
     
108.     for(auto n :removePeaks(a)) cout << n << " ";
     
109.     cout << endl;
     
110. }

复制代码

pq 复杂度能降到nlogn吗？

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

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

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

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

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

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

yourdoraemon 发表于 2021-12-15 17:09
我觉得你可以用 double linked list  找peak的时候 顺便把iterator一起存下来, 然后O(1) erase 掉, O(1)  ...

确实，这样确实方便太多了

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

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

请问n^2有过吗？

https://www.geeksforgeeks.org/mi ... ation-of-the-array/