Citadel Security QR 面经

之前面的Citadel Securities 第一轮，想知道这个题目最好的解法。

45 min 面试：
30 min 聊 research。
15 min 一道coding题目：Given an n by n grid,

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

s. 我用了dp (dynamic programming) 的思路没有写完。求问这个思路是否是对的，或者有没有更好的解法？

就是2维的gambler's ruin问题: https://core.ac.uk/download/pdf/81949317.pdf

应该可以用matrix solution解，dp的话base case 不够clean

expected steps是指数学期望的意思吗？
如果是这样的话，感觉只能dp一步一步推了。概率在达到边界之后就不会再回来了，所以grid里面的总概率会衰减得很快，大概在n步之后就可以忽略不计了。这个时候可以得到一个数学期望的近似收敛值。
感觉这和算法没太大关系啊，更像是电磁学里的discretization，FDTD什么的hh

思路没问题，可以参考利口688，只不过把概率改成步数的期望即可，推到边界外的时候步数期望是0就行

可以用Markov chain解吧

感觉是不是也不用coding，达到四个边界的概率比是1/i, 1/(n-i), 1/j, 1/(n-j)，然后grid上下和左右可以视为两个独立的一维随机游走，任意一个到达边界为结束条件，可以直接得到预期时间是4n/(1/i+1/(n-i)+1/j+1/(n-j))