一亩三分地论坛

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

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

Uber 电面 china growth (新题附代码)

[复制链接] |试试Instant~ |关注本帖
qyyyqlm 发表于 2016-7-19 08:20:02 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Uber - 内推 - 技术电面 |Failfresh grad应届毕业生

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

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

x
上周五面了Uber China Growth, 面试官是个国人小哥,题目还挺难的(T T),如下:

有两个人A和B,给一个数组array,A和B轮流在这个array中取出数字,每次一个,并且只能取array第一个数字或者最后一个数字,取出数字后,array也随之更新,A先取,两人轮流,直到取完为止。A和B都相当相当相当的机智,他们都按照某个让自己最终能取出所有数字和最大的算法来取数字(这个算法是你要实现的),最后让你返回A最终得到的数字和。.鐣欏璁哄潧-涓浜-涓夊垎鍦

当时电话面试,我也是理解了好久题目,给两个例子:
例子1: array = {1,2,3}
            只能选头尾,A会先选3,B会选2,A接着选1,最后返回4。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

例子2: array = {5, 9, 3, 1 }.鏈枃鍘熷垱鑷1point3acres璁哄潧
            A先选:如果选5的话,虽然比尾部的1大,但是就把下一个较大的数字9让给了B,所以A先选1,
            B选:现在array变成了{5,9,3},B会选5,
            A选:现在array变成了{9,3},于是A开心的选了9,
            B选:现在array变成了{3},于是B只能选3.
            所以返回和为 1+9=10。

当时拿到这个题懵的很 =。=,anyway,上代码:

  1. public class Pair {
  2.                 int first;
  3.                 int second;
  4.                 Pair(int first, int second) {
  5.                         this.first = first;
  6.                         this.second = second;. From 1point 3acres bbs
  7.                 }
  8. }. 鍥磋鎴戜滑@1point 3 acres
复制代码
  1. public class game {. from: 1point3acres.com/bbs
  2.         . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  3.         public static void main(String args[]) {
  4.                 int[] a = {3,9,1,2};
  5.                 int result = getMax(a);
  6.                 System.out.println(result);
  7.         }
  8.        
  9.         static int getMax(int[] array) {
  10.                 int n = array.length;
  11.                 Pair[][] dp = new Pair[n][n];
  12.                 for (int i = 0; i < n; i++) {                       
  13.                         dp[i][0] = new Pair(i,0);
  14.                 }
  15.                 for (int i = 0; i < n-1; i++) {
  16.                         Pair p;
  17.                         if (array[i] < array[i+1]) {
  18.                                 p = new Pair(array[i+1],array[i]);
  19.                         } else {
  20.                                 p = new Pair(array[i],array[i+1]);
  21.                         }. From 1point 3acres bbs
  22.                         dp[i][1] = p;
  23.                 }
  24.                 for (int j = 2; j < n; j++) {
  25.                         for (int p = 0; p < n-2; p++) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  26.                                 if (p + j >= n) {
  27.                                         continue;
  28.                                 }
  29.                                 int sum = getSum(array, p, j+1);
  30.                                 int x = array[p] + dp[p + 1][j - 1].second;
    . visit 1point3acres.com for more.
  31.                                 int y = array[p + j] + dp[p][j - 1].second;
  32.                                 dp[p][j] = new Pair(Math.max(x, y), sum - Math.max(x, y));
  33.                         }. visit 1point3acres.com for more.
  34.                 }
  35.                
  36.                 return dp[0][n-1].first;
  37.         }
  38.         . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  39.         static int getSum(int[] array, int i, int j) {
  40.                 int sum = 0;. visit 1point3acres.com for more.
  41.                 for (int m = i; m < i+j; m++) {
  42.                         sum += array[m];
  43.                 }
  44.                 return sum;
  45.         }
  46. }.鏈枃鍘熷垱鑷1point3acres璁哄潧
复制代码
这里dp[j]里存的是一个Pair(first, second),
这么解释,假如这轮选数字的人是A,并且现在的array已经更新成了以 array为开头,并且长度为(j+1)的新数组。
那么first是A在这个新array里能够取到的最大和,second是下一轮选数字的B能够取到的最大和。

一开始初始化dp[0] = new Pair(i,0),因为这个子数组的长度是1,这轮取到的最大值是array, 下一路没的选,就是0。
以{3,9,1,2}为例,dp是个4*4的二维数组,假如数组此时长度只有1,那么dp[0][0]=(3,0),  dp[1][0]=(9,0),  dp[2][0]=(1,0),  dp[3][0]=(2,0).
假如考虑子数组的长度为2,那么分别有{3,9},{9,1},{1,2},那么dp[0][1]=(9,3),  dp[1][1]=(9,1), dp[2][1]=(2,1)
接着考虑子数组的长度为3,那么分别有{3,9,1},{9,1,2}, dp[0][2].first = max((3 + dp[1][1].second),(1 + dp[0][1].second) ) = max(4, 4)=4
dp[1][2].first = max( (9+dp[2][1].second), (2+dp[1][1].second) ) = max(10, 3)=10
dp[0][2].second 和 dp[1][2].second用sum减一减就可以了, 分别是9和2。
接着考虑数组长度为4的时候,此时已然变成原数组{3,9,1,2},dp[0][3].first = max(3 + dp[1][2].second, 2 + dp[0][2].second) = max(5,11)=11
最后返回11.
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. 鍥磋鎴戜滑@1point 3 acres
anyway,跪了。伤感ing。


评分

2

查看全部评分

zq13667243992 发表于 2016-7-19 10:06:20 | 显示全部楼层
这个就是leetcode coins in a line. 那本leetcode 书讲解的还挺清楚的

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

ww55201 发表于 2016-7-19 08:40:15 | 显示全部楼层
楼主之前有hr聊一下吗?
回复 支持 反对

使用道具 举报

 楼主| qyyyqlm 发表于 2016-7-19 08:49:57 | 显示全部楼层
ww55201 发表于 2016-7-19 08:40. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
楼主之前有hr聊一下吗?

没聊 hr就打了个电话跟我约了下时间
回复 支持 反对

使用道具 举报

josephdesire 发表于 2016-7-19 13:40:52 | 显示全部楼层
可不可以递归来做?
回复 支持 反对

使用道具 举报

 楼主| qyyyqlm 发表于 2016-7-19 22:00:23 | 显示全部楼层
zq13667243992 发表于 2016-7-19 10:06. 1point 3acres 璁哄潧
这个就是leetcode coins in a line. 那本leetcode 书讲解的还挺清楚的

原来如此!看来是我刷题太少
回复 支持 反对

使用道具 举报

qiangwan 发表于 2016-7-19 22:19:25 | 显示全部楼层
我昨天也面了这个组, 也是国人小哥, 给了一个 题也很难。。。。写完都不知道他到底要什么。。。 每次问他 他就反问我。。。
回复 支持 反对

使用道具 举报

 楼主| qyyyqlm 发表于 2016-7-19 22:45:19 | 显示全部楼层
qiangwan 发表于 2016-7-19 22:19
我昨天也面了这个组, 也是国人小哥, 给了一个 题也很难。。。。写完都不知道他到底要什么。。。 每次问他 ...

anyway还是祝你好运奥!加油!
回复 支持 反对

使用道具 举报

yuanxiehuang 发表于 2016-7-20 01:00:15 | 显示全部楼层
是不是叫bill....
回复 支持 反对

使用道具 举报

 楼主| qyyyqlm 发表于 2016-7-20 08:39:44 | 显示全部楼层

++++ 不是的呢  ++++
回复 支持 反对

使用道具 举报

yuanxiehuang 发表于 2016-7-20 10:34:07 | 显示全部楼层
qyyyqlm 发表于 2016-7-20 08:39
++++ 不是的呢  ++++

当年也面过这个组,碰到了一个中国人,在面试过程中我问他可以这么理解吗?他说可以然后写了20行说"这样不行,我刚才说错了",我把20行都删了。。
回复 支持 反对

使用道具 举报

mtler 发表于 2016-7-21 04:02:27 | 显示全部楼层
zq13667243992 发表于 2016-7-19 10:06
这个就是leetcode coins in a line. 那本leetcode 书讲解的还挺清楚的

具体是哪一题? leetcode 上没找到啊
回复 支持 反对

使用道具 举报

stonetao 发表于 2016-7-24 07:26:16 | 显示全部楼层
mtler 发表于 2016-7-21 04:02. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
具体是哪一题? leetcode 上没找到啊

http://articles.leetcode.com/coins-in-line/ 这个是讲解

online judge 可以看lintcode coins in a line III
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-7-24 14:00:13 | 显示全部楼层
dp和递归都是可以的,确实就是lintcode硬币的变形题。
回复 支持 反对

使用道具 举报

rjr130 发表于 2016-7-24 14:10:41 | 显示全部楼层
是不是叫Ben
回复 支持 反对

使用道具 举报

kevinlee816 发表于 2016-7-30 06:40:30 | 显示全部楼层
我上个月去snapchat电面也是这道题,连举得例子都一模一样。也是跪了T_T
回复 支持 反对

使用道具 举报

rk_jh 发表于 2016-7-30 08:40:04 | 显示全部楼层
  1. def maxSumPossible(nums):
  2.     if len(nums) <= 2:
  3.         return max(nums). 1point3acres.com/bbs
  4.     # assuming the rival is intellegent, I won't be left with a better choice
  5.     pick_l = min(maxSumPossible(nums[2:]), maxSumPossible(nums[:-1])). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  6.     pick_r = min(maxSumPossible(nums[1:]), maxSumPossible(nums[:-2]))
  7.     return max(pick_l + nums[0], pick_r + nums[-1])
复制代码
回复 支持 反对

使用道具 举报

 楼主| qyyyqlm 发表于 2016-7-31 02:14:16 | 显示全部楼层
kevinlee816 发表于 2016-7-30 06:40 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我上个月去snapchat电面也是这道题,连举得例子都一模一样。也是跪了T_T

我前两天snapchat电面,又碰到个国人小哥new grad刚工作一年,代码跑对,但是不知道为啥人家要求贼高不满意,第二天收到了拒信。总之醉醉的。
回复 支持 反对

使用道具 举报

 楼主| qyyyqlm 发表于 2016-7-31 02:20:08 | 显示全部楼层
yuanxiehuang 发表于 2016-7-20 10:34
当年也面过这个组,碰到了一个中国人,在面试过程中我问他可以这么理解吗?他说可以然后写了20行说"这样 ...

感觉刚工作不久的国人小哥面试官,要求都很高。。。。
回复 支持 反对

使用道具 举报

haoshenxiong 发表于 2016-8-16 13:38:48 | 显示全部楼层
贴个我的解法,dp存的是index from i to j 能得到的最大结果
        public static int calculate(int[] nums) {
                int n = nums.length;
                int[][] dp = new int[n][n];
                int[] sum = new int[n+1];. from: 1point3acres.com/bbs
                for(int i=1;i<=n;i++) {
                        sum[i] = sum[i-1] + nums[i-1];
. From 1point 3acres bbs                }
               
                for(int i=n-1;i>=0;i--) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        for(int j=i;j<n;j++) {
                                int num1 = sum[j]- sum[i] - (j-1>=0 ? dp[i][j-1] : 0) + nums[j];. visit 1point3acres.com for more.
                                int num2 = sum[j+1] - sum[i+1] - (i+1<=j ? dp[i+1][j] : 0) + nums[i];
                                dp[i][j] =  Math.max(num1, num2);
                        }
                }. visit 1point3acres.com for more.
                return dp[0][n-1];. 1point3acres.com/bbs
        }
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 18:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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