May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 4926|回复: 22
收起左侧

SnapChat 电面挂经

[复制链接] |试试Instant~ |关注本帖
ruochenzhang 发表于 2016-4-19 06:22:19 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Snapchat - 网上海投 - 技术电面 |Fail在职跳槽

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

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

x
很nice的国人小哥,说不定他能看到这里,haha

不知道是不是leetcode原题,我没见到过,求见过的给个link
题目:A跟B在play game,从int[]里拿数字
A:拿第一个/最后一个,都有可能
B:greedy,总拿第一个/最后一个中最大的

A先开始,然后B,轮流,直到拿完
求A拿到的最大

举个例子:
{3, 7, 2, 1}
A: {3, 1} -- 4
B: {7, 2} -- 9

A: {1, 7} -- 8. from: 1point3acres.com/bbs
B: {3, 2} -- 5
答案是8

我能感觉出来是DP,但是想不出来公式以及从哪里开始base case
. From 1point 3acres bbs小哥很好一直说don't worry,方向是对的,在这里呢,谢谢他(如果他看到的话)

反正呢就是没有写出来,因为智商是无法逾越的鸿沟啊。。最后祝大家offer多多!

评分

2

查看全部评分

Mark6 发表于 2016-4-21 10:20:21 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
谢谢楼主分享。我也说一下我的想法。

假设输入为Array nums,如果我们定义Max(i, j)为A能从nums的i到j子序列中能拿到的最大和的话。那么,
(1) Max(i, j) = nums, if i == j;
(2) Max(i, j) = Math.max(nums, nums[j]), if j - i = 1;
这两个是base cases
(3) 然后如果 j - i > 1, 那么我们就比较拿第一个nums好,还是最后一个nums[j]好:
     1. 假如拿nums, Max(i, j)’ = nums + (nums[i+1] > nums[j] ? Max(i+2, j) : Max(i+1, j-1)) // 括号里面决定B拿剩下的第一个还是最后一个。
     2. 假如拿nums[j], Max(i, j)’’ = nums[j] + (nums > nums[j-1] ? Max(i+1, j-1) : Max(i, j-2)).
所以Max(i, j) = Math.max(Max(i, j)’, Max(i, j)’’)-google 1point3acres
最后return Max(0,nums.length - 1).

因为j 是大于等于i的,所以我们只用了dp table的右上部分。从对角线开始,以与对角线垂直方向,一步一步向右上方增加。
dp代码:
public static int maxSumOfA(int[] nums){
                int dp[][] = new int[nums.length][nums.length];
                for(int i = 0; i < nums.length; i++){
                        dp = nums;
                }
                for(int i = 0; i < nums.length - 1; i++){
                        dp[i+1] = Math.max(nums, nums[i+1]);
                }
                int j = 2;
                while(j < nums.length){
                        for(int i = 0; i < nums.length - j; i++){
                                int takeFirst = nums + (nums[i+1] > nums[i+j] ? dp[i+2][i+j] : dp[i+1][i+j-1]);
                                int takeLast = nums[i+j] + (nums > nums[i+j-1] ? dp[i+1][j-1] : dp[j-2]);
                                dp[j+i] = Math.max(takeFirst, takeLast);
                        }
                        j++;
                }
                return dp[0][nums.length - 1];

        }






补充内容 (2016-4-21 10:23):
(1) Max(i, j) = nums, if i == j;.鏈枃鍘熷垱鑷1point3acres璁哄潧
(2) Max(i, j) = Math.max(nums, nums[j]), if j - i = 1;-google 1point3acres

补充内容 (2016-4-21 10:23):
nums【i】显示不出来。。
回复 支持 3 反对 0

使用道具 举报

newbiee 发表于 2016-4-19 06:36:59 | 显示全部楼层
关注一亩三分地微博:
Warald
coins in a line, leetcode-google 1point3acres

补充内容 (2016-4-19 06:37):
sorry, Lintcode   Coins in a LineII
回复 支持 反对

使用道具 举报

ykwwind 发表于 2016-4-19 07:01:47 | 显示全部楼层
  1. class Solution {
  2.   public static void main(String[] args) {. more info on 1point3acres.com
  3.     int[] nums = {3,7,2,1};
  4.     int max = dp(nums);
  5.     System.out.println(max);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  6.   }
  7.   public static int dp(int[] nums) {
  8.     int size = nums.length;
  9.     int[][] dp = new int[size][size];
  10.     //----gap----//. 鍥磋鎴戜滑@1point 3 acres
  11.     for(int i = 0; i < size; ++i) {
  12.       dp[i][i] = nums[i];
  13.     }
  14.     for(int i = 0; i+1 < size; ++i) {
  15.       dp[i][i+1] = Math.max(nums[i], nums[i+1]);
  16.     }
  17.     for(int i = 2; i < size; ++i) {
  18.       //left bound.1point3acres缃
  19.       for(int j = 0; j+i < size; ++j) {
  20.         int one = nums[j]+(nums[j+1] < nums[j+i]?dp[j+1][j+i-1]:dp[j+2][j+i]);
  21.         int two = nums[j+i]+(nums[j] < nums[j+i-1]?dp[j][i+j-2]:dp[j+1][j+i-1]);
  22.         dp[j][i+j] = Math.max(one, two);. visit 1point3acres.com for more.
  23.       }
  24.     }
  25.     return dp[0][size-1];
  26.   }
  27. }. from: 1point3acres.com/bbs
复制代码
. 1point3acres.com/bbs
补充内容 (2016-4-19 07:02):
感觉最近都是这种路数..........

补充内容 (2016-4-19 11:12):
要不要去投下snapchat.....
回复 支持 反对

使用道具 举报

 楼主| ruochenzhang 发表于 2016-4-19 07:40:30 | 显示全部楼层
ykwwind 发表于 2016-4-19 07:01
补充内容 (2016-4-19 07:02):
感觉最近都是这种路数..........

赞!谢谢层主
回复 支持 反对

使用道具 举报

 楼主| ruochenzhang 发表于 2016-4-19 07:41:19 | 显示全部楼层
newbiee 发表于 2016-4-19 06:36
coins in a line, leetcode. more info on 1point3acres.com

补充内容 (2016-4-19 06:37):

是很像,谢谢~~
回复 支持 反对

使用道具 举报

lzb700m 发表于 2016-4-19 10:50:01 | 显示全部楼层
这题有点意思。还有个变种,就是B也用最优策略(和A一样),想尽一切办法拿到最大的数字。问先手的A能拿到多少。
回复 支持 反对

使用道具 举报

lzb700m 发表于 2016-4-19 10:51:03 | 显示全部楼层

不太一样。Coins in a line只能从一头拿,所以是个一维的DP问题。这个题可以从两头拿,就变成二维的了。
回复 支持 反对

使用道具 举报

wangmengcathy 发表于 2016-4-21 01:41:13 | 显示全部楼层
这题思想感觉跟他家前段时间考的那个minimum palindrome edit distance有点相似啊
回复 支持 反对

使用道具 举报

BlackSmith 发表于 2016-4-21 04:57:38 | 显示全部楼层
写了个recursive的,你们看下吧
  1. import java.io.*;
  2. import java.util.*;

  3. public class Solution{
  4.     .鐣欏璁哄潧-涓浜-涓夊垎鍦
  5.     public static void main(String[] args){
  6.         int[] nums = {3,7,2,1};. 鍥磋鎴戜滑@1point 3 acres
  7.         int start = 0;
  8.         int end = nums.length-1;
  9.         System.out.println(Math.max(helper(1, nums, start, end),helper(2, nums, start, end)));
  10.     }
  11.    
  12.     public static int helper(int flag, int[] nums, int start, int end){
  13.         if(start>end) return 0;. visit 1point3acres.com for more.
  14.         
  15.         int sum = 0;
  16.         if(flag==1){.鏈枃鍘熷垱鑷1point3acres璁哄潧
  17.             sum = nums[start];
  18.             start++;
  19.         }else{
  20.             sum = nums[end];
    . 1point3acres.com/bbs
  21.             end--;
  22.         }
  23.         
  24.         if(nums[start]<nums[end])end--;
  25.         else start++;
  26.         . from: 1point3acres.com/bbs
  27.         return Math.max(helper(1, nums, start, end),helper(2, nums, start, end))+sum;
  28.         
  29.     }
  30. }
复制代码
回复 支持 反对

使用道具 举报

Mark6 发表于 2016-4-21 10:21:09 | 显示全部楼层
recursion 代码
public static int maxSumOfA(int[] nums, int i, int j){
                if(i == j){ return nums[i];}. 鍥磋鎴戜滑@1point 3 acres
                if(j - i == 1){ return Math.max(nums[i], nums[j]);}
               
                int candidate1 = nums[i] +
                                (nums[i+1] > nums[j] ? maxSumOfA(nums, i+2, j) : maxSumOfA(nums, i+1, j-1));
                int candidate2 = nums[j] +
                                (nums[i] > nums[j-1] ? maxSumOfA(nums, i+1, j-1) : maxSumOfA(nums, i, j-2));
                return Math.max(candidate1, candidate2);
        }
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-4-21 11:19:44 | 显示全部楼层
Mark6 发表于 2016-4-21 10:21. 1point 3acres 璁哄潧
recursion 代码
public static int maxSumOfA(int[] nums, int i, int j){.鏈枃鍘熷垱鑷1point3acres璁哄潧
                if(i == j){ return nums;}
...

感谢分享。我想再问下递归的话时间复杂度大概是多少呢,我不太确定。谢谢
回复 支持 反对

使用道具 举报

Mark6 发表于 2016-4-21 11:44:10 | 显示全部楼层
jy_121 发表于 2016-4-21 11:19. Waral 鍗氬鏈夋洿澶氭枃绔,
感谢分享。我想再问下递归的话时间复杂度大概是多少呢,我不太确定。谢谢

exponential, 2^n, 因为长度为n的问题,需要两个长度为n-1的子问题的结果。所以 T(n) = 2 T(n-1) + c. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

补充内容 (2016-4-21 11:45):
T(n) = 2 T(n-2) + c
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-4-21 11:53:48 | 显示全部楼层
Mark6 发表于 2016-4-21 11:44
exponential, 2^n, 因为长度为n的问题,需要两个长度为n-1的子问题的结果。所以 T(n) = 2 T(n-1) + c

...

好的,谢谢。
回复 支持 反对

使用道具 举报

qyyyqlm 发表于 2016-7-27 23:44:55 | 显示全部楼层
我面优步就类似这个题,但是不同的是B也是用A的方法来取数字,套路好深-。-
回复 支持 反对

使用道具 举报

importcoder 发表于 2016-9-3 17:40:40 | 显示全部楼层
  1. public class CoinsInLine {
  2.         . 1point3acres.com/bbs
  3.         public int maxCoins(int[] coins) {
  4.                 int first = coins[0] + max(coins, 1, coins.length - 1);
  5.                 int last = coins[coins.length - 1] + max(coins, 0, coins.length - 2);
  6.                 return Math.max(first, last);
  7.         }. Waral 鍗氬鏈夋洿澶氭枃绔,
  8.        
  9.         private int max(int[] coins, int left, int right) {-google 1point3acres
  10.                 if (left == right) {
  11.                         return 0;
  12.                 }
  13.                 if (coins[left] > coins[right]) {
  14.                         left++;
  15.                 } else {
  16.                         right--;
  17.                 }
  18.                 int first = coins[left] + max(coins, left + 1, right);. more info on 1point3acres.com
  19.                 int last = coins[right] + max(coins, left, right - 1);. 鍥磋鎴戜滑@1point 3 acres
  20.                 return Math.max(first, last);
  21.         }
  22.        
  23.         public static void main(String[] args) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  24.                 CoinsInLine solution = new CoinsInLine();
  25.                 int[] coins = {3, 7, 2, 1};
  26.                 System.out.println(solution.maxCoins(coins));
  27.         }
  28. }
复制代码


大半夜的,只能想出来recursive的解法,第一反应是dp,但是死活想不出来
回复 支持 反对

使用道具 举报

kwang1993 发表于 2016-9-3 21:15:44 | 显示全部楼层
第一反应递归,关键确定下一层递归的子串。
  1. #include <iostream>
  2. using namespace std;

  3. int maxSumA(int nums[], int b, int n){//b is beginning
  4.         //edge case
  5.         if(n <= b) return 0;. From 1point 3acres bbs
  6.         if(n - b == 1) return nums[b];. 1point 3acres 璁哄潧
  7.         .1point3acres缃
  8.         int sumA = 0;
  9.         //One is that A select the first number
  10.         sumA += nums[b];

  11.         if(nums[b+1] < nums[n-1])//Determine B's choice
  12.                 sumA += maxSumA(nums, b+1, n-1);
  13.         else 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  14.                 sumA += maxSumA(nums, b+2, n);
  15.                
  16.         int sum = sumA;
  17.        
  18.         //The other is that A select the last number
    . 1point 3acres 璁哄潧
  19.         sumA = nums[n-1];
  20.         if(nums[b] < nums[n-2])//Determine B's choice
  21.                 sumA += maxSumA(nums, b, n-2);
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  22.         else
  23.                 sumA += maxSumA(nums, b+1, n-1);. visit 1point3acres.com for more.
  24.        
  25.         return sum > sumA? sum: sumA;
  26. }
  27. int main(){
  28.         int nums[] = {3, 7, 2, 1};
  29.         cout << maxSumA(nums, 0, 4) << endl;. From 1point 3acres bbs
  30.         return 0;. 1point3acres.com/bbs
  31. }
复制代码
回复 支持 反对

使用道具 举报

满城尽带黄金甲 发表于 2016-9-5 02:21:42 | 显示全部楼层
有个问题,如果是[5, 7, 8, 5]这个subarray, B先拿,那么它会拿哪个?如果B拿第一个5,那么A可以在剩下的拿到12,如果B拿最后一个5,那么A可以拿到13。怎么处理这种情况?
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-9-5 02:34:40 | 显示全部楼层
思路大概是这个样,当有一个一个元素时,trivial,有两个元素时,取大的那个。有n(n > 2)个元素时,模拟一轮A, Bpick的过程,然后取剩下的最大的那个。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-29 18:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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