一亩三分地论坛

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

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

Google面经题 guess game cost

[复制链接] |试试Instant~ |关注本帖
bobzhang2004 发表于 2016-3-28 01:46:06 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 内推 - HR筛选 |Other其他

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

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

x
google 一道面经题
第二道题目是guess number game with cost, 写个方程返回best first guess number,我看了这题就知道是dp了,然后等我给他解释了我的optimal substructure,结果就剩五分钟了,还有一点点没写完就到时间了。。
有大神遇到过吗?这个题具体是什么呢?
http://www.1point3acres.com/bbs/thread-158832-1-1.html

评分

1

查看全部评分

本帖被以下淘专辑推荐:

ctzsm 发表于 2016-3-28 02:59:39 | 显示全部楼层
  1. f[i][i] = 0 for 1 <= i <= 100,
  2. f[i][j] = min{max(f[i][k - 1], f[k + 1][j]) + k} for i < k < j,
复制代码

评分

2

查看全部评分

回复 支持 1 反对 0

使用道具 举报

user123456 发表于 2016-3-28 01:59:58 | 显示全部楼层
Guessing game - I pick a number between 1 and 100 and you   are trying to guess it. Every time you query a number I tell you if it is higher or lower. Part 1- Write the code of it, if cost of querying a number is equal. Part 2- How about if cost of querying number x is x? How would you change the algorithm?

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| bobzhang2004 发表于 2016-3-28 02:13:07 | 显示全部楼层
[quote][url=forum.php?mod=redirect

大神可以说下解法吗?
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-3-28 02:48:26 | 显示全部楼层
user123456 发表于 2016-3-28 01:59. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
Guessing game - I pick a number between 1 and 100 and you   are trying to guess it. Every time you q ...

第二题 加入了cost, 那么是希望改binary search, 让cost减小么。请问思路是什么
回复 支持 反对

使用道具 举报

ctzsm 发表于 2016-3-28 02:49:36 | 显示全部楼层
f = 0 for 1 <= i <= 100,. from: 1point3acres.com/bbs
f[j] = min(max(f[k - 1], f[k + 1][j]) + k) for i < k < j,
另外再开一个数组g记录下最优决策时候的k,然后二分的时候替换m = (l + r) / 2为m = g[l][r].鐣欏璁哄潧-涓浜-涓夊垎鍦

补充内容 (2016-3-28 02:54):
这就是算导上最优二叉搜索树的应用。
-google 1point3acres
补充内容 (2016-3-28 02:57):
补充了之后
f = 0 for 1 <= i <= 100,
f[j] = min(max(f[k - 1], f[k + 1][j]) + k) for i < k < j
被吞了。。
回复 支持 反对

使用道具 举报

 楼主| bobzhang2004 发表于 2016-3-28 23:37:30 | 显示全部楼层
. visit 1point3acres.com for more.
写了下Java code,不确定是不是对了
  1. public class GuessNumberGameWithCost {

  2.         public static void main(String[] args) {-google 1point3acres
  3.                 int res = guessGameFollowUp();
  4.                 System.out.println(res); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  5.         }

  6.        
  7.         public static int guessGameFollowUp() {
  8.                 int[][] f = new int[100 + 1][100 + 1];
  9.                 for (int i = 1; i <= 100; i++) {
  10.                         f[i][i] = i;
  11.                 }
  12.                 for (int len = 2; len <= 100; len++) {
  13.                         for (int i = 1; i <= 100 - len + 1; i++) {
  14.                                 int j = i + len - 1;
  15.                                
  16.                                 if (len == 2) {
  17.                                         f[i][j] = Math.max(f[i][i], f[j][j]);
  18.                                 } else {. Waral 鍗氬鏈夋洿澶氭枃绔,
  19.                                         f[i][j] = Integer.MAX_VALUE;
  20.                                         for (int k = i + 1; k < j; k++) {
    -google 1point3acres
  21.                                                 f[i][j] = Math.min(f[i][j], Math.max(f[i][k - 1], f[k + 1][j]) + k);.1point3acres缃
  22.                                         }
  23.                                 }. more info on 1point3acres.com
  24.                         }
  25.                 }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  26.                 return f[1][100];
  27.         }
  28. }
复制代码
回复 支持 反对

使用道具 举报

qiuxuxing007 发表于 2016-4-5 14:10:23 | 显示全部楼层
这段程序答案出来的有问题, 我在eclipse上跑了一下死452
回复 支持 反对

使用道具 举报

wsrrzxl 发表于 2016-4-7 06:25:14 | 显示全部楼层
bobzhang2004 发表于 2016-3-28 23:37
写了下Java code,不确定是不是对了

楼主请问dp的状态代表什么?
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-4-9 04:10:20 | 显示全部楼层
wsrrzxl 发表于 2016-4-7 06:25
楼主请问dp的状态代表什么?

dp 应该是最小的cost 在range(i, i)之间inclusive。 所以dp = 0 因为不需要 guess。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 10:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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