高频美国量化面试题及答案

高频美国量化面试题及答案连续抛一枚公平硬币，直到首次出现序列"HTT"（正面、反面、反面）或"HHT"（正面、正面、反面），问哪个序列更可能先出现？并计算各自的期望等待时间。要解决这个问题，首先需要定义状态，分析状态转移过程。设状态为当前末尾的连续字符序列：S0：初始状态（无字符或最后一个字符不构成任何前缀）S1：最后一个字符是H（可能的前缀为H）S2：最后两个字符是HH（前缀为HH）S3：最后两个字符是HT（前缀为HT）T1：终止状态（出现HHT）T2：终止状态（出现HTT）从S0开始，抛硬币有两种可能：抛H（概率1/2）：转移到S1抛T（概率1/2）：留在S0（因为T不能作为HHT或HTT的有效前缀）从S1（末尾是H）：抛H（1/2）：转移到S2（末尾HH）抛T（1/2）：转移到S3（末尾HT）从S2（末尾HH）：抛H（1/2）：仍留在S2（新的末尾是最后两个H）抛T（1/2）：转移到T1（HHT出现）从S3（末尾HT）：抛H（1/2）：转移到S1（新的末尾是H）抛T（1/2）：转移到T2（HTT出现）现在比较HHT和HTT的出现概率。假设从S0出发，到达T1的概率为P1，到达T2的概率为P2，显然P1+P2=1（必终止于其中一个）。但需要验证是否存在偏向。考虑从S3状态：抛H回到S1，抛T到T2；从S2状态抛T到T1。关键观察是，当处于S1（末尾H）时，抛H到S2，抛T到S3；而S2抛H会留在S2（因为HH的最后一个H可以作为新HH的前缀），而S3抛H会回到S1（HT的最后一个H不能作为HT的前缀，但可以作为H的前缀）。假设从S0开始，到达HHT的概率为p，到达HTT的概率为1-p。从S1出发，设到达HHT的概率为p1，从S2出发为p2，从S3出发为p3。状态转移方程：p=(1/2)p1+(1/2)p（S0抛T回到S0，抛H到S1）→化简得p=p1p1=(1/2)p2+(1/2)p3（S1抛H到S2，抛T到S3）p2=(1/2)p2+(1/2)1（S2抛H留S2，抛T到T1，概率1）→解得p2=1p3=(1/2)p1+(1/2)0（S3抛H到S1，抛T到T2，概率0）→p3=p1/2代入p1的方程：p1=(1/2)1+(1/2)(p1/2)→p1=1/2+p1/4→3p1/4=1/2→p1=2/3。因此p=2/3，即HHT先出现的概率是2/3，HTT是1/3。接下来计算期望等待时间。设E0为S0的期望时间，E1为S1的期望时间，E2为S2的期望时间，E3为S3的期望时间。每次抛硬币时间+1，因此：E0=1+(1/2)E1+(1/2)E0→E0=2+E1E1=1+(1/2)E2+(1/2)E3E2=1+(1/2)E2+(1/2)0（到T1终止，时间停止）→E2=2E3=1+(1/2)E1+(1/2)0（到T2终止）→E3=1+E1/2将E2=2代入E1的方程：E1=1+(1/2)2+(1/2)E3=1+1+(1/2)E3=2+E3/2又E3=1+E1/2，代入得：E1=2+(1+E1/2)/2=2+1/2+E1/4→E1E1/4=5/2→3E1/4=5/2→E1=10/3则E0=2+10/3=16/3≈5.333。对于HTT的期望时间，需要重新定义状态（因为终止条件不同）。设E0'为初始状态期望，E1'（末尾H），E3'（末尾HT），E4'（末尾TT，对HTT无贡献）。但更简单的方法是注意到HTT的期望时间更长，实际计算可得约为8。给定一个股票价格序列P=[p1,p2,...,pn]，其中pi是第i天的收盘价，无风险利率为r（年化），要求用Python实现一个函数计算移动夏普比率（窗口大小为k）。夏普比率定义为（平均超额收益）/（超额收益的标准差），超额收益=日收益率-无风险日利率，假设一年252个交易日。实现步骤：1.计算日收益率：ri=ln(pi/pi-1)（对数收益率）或(pipi-1)/pi-1（简单收益率），通常对数更常用。2.计算无风险日利率：r_day=(1+r)^(1/252)1（连续复利）或r/252（简单）。需明确假设，此处用连续复利。3.计算超额收益：excess=rir_day4.滑动窗口计算：对每个i≥k，取窗口[i-k+1,i]内的excess，计算均值μ和标准差σ（样本标准差，分母n-1），夏普比率=μ/σ。若σ=0（收益无波动），返回0或无穷大（根据需求）。Python代码示例：```pythonimportnumpyasnpdefmoving_sharpe(prices,k,risk_free_rate):n=len(prices)ifn<k:return[np.nan]n窗口不足计算日对数收益率returns=np.log(prices[1:]/prices[:-1])无风险日利率（连续复利）r_day=np.log(1+risk_free_rate)/252年化连续利率r=ln(1+R)，日利率r/252excess_returns=returnsr_day扩展excess_returns长度与原价格序列一致（首日无收益）excess_returns=np.concatenate([[np.nan],excess_returns])滑动窗口计算均值和标准差sharpe=[]foriinrange(n):ifi<k:sharpe.append(np.nan)else:window=excess_returns[ik+1:i+1]包含当前日的超额收益？需确认窗口定义注意：returns长度为n-1，excess_returns长度为n（首元素nan），i从0到n-1正确窗口应为i-1往前k-1个元素（因为returns从i=1开始）修正窗口索引：当计算第i天（i≥1）的k日窗口，对应returns[i-k:i]（左闭右开）ifi<1:sharpe.append(np.nan)continuestart=max(0,ik)window_returns=returns[start:i]iflen(window_returns)<k1:前k-1天窗口不足sharpe.append(np.nan)continueexcess_window=window_returnsr_daymu=np.mean(excess_window)sigma=np.std(excess_window,ddof=1)样本标准差ifsigma==0:sharpe_val=0.0或np.inf，根据业务逻辑else:sharpe_val=mu/sigmasharpe.append(sharpe_val)前k-1天无足够数据，填充nanreturn[np.nan](k1)+sharpe[k1:]测试prices=np.array([100,102,101,105,103,106,104])k=3risk_free_rate=0.022%年化print(moving_sharpe(prices,k,risk_free_rate))```注意：代码中需处理窗口索引的边界条件，确保计算的是过去k个交易日的收益（包括当前日的前k-1个收益）。实际应用中需根据具体需求调整窗口定义（如是否包含当日价格）。一个赌徒有i美元，每次赌博以概率p赢1美元，以概率q=1-p输1美元，直到输光（0美元）或达到N美元（目标）。求赌徒破产概率（输光的概率）。设破产概率为f(i)，边界条件f(0)=1（已破产），f(N)=0（已成功）。状态转移满足：f(i)=pf(i+1)+qf(i-1),0<i<N这是一个二阶线性差分方程。特征方程为pr²r+q=0，解得根r1=1，r2=q/p（当p≠q时）。当p≠q时，通解为f(i)=A+B(q/p)^i。代入边界条件：f(0)=A+B=1f(N)=A+B(q/p)^N=0解得A=-B(q/p)^N，代入第一个方程：-B(q/p)^N+B=1→B=1/(1(q/p)^N)因此f(i)=[(q/p)^i(q/p)^N]/[1(q/p)^N]当p=q=1/2（公平赌博），特征方程有重根r=1，通解为f(i)=A+Bi。代入边界条件：f(0)=A=1f(N)=A+BN=0→B=-1/N因此f(i)=1i/N例如，若p=0.4（输的概率更高），N=100，初始i=50，则(q/p)=0.6/0.4=1.5，破产概率f(50)=(1.5^501.5^100)/(11.5^100)≈(1.5^50)/(1.5^100)=1/1.5^50≈极小值？不，实际计算应为分子分母同乘-1：f(i)=[(q/p)^N(q/p)^i]/[(q/p)^N1]，当q/p>1（p<q），分子分母均为正，且(q/p)^N>(q/p)^i，因此f(i)随i增大而减小，符合直觉：初始资金越多，破产概率越低。设计一个数据结构，支持以下操作：insert(val)：插入一个元素，若已存在则不插入。remove(val)：删除一个元素，若不存在则不操作。getRandom()：等概率返回任意一个元素。要求所有操作时间复杂度O(1)（平均情况）。关键思路是结合哈希表和动态数组：动态数组存储元素，支持O(1)随机访问（通过索引）。哈希表记录元素到数组索引的映射，支持O(1)查找。插入操作：若val已在哈希表中，返回。否则，将val添加到数组末尾，哈希表记录val→数组长度-1（新索引）。删除操作：若val不在哈希表中，返回。否则，获取val的索引i。将数组最后一个元素last_val移动到索引i的位置（覆盖val），更新哈希表中last_val的索引为i。从数组末尾删除last_val（O(1)时间，通过弹出最后一个元素）。从哈希表中删除val的记录。getRandom()：提供0到数组长度-1的随机索引，返回对应元素。示例实现（Python）：```pythonimportrandomclassRandomizedSet:def__init__(self):self.nums=[]存储元素的动态数组self.val_to_idx={}元素到索引的映射definsert(self,val:int)->bool:ifvalinself.val_to_idx:returnFalseself.val_to_idx[val]=len(self.nums)self.nums.append(val)returnTruedefremove(self,val:int)->bool:ifvalnotinself.val_to_idx:returnFalseidx=self.val_to_idx[val]last_val=self.nums[-1]用最后一个元素覆盖当前索引的位置self.nums[idx]=last_valself.val_to_idx[last_val]=idx更新最后一个元素的索引删除最后一个元素self.nums.pop()delself.val_to_idx[val]returnTruedefgetRandom(self)->int:returnrandom.choice(self.nums)```关键点：删除时通过交换最后一个元素到被删位置，保持数组连续，避免中间删除的O(n)时间。哈希表始终维护当前有效元素的索引，确保插入、删除、随机访问均为O(1)。求解随机微分方程（SDE）dX(t)=μX(t)dt+σX(t)dB(t)，其中B(t)是标准布朗运动，初始条件X(0)=x0。这是几何布朗运动（GBM），常用于股票价格建模。使用伊藤引理求解。设Y(t)=ln(X(t))，则根据伊藤引理：dY=(∂Y/∂X)dX+(1/2)(∂²Y/∂X²)(dX)²计算偏导数：∂Y/∂X=1/X，∂²Y/∂X²=-1/X²dX的二次变差项：(dX)²=(σXdB)²=σ²X²(dt)（因为(dB)²=dt，交叉项dtdB=0）代入得：dY=(1/X)(μXdt+σXdB)+(1/2)(-1/X²)(σ²X²dt)=μdt+σdB(σ²/2)dt=(μσ²/2)dt+σdB这是一个关于Y(t)的随机微分方程，其解为：Y(t)=Y(0)+(μσ²/2)t+σB(t)因为Y(0)=ln(X(0))=ln(x0)，所以：X(t)=exp(ln(x0)+(μσ²/2)t+σB(t))=x0exp((μσ²/2)t+σB(t))验证：当σ=0时，退化为普通微分方程dX=μXdt，解为X(t)=x0e^(μt)，符合预期。当μ=0时，解为几何布朗运动的纯扩散形式，体现对数正态分布特性。100个球，50红50蓝，分成两个盒子（可以空盒），如何分配使得随机选一个盒子（概率各1/2）并从中摸一个球是红球的概率最大？设第一个盒子放r个红球，b个蓝球（r≤50，b≤50），第二个盒子放50-r红，50-b蓝。总概率P=(1/2)(r/(r+b))+(1/2)((50-r)/(100rb))（假设盒子非空时分母为球数，若盒子为空则概率为0）。要最大化P，考虑极端情况：若第一个盒子放1红0蓝（r=1,b=0），则第一个盒子摸红概率1/1=1；第二个盒子放49红50蓝，概率49/99≈0.4949。总P=0.51+0.5(49/99)≈0.5+0.247≈0.747。若第一个盒子放0红0蓝，总P=0.50+0.5(50/100)=0.25，更小。若第一个盒子放50红0蓝，第二个盒子0红50蓝，P=0.51+0.50=0.5，小于0.747。若第一个盒子放1红1蓝，概率=0.5(1/2)+0.5(49/98)=0.25+0.25=0.5，更小。关键在于让一个盒子的红球概率尽可能接近1（如放1红0蓝），另一个盒子尽可能保留多的红球但分母小。数学证明：设第一个盒子r红，b蓝，r≥1，b=0，则P=0.5(r/r)+0.5((50-r)/(100r))=0.5+0.5(50r)/(100r)。求导得dP/dr=0.5[(100r)(50r)(-1)]/(100r)^2=0.5[-100+r+50r]/(100r)^2=0.5(-50)/(100r)^2<0，因此P随r增大而减小。故r=1时P最大，为0.5+0.5(49/99)≈0.747。两个玩家轮流从1到10中选一个数（可重复选），累加和初始为0，先使总和≥100的玩家获胜。问先手是否有必胜策略？逆向分析，确定“必胜点”：若当前总和为s，玩家选x（1≤x≤10）后s+x≥100，则获胜。因此，当s≥90时，当前玩家可以选10-s%10（或直接选100-s）获胜。关键观察：若玩家能使每轮后总和增加11（1+10,2+9,...,10+1），则可以控制对手进入必败点。例如，先手选a，后手选b，则先手选11-b，使两轮总和增加11。这样，先手可以确保在第9轮后总和为911=99，此时后手必须选x（1≤x≤10），总和变为99+x≥100，后手获胜？不，这矛盾，说明逆向推导更准确。正确逆向：若当前总和s≥90，当前玩家选100-s（若s≤99）或任意数（s≥100）获胜。若s=89，当前玩家选1→s=90，对手获胜；选2→s=91，对手选9→s=100，对手胜。实际上，当s=89时，无论选x（1≤x≤10），对手都能选10-x+1？不，更简单的方法是找到“安全点”s=100k11，k=1,2,...例如，安全点为89（100-11）、78（100-22）、…，直到s=100-911=1。若先手第一次选1，使总和=1（安全点），之后无论后手选x（1-10），先手选11-x，使总和增加11，保持在安全点序列（1→12→23→…→89→100）。当总和到89时，后手选x（1-10），总和变为89+x，先手选100-(89+x)=11-x，若89+x≥90，先手直接获胜。例如：先手选1（总和1）后手选5（总和6），先手选6（11-5），总和12后手选3（总和15），先手选8（11-3），总和23…总和到89时，后手选7（总和96），先手选4（100-96=4），总和100，先手胜。因此，先手有必胜策略：第一步选1，之后每轮选11减去对手选的数，确保总和按11递增，最终先手达到或超过100。假设某资产收益率r~N(μ,σ²)，持有期为T天，计算在95%置信水平下的VaR（风险价值）。若收益率不服从正态分布，需如何调整计算方法？VaR定义为在一定置信水平下，某一持有期内的最大可能损失。对于正态分布，VaR=-μT+σ√TZα，其中Zα是标准正态分布的α分位数（α=5%时Zα≈-1.645）。通常取绝对值，VaR=μTσ√TZα（若μ=0，简化为σ√T1.645）。若收益率非正态，常用方法：1.历史模拟法：用历史收益率排序，取5%分位数作为VaR。2.蒙特卡洛模拟：提供大量非正态分布的模拟收益率（如t分布、GARCH模型），计算分位数。3.半参数法：假设分布尾部用极值理论（EVT）拟合，中间部分用经验分布。4.协方差-矩阵法扩展：加入偏度、峰度调整，如Cornish-Fisher展开，修正分位数Zα=Zα+(Zα²-1)γ/6+(Zα³-3Zα)(κ-3)/24(2Zα³-5Zα)γ²/36，其中γ是偏度，κ是峰度。有n级台阶，每次可以走1、2或3步，但不能连续走3步（即若上一步走了3步，当前步只能走1或2步）。求走n级台阶的方法数。动态规划状态定义：dp[n][0]：走到第n级，且最后一步走了1或2步（非3步）的方法数。dp[n][1]：走到第n级，且最后一步走了3步的方法数。转移方程：最后一步走1或2步（状态0）：前一步可以是状态0或状态1（因为上一步是否走3步不影响当前走1/2步），且当前步走1或2步。dp[n][0]=(dp[n-1][0]+dp[n-1][1])2（走1或2步）？不，实际是：若当前步走1步，则前n-1级可以是状态0或1，方法数为dp[n-1][0]+dp[n-1][1]。若当前步走2步，则前n-2级可以是状态0或1，方法数为dp[n-2][0]+dp[n-2][1