分享题解攒人品（写题能力严重退化~第一题题意：凸多边形有n条边，每条边上ai个标记，问选三个标记组成三角形的方案数，对1e9+7取模(n<=1e5, ai <=1e9)思路：dpdp[i][j]表示前i条边取了j个标记，有转移式dp[i][j+k] += dp[i-1][j] + C(ai, k) 第i条边取了k个标记。由于j不超过3，k不超过2，且C(ai, k)可以直接乘除得到，复杂度O(n) 看到有大佬容斥思路做的，很妙，没想到哈哈哈。第二题题意: 给定一个字符串，求包含"byte"或者"dance&quo...

暑期第一面凉，来攒攒人品。面试官人很好，就是不太爱问八股，偏实际应用，回答的都不是很全面- 自我介绍- 拷打实习和项目- 如何解决bug？- redis为什么比sql快- 热点数据一定适合放在Redis中嘛？- Kafka延迟写入有什么问题，不包括消息丢失，重复消费，顺序消费- hashmap为啥不安全- 算法：约瑟夫环   很多年没做了，讲了思路，写了没来及测试，时间到了。

小红的图上染色（100%）1e5点数的无向图，有些边是红色，定义一个“好点”当且仅当该点所有邻边都是红边碰到无色的边则标记两个点，最后未被标记的点数就是答案小红的链表断裂（100%）总长1e5的链表，元素不重复，如果可以把该链表一分为二重新拼接后升序则返回true，否则返回false遍历一遍如果没有降序则为true，碰到第一个降序则标记位置重新拼接，整体升序返回true，否则false小红的连通图（100%）1e5点数的无向图，有多少种方法使得添加一条边后图连通并查集合并，最后统计各个集合的点数，若：只有一个集合：答案为n * (n - 1) / 2 - m（n个点m条边）两个集合：答案为两个...

也算是经历了挺多场笔试，大厂笔试难度其实还好，主要是考得范围有些广，需要大家对各个算法都有一定的了解。其中令我印象最深的应该是字符串算法，这个无论是在笔试还是面试中都是非常高频的考点，所以我建议大家有时间一定要把下列字符串的基本算法掌握！1. manacher算法回文串也算是笔试面试常客了，而manacher算法就是用来高效解决回文串问题的，该算法可用来求解回文串个数，不重复回文串个数，最长回文串等等，还可以结合动态规划等算法思想求解更难的问题。2. kmp算法字符串单模匹配也是很常见的问题，kmp则是为高效解决单模匹配问题而生，对其核心的next数组灵活运用，可帮你求解各种单模匹配问题的变体。3. AC自动机如果需要解决字符串多模匹配问题，kmp可能无法胜任，但对其核心的next数组加以改造，便诞生了AC自动机，通过将字典树与next结合，高效的解决了多模匹配问题以及变体问题4. 后缀数组后缀数组堪称字符串算法的瑞士军刀，三个核心的数组rk，sa，height使得该算法可以高效求解更为广泛的字符串问题，如不重复子串计数，单模以及多模匹配等等，具体可自行查阅资料了解。