黑车公司OA

今天刚做的OA,  分享给大家，好久没做题手都生了

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

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

整理了过去两个月OA的题目，感觉做的时候按照1->4->2->3的顺序比较好。第四题属于leetcode medium，我遇到的覆盖了：双指针，two sum，滑动窗口，数据结构可能要准备（linked）hash（set，map）

求问第二题有没有写起来比较简短的方法。希望大家求职顺利。



补充内容 (2021-2-16 13:54):
第二问的答案又整错了，是[4, 2, 5, 3, 1]。。。

HenryXPHB 发表于 2021-2-19 12:23
谢谢分享， 第四题没看明白啥意思。 能解释一下吗

我的理解：

1. 给定两个数组a和b，还有一连串的query，求结果。query的规则是这样：如果是[0, x], 表示返回 a[i] + b[j] = x的{i, j} pair的个数；如果是[1, i, x], 表示把b[i]替换成x

复制代码

第二题, 用double linked list和priority queue，总的时间复杂度是O(NlogN)，但写得挺长的。

1. struct Node {
   
2.     Node *prev, *next;
   
3.     int val;
   
4.     Node (int num) {
   
5.         prev = next = NULL;
   
6.         val = num;
   
7.     }
   
8. };
   
9. 
   
10. void insert(Node *&head, Node *&tail, int num)
    
11. {
    
12.     Node *node = new Node(num);
    
13. 
    
14.     node->prev = tail;
    
15.     if (tail)
    
16.         tail->next = node;
    
17.     else
    
18.         head = node;
    
19.     tail = node;
    
20. }
    
21. 
    
22. void remove(Node *&head, Node *&tail, Node *node)
    
23. {
    
24.     Node *prev = node->prev;
    
25.     Node *next = node->next;
    
26. 
    
27.     if (prev)
    
28.         prev->next = next;
    
29.     if (next)
    
30.         next->prev = prev;
    
31. 
    
32.     if (head == node)
    
33.         head = next;
    
34.     if (tail == node)
    
35.         tail = prev;
    
36. }
    
37. 
    
38. struct comp {
    
39.     bool operator()(const Node *n1, const Node *n2) {
    
40.         return n1->val > n2->val;
    
41.     }   
    
42. };
    
43. 
    
44. bool is_peek(Node *node)
    
45. {
    
46.     int prev_num = INT_MIN, next_num = INT_MIN;
    
47.     if (node->prev)
    
48.         prev_num = node->prev->val;
    
49.     if (node->next)
    
50.         next_num = node->next->val;
    
51. 
    
52.     if (node->val > prev_num && node->val > next_num)
    
53.         return true;
    
54. 
    
55.     return false;
    
56. }
    
57. 
    
58. vector<int> smallest_peeks(vector<int> &nums)
    
59. {
    
60.     priority_queue<Node *, vector<Node *>, comp> pq;
    
61. 
    
62.     Node *head = NULL, *tail = NULL;
    
63.     for (int num : nums)
    
64.         insert(head, tail, num);
    
65. 
    
66.     Node *node = head;
    
67.     while (node) {
    
68.         if (is_peek(node))
    
69.             pq.push(node);
    
70.         node = node->next;
    
71.     }
    
72. 
    
73.     vector<int> result;
    
74. 
    
75.     while (!pq.empty()) {
    
76.         Node *node = pq.top(); pq.pop();
    
77.         Node *prev_node = node->prev;
    
78.         Node *next_node = node->next;
    
79. 
    
80.         result.push_back(node->val);
    
81.         remove(head, tail, node);
    
82. 
    
83.         if (prev_node && is_peek(prev_node))
    
84.             pq.push(prev_node);
    
85.         if (next_node && is_peek(next_node))
    
86.             pq.push(next_node);
    
87.     }
    
88. 
    
89.     return result;
    
90. }
    
91. 
    
92. int main()
    
93. {
    
94.     vector<int> nums = {3, 5, 1, 4, 2};
    
95.     vector<int> result = smallest_peeks(nums);
    
96.     for (int r : result)
    
97.         cout << r << " ";
    
98.     cout << endl;
    
99.     return 0;
    
100. }

复制代码

请问oa需要录屏或者开摄像头吗？

Tsul 发表于 2021-2-17 08:37
请问oa需要录屏或者开摄像头吗？

是啊 两个都需要 加米加米

谢谢分享， 第四题没看明白啥意思。 能解释一下吗

第4题，O(NlogN)

https://paste.ubuntu.com/p/XDhBttJP8w/