🐶 昂赛 + match 后还是没过HC

匿名者 发表于 2021-11-17 16:25
一维就够了。长度为K的数组 （K是圈数）。 第i个位置是跑i圈的最佳成绩，因为从 i 到 i+1 就只有停和不停 ...

一维数组的话第i圈不停状态转移方程不好写啊，因为不停的话得知道 i-1 圈用的是哪种轮胎，以及那个轮胎已经磨损了几圈。有点不理解 -_-

楼主，第四题感觉一维数组转换方程写不出来啊...

patpat 极少的情况match完后过不了hc

可以麻烦楼主分享下轮胎那题1维Dp的写法吗  因为有N中轮胎 所以要记录目前最优，还要记录上一轮是哪个轮胎以及那个轮胎用几轮了呀 只想到三维 谢谢啦

匿名者 发表于 2021-11-17 17:25
一维就够了。长度为K的数组 （K是圈数）。 第i个位置是跑i圈的最佳成绩，因为从 i 到 i+1 就只有停和不停 ...

一维不够吧？至少需要知道上一圈用了哪种轮胎，以及是那条轮胎被使用的第几圈？

2. DP+二分，dp[k]表示第k位置可接受的最小值，返回dp填坑的长度
3. 取出所有房子坐标，dfs+backtracking求解，注意比较是否需要种新花，如果需要，确定新的花不会和已种的row/col发生collision
4. DP，dp[k]表示跑k圈需要的最短时间，初始化的时候dp[k]=Min(不换胎单一轮胎跑k圈总时间)，k属于(0, K)。然后从0<i<K, 0<j<i循环，计算包括换胎在内跑k圈最短时间，dp[i] = min(dp[i], dp[j] + dp[i-j] + p)。返回dp[k]
5. 经典线段树，如果要最优化空间可能要用到Binary Indexed Tree。。。如果要求写这个也太难了。。。

lxy16555 发表于 2021-11-18 21:20
2. DP+二分，dp[k]表示第k位置可接受的最小值，返回dp填坑的长度
3. 取出所有房子坐标，dfs+backtracking ...

我直接给你跪下，收下我的膝盖，太强了。你第四题用了多久想清楚的？我和我同学俩人面试后花了一个多小时才想明白。。。

介意我把你的答案复制补充到主贴里吗？我会属上你的名字的。

匿名用户 发表于 2021-11-16 21:21:11
1. 是的，有support letter几率会大
2. 有拿到，hr明确和我说会把support letter放到面试的feedback，做成一个packet，一起拿给HC看。
3. 我当时聊了

谢谢，我和hm聊完就没有消息了， hr说他有update会跟我说。但是3天过去了……我感觉可能凉凉了……

匿名者 发表于 2021-11-18 20:41
我直接给你跪下，收下我的膝盖，太强了。你第四题用了多久想清楚的？我和我同学俩人面试后花了一个多小时 ...

不介意。

一开始读完第四题就感觉是个DP，然后就想DP[k]来表示跑k圈，然后又涉及到轮胎，我一开始想的是DP[k][n]表示用第n个轮胎跑完第k圈的最短时间，然后发现没法去确定到底这个轮胎已经用了多久，然后考虑到最单纯的情况就是不换胎，发现DP[k]就够了，大概半小时这样吧

寒水依痕moon 发表于 2021-11-19 13:16
谢谢，我和hm聊完就没有消息了， hr说他有update会跟我说。但是3天过去了……我感觉可能凉凉了……

有可能吧，我当时team match时，对我感兴趣的manager，要么直接和HR说可以，要么book一个我和他们Tech lead的另外一个1:1。一般面完之后啥消息都没有的，那就是不感兴趣。。。不过我觉得也看recruiter的，有些recruiter就是很慢。。。