字节跳动

在这里想分享一下周日（2020.9.20）做的字节跳动的算法笔试，挂的很惨，不需积分免费分享给大家，一是求个思路，二是想看看字节算法题的难度相对其他算法题的难度如何。

一共四道题：

1. 算一个字符串的最短循环，比如abababab, ab 就是最短循环， abaaba， aba是最短循环， absdasqwe，就没有循环，返回源字符串。 我的解法是暴力两个for loop，但是只对了90%，应该有类似动态规划解法会更快。

2. Implement 加减乘幂运算， 对于 1e9 + 7 取模，这道题的难点在于如果你不知道对于幂运算取模的高速算法，对于2^100000000就根本算不了，讲解的帖子：https://leetcode-cn.com/problems/super-pow/comments/

3. 给出 若干个 (x1,y1)坐标的人，若干个 (x2,y2)坐标的火车站，火车站离每个人的距离是 |x1-x2| + |y1-y2|， 问哪个火车站距离所有人距离最短。 这道题其实不难，把所有数都加上一个最小的数，然后先算人的X坐标的平均数，Y的坐标的平均数，然后算与火车站分别的距离，我是这么搞的。

4. 这道题特别诡异，先给了很长的关于DAG的定义，然后其实是在考翻硬币的问题.....  具体问题是硬币有两面，分别表示为1，0，给一串长度不等的1，0 list， 问通过若干次翻转是否可以将所有硬币翻为1。 翻转规则是，每翻转一枚硬币，相邻的两枚硬币会跟着翻转，最开始和最结尾相邻的硬币是一枚。 这道题我感觉是贪心算法，但是当时头短路了没有写出来，我之后有时间估计会自己写一写。

不知道地里的觉得字节的算法难度和美国这边大厂的难度比较如何？ 欢迎大家讨论一下。

字节是笔试算法题特难 但是只要做出来一题基本都会给面试。。

第一个是不是可以二分查找？ NLog（N）

觉得有道理请加分

第一题直接用(s+s).find(s,1)
第三题应该是中位数而不是平均数吧？如果偶数个人再取中间两个数的平均
第四题感觉只有两种情况，第一次遇到n个1的时候可以选择向左传递，根据i的奇偶性让左边届消掉1或2个1，因为[1,1,0,0,0..]是可以被消掉的 而[1,0,0,0]不行。第二种就是不向左传递。然后两种情况直接向右推导就可以了。
大概想了一下，不知道有没有bug

素手纫秋 发表于 2020-9-22 23:45
第一题直接用(s+s).find(s,1)
第三题应该是中位数而不是平均数吧？如果偶数个人再取中 ...

谢谢！我准备自己试一试第四题

请问楼主投的是 北美new grad的职位吗？谢谢

第一题感觉上可以用KMP做。构建出失配数组A以后A[-1]对应的应该就是倒数第二个循环的结束。然后再从头检查一下是否真的循环就好。

第四题可以试作为LC995的特殊情形。