一亩三分地论坛

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

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

SnapChat 电面挂经

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

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

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

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

x
很nice的国人小哥,说不定他能看到这里,haha
. visit 1point3acres.com for more.
不知道是不是leetcode原题,我没见到过,求见过的给个link
题目:A跟B在play game,从int[]里拿数字. Waral 鍗氬鏈夋洿澶氭枃绔,
A:拿第一个/最后一个,都有可能
B:greedy,总拿第一个/最后一个中最大的
. 1point3acres.com/bbs
A先开始,然后B,轮流,直到拿完
求A拿到的最大

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

A: {1, 7} -- 8
B: {3, 2} -- 5
答案是8

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

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

评分

2

查看全部评分

Mark6 发表于 2016-4-21 10:20:21 | 显示全部楼层
谢谢楼主分享。我也说一下我的想法。
. From 1point 3acres bbs
假设输入为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;. 1point3acres.com/bbs
这两个是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)’’)
最后return Max(0,nums.length - 1). 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

. from: 1point3acres.com/bbs 因为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];

        }

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷


. Waral 鍗氬鏈夋洿澶氭枃绔,

补充内容 (2016-4-21 10:23):
(1) Max(i, j) = nums, if i == j;
(2) Max(i, j) = Math.max(nums, nums[j]), if j - i = 1;. visit 1point3acres.com for more.

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

使用道具 举报

newbiee 发表于 2016-4-19 06:36:59 | 显示全部楼层
coins in a line, leetcode

补充内容 (2016-4-19 06:37):. Waral 鍗氬鏈夋洿澶氭枃绔,
sorry, Lintcode   Coins in a LineII
回复 支持 反对

使用道具 举报

ykwwind 发表于 2016-4-19 07:01:47 | 显示全部楼层
  1. class Solution {
  2.   public static void main(String[] args) {
  3.     int[] nums = {3,7,2,1};. 1point 3acres 璁哄潧
  4.     int max = dp(nums);
  5.     System.out.println(max);
  6.   }.1point3acres缃
  7.   public static int dp(int[] nums) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  8.     int size = nums.length;.1point3acres缃
  9.     int[][] dp = new int[size][size];
  10.     //----gap----//
  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
  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);
  23.       }
  24.     }
  25.     return dp[0][size-1];
  26.   }
  27. }
复制代码

补充内容 (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):. more info on 1point3acres.com
感觉最近都是这种路数..........

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

使用道具 举报

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

补充内容 (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. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  4. public class Solution{-google 1point3acres
  5.    
  6.     public static void main(String[] args){
  7.         int[] nums = {3,7,2,1};
  8.         int start = 0;
  9.         int end = nums.length-1;
  10.         System.out.println(Math.max(helper(1, nums, start, end),helper(2, nums, start, end)));
  11.     }
  12.    
  13.     public static int helper(int flag, int[] nums, int start, int end){
  14.         if(start>end) return 0;
  15.         . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  16.         int sum = 0;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  17.         if(flag==1){
  18.             sum = nums[start];
  19.             start++;
  20.         }else{
  21.             sum = nums[end];
  22.             end--;
  23.         }
  24.         
  25.         if(nums[start]<nums[end])end--;
    . from: 1point3acres.com/bbs
  26.         else start++;
  27.         
  28.         return Math.max(helper(1, nums, start, end),helper(2, nums, start, end))+sum;
  29.         
  30.     }. more info on 1point3acres.com
  31. }
复制代码
回复 支持 反对

使用道具 举报

Mark6 发表于 2016-4-21 10:21:09 | 显示全部楼层
recursion 代码
public static int maxSumOfA(int[] nums, int i, int j){
                if(i == j){ return nums[i];}. Waral 鍗氬鏈夋洿澶氭枃绔,
                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] + -google 1point3acres
                                (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
recursion 代码
public static int maxSumOfA(int[] nums, int i, int j){
                if(i == j){ return nums;}
...

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

使用道具 举报

Mark6 发表于 2016-4-21 11:44:10 | 显示全部楼层
jy_121 发表于 2016-4-21 11:19. 1point 3acres 璁哄潧
感谢分享。我想再问下递归的话时间复杂度大概是多少呢,我不太确定。谢谢

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.        
  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.         }
  8.         . visit 1point3acres.com for more.
  9.         private int max(int[] coins, int left, int right) {
  10.                 if (left == right) {
  11.                         return 0;. 1point 3acres 璁哄潧
  12.                 }
  13.                 if (coins[left] > coins[right]) {
  14.                         left++;
  15.                 } else {
  16.                         right--;
  17.                 }
  18.                 int first = coins[left] + max(coins, left + 1, right);
  19.                 int last = coins[right] + max(coins, left, right - 1);
  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. 鍥磋鎴戜滑@1point 3 acres
  4.         //edge case
  5.         if(n <= b) return 0;. From 1point 3acres bbs
  6.         if(n - b == 1) return nums[b];. more info on 1point3acres.com
  7.        
  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
  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);
  24.        
  25.         return sum > sumA? sum: sumA;
  26. }
  27. int main(){. from: 1point3acres.com/bbs
  28.         int nums[] = {3, 7, 2, 1};
  29.         cout << maxSumA(nums, 0, 4) << endl;. Waral 鍗氬鏈夋洿澶氭枃绔,
  30.         return 0;
  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的过程,然后取剩下的最大的那个。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 03:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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