字节跳动算法工程师面经
字节跳动 算法工程师一面 （3月30日，60分钟，牛客网视频面）
我投的是AI lab的视觉岗，暑期实习，捞我的是AI lab的算法工程师。
看面经说字节跳动的面试很重视算法，阿里很重视底层，果然没错，我第一次面字节，就被吓到了，全程只有三个算法题（除了自我介绍）。
全程没问我比赛项目。凉凉。太菜了，不知道挂了多少次了，腾讯挂了三次，美团挂了一次，阿里挂了一次，至今不知道二面为何物。
1.自我介绍
2.做个题吧（惊到我了，直接上题，不关心项目）
因为是牛客网视频面，所以代码是可以提交的，并且需要自己写输入输出，不能写伪代码了，能不能AC对方看得到。
题目1：
10个小球，随机分到12个盒子里，求恰好10个盒子都为空的概率。要求用Python程序模拟十万次，暴力求出该概率。
看到这题我懵了，让我蒙特卡洛模拟？伪随机数也不好近似出概率啊，误差大的一批。头一次见不要手推数学公式，特意要求你暴力的数学题。话不多说，动手开始写，balabala,模拟完了，在牛客网一运行，我懵了，输出在十万分之一到十万分之3之间波动（十万次只有两三次恰好10个盒子为空），题目要求一共只能模拟十万次，我开始怀疑人生，检查代码，并且重新设置了随机种子，结果还是很小的概率。一下急了，情急之下打印出来前几次模拟的结果，确实很难出现恰好10个盒子同时为空。然后就跟面试官说，这个概率太低了，同时模拟十万次又太少，所以模拟出来的结果很小。然后面试官没说啥了，直接下一题。好像他也是随便选的题目，自己没做过，只是看到这个题目在题库里分类是数学，就选了这个。我也不知道这个题目的用意是啥，也不知道自己是不是想错了。（PS: 面试之后我直接算概率，C(12,2)*(2^10-2)/(12^10)=1.091e-06,如果我算错了，欢迎各位指出。）
直接计算概率: 10个小球，随机分到12个盒子。每个小球都有12个可能，事件总数是12^10。事件“恰好10个盒子为空”意味着：将10个球随机分到12个盒子的两个盒子中（这两个盒子不能有任何一个为空）。C(12,2)决定是哪两个盒子不为空；将10个球分到两个盒子中，有2^10种可能（不能确保两个盒子均为非空的），需要再减去两个盒子中有一个盒子为空的情况（共2种可能，设盒子为A、B,即“A为空并且B非空”和“A非空并且B为空”这两种可能）。所以最后结果为C(12,2)*(2^10-2)/(12^10)。
（写这一题的时候我用的random包（牛客网系统不让导numpy），random.randint(0,12)，发现数组越界，事后发现原来API果然不一样，random.randint(0,12)包括了右端点12，而numpy.random.randint(0,12)是不包括右端点12的，巨坑，平时使用numpy.random比较多，难怪面试的时候数组越界）
import random random.seed(4) n=100000 cnt=0 for i in range(n): arr=[0]*12 for j in range(10): rnd=random.randint(0,11) arr[rnd]+=1 cnt0=0 for j in range(12): if arr[j]==0: cnt0+=1 if cnt0==10: cnt+=1 print(cnt/n)
题目2：
二分查找元素在有序数组中的位置，如果不存在，输出-1，如果存在，输出下标（存在多个，输出下标最小的）。
水的不能再水的题，但是一开始没处理好有重复数字的情况，只过了30%用例（面试过程你可以自己提交代码，并且可以看到一个错误用例，跟牛客网练习模式一样），比如4,4,5,6,7里面找4，我的代码返回了1，本该返回0。后面处理了一下，AC了，二分都不能一次通过，差点急出一把汗。
def getPos(arr,val): n=len(arr) l=0 r=n-1 while l<r: mid=(l+r)//2 if arr[mid]>=val: r=mid else: l=mid+1 if arr[l]!=val: return -1 return l
题目3：
给定一个数组，找出数组的最长连续子序列。例：3,3,4,7,5,6,8，最长的连续子序列（这里的连续是说连续整数，整个子序列是连续整数，我一开始题都没看明白）应该是(3,4,5,6)，需要返回它们的下标(1,2,4,5)。如果存在多种答案，只需给出任意一组下标。面试官看我不会，让我先写一个暴力的方法，我还是不会啊，然后一个小时过完了，凉凉。
第三题暴力其实很简单，事后再写，五分钟写完了O(n^2)的。
O(n^2)的：
import sys
line=sys.stdin.readline().strip()
n=int(line)
line=sys.stdin.readline().strip().split(" ")
arr=[]
for x in line:
arr.append(int(x))
MAX=0
rtn=[]
for i in range(n):
val=arr[i]
ans=[]
for j in range(i,-1,-1):
if val==arr[j]:
val-=1
ans.append(j)
if MAX<len(ans):
MAX=len(ans)
rtn=ans[::-1]
print(MAX,rtn) O(n)复杂度的（Python的字典查询是O(1)）：
a=[3,3,4,7,5,6,8]
n=len(a)
pre=[0]*n
dic={}
idx={}
MAX_len=0
dic[a[0]] = 1
pre[0] = -1
last = 0
idx[a[0]] = 0
for i in range(1,n):
if a[i] not in dic:
if a[i]-1 not in dic:
dic[a[i]]=1
pre[i]=-1
else:
dic[a[i]]=dic[a[i]-1]+1
pre[i]=idx[a[i]-1]
idx[a[i]]=i
else:
if a[i]-1 not in dic:
pass
elif dic[a[i]]<dic[a[i]-1]+1:
dic[a[i]]=dic[a[i]-1]+1
pre[i]=idx[a[i]-1]
idx[a[i]]=i
if dic[a[i]]>MAX_len:
MAX_len=dic[a[i]]
last=i
rtn=[]
res=[]
while last!=-1:
rtn.append(last)
res.append(a[last])
last=pre[last]
print("val:",res[::-1])
print("index:",rtn[::-1]) 两天后（4月1号）通知这次一面过了，挺意外的，感谢面试官高抬贵手。面了一个月，终于有一个一面过了，感动到哭。。。
二面和HR面的面经在另一个讨论帖： https://www.nowcoder.com/discuss/408301
