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


一亩三分地论坛

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

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

Snapchat 9/27 Onsite

[复制链接] |试试Instant~ |关注本帖
abcd1992719g 发表于 2016-10-8 05:03:24 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Snapchat - 内推 - Onsite |Passfresh grad应届毕业生

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

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

x
总共面了4轮.
. 1point 3acres 璁哄潧
第一轮是国人大哥, 以前没出现过的题. 是什么把两个数运到对面, 一个再跑回来...描述起来很复杂...这个国人大哥说话挺快的 感觉是个技术宅 交流的不是很好 但我能感觉出来他还是很有善意的.

第二轮也是国人大哥. 是关于6度人脉理论的. 地理貌似有. 大哥人很好 交流起来很开心.

第三轮是个美国大叔. 第一题是青蛙, 他一开始说我方法错了 然后看了很久说是对的 他说我的方法与众不同. 然后cache优化. 然后时间还很多 他又给了我另外一个关于编码往前找合法前缀的问题. 也解决掉了. 我问他我表现怎么样, 他说much better than average. 我还和他聊到家人 他家在MTV 经常开5小时车回去 开车还很快迟到罚单😄.

第四轮是韩国小哥, 是地理出现过的什么index. 交流的也很开心,讨论健身什么最后.

总体下来, 大家都很活泼,都很开心的样子. 也顺利拿到了他们家 ~~


补充内容 (2016-10-8 05:09):
求star求follow https://github.com/gzc

补充内容 (2016-10-9 06:25):
第一题, 有一堆数, 比如{2,3,5,8}. 每次带2个过去, 比如我选了3和5, cost是最大的那个值. 一旦过去, 还要带回来一个数. 比如带回3, 花销是3. 所以这一趟把5运了过去, 总花销是3+5. 求找出最小的花销运过去所有数字

补充内容 (2016-10-9 06:26):
每次带回来的数不一定是这一趟带过去的两个数中的一个,可以从已经运过去的数中任意选一个

补充内容 (2016-10-9 14:08):
第一题 我花了点时间弄清楚了面试官的意思 最后只写了最基本的dfs 0.0
神罗天征 发表于 2016-10-8 08:27:23 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
请问第一题啥意思啊
回复 支持 反对

使用道具 举报

哈哈贼 发表于 2016-10-9 00:35:14 | 显示全部楼层
关注一亩三分地微博:
Warald
楼主有这么多offer 想好去哪家了吗
回复 支持 反对

使用道具 举报

linweihua0 发表于 2016-10-9 06:10:41 | 显示全部楼层
大神可以把题目描述一下嘛谢谢啦!
回复 支持 反对

使用道具 举报

linweihua0 发表于 2016-10-9 06:59:30 | 显示全部楼层
所以第一题是不是greedy。每次用最小的那个数字带其他数字过河,然后最小的那个回来。
这样[2,3,5,8]岂不是2*3 + 3 + 5 + 8是最优解了
回复 支持 反对

使用道具 举报

 楼主| abcd1992719g 发表于 2016-10-9 07:01:58 | 显示全部楼层
linweihua0 发表于 2016-10-9 06:59
所以第一题是不是greedy。每次用最小的那个数字带其他数字过河,然后最小的那个回来。
这样[2,3,5,8]岂不 ...
. more info on 1point3acres.com
不是greedy
回复 支持 反对

使用道具 举报

 楼主| abcd1992719g 发表于 2016-10-9 07:03:00 | 显示全部楼层
linweihua0 发表于 2016-10-9 06:59
. 1point3acres.com/bbs所以第一题是不是greedy。每次用最小的那个数字带其他数字过河,然后最小的那个回来。. From 1point 3acres bbs
这样[2,3,5,8]岂不 ...
. 鍥磋鎴戜滑@1point 3 acres
比如2,3过去, 2回来.   5,8过去,可以带3回来。 这样5这个item就不会在cost里了
回复 支持 反对

使用道具 举报

warmland 发表于 2016-10-9 08:02:30 | 显示全部楼层
请问面的是什么组呀?
回复 支持 反对

使用道具 举报

keytion 发表于 2016-10-9 09:04:36 | 显示全部楼层
第一题目前只会DFS+DP,不知有更好的solution吗?
回复 支持 反对

使用道具 举报

keytion 发表于 2016-10-9 09:08:25 | 显示全部楼层
  1. <blockquote>#include <vector>
复制代码
回复 支持 反对

使用道具 举报

keytion 发表于 2016-10-9 09:11:40 | 显示全部楼层
比如之前的例子 {2,3, 5, 8};Optimal solution 是
{2,3}->    3
<-{2}         2
{5,8}->      8
<-{3}         3
{2,3}->      3. more info on 1point3acres.com
total cost 19;

Comparing with the naive greedy
{2,8}->    8
<-{2}         2
{2,5}->      5
<-{2}         2
{2,3}->      3

total cost 20;
  1. #include <vector>
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  2. #include <unordered_map>
  3. #include <unordered_set>
  4. #include <map>
  5. #include <set>
  6. #include <queue>
  7. #include <cmath>
  8. #include <array>
  9. #include <algorithm>
  10. #include <numeric>. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  11. #include <string>. visit 1point3acres.com for more.
  12. #include <list>
  13. #include <iostream>

  14. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  15. using namespace std;

  16. class Solution
  17. {
  18.   private:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  19.     vector<int> nums;

  20.     unordered_map<string, int> dp1go;
  21.     unordered_map<string, int> dp1back;
  22. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  23.   public:
  24.     Solution(vector<int> &_nums) : nums(_nums)
  25.     {. 鍥磋鎴戜滑@1point 3 acres
  26.         sort(nums.begin(), nums.end());. 1point3acres.com/bbs
  27.     };

  28.     int solve1()
  29.     { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  30.         // brute force
  31.         int n = nums.size();
  32.         string s(n, '0');
  33.         for (int i = 0; i < n; i++). more info on 1point3acres.com
  34.         {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  35.             s[i] = '1';
  36.             dp1go[s] = nums[i];
  37.             s[i] = '0';
  38.         }
  39.         for (int i = 0; i < n; i++)
  40.         {. from: 1point3acres.com/bbs
  41.             for (int j = i + 1; j < n; j++)
  42.             {
  43.                 s[i] = '1';
  44.                 s[j] = '1';
  45.                 dp1go[s] = nums[j];
  46.                 s[i] = '0';
  47.                 s[j] = '0';
  48.             }
  49.         }
  50.         string tmp(n, '1');. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  51.         return solve1go(tmp);
  52.     }

  53.     int solve1go(string &s)
  54.     {
  55.         // brute force
  56.         auto it = dp1go.find(s);
  57.         if (it != dp1go.end())
  58.             return it->second;
  59. . more info on 1point3acres.com
  60.         int n = s.size();
  61.         int ret = INT_MAX;
  62.         for (int i = 0; i < n; i++)
  63.         {
  64.             for (int j = i + 1; j < n; j++)
  65.             {
  66.                 if (s[i] == '1' && s[j] == '1')
  67.                 {
  68.                     s[i] = '0';
  69.                     s[j] = '0';. Waral 鍗氬鏈夋洿澶氭枃绔,
  70.                     ret = min(ret, nums[j] + solve1back(s));
  71.                     s[i] = '1';. 鍥磋鎴戜滑@1point 3 acres
  72.                     s[j] = '1';
  73.                 }
  74.             }
  75.         }
  76.         dp1go[s] = ret;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  77.         return ret;
  78.     }. 鍥磋鎴戜滑@1point 3 acres

  79.     int solve1back(string &s)
  80.     {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  81.         auto it = dp1back.find(s);
  82.         if (it != dp1back.end())
  83.             return it->second;. from: 1point3acres.com/bbs
  84. . From 1point 3acres bbs
  85.         int n = s.size();. From 1point 3acres bbs
  86.         int ret = INT_MAX;. From 1point 3acres bbs
  87.         for (int i = 0; i < n; i++)
  88.         {
  89.             if (s[i] == '0')
  90.             {. Waral 鍗氬鏈夋洿澶氭枃绔,
  91.                 s[i] = '1';
  92.                 ret = min(ret, nums[i] + solve1go(s));
  93.                 s[i] = '0';
  94.             }
  95.         }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  96.         dp1back[s] = ret;. 鍥磋鎴戜滑@1point 3 acres
  97.         return ret;
  98.     }
  99. };

  100. int main()
  101. {
  102.     vector<int> tmp{2, 3, 5, 8, 10, 110, 100};
  103.     Solution sl(tmp);
  104.     cout << sl.solve1() << endl;. 鍥磋鎴戜滑@1point 3 acres
  105. }
复制代码
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-9 10:24:51 | 显示全部楼层
请问楼主第一题啥思路呀, 记忆画搜索么。。?
回复 支持 反对

使用道具 举报

 楼主| abcd1992719g 发表于 2016-10-10 00:50:17 | 显示全部楼层
哈哈贼 发表于 2016-10-9 00:35.鏈枃鍘熷垱鑷1point3acres璁哄潧
楼主有这么多offer 想好去哪家了吗
. 鍥磋鎴戜滑@1point 3 acres
你去哪 我就去哪
回复 支持 反对

使用道具 举报

suiyuan2009 发表于 2016-10-10 01:57:10 | 显示全部楼层
用最小的两个数运,有反例吗
回复 支持 反对

使用道具 举报

 楼主| abcd1992719g 发表于 2016-10-10 04:19:10 | 显示全部楼层
suiyuan2009 发表于 2016-10-10 01:57
用最小的两个数运,有反例吗

11楼不是给了具体的例子么
回复 支持 反对

使用道具 举报

keytion 发表于 2016-10-10 05:23:51 | 显示全部楼层
abcd1992719g 发表于 2016-10-10 04:19
11楼不是给了具体的例子么

用最小的两个数貌似是对的:见.鐣欏璁哄潧-涓浜-涓夊垎鍦
http://blog.sina.com.cn/s/blog_b9bce1550101i9bp.html
不过好像也没有证明。

基本也是贪心,只不过要考虑两种情况,一种是大带小,小回;一种是两小过,小回,两大过,小回。
以4个单位为基础进行贪心。
回复 支持 反对

使用道具 举报

haoshenxiong 发表于 2016-10-10 06:34:58 | 显示全部楼层
请问第四题是什么题?
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-10-11 07:42:43 | 显示全部楼层
请问给了lz多久时间考虑呀
回复 支持 反对

使用道具 举报

 楼主| abcd1992719g 发表于 2016-10-11 08:16:38 | 显示全部楼层
pawprinter 发表于 2016-10-11 07:42. 1point3acres.com/bbs
请问给了lz多久时间考虑呀

. from: 1point3acres.com/bbs 10 businees day
回复 支持 反对

使用道具 举报

mooc 发表于 2016-11-1 22:41:44 | 显示全部楼层
lz面试题都好难的样子,请问你都是怎么准备的?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-24 03:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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