新鲜Houzz半Onsite面筋

第一次写面筋，攒攒rp～让地里的同样还在找工作的new grad们来份新鲜面筋尝尝，充充血～

半Onsite：不知道为啥地里的童鞋们4轮的onsite，我的被切成了2次各2轮。。。可能因为我不用飞来吧

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

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



补充内容 (2017-5-13 12:40):
不大会用T_T。。我试试在这里看看能不能补充个例子～ input: [[5, 8, 4, 2], [11, 3, 7, 15], [14, 10, 1, 6], [9, 13, 12, 0]]. 0代表那个可以移动的block～每次能跟四周的数字swap～

补充内容 (2017-5-13 12:40):
最后要output变成[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,0]]所经历的path这样～希望能有帮助～

打倒小怪兽yeah 发表于 2017-8-10 06:40
啊那请问一下，a star search在这题里面怎么用啊。。能不能简单讲讲想法？谢谢喔！

准备别家的时候写了个3*3的npuzzle：

1. auto weight = [](const string& cur) {
   
2.   int w = 0;
   
3.   for (char c = '1'; c <= '8'; ++c) {
   
4.     int id = cur.find_first_of(c);
   
5.     w += abs(id / 3 - (c - '1') / 3) + abs(id % 3 - (c - '1') % 3);
   
6.   }
   
7.   int id = cur.find_first_of(' ');
   
8.   w += abs(id / 3 - 2) + abs(id % 3 - 2);
   
9.   return w;
   
10. };
    
11. 
    
12. 
    
13. vector<string> NPuzzle(string input) {
    
14.   unordered_set<string> visited;
    
15.   auto comp = [](
    
16.                  const pair<string, int>& a,
    
17.                  const pair<string, int>& b
    
18.                  ) {
    
19.     return a.second + weight(a.first) > b.second + weight(b.first);
    
20.   };
    
21.   priority_queue<pair<string, int>, vector<pair<string, int> >, decltype(comp) > pq(comp);
    
22.   pq.push({input, 0});
    
23.   unordered_map<string, string> prev;
    
24.   int di[] = {1, 0, -1, 0};
    
25.   int dj[] = {0, 1, 0, -1};
    
26.   bool found = false;
    
27.   while (not pq.empty() && !found) {
    
28.     auto p = pq.top();
    
29.     pq.pop();
    
30.     string cur = p.first;
    
31.     visited.insert(cur);
    
32.     int steps = p.second;
    
33.     int id = cur.find_first_of(' ');
    
34.     int i = id / 3;
    
35.     int j = id % 3;
    
36.     for (int k = 0; k < 4; ++k) {
    
37.       string next = cur;
    
38.       int next_i = i + di[k];
    
39.       int next_j = j + dj[k];
    
40.       if (next_i < 0 || next_i >= 3 || next_j < 0 || next_j >= 3)
    
41.         continue;
    
42.       int next_id = next_i * 3 + next_j;
    
43.       swap(next[id], next[next_id]);
    
44.       if (visited.count(next))
    
45.         continue;
    
46.       pq.push({next, steps + 1});
    
47.       prev[next] = cur;
    
48.       if (next == "12345678 ") {
    
49.         found = true;
    
50.         break;
    
51.       }
    
52.     }
    
53.     if (found)
    
54.       break;
    
55.   }
    
56.   vector<string> res;
    
57.   string tmp = "12345678 ";
    
58.   while (tmp != input) {
    
59.     res.push_back(tmp);
    
60.     tmp = prev[tmp];
    
61.   }
    
62.   reverse(res.begin(), res.end());
    
63.   return res;
    
64. }

复制代码

不知道有没有问题。。。

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

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

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

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

问一下什么是Integers are not stored. 每次swap是会把这个位置的integer 存上么，可以给个例子么？

看错了是not sorted lol, ignore my question:)

第一题有好的解法吗? 感觉 DFS 似乎太暴力... 求讨论...

amaze 发表于 2017-5-12 10:27
问一下什么是Integers are not stored. 每次swap是会把这个位置的integer 存上么，可以给个例子么？

sorry才看到呢～ 我在原贴上看看能不能加个例子～第一次地里发帖。。不大会用

打倒小怪兽yeah 发表于 2017-5-13 12:39
不大会用T_T。。我试试在这里看看能不能补充个例子～ input: [[5, 8, 4, 2], [11, 3, 7, 15], [14, 10, 1,  ...

楼主有想到好的解法吗 swap 这题...

请问楼主是怎么投的呀？内推吗？

say543 发表于 2017-5-14 14:45
楼主有想到好的解法吗 swap 这题...

我当时是用bfs给做的。。好像面试官小美眉没有很满意。。说还行也能work