推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

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

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

SnapChat 电面挂经

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

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

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

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

x
很nice的国人小哥,说不定他能看到这里,haha
-google 1point3acres
不知道是不是leetcode原题,我没见到过,求见过的给个link
题目:A跟B在play game,从int[]里拿数字
A:拿第一个/最后一个,都有可能
B:greedy,总拿第一个/最后一个中最大的

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

举个例子:
{3, 7, 2, 1}
.鏈枃鍘熷垱鑷1point3acres璁哄潧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 | 显示全部楼层
谢谢楼主分享。我也说一下我的想法。
. visit 1point3acres.com for more.
假设输入为Array nums,如果我们定义Max(i, j)为A能从nums的i到j子序列中能拿到的最大和的话。那么,. more info on 1point3acres.com
(1) Max(i, j) = nums, if i == j;
(2) Max(i, j) = Math.max(nums, nums[j]), if j - i = 1;.鏈枃鍘熷垱鑷1point3acres璁哄潧
这两个是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).

因为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;
(2) Max(i, j) = Math.max(nums, nums[j]), if j - i = 1;
. Waral 鍗氬鏈夋洿澶氭枃绔,
补充内容 (2016-4-21 10:23):. 1point 3acres 璁哄潧
nums【i】显示不出来。。
回复 支持 3 反对 0

使用道具 举报

ykwwind 发表于 2016-4-19 07:01:47 | 显示全部楼层
  1. class Solution {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  2.   public static void main(String[] args) {
  3.     int[] nums = {3,7,2,1};
  4.     int max = dp(nums);
  5.     System.out.println(max);. from: 1point3acres.com/bbs
  6.   }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  7.   public static int dp(int[] nums) {
  8.     int size = nums.length;
  9.     int[][] dp = new int[size][size];. 1point3acres.com/bbs
  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. visit 1point3acres.com for more.
  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]);. 1point 3acres 璁哄潧
  22.         dp[j][i+j] = Math.max(one, two);
  23.       }
  24.     }
  25.     return dp[0][size-1];. Waral 鍗氬鏈夋洿澶氭枃绔,
  26.   }
  27. }
复制代码

补充内容 (2016-4-19 07:02):. From 1point 3acres bbs
感觉最近都是这种路数........... 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

补充内容 (2016-4-19 11:12):.鐣欏璁哄潧-涓浜-涓夊垎鍦
要不要去投下snapchat.....
回复 支持 1 反对 0

使用道具 举报

newbiee 发表于 2016-4-19 06:36:59 | 显示全部楼层
coins in a line, leetcode
.鐣欏璁哄潧-涓浜-涓夊垎鍦
补充内容 (2016-4-19 06:37):
sorry, Lintcode   Coins in a LineII
回复 支持 反对

使用道具 举报

 楼主| 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.鏈枃鍘熷垱鑷1point3acres璁哄潧

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

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

使用道具 举报

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

使用道具 举报

lzb700m 发表于 2016-4-19 10:51:03 | 显示全部楼层
ruochenzhang 发表于 2016-4-19 07:41. From 1point 3acres bbs
是很像,谢谢~~

不太一样。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){. From 1point 3acres bbs
  6.         int[] nums = {3,7,2,1}; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  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.     }. 鍥磋鎴戜滑@1point 3 acres
  11.    
  12.     public static int helper(int flag, int[] nums, int start, int end){
  13.         if(start>end) return 0;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  14.         . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  15.         int sum = 0;
  16.         if(flag==1){
  17.             sum = nums[start];
  18.             start++;
  19.         }else{
  20.             sum = nums[end];
  21.             end--;
  22.         }
  23.         
  24.         if(nums[start]<nums[end])end--;
  25.         else start++;
  26.         .鏈枃鍘熷垱鑷1point3acres璁哄潧
  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];}
                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. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
recursion 代码
public static int maxSumOfA(int[] nums, int i, int j){
                if(i == j){ return nums;}. Waral 鍗氬鏈夋洿澶氭枃绔,
...

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

使用道具 举报

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

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);. 1point 3acres 璁哄潧
  7.         }
  8.         . Waral 鍗氬鏈夋洿澶氭枃绔,
  9.         private int max(int[] coins, int left, int right) {
  10.                 if (left == right) {
  11.                         return 0;. From 1point 3acres bbs
  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);. more info on 1point3acres.com
  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.         }. more info on 1point3acres.com
  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;
  6.         if(n - b == 1) return nums[b];
  7.        
    . from: 1point3acres.com/bbs
  8.         int sumA = 0;
  9.         //One is that A select the first number
  10.         sumA += nums[b];
  11. . Waral 鍗氬鏈夋洿澶氭枃绔,
  12.         if(nums[b+1] < nums[n-1])//Determine B's choice
  13.                 sumA += maxSumA(nums, b+1, n-1);
  14.         else . from: 1point3acres.com/bbs
  15.                 sumA += maxSumA(nums, b+2, n);
  16.                
  17.         int sum = sumA;
  18.        
  19.         //The other is that A select the last number. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  20.         sumA = nums[n-1];
  21.         if(nums[b] < nums[n-2])//Determine B's choice
  22.                 sumA += maxSumA(nums, b, n-2);
  23.         else
  24.                 sumA += maxSumA(nums, b+1, n-1);
  25.        
  26.         return sum > sumA? sum: sumA;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  27. }
  28. int main(){
  29.         int nums[] = {3, 7, 2, 1};
  30.         cout << maxSumA(nums, 0, 4) << endl;
  31.         return 0;. From 1point 3acres bbs
  32. }
复制代码
回复 支持 反对

使用道具 举报

满城尽带黄金甲 发表于 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 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-8-21 01:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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