新鲜Houzz半Onsite面筋

Seventh 发表于 2017-5-14 16:22
请问楼主是怎么投的呀？内推吗？

是Hr来找我的之前

请问楼主第一题大概思路是什么呢

lj910817 发表于 2017-7-10 07:20
请问楼主第一题大概思路是什么呢

bfs可以的，就是搜索空间相对慢，我想面试官估计想要写a star search，但三十分钟写出来没有bug实在太变态了。

楼主面的哪个组呢

cawe 发表于 2017-7-16 10:08
楼主面的哪个组呢

啊不好意思，才看到！面的是marketplace的组好像

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

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

打倒小怪兽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