一亩三分地论坛

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

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

Snapchat 9/27 Onsite

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

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

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

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

x
总共面了4轮.
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第一轮是国人大哥, 以前没出现过的题. 是什么把两个数运到对面, 一个再跑回来...描述起来很复杂...这个国人大哥说话挺快的 感觉是个技术宅 交流的不是很好 但我能感觉出来他还是很有善意的.

第二轮也是国人大哥. 是关于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):.鏈枃鍘熷垱鑷1point3acres璁哄潧
第一题, 有一堆数, 比如{2,3,5,8}. 每次带2个过去, 比如我选了3和5, cost是最大的那个值. 一旦过去, 还要带回来一个数. 比如带回3, 花销是3. 所以这一趟把5运了过去, 总花销是3+5. 求找出最小的花销运过去所有数字

补充内容 (2016-10-9 06:26):
每次带回来的数不一定是这一趟带过去的两个数中的一个,可以从已经运过去的数中任意选一个
. 1point3acres.com/bbs
补充内容 (2016-10-9 14:08):
第一题 我花了点时间弄清楚了面试官的意思 最后只写了最基本的dfs 0.0
神罗天征 发表于 2016-10-8 08:27:23 | 显示全部楼层
请问第一题啥意思啊
回复 支持 反对

使用道具 举报

哈哈贼 发表于 2016-10-9 00:35:14 | 显示全部楼层
楼主有这么多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]岂不 ...

不是greedy
回复 支持 反对

使用道具 举报

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

比如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. 鍥磋鎴戜滑@1point 3 acres
{2,3}->      3
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>. From 1point 3acres bbs
  4. #include <map>
  5. #include <set>. more info on 1point3acres.com
  6. #include <queue>
  7. #include <cmath>. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  8. #include <array>
  9. #include <algorithm>
  10. #include <numeric>
  11. #include <string>
  12. #include <list>
  13. #include <iostream>

  14. using namespace std;

  15. class Solution
  16. {
  17.   private:
  18.     vector<int> nums;

  19.     unordered_map<string, int> dp1go;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  20.     unordered_map<string, int> dp1back;

  21.   public:
  22.     Solution(vector<int> &_nums) : nums(_nums)
  23.     {
  24.         sort(nums.begin(), nums.end());
    . From 1point 3acres bbs
  25.     };

  26.     int solve1()
  27.     {
  28.         // brute force
  29.         int n = nums.size();. 1point3acres.com/bbs
  30.         string s(n, '0');. 1point 3acres 璁哄潧
  31.         for (int i = 0; i < n; i++)
  32.         {
  33.             s[i] = '1';
  34.             dp1go[s] = nums[i];
  35.             s[i] = '0';
  36.         }
  37.         for (int i = 0; i < n; i++)
  38.         {
  39.             for (int j = i + 1; j < n; j++)
  40.             {
  41.                 s[i] = '1';
  42.                 s[j] = '1';
  43.                 dp1go[s] = nums[j];
  44.                 s[i] = '0';
  45.                 s[j] = '0';. Waral 鍗氬鏈夋洿澶氭枃绔,
  46.             }
  47.         }
  48.         string tmp(n, '1');
  49.         return solve1go(tmp);. visit 1point3acres.com for more.
  50.     }
  51. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  52.     int solve1go(string &s)
  53.     {
  54.         // brute force
  55.         auto it = dp1go.find(s);
  56.         if (it != dp1go.end())
  57.             return it->second;

  58.         int n = s.size();
  59.         int ret = INT_MAX;
  60.         for (int i = 0; i < n; i++)
  61.         {
  62.             for (int j = i + 1; j < n; j++)
  63.             {-google 1point3acres
  64.                 if (s[i] == '1' && s[j] == '1')
  65.                 {
  66.                     s[i] = '0';
  67.                     s[j] = '0';
  68.                     ret = min(ret, nums[j] + solve1back(s));. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  69.                     s[i] = '1';
  70.                     s[j] = '1';
  71.                 }
  72.             }
  73.         }
  74.         dp1go[s] = ret;
  75.         return ret;. From 1point 3acres bbs
  76.     }
  77. -google 1point3acres
  78.     int solve1back(string &s)
  79.     {
  80.         auto it = dp1back.find(s);. from: 1point3acres.com/bbs
  81.         if (it != dp1back.end())
  82.             return it->second;

  83.         int n = s.size();.鏈枃鍘熷垱鑷1point3acres璁哄潧
  84.         int ret = INT_MAX;. From 1point 3acres bbs
  85.         for (int i = 0; i < n; i++)
  86.         {
  87.             if (s[i] == '0')
  88.             {
  89.                 s[i] = '1';
  90.                 ret = min(ret, nums[i] + solve1go(s));
  91.                 s[i] = '0';
  92.             }
  93.         }
  94.         dp1back[s] = ret;
  95.         return ret;
  96.     }
  97. };

  98. int main()
  99. {
  100.     vector<int> tmp{2, 3, 5, 8, 10, 110, 100};
  101.     Solution sl(tmp);
  102.     cout << sl.solve1() << endl; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  103. }
复制代码
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| abcd1992719g 发表于 2016-10-10 00:50:17 | 显示全部楼层
哈哈贼 发表于 2016-10-9 00:35
楼主有这么多offer 想好去哪家了吗

你去哪 我就去哪
回复 支持 反对

使用道具 举报

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
请问给了lz多久时间考虑呀

10 businees day
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 03:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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