买新车如何让dealer直接竞价?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 5417|回复: 44
收起左侧

Google on campus

[复制链接] |试试Instant~ |关注本帖
我的人缘0
22691482 发表于 2014-10-31 01:57:15 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

2014(10-12月) 码农类General 硕士 全职@Google - 内推 - 校园招聘会  | Other |

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

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

x
两轮连续45分钟。.本文原创自1point3acres论坛

第一轮:
1. 一串数,例如 10, 20,30,40,20,50,25. 两个玩家,只能选最左或最右,轮流选,怎样max你的和。举出贪心反例。用max-min。
2. reverse linked list, 一次 K 个。

第二轮:
int returnRandomNumber(int max, vector<int> &bad_numbers){
}. from: 1point3acres
返回0-max之间的随机数,不能包含bad_numbers之中的数。bad_numbers是排好序的。

都没见过。面试官会一起讨论解法。

. 牛人云集,一亩三分地
补充内容 (2014-11-1 03:02):
第一题DP解法:http://leetcode.com/2011/02/coins-in-line.html

评分

参与人数 4大米 +103 收起 理由
北美农民 + 60
Arthur2012 + 3 感谢分享!
rsun + 10
nunuh89 + 30

查看全部评分


上一篇:新人请教,Epic OA到onsite要等多久
下一篇:Amazon OA面经
我的人缘0
pf22099 发表于 2014-10-31 02:43:50 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
reverse linked list里的一次 K 个是啥意思?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| 22691482 发表于 2014-10-31 03:04:20 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
pf22099 发表于 2014-10-31 02:43. visit 1point3acres for more.
reverse linked list里的一次 K 个是啥意思?
. 1point3acres
Leetcode那个。。
回复 支持 反对

使用道具 举报

我的人缘0
pf22099 发表于 2014-10-31 03:05:01 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
. Waral 博客有更多文章,
噢···了然了然,多谢!
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| 22691482 发表于 2014-10-31 04:05:28 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
pf22099 发表于 2014-10-31 03:05
噢···了然了然,多谢!

校友你好 !! 哈哈
回复 支持 反对

使用道具 举报

我的人缘0
pf22099 发表于 2014-10-31 04:27:32 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
22691482 发表于 2014-10-30 12:05
校友你好 !! 哈哈

哈哈,Trojans遍天下啊
回复 支持 反对

使用道具 举报

我的人缘0
忽而今夏 发表于 2014-10-31 12:25:07 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
请问楼主能否说一下randomNumber那个题的做法?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| 22691482 发表于 2014-10-31 12:37:27 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
忽而今夏 发表于 2014-10-31 12:25
请问楼主能否说一下randomNumber那个题的做法?

说来话长啊。。。主要是跟面试官聊,一步步的改进时间和空间。。更注重过程吧。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
averillzheng 发表于 2014-11-4 03:15:17 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第一题比较容易:
  1. public class MaxGame {
  2.         public static int maxGame(int[] arr) {
  3.                 if(arr == null || arr.length == 0)        return 0;
  4.                 int len = arr.length;
  5.                
  6.                 //calculate the sum from index i to index j-google 1point3acres
  7.                 //dynamic programming method
  8.                 int[][] segSum = new int[len][len];
  9.                 for(int i = 0; i < len; ++i)        segSum[i][i] = arr[i];
  10.                 for(int i = 0; i < len; ++i) {                       
  11.                         for(int j = i + 1; j < len; ++j) {                               
  12.                                 segSum[i][j] = (segSum[i][j - 1] + arr[j]);. 一亩-三分-地,独家发布
  13.                         }
  14.                 }. 牛人云集,一亩三分地
  15.                
  16.                 //dynamic programming method to find the max picks
  17.                 int[][] maxPick = new int[len][len];
  18.                 for(int i = 0; i < len; ++i)                maxPick[i][i] = arr[i];
  19.                 for(int i = len - 2; i >= 0; --i) {
  20.                         for(int j = i + 1; j < len; ++j) {
  21.                                 maxPick[i][j] = Math.max(arr[i] + segSum[i + 1][j] - maxPick[i + 1][j],
  22.                                                                              arr[j] + segSum[i][j - 1] - maxPick[i][j - 1]);. Waral 博客有更多文章,
  23.                         }
  24.                 }               
  25.                 return maxPick[0][len - 1];
  26.         }
  27.        
  28.         public static void main(String[] args) {
  29.                 int[] arr = new int[] {1, 2, 2, 3, 2,1};
  30.                 System.out.println(maxGame(arr));
  31.         }
  32. }
复制代码
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| 22691482 发表于 2014-11-4 03:20:17 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

你好,,请问代码里面的segsum是干嘛的?
回复 支持 反对

使用道具 举报

我的人缘0
averillzheng 发表于 2014-11-4 03:23:15 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
22691482 发表于 2014-10-31 12:37
说来话长啊。。。主要是跟面试官聊,一步步的改进时间和空间。。更注重过程吧。

random number 那题,说说你的想法。
回复 支持 反对

使用道具 举报

我的人缘0
averillzheng 发表于 2014-11-4 03:24:59 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
22691482 发表于 2014-11-4 03:20
你好,,请问代码里面的segsum是干嘛的?

注释里不是说了,用来存从index i 到index j 的所有元素的和。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| 22691482 发表于 2014-11-4 03:47:15 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
averillzheng 发表于 2014-11-4 03:24. from: 1point3acres
注释里不是说了,用来存从index i 到index j 的所有元素的和。

maxPick[j] = Math.max(arr + segSum[i + 1][j] - maxPick[i + 1][j],
                                    arr[j] + segSum[j - 1] - maxPick[j - 1]);
. 牛人云集,一亩三分地
可不可以详细解释下这个递推式?

maxPick 是 从 i 到 j 可以得到的max sum 吗?
segSum[i + 1][j] - maxPick[i + 1][j] 是从i+1 到 j 另外一个玩家得到的maxSum吧? . 1point3acres

谢谢。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| 22691482 发表于 2014-11-4 03:51:33 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
averillzheng 发表于 2014-11-4 03:23. more info on 1point3acres
random number 那题,说说你的想法。
. 围观我们@1point 3 acres
首先是把0到max用个数组存起来
面试官说优化空间
然后我说用个哈希表去掉bad numbers
面试官说再优化空间. 牛人云集,一亩三分地
然后提示1,2,3,4,5. 如果bad numbers {2,3}, 随机到3,我从3往右边走,会有什么问题。 来源一亩.三分地论坛.
我说4的概率会比其他大。
然后提示max - size of bad numbers 会得到什么?
然后我说可以只随机max - size of bad numbers 个数。
这个可以用两个指针,一个从0到max,一个指在bad numbers数组里面。
然后他说再优化空间.留学论坛-一亩-三分地
可以直接看bad numbers里面的数,得出“good numbers” 的个数,然后根据随机数返回。

回复 支持 反对

使用道具 举报

我的人缘0
averillzheng 发表于 2014-11-4 04:21:51 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
22691482 发表于 2014-11-4 03:51
首先是把0到max用个数组存起来
面试官说优化空间
然后我说用个哈希表去掉bad numbers
. 1point 3acres 论坛
这个题主要是怎么样弄才能使每个数出现的概率一样。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| 22691482 发表于 2014-11-4 05:56:19 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
averillzheng 发表于 2014-11-4 04:21
这个题主要是怎么样弄才能使每个数出现的概率一样。

就是讨论吧。。。 直接给最优解估计面试官也会很迷茫。。

你看看我回你的那个DP解法。
回复 支持 反对

使用道具 举报

我的人缘0
averillzheng 发表于 2014-11-4 07:01:12 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
22691482 发表于 2014-11-4 03:47
maxPick[j] = Math.max(arr + segSum[j] - maxPick[j], . from: 1point3acres
                                    arr[j] + ...
. 1point 3acres 论坛
你理解的都是对的。
maxPick[j]就是表示从i到j第一个player可以得到的最大的。
他可以取arr也可以取arr[j]. 当他取了一个之后他就在后面的过程中成了第二个player。. 围观我们@1point 3 acres
所以它能得到的就是arr + total sum  from (i + 1) to j - 从i +1 to j第一个player的maxPick, 或这arr[j] + total sum from i to (j - 1) - 从 i  to (j - 1)第一个player 的maxPick。 这就是那个递归的含义。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| 22691482 发表于 2014-11-4 08:14:44 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
averillzheng 发表于 2014-11-4 07:01
你理解的都是对的。
maxPick[j]就是表示从i到j第一个player可以得到的最大的。. visit 1point3acres for more.
他可以取arr也可以取arr ...

我有个地方还是不太清楚。。 不好意思。。

maxPick[j]都是表示player1的吗?

如果是的话:total_sum[i+1,j] - maxPick[i+1,j] 应该表示的是player2的解。

那么arr + player2 的解是什么意思?
回复 支持 反对

使用道具 举报

我的人缘0
averillzheng 发表于 2014-11-4 10:38:34 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
22691482 发表于 2014-11-4 08:14
我有个地方还是不太清楚。。 不好意思。。

maxPick[j]都是表示player1的吗?

player1 已经取了arr【i】 或者arr【j】。
这样player1 就变成了player2. 而原来的player2 就变成了player1.
回复 支持 反对

使用道具 举报

我的人缘0
averillzheng 发表于 2014-11-4 10:41:57 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
随机数的题就是用两个random就可以了。
我取max = 10, badNum = [2,3,7];
run 了我的代码1000000000 次,得到的结果是:
142863390 142859239 0 0 142869697 142870183 142844284 0 142860162 142833045
每个数都可以等概率的得到。
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-6-22 17:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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