LiveRamp OA之青蛙過河

剛做完LiveRamp的OA題，結果尚未揭曉，不過想和各位討論一下自己的解法。
LiveRamp在Codility上的online test的題目好像就那一題青蛙過河，有朋友說他投很多次履歷，每次都做到同一題；版上有人說做過別的題目，不確定是不是因為職位別不同的關係。
先把 algorithm的架構講一下：
首先需要trace每個位置是否已經有葉子，因為葉子會重覆掉落在相同位置上，如果某位置上已有葉子，就可以不用做 => 建一個 size = X 的 boolean array
接著我們要用類似 dynamic programming的方法來解，需要兩個 variable: fwd_fp和bwd_fp，分別代表「從0往下跳最遠可到達的點」和「從X往前跳最遠可到達的點」
fwd_fp 初始

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

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

me complexity = O(n)；判斷是否已有葉子的array 是size X，所以space complexity = O(X)。







补充内容 (2015-11-4 17:51):
忘記論壇的語法會把 [ i ] 視為斜體命令；文中除了 "array A"之外的所有大寫 A 都是指 A[ i ] ：A的第 i 個元素。