一亩三分地论坛

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

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

Snapchat 9/27 Onsite

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

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

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

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

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

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

第三轮是个美国大叔. 第一题是青蛙, 他一开始说我方法错了 然后看了很久说是对的 他说我的方法与众不同. 然后cache优化. 然后时间还很多 他又给了我另外一个关于编码往前找合法前缀的问题. 也解决掉了. 我问他我表现怎么样, 他说much better than average. 我还和他聊到家人 他家在MTV 经常开5小时车回去 开车还很快迟到罚单😄.
. 鍥磋鎴戜滑@1point 3 acres
第四轮是韩国小哥, 是地理出现过的什么index. 交流的也很开心,讨论健身什么最后.. more info on 1point3acres.com

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


补充内容 (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. 求找出最小的花销运过去所有数字. visit 1point3acres.com for more.

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

补充内容 (2016-10-9 14:08):.1point3acres缃
第一题 我花了点时间弄清楚了面试官的意思 最后只写了最基本的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]岂不 ...
. more info on 1point3acres.com
不是greedy
回复 支持 反对

使用道具 举报

 楼主| abcd1992719g 发表于 2016-10-9 07:03:00 | 显示全部楼层
linweihua0 发表于 2016-10-9 06:59
所以第一题是不是greedy。每次用最小的那个数字带其他数字过河,然后最小的那个回来。
这样[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. 1point 3acres 璁哄潧
<-{2}         2
{5,8}->      8
<-{3}         3
{2,3}->      3
total cost 19;. from: 1point3acres.com/bbs
. From 1point 3acres bbs
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>. 鍥磋鎴戜滑@1point 3 acres
  5. #include <set>
  6. #include <queue>. 1point3acres.com/bbs
  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. . 鍥磋鎴戜滑@1point 3 acres
  22.   public:.鐣欏璁哄潧-涓浜-涓夊垎鍦
  23.     Solution(vector<int> &_nums) : nums(_nums)
  24.     {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  25.         sort(nums.begin(), nums.end());
  26.     };
  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++)
  34.         {
  35.             s[i] = '1';
  36.             dp1go[s] = nums[i];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  37.             s[i] = '0';
  38.         }
  39.         for (int i = 0; i < n; i++)
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  40.         {
  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.     }.鏈枃鍘熷垱鑷1point3acres璁哄潧

  53.     int solve1go(string &s)
  54.     {
  55.         // brute force
  56.         auto it = dp1go.find(s);
  57.         if (it != dp1go.end()). visit 1point3acres.com for more.
  58.             return it->second;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  59.         int n = s.size();
  60.         int ret = INT_MAX;
  61.         for (int i = 0; i < n; i++)
  62.         {
  63.             for (int j = i + 1; j < n; j++)
  64.             {
  65.                 if (s[i] == '1' && s[j] == '1')
  66.                 {
  67.                     s[i] = '0';
  68.                     s[j] = '0';. more info on 1point3acres.com
  69.                     ret = min(ret, nums[j] + solve1back(s));
  70.                     s[i] = '1'; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  71.                     s[j] = '1';. from: 1point3acres.com/bbs
  72.                 }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  73.             }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  74.         }
  75.         dp1go[s] = ret;
  76.         return ret;. 鍥磋鎴戜滑@1point 3 acres
  77.     }. more info on 1point3acres.com

  78.     int solve1back(string &s)
  79.     {
    . from: 1point3acres.com/bbs
  80.         auto it = dp1back.find(s);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  81.         if (it != dp1back.end()). visit 1point3acres.com for more.
  82.             return it->second;

  83.         int n = s.size();
  84.         int ret = INT_MAX;
  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));. visit 1point3acres.com for more.
  91.                 s[i] = '0';
  92.             }
  93.         }. more info on 1point3acres.com
  94.         dp1back[s] = ret;
  95.         return ret;
  96.     }
  97. };

  98. int main()
  99. {. Waral 鍗氬鏈夋洿澶氭枃绔,
  100.     vector<int> tmp{2, 3, 5, 8, 10, 110, 100};
  101.     Solution sl(tmp);. visit 1point3acres.com for more.
  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. 1point 3acres 璁哄潧
楼主有这么多offer 想好去哪家了吗

. 1point 3acres 璁哄潧你去哪 我就去哪
回复 支持 反对

使用道具 举报

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
不过好像也没有证明。
. visit 1point3acres.com for more.
基本也是贪心,只不过要考虑两种情况,一种是大带小,小回;一种是两小过,小回,两大过,小回。
以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多久时间考虑呀
. From 1point 3acres bbs
10 businees day
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-21 08:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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