Tiktok Intern OA

前面两道选择题，都很简单，没啥问题
算法第一题，给出一个序列a和序列b，问能不能通过给序列a的一部分或者全部元素 + 1，让a成为b的一个permutation
都2202年了，还有人把数组以string形式传参，差评！！而且这题卡常，

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

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

二维树状数组写的一个n^5大dp，最后t了一个点，挺复杂的，写到最后人都麻了。
然后总结，整体体验很一般。a了2题多，看脸了。

tiany7 发表于 2022-10-4 21:23
第一题O(nlogn)会被卡，今天朋友线性复杂度也被卡了

这题还能线性复杂度吗，不sort感觉没有办法做呀

微信用户_7038874 发表于 2022-10-5 01:05
米少看不了，可以贴回复里吗？

前面两道选择题，都很简单，没啥问题
算法第一题，给出一个序列a和序列b，问能不能通过给序列a的一部分或者全部元素 + 1，让a成为b的一个permutation
都2202年了，还有人把数组以string形式传参，差评！！而且这题卡常，差评x2！！不是很懂又考输入处理又卡常有啥意义，没活整了可以咬个打火机。最后做了一些常数级别优化过了。
第二题，给出n个雨伞，每个雨伞能覆盖a[i]个人，有无限把，问m个人最少需要几把雨伞能覆盖掉
这个很裸，不多赘述了
第三题，就是给出一个01矩阵，每次横切或者竖切，横切上半部分丢弃，下半部分继续，竖切左边丢掉，右边继续，问有多少种方法切成k块，使得每一块包含至少一个1
这个不给范围，但是hidden case的cout能看输入范围，n，k是50。没啥思路，二维前缀和不会，用二维树状数组写‍‌‍‌‍‍‍‌‍‌‌‍‌‌‌‌‍‍‌‍的一个n^5大dp，最后t了一个点，挺复杂的，写到最后人都麻了。
然后总结，整体体验很一般。a了2题多，看脸了。

Sean2018 发表于 2022-10-4 21:48
这题还能线性复杂度吗，不sort感觉没有办法做呀

我用了2个map分别存对应数字的个数，然后从listA拿数字 ai 比较mapA和mapB里 ai 和 ai+1 对应的个数。这样时间复杂度是O(n)的。

反倒是之前看的sort的做法“先sort 了一下a, b list, 然后scan 从头到尾， 如果a[i] != b[i] and a[i]+1!=b[i], 就return false”。我感觉这个做法是对的，然而写出来有1/3的testcase过不了 不知道哪写错了。。

用的java，两种方法都没出现TLE

楼主可以分享下第二题思路吗

匿名用户 发表于 2022-10-4 09:24
楼主可以分享下第二题思路吗

第二题是完全背包问题模板题

二维树状数组意义何在。。。都没修改
不会有人写只有查询的树状数组吧，不会吧不会吧

匿名用户 发表于 2022-10-03 19:40:57
二维树状数组意义何在。。。都没修改
不会有人写只有查询的树状数组吧，不会吧不会吧

我不会推二维前缀和，只会用，但忘了怎么推了，不过50这个数据而这差距不大吧。他有监考，我也不能切出去查啊

请问卡常是什么意思

LeoLv 发表于 2022-10-03 20:09:24
请问卡常是什么意思

就是说有些算法之间复杂度一样，但是有些人的写法可以ac，有些人不行，这个就是常系数的区别，这样搞没有任何意义，脱离算法本身了

tiany7 发表于 2022-10-3 23:16
就是说有些算法之间复杂度一样，但是有些人的写法可以ac，有些人不行，这个就是常系数的区别，这样搞没有 ...

哦哦懂了 请问第一题是要求O(n)的么

想请问第一题楼主是用什么语言做的遇到卡常了呀 听做过的朋友说好像python c++ js没有这个问题

我一个题都没看懂