骨骼虚拟上门

面的l4, 狗屎运比较偏简单;
走过路过，求好心人施舍点大米😂
（没有设置限制，如果看不到可能是论坛默认。。试试手机版）

第1轮：李寇 意思二三； follow-up：还是取数组头和尾k次，新加入multiplier int[k], 每次也从multiplier 按序取出数相乘算结果，求max，例子：k=2, array [3,2,1,4], multiplier [1,2], 第一次取结果：4

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

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

；
分别写了BFS 和DFS，BFS占空间，DFS好一点；
follow-up：优化BFS空间，讨论了改tree node，加入child -> parent；不改树就用hash-map memorize

第五轮：BQ轮，恶意竞争等等

houghstc 发表于 2021-1-9 05:55
第一题的follow-up
[mw_shl_code=cpp,true]    int n, k;
    vector arr, multiplier;

厉害了 谢谢大佬

第一题的follow-up

1.     int n, k;
   
2.     vector<int> arr, multiplier;
   
3.    
   
4.     // dp[l][r] stands for the max result we can get
   
5.     // if we take l elements from left, and r elements from right
   
6.     vector<vector<int>> dp;
   
7.    
   
8.     // the max result we can get
   
9.     // if we take l elements from left, and r elements from right
   
10.     int dfs(int l, int r)
    
11.     {
    
12.         if(l == 0 && r == 0)
    
13.             return 0;
    
14.         int &v = dp[l][r];
    
15.         if(v > INT_MIN)
    
16.             return v;
    
17.         // consider the last element we choose
    
18.         // if the last element is chosen from left, it should be the (l-1)-th element in arr
    
19.         // if the last element is chosen from right, it should be the (n-r)-th element in arr
    
20.         // the multiplier will always be (l+r-1)-th element in multipliers
    
21.         if(l > 0)
    
22.             v = max(v, dfs(l-1, r) + arr[l-1]*multiplier[l+r-1]);
    
23.         if(r > 0)
    
24.             v = max(v, dfs(l, r-1) + arr[n-r]*multiplier[l+r-1]);
    
25.         return v;
    
26.     }
    
27. 
    
28.     int main() {
    
29.         cin >> n >> k;
    
30.         arr = vector<int>(n), multiplier = vector<int>(k);
    
31.         for(int i = 0; i < n; ++i)
    
32.             cin >> arr[i];
    
33.         for(int i = 0; i < k; ++i)
    
34.             cin >> multiplier[i];
    
35. 
    
36.         dp = vector<vector<int>>(k+1, vector<int>(k+1, INT_MIN));
    
37. 
    
38.         int res = INT_MIN;
    
39.         // we take i elements from left, and k-i elements from right
    
40.         for(int i = 0; i <= k; ++i)
    
41.         {
    
42.             res = max(res, dfs(i, k-i));
    
43.         }
    
44.         cout << res << endl;
    
45.     }

复制代码

[/i][/i]

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

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

hi 楼主, 第一题的 followup, 如果 k > 2 的情况下, multiplier 是需要循环使用吗, 还是 multiplier 的长度跟 k 是一样的

还有第四轮的, 意思是如果 node 的值在 set 里, 就是 valid 的吗, 那假如 root 在 set 里面, 那最短的 path 是不是就是 root 的呢? 谢谢!

sunnybegoffers 发表于 2020-9-27 05:53
hi 楼主, 第一题的 followup, 如果 k > 2 的情况下, multiplier 是需要循环使用吗, 还是 multiplier 的长度 ...

第一题：followup的multiplier的size就是k；
第四题：对的；

居然问l4 scheduler… 这题我面PayPal遇到了，当时用的是创建thread，thread里面sleep… 然后到点后自动开始跑其他代码…
果然狗家面试不一样，这种实打实的代码可不是做题家能做出来的吧

请问楼主round 4 最短的root -> valid node的path， 这里是指只要终点是valid node就可以吗， 还是path里的node全都要是valid的呀

Dido94 发表于 2020-9-27 08:37
请问楼主round 4 最短的root -> valid node的path， 这里是指只要终点是valid node就可以吗， 还是path里的 ...

只要终点是就可以了

第一轮lz给的例子应该是3 * 1 + 4 * 2 = 11 吧？

lz可以详细写一下第三轮的思路吗？谢谢啦， 感觉链接里的贴子写的都不是很对路，看原题的要求是要在addTimer里调用setTimer的API不知道这样写对不对

1. PriorityQueue<Event> pq = new PriorityQueue<>((a, b) -> a.time - b.time);
   
2. MySystem system = new MySystem();
   
3. 
   
4. class Event {
   
5.         Long time;
   
6.         Runnable runnable;
   
7. 
   
8.         public Event(Long time, Runnable runnable) {
   
9.         this.time = time;
   
10.         this.runnable = runnable;
    
11. }
    
12. }
    
13. 
    
14. void addTimer(long durationMillis, Runnable callback) {
    
15.         synchronized(lock) {
    
16.                 long curTime = system.getCurrentMillis() + durationMillis;
    
17.                 // insert time is earlier than the head of the pq, need to schedule task first to override previous one
    
18.                 if (pq.isEmpty() || curTime <= pq.peek()) {
    
19.                         system.setTimer(curTime, callBack);
    
20. } else {
    
21.         pq.poll();
    
22.         system.setTimer(pq.peek().time, pq.peek().runnable)
    
23. }
    
24. pq.add(new Event(curTime, callBack));
    
25. }
    
26. }
    

复制代码

什么职位？