Snapchat 9/27 Onsite

总共面了4轮.

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

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

第三轮是个美国大叔. 第一

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

每次带回来的数不一定是这一趟带过去的两个数中的一个，可以从已经运过去的数中任意选一个

补充内容 (2016-10-9 14:08):
第一题 我花了点时间弄清楚了面试官的意思 最后只写了最基本的dfs 0.0

比如之前的例子 {2，3， 5， 8}；Optimal solution 是
{2，3}->    3
<-{2}         2
{5,8}->      8
<-{3}         3
{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>
   
4. #include <map>
   
5. #include <set>
   
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. 
    
15. using namespace std;
    
16. 
    
17. class Solution
    
18. {
    
19.   private:
    
20.     vector<int> nums;
    
21. 
    
22.     unordered_map<string, int> dp1go;
    
23.     unordered_map<string, int> dp1back;
    
24. 
    
25.   public:
    
26.     Solution(vector<int> &_nums) : nums(_nums)
    
27.     {
    
28.         sort(nums.begin(), nums.end());
    
29.     };
    
30. 
    
31.     int solve1()
    
32.     {
    
33.         // brute force
    
34.         int n = nums.size();
    
35.         string s(n, '0');
    
36.         for (int i = 0; i < n; i++)
    
37.         {
    
38.             s[i] = '1';
    
39.             dp1go[s] = nums[i];
    
40.             s[i] = '0';
    
41.         }
    
42.         for (int i = 0; i < n; i++)
    
43.         {
    
44.             for (int j = i + 1; j < n; j++)
    
45.             {
    
46.                 s[i] = '1';
    
47.                 s[j] = '1';
    
48.                 dp1go[s] = nums[j];
    
49.                 s[i] = '0';
    
50.                 s[j] = '0';
    
51.             }
    
52.         }
    
53.         string tmp(n, '1');
    
54.         return solve1go(tmp);
    
55.     }
    
56. 
    
57.     int solve1go(string &s)
    
58.     {
    
59.         // brute force
    
60.         auto it = dp1go.find(s);
    
61.         if (it != dp1go.end())
    
62.             return it->second;
    
63. 
    
64.         int n = s.size();
    
65.         int ret = INT_MAX;
    
66.         for (int i = 0; i < n; i++)
    
67.         {
    
68.             for (int j = i + 1; j < n; j++)
    
69.             {
    
70.                 if (s[i] == '1' && s[j] == '1')
    
71.                 {
    
72.                     s[i] = '0';
    
73.                     s[j] = '0';
    
74.                     ret = min(ret, nums[j] + solve1back(s));
    
75.                     s[i] = '1';
    
76.                     s[j] = '1';
    
77.                 }
    
78.             }
    
79.         }
    
80.         dp1go[s] = ret;
    
81.         return ret;
    
82.     }
    
83. 
    
84.     int solve1back(string &s)
    
85.     {
    
86.         auto it = dp1back.find(s);
    
87.         if (it != dp1back.end())
    
88.             return it->second;
    
89. 
    
90.         int n = s.size();
    
91.         int ret = INT_MAX;
    
92.         for (int i = 0; i < n; i++)
    
93.         {
    
94.             if (s[i] == '0')
    
95.             {
    
96.                 s[i] = '1';
    
97.                 ret = min(ret, nums[i] + solve1go(s));
    
98.                 s[i] = '0';
    
99.             }
    
100.         }
     
101.         dp1back[s] = ret;
     
102.         return ret;
     
103.     }
     
104. };
     
105. 
     
106. int main()
     
107. {
     
108.     vector<int> tmp{2, 3, 5, 8, 10, 110, 100};
     
109.     Solution sl(tmp);
     
110.     cout << sl.solve1() << endl;
     
111. }

复制代码

abcd1992719g 发表于 2016-10-10 04:19
11楼不是给了具体的例子么

用最小的两个数貌似是对的：见
http://blog.sina.com.cn/s/blog_b9bce1550101i9bp.html
不过好像也没有证明。

基本也是贪心，只不过要考虑两种情况，一种是大带小，小回；一种是两小过，小回，两大过，小回。
以4个单位为基础进行贪心。

linweihua0 发表于 2016-10-9 06:59
所以第一题是不是greedy。每次用最小的那个数字带其他数字过河，然后最小的那个回来。
这样[2,3,5,8]岂不 ...

比如2,3过去, 2回来.   5，8过去，可以带3回来。 这样5这个item就不会在cost里了

请问第一题啥意思啊

楼主有这么多offer 想好去哪家了吗

大神可以把题目描述一下嘛谢谢啦！

所以第一题是不是greedy。每次用最小的那个数字带其他数字过河，然后最小的那个回来。
这样[2,3,5,8]岂不是2*3 + 3 + 5 + 8是最优解了

linweihua0 发表于 2016-10-9 06:59
所以第一题是不是greedy。每次用最小的那个数字带其他数字过河，然后最小的那个回来。
这样[2,3,5,8]岂不 ...

不是greedy

请问面的是什么组呀？

第一题目前只会DFS+DP，不知有更好的solution吗？

1. <blockquote>#include <vector>

复制代码