一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1209|回复: 9
收起左侧

[找工就业] LiveRamp OA C++ 代码加原题

[复制链接] |试试Instant~ |关注本帖
loveonts 发表于 2015-12-10 02:45:20 | 显示全部楼层 |阅读模式

2016(1-3月)-[14]IEOR硕士+<3个月短暂实习/全职 - 网上海投| 码农类全职@LiveRampfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
LiveRamp OA 青蛙过河问题 (好像他家从没变过) Hash + DP 因为他家不给全部的test case,so也不知道是不是代码有问题 望指正。
好像Bucket sort的思想 能把时间减少到O(n) 但实在太难写 我就写了比较straightforward的方法 感觉算是median稍微偏难一点的题目 但还是完全可做的
.鐣欏璁哄潧-涓浜-涓夊垎鍦

写完代码后 还有两道简答 第一道是讲讲你的代码 第二题介绍why LiveRamp

最后求Phone
  1. int EarliestJump(vector <int> &A, int X, int D) {
  2.     // First deal with corner cases
  3.     if (X <= D) {
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  4.         // One jump should be enough
  5.         return 0;
  6.     }
  7.     . 1point 3acres 璁哄潧
  8.     if (A.size() == 0 && X > D) {
  9.         // No leaf drops, but jump is not enough. Waral 鍗氬鏈夋洿澶氭枃绔,
  10.         return -1;
  11.     }
  12.    
  13.     // Using a hash table to store earliest time a leaf drops on one position
  14.     unordered_map <int, int> PosLeaveHash;
  15.     PosLeaveHash[0] = 0;   // Assume starting point has a leaf at time 0
  16.     PosLeaveHash[X] = 0;   // Assume the opposite end has a leaf at time 0
  17.    
  18.     for (int i=0; i<A.size(); i++) {
  19.         if (PosLeaveHash.find(A[i]) == PosLeaveHash.end()) {
  20.             // No leave arrives previously
  21.             PosLeaveHash[A[i]] = i;
  22.         }
  23.     }
  24.    
  25.     // Dynamic Programming: every state represents for the earliest time arriving at this position
  26.     vector <int> DP(X+1, INT_MAX);  // Initiate every point as INT_MAX. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  27.     DP[0] = 0;
  28.    
  29.     for (int pos = 0; pos <= X; pos++) {.1point3acres缃
  30.         if (PosLeaveHash.find(A[pos]) != PosLeaveHash.end()) {
  31.             // Only there are leaves, can a frog reach there
  32.             if (pos <= D) {
  33.                 // If it's with the range of one jump, then frog can reach there as long as a leaf drops. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  34.                 DP[pos] = PosLeaveHash[pos];
  35.             }
  36.             
  37.             else {
  38.                 for (int step = 1; step <= D; step++) {
  39.                     // Iterate through each step to transfer every state
  40.                     if (PosLeaveHash[pos] < DP[pos - step]) {
  41.                         // If a leave drops first, then DP[pos] is the min of pre-step and current's DP value. 1point 3acres 璁哄潧
  42.                         DP[pos] = min(DP[pos], DP[pos-step]);. from: 1point3acres.com/bbs
  43.                     }
  44.                     else {
  45.                         // If a leave drop later, then the earliest time would be PosLeaveHash[pos]   
  46.                         DP[pos] = min(DP[pos], PosLeaveHash[pos]);
  47.                     }
  48.                 }
  49.             }
  50.         }
  51.     }
  52.    
  53.     if (DP[X] == INT_MAX) {
  54.         // Cannot cross
  55.         return -1;
  56.     }.1point3acres缃
  57.     else {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  58.         return DP[X];-google 1point3acres
  59.     }
  60. }
复制代码
面完HR发邮件说 过几天会给结果

Tsien 发表于 2015-12-24 05:59:49 | 显示全部楼层
line 30:
  1. if (PosLeaveHash.find(A[pos]) != PosLeaveHash.end())
复制代码
. more info on 1point3acres.com
shouldn't it be
  1. if (PosLeaveHash.find(pos) != PosLeaveHash.end())
复制代码

?
回复 支持 反对

使用道具 举报

xzhangjohn 发表于 2016-1-8 06:42:17 | 显示全部楼层
Did you get the phone interview finally?
回复 支持 反对

使用道具 举报

Toby 发表于 2016-1-8 06:45:32 | 显示全部楼层
这公司投了也没啥用
回复 支持 反对

使用道具 举报

zzx04025 发表于 2016-1-25 02:50:31 | 显示全部楼层
Toby 发表于 2016-1-8 06:45
这公司投了也没啥用

为什么啊,刚刚投呢。。。是不是因为bar很高拿不到offer啊
回复 支持 反对

使用道具 举报

Toby 发表于 2016-1-26 11:30:20 | 显示全部楼层
zzx04025 发表于 2016-1-24 13:50
为什么啊,刚刚投呢。。。是不是因为bar很高拿不到offer啊

面试完你就知道为啥啦,还是好好准备
回复 支持 反对

使用道具 举报

G_cy 发表于 2016-2-6 02:43:27 | 显示全部楼层
Toby 发表于 2016-1-8 06:45. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这公司投了也没啥用

求大神解读为什么这个公司投了没用。。。
回复 支持 反对

使用道具 举报

calbears 发表于 2016-2-6 07:32:14 | 显示全部楼层
quora上看那个ceo说只有1%不到的录取率。。
回复 支持 反对

使用道具 举报

Toby 发表于 2016-2-8 10:49:05 | 显示全部楼层
G_cy 发表于 2016-2-5 13:43
求大神解读为什么这个公司投了没用。。。

非大神哈,他们招人非常少,不过可以拿面试练手
回复 支持 反对

使用道具 举报

G_cy 发表于 2016-2-8 17:58:58 | 显示全部楼层
Toby 发表于 2016-2-8 10:49
非大神哈,他们招人非常少,不过可以拿面试练手

好吧,我就希望能过OA到能让我练手这个阶段吧。。。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 20:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表