[汇总] 转码选手20+公司技术面遇到的较难coding题

为了赚米看帖，最近开始写点总结，求加米！


关于转码的面试过程和经验小结，可以参考这篇
https://www.1point3acres.com/bbs/thread-903131-1-1.html

经历了各大厂的技术面，总体来说都是leetcode题或者变形题。推荐大家面试前刷标签的高频题。这里分享一些我遇到过的medium-hard题。

--------------------

》》Google 电面1
写一个公司员工的class，有普通员工，manager和CEO三类（一个人有且只有report给一人，CEO除外）。（面试官其实就是希望你写这个class生成一个graph为follow up做准备，这个graph中key是manger, value是report给manger的所有员工）
follow up 1: 从graph中找出CEO。
follow up 2: CEO传递message一层一层下去直到某一个普通员工，最快要多久？

Google 电面2:
就是一个普通DFS/BFS求路径的问题，具体有点忘了，没啥trick，不是很难。

--------------------

》》Google VO 第一轮
BFS/DFS求最短路径的题，就是leetcode上飞机飞不同城市的最小花费的变形 （Leetcode 787变形，没有num of stops的要求, 给的条件是各个航班的时间表，包括【起飞时间，到达时间，起飞地点，到达地点】，求最快从A地到达B地的时间，还是用heapq + bfs）

VO第二轮是HM的BQ轮，都是常规的BQ。

VO第三轮是一道list的题目，具体忘了，medium的题分了两问，好像是heapq求解，不是很难。

--------------------

》》Google VO 最后一轮
感觉挺难的：只有ABC三个字母，每个字母数目相同，有多少种不同的组合？并返回各种不同的组合。
比如三个字母都有两个：AABBCC,BBCCAA,ABCABC....
follow up: 这些组合中包含ABC序列（subsequence）的有多少个？
比如AABBCC,ACBBAC都满足条件，AACCBB,CCXXXX不满足条件.

--------------------

》》Waymo电面：
Restaurant Waiting List, add and delete custom in O(1) time
. check 1point3acres for more.题意大概是写一个class安排排队的customers，实现
1.开始排队（餐厅有各种不同数量的table类型，每个customer ID也有一定数量的人，最后安排座位时要满足座位数>=customer人数。）
2.取消排队（customer ID中途离开了）
3.有空余座位后按先后顺序安排给合适的customer（比如有个table有5各座位，需要把它安排给人数不超过5的customer ID）
Follow-up:
1，2如何实现O(1)time complexity

--------------------

》》Twitch （电面）
有三类卡片：
A类: 有50张（每张不同），A类每张被抽到概率都一样90%
B类: 有10张（每张不同），B类每张被抽到概率都一样8%
C类: 有2张（每张不同），C类每张被抽到概率都一样2%
抽卡方式：
每次抽5张（为一组），直到抽到C类卡片为止（只要那组中有C就可以），返回每次抽到的每组卡片，没有抽到C就不停放回去重新再抽
follow up:
还是相同的抽卡方式，每次抽了一组后统计具体抽了那些卡，然后放回去重新抽。直到ABC每类卡中的每张都被抽过至少2遍后停止。返回得抽多少次才满足条件 （每次返回的答案肯定不一样，数学问题）

--------------------

》》 TikTok VO最后一题：
给定一个很长的整数，求其平方根（不能用function直接求）。面试官解释到，这个整数特别特别长，一般c++不支持直接求，虽然python可以直接求，但是这里不允许。。
例子：
input:
16184376115026738589251576634554060416080719792960076369818259654580599251323077384820961
output:
127217829391271798216891268261913129182391281
》
面试官直接提示，分几步走：
. 1point 3acres 1. 如果现在支持很大的两个数相乘（任何两个大数都可以直接相乘），如何求解上面的题目？
brutal force: 比如要求num的平方根，那就从1开始尝试，1*1，2*2， 3*3，.... 直到 n*n<=num and (n+1)*(n+1)<num, 那结果就是n
改进1：比如num=128812391....298281837 (例如一共20位)，那肯定有 10^20<=num<=10^21, 所以可以从10^10开始循环，直到满足n*n<=num and (n+1)*(n+1)<num
改进2：同样用"改进1"的例子，设 left边界为10^10, right边界为10^11, 基于binary search考查mid=(left+right)//2是不是解，然后在while循环中移动left/right （面试官问：time complexity是多少）

2. 如果现在只支持最大m位数的乘法，如何写一个function求解两个大数相乘（比如最大只支持0-999内的乘法，如何算2318728 x 83924938）
思想：把这两个大数按m切成很多块： （2 E6 + 318 E3 + 728 E0） x （83 E6 + 924 E3 + 938 E0）。开一个hash map, 把power相同的乘积放一起相加，key就是power number，val就是相同power下求得的和： {0：938*728； 3：318*938+924*728； 6：2*83}，最后依次加在一起就可以了。

3. 对于加法，如果只支持最大m位数相加，如何求两个大数相加？
类似2，但还要考虑可能越位的情况（这种题到后面肯定只需要分析方法，不需要写代码跑出来）

1，2，3问加在一起，解决最初问题

--------------------

VO题（Waymo还是哪家有点忘了）:
给定一个二维数组，里面的数值表示一个路口的红灯等待时间，从左上角开车到右下角，最快需要多久（可以上下左右的走）？（其实就是从所有路径中选择某条路径：这条路径中的最大值是所有路径中最小的。也就是说走过某个路口后，所有路口的时间都在流动：1s前某个路口等待时间是5s，那这一秒之后这个路口的等待时间就变成4s。所以其实就是要使选择的这条路径中的最大值是所有路径中最小的即可）
例子:
1 2 1 3
7 3 5 1
1 6 5 8
2 3 1 0
应该选择 1-> 2 -> 1 -> 5 -> 5 -> 1 -> 0 (最佳路径的其中之一) ---> 返回 5就行，不需要返回路径
（还是heapq+BFS求最短路径，不要回溯！不要dp！）
follow up: 同样的问题，这次只能向右或者向下走，应该怎么求解？（heapq+BFS照样能求解，而且就改原来代码一处就行，O（nlogn）复杂度；但明显面试官在考dp，o(n)时间复杂度。n是所有元素数量）

--------------------

DoorDash (没记错的话) VO
Number of Islands 变形 （里面除了0，1还有2，3，4…。0是什么都没有，1，2，3…表示不同颜色的快递），返回快递的数量。
follow up1: 形状一样的快递以及数量 （跟颜色无关了，只看形状）；
follow up2: 形状一样的快递以及数量（这次只要通过“翻转”某个角度形状一样就算是一样的）

--------------------

其他遇到的仍然有印象的题：

@yahoo VO & Tesla VO
Coin Change 2

@ Microsoft
电面：写树的三种遍历方式。follow up: 不能用recursion应该怎么写？follow up: resursion实际应用中有什么缺点？(这个是电面，其他是VO)
VO: Word Search 变形（不仅仅可以上下左右，对角也可以看作是相连的），follow up: time complexity 是多少？

@ Bloomberg （电面&VO）
Design an Ordered Stream
Design Browser History
Meeting Rooms II

@ Oracle
Trapping Rain Water （电面）

@ Amazon
Sum of Subarray Ranges (OA)

@ Citadel
Subarray Sum Equals K （OA）

--------------------

》面了很多家，还遇到过很多easy，medium偏easy的题，但记不住了。整体上肯定不会偏难！！

》总体而言，高频题很多，大家如果刷了200-300题肯定会觉得大多数都很熟悉。建议刷高频题，有些不会的可以反复刷，不需要苛求刷题数量。

. Χ》最后，求加米！




. 1point 3 acres

谢谢楼主，不错的分享

CHENCYZW 发表于 2022-6-13 13:37
不是，可以选任何语言。但是vo我遇到了两轮data fluency，只能用python

按这个概率来说，waymo VO python反而变成必需的了..

pptmaster 发表于 2022-6-13 20:04
按这个概率来说，waymo VO python反而变成必需的了..

跟具体职位相关，其实我也不清楚为啥让我面data fluency，完全不会。。

Waymo是不是只能C++?

pptmaster 发表于 2022-06-13 13:32:59
Waymo是不是只能C++?

不是，可以选任何语言。但是vo我遇到了两轮data fluency，只能用python

谢谢楼主！

谢谢分享 mark

谢谢分享！紫薯紫薯

定个坐标