一亩三分地论坛

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

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

Google on campus

[复制链接] |试试Instant~ |关注本帖
22691482 发表于 2014-10-31 01:57:15 | 显示全部楼层 |阅读模式

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

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

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

x
两轮连续45分钟。

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

第二轮:
int returnRandomNumber(int max, vector<int> &bad_numbers){.鐣欏璁哄潧-涓浜-涓夊垎鍦
}
返回0-max之间的随机数,不能包含bad_numbers之中的数。bad_numbers是排好序的。

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


补充内容 (2014-11-1 03:02):
第一题DP解法:http://leetcode.com/2011/02/coins-in-line.html

评分

4

查看全部评分

pf22099 发表于 2014-10-31 02:43:50 | 显示全部楼层
reverse linked list里的一次 K 个是啥意思?
回复 支持 反对

使用道具 举报

 楼主| 22691482 发表于 2014-10-31 03:04:20 | 显示全部楼层
pf22099 发表于 2014-10-31 02:43
reverse linked list里的一次 K 个是啥意思?

Leetcode那个。。
回复 支持 反对

使用道具 举报

pf22099 发表于 2014-10-31 03:05:01 | 显示全部楼层
22691482 发表于 2014-10-30 11:04. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
Leetcode那个。。

噢···了然了然,多谢!
回复 支持 反对

使用道具 举报

 楼主| 22691482 发表于 2014-10-31 04:05:28 | 显示全部楼层
pf22099 发表于 2014-10-31 03:05
噢···了然了然,多谢!

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

使用道具 举报

pf22099 发表于 2014-10-31 04:27:32 | 显示全部楼层
22691482 发表于 2014-10-30 12:05
校友你好 !! 哈哈
. 鍥磋鎴戜滑@1point 3 acres
哈哈,Trojans遍天下啊
回复 支持 反对

使用道具 举报

忽而今夏 发表于 2014-10-31 12:25:07 | 显示全部楼层
请问楼主能否说一下randomNumber那个题的做法?
回复 支持 反对

使用道具 举报

 楼主| 22691482 发表于 2014-10-31 12:37:27 | 显示全部楼层
忽而今夏 发表于 2014-10-31 12:25. Waral 鍗氬鏈夋洿澶氭枃绔,
请问楼主能否说一下randomNumber那个题的做法?

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

使用道具 举报

averillzheng 发表于 2014-11-4 03:15:17 | 显示全部楼层
第一题比较容易:
  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;-google 1point3acres
  5.                 . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  6.                 //calculate the sum from index i to index j
  7.                 //dynamic programming method
  8.                 int[][] segSum = new int[len][len];. From 1point 3acres bbs
  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) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  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], . 1point3acres.com/bbs
  22.                                                                              arr[j] + segSum[i][j - 1] - maxPick[i][j - 1]);
  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));
    . From 1point 3acres bbs
  31.         }
  32. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| 22691482 发表于 2014-11-4 03:20:17 | 显示全部楼层
averillzheng 发表于 2014-11-4 03:15. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第一题比较容易:

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

使用道具 举报

averillzheng 发表于 2014-11-4 03:23:15 | 显示全部楼层
22691482 发表于 2014-10-31 12:37
说来话长啊。。。主要是跟面试官聊,一步步的改进时间和空间。。更注重过程吧。

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

使用道具 举报

averillzheng 发表于 2014-11-4 03:24:59 | 显示全部楼层
22691482 发表于 2014-11-4 03:20
你好,,请问代码里面的segsum是干嘛的?

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

使用道具 举报

 楼主| 22691482 发表于 2014-11-4 03:47:15 | 显示全部楼层
averillzheng 发表于 2014-11-4 03:24
注释里不是说了,用来存从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吧?

谢谢。
回复 支持 反对

使用道具 举报

 楼主| 22691482 发表于 2014-11-4 03:51:33 | 显示全部楼层
averillzheng 发表于 2014-11-4 03:23
random number 那题,说说你的想法。

首先是把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” 的个数,然后根据随机数返回。

回复 支持 反对

使用道具 举报

averillzheng 发表于 2014-11-4 04:21:51 | 显示全部楼层
22691482 发表于 2014-11-4 03:51. visit 1point3acres.com for more.
首先是把0到max用个数组存起来
面试官说优化空间. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
然后我说用个哈希表去掉bad numbers

这个题主要是怎么样弄才能使每个数出现的概率一样。
回复 支持 反对

使用道具 举报

 楼主| 22691482 发表于 2014-11-4 05:56:19 | 显示全部楼层
averillzheng 发表于 2014-11-4 04:21
这个题主要是怎么样弄才能使每个数出现的概率一样。

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

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

使用道具 举报

averillzheng 发表于 2014-11-4 07:01:12 | 显示全部楼层
22691482 发表于 2014-11-4 03:47
maxPick[j] = Math.max(arr + segSum[j] - maxPick[j],
                                    arr[j] + ...

你理解的都是对的。
maxPick[j]就是表示从i到j第一个player可以得到的最大的。
他可以取arr也可以取arr[j]. 当他取了一个之后他就在后面的过程中成了第二个player。
所以它能得到的就是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。 这就是那个递归的含义。
回复 支持 反对

使用道具 举报

 楼主| 22691482 发表于 2014-11-4 08:14:44 | 显示全部楼层
averillzheng 发表于 2014-11-4 07:01
你理解的都是对的。
maxPick[j]就是表示从i到j第一个player可以得到的最大的。
他可以取arr也可以取arr ...
. 1point 3acres 璁哄潧
我有个地方还是不太清楚。。 不好意思。。

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

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

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

使用道具 举报

averillzheng 发表于 2014-11-4 10:38:34 | 显示全部楼层
22691482 发表于 2014-11-4 08:14
我有个地方还是不太清楚。。 不好意思。。

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

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

使用道具 举报

averillzheng 发表于 2014-11-4 10:41:57 | 显示全部楼层
随机数的题就是用两个random就可以了。
我取max = 10, badNum = [2,3,7];
run 了我的代码1000000000 次,得到的结果是:
142863390 142859239 0 0 142869697 142870183 142844284 0 142860162 142833045.鐣欏璁哄潧-涓浜-涓夊垎鍦
每个数都可以等概率的得到。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 18:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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