2022暑期实习面经---手撕算法题记录

写在前面：主要记录暑期实习面试中的手撕算法题，面试岗位均为机器学习算法工程师

3.30腾讯一面

1. 逆时针打印矩阵，考察模拟，注意边界处理。 (类似LC剑指offer 29:顺时针打印矩阵 )
2. 旋转数组的最小值，考察二分查找，注意重复数字情况。 (LC原题 剑指offer 11:旋转数组的最小数字 )

4.2字节一面

• 记不清楚了。。。应该不难

4.13美团一面

1. 面试官：写个二分查找吧。我：???

4.15字节二面

1. 不用内置函数和幂运算符，计算x的平方根，考察二分，注意x是否大于1。(LC 69:x的平方根 的进阶)
   题目描述：给定正浮点数x，err；计算x的平方根res，要求满足收敛条件：|x^0.5-res|<=err.

4.25京东一面

1. 括号生成，考察dfs+回溯。(原题 LC 22:括号生成 )
2. 构成交替字符串需要的最小交换次数，字符串仅包含0和1，且每次操作只可以交换两个相邻的字符，考察双指针。
   例子：源串s='11100'，要变成目标串10101，最少需要交换3次('11100'->'11010'->'11001'->'10101')
   LC 类似的题：
   • 777.在LR字符串中交换相邻字符
   • 1864.构成交替字符串需要的最小交换次数
   • 1703.得到连续 K 个 1 的最少相邻交换次数

4.28京东二面

1. 求字符串s中包含指定子序列t的方案数，考察动态规划。(LC 原题 剑指Offer II 097:子序列的数目 )
   例子：s = "babgbag", t = "bag", 一共有5种方案: babgbag、babgbag、babgbag、babgbag、babgbag

5.18虾皮一面

1. 输入一个字符串s和整数K, 返回最多包含K种不同字符的最长子串的长度，考察双指针滑窗。(LC 340:至多包含K个不同字符的最长子串 )
   例子：s='acbciaac', k=3, 最长子串长度为5(最长子串为'ciaac')
   LC 类似的题：
   • 3.无重复字符的最长子串
   • 395.至少有 K 个重复字符的最长子串
2. LC 原题，考察动态规划。(123.买卖股票的最佳时机 III )