《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 5295|回复: 21
收起左侧

Snapchat 9/27 Onsite

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

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

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

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

x
总共面了4轮.

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

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

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

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

总体下来, 大家都很活泼,都很开心的样子. 也顺利拿到了他们家 ~~
. From 1point 3acres bbs
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
补充内容 (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):.鏈枃鍘熷垱鑷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. 1point 3acres 璁哄潧
所以第一题是不是greedy。每次用最小的那个数字带其他数字过河,然后最小的那个回来。
这样[2,3,5,8]岂不 ...

不是greedy
回复 支持 反对

使用道具 举报

 楼主| abcd1992719g 发表于 2016-10-9 07:03:00 | 显示全部楼层
linweihua0 发表于 2016-10-9 06:59
所以第一题是不是greedy。每次用最小的那个数字带其他数字过河,然后最小的那个回来。. from: 1point3acres.com/bbs
这样[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.鏈枃鍘熷垱鑷1point3acres璁哄潧
<-{2}         2
{5,8}->      8
<-{3}         3
{2,3}->      3
total cost 19;. from: 1point3acres.com/bbs

Comparing with the naive greedy
{2,8}->    8
<-{2}         2
. visit 1point3acres.com for more.{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>-google 1point3acres
  11. #include <string>
  12. #include <list>
  13. #include <iostream>-google 1point3acres

  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());. Waral 鍗氬鏈夋洿澶氭枃绔,
  25.     };. 鍥磋鎴戜滑@1point 3 acres

  26.     int solve1()
  27.     {
  28.         // brute force
  29.         int n = nums.size();
  30.         string s(n, '0');
  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';.鏈枃鍘熷垱鑷1point3acres璁哄潧
  43.                 dp1go[s] = nums[j];. From 1point 3acres bbs
  44.                 s[i] = '0';
  45.                 s[j] = '0';
  46.             }
  47.         }
  48.         string tmp(n, '1');. more info on 1point3acres.com
  49.         return solve1go(tmp);
  50.     }

  51.     int solve1go(string &s)
  52.     {
  53.         // brute force
  54.         auto it = dp1go.find(s);
  55.         if (it != dp1go.end()). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  56.             return it->second;

  57.         int n = s.size();
  58.         int ret = INT_MAX;
  59.         for (int i = 0; i < n; i++)
  60.         {
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  61.             for (int j = i + 1; j < n; j++)
  62.             {
  63.                 if (s[i] == '1' && s[j] == '1'). Waral 鍗氬鏈夋洿澶氭枃绔,
  64.                 {
  65.                     s[i] = '0';
  66.                     s[j] = '0';
  67.                     ret = min(ret, nums[j] + solve1back(s)); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  68.                     s[i] = '1';
  69.                     s[j] = '1';. from: 1point3acres.com/bbs
  70.                 }. Waral 鍗氬鏈夋洿澶氭枃绔,
  71.             }
  72.         }
  73.         dp1go[s] = ret;
  74.         return ret;
  75.     }

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

  81.         int n = s.size();-google 1point3acres
  82.         int ret = INT_MAX;
  83.         for (int i = 0; i < n; i++)
  84.         {. from: 1point3acres.com/bbs
  85.             if (s[i] == '0')
  86.             {
  87.                 s[i] = '1';
  88.                 ret = min(ret, nums[i] + solve1go(s));
  89.                 s[i] = '0';. from: 1point3acres.com/bbs
  90.             }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  91.         }. from: 1point3acres.com/bbs
  92.         dp1back[s] = ret;
  93.         return ret;. visit 1point3acres.com for more.
  94.     }
  95. };

  96. int main()
  97. {
  98.     vector<int> tmp{2, 3, 5, 8, 10, 110, 100};
  99.     Solution sl(tmp);
  100.     cout << sl.solve1() << endl;
  101. }
复制代码
回复 支持 反对

使用道具 举报

小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. 1point3acres.com/bbs
不过好像也没有证明。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
基本也是贪心,只不过要考虑两种情况,一种是大带小,小回;一种是两小过,小回,两大过,小回。
以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. Waral 鍗氬鏈夋洿澶氭枃绔,
请问给了lz多久时间考虑呀

10 businees day
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-19 11:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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