2016/08/19 Yahoo (E2E team)

没有概念题，两道 Coding：

1、[3, 2, 1, 5, 6, 19, 9, 20] 返回范围  ["1->3", "5->6", "9", "19->20"

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

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

ize="3">     每个station 有 cost [C0, C1, C2...]
     求使得 cost 最小，返回停车加油次数

周珈羽 发表于 2016-8-25 06:22
HR 提示我说，2.2 是要求 cost 最小，所以 dp 应该是minimum cost

2.2   现在 C1 表示在 X1 加油花销，C2 表示在 X2 花销，如 X1 = 60，X2 = 70，X3 = 120，C1 = 80，C2 = 90
就要选择在 X2 停下加油，使得 Cost 最小。

cost(i) : minimum cost   of  driving to  x[i];
function :  cost(i) = min (cost(j)  + c[i] -c[j])  if( x[i] - x[j-1] < 100  0 <j < i
answer cost(n+1);
init cost(0) = 0; cost(1) = c[0]

周珈羽 发表于 2016-8-24 23:28
2.1   Xn 表示第n个加油站相对于出发点的距离，每一次加油最多能走100，比如 X1 = 90，X2  = 120 那你在 ...

try for the dp  correct if  I am wrong :

dp(i) : minum stop  to  x[i]
function  dp(i) = dp(i-1)  if x[i]-x[i-2]<=100
             dp(i) =dp(i-1)+1 if(x[i] -x[i-2] > 100)
answer : dp(n)
initial : dp(0) =0; dp(1) =0;

haobotao000 发表于 2016-8-24 07:44
2.1没理解错的话在前 (Xn - X0)/100 个点停就行了吧。 2.2没太理解，C0是指从station0 到 station1所花费的 ...

2.1   Xn 表示第n个加油站相对于出发点的距离，每一次加油最多能走100，比如 X1 = 90，X2  = 120 那你在到达 X1时候就需要停下加油，求走到 Xn 这一路停得最少次数。

2.2   现在 C1 表示在 X1 加油花销，C2 表示在 X2 花销，如 X1 = 60，X2 = 70，X3 = 120，C1 = 80，C2 = 90
就要选择在 X2 停下加油，使得 Cost 最小。

楼主是new graduate嘛

嗯嗯，是的呀

Crius康 发表于 2016-8-20 15:21
楼主是new graduate嘛

嗯嗯，是的呢~

楼主，请问你可以将你的code贴出来吗？对于求cost最小，返回停车加油次数，我想看看你的答案。

leongzn 发表于 2016-8-24 03:36
楼主，请问你可以将你的code贴出来吗？对于求cost最小，返回停车加油次数，我想看看你的答案。

follow up  没有要求写完代码。她问我用 greedy 还是 DP，我用的 DP，然后叫我写出方程。

2.1没理解错的话在前 (Xn - X0)/100 个点停就行了吧。 2.2没太理解，C0是指从station0 到 station1所花费的油吗？那每次加油能补多少没给啊。

请问楼主在哪里找的内推，可以私信透露下吗

gaocan1992 发表于 2016-8-24 07:55
请问楼主在哪里找的内推，可以私信透露下吗

就 LinkedIn