📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
回复: 17
跳转到指定楼层
上一主题 下一主题
收起左侧

新鲜Houzz半Onsite面筋

全局:

2017(4-6月) 码农类General 本科 全职@ - Other - Onsite  | | Other | 应届毕业生

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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

半Onsite:不知道为啥地里的童鞋们4轮的onsite,我的被切成了2次各2轮。。。可能因为我不用飞来吧
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular 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这样~希望能有帮助~

评分

参与人数 3大米 +36 收起 理由
atlantic7200 + 5 很有用的信息!
夏虫不知雪花 + 30
amaze + 1 感谢分享!

查看全部评分


上一篇:mathwork 电面
下一篇:多伦多亚麻Onsite面经
推荐
endofunctor 2017-8-10 07:00:16 | 只看该作者
全局:
打倒小怪兽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. vector<string> NPuzzle(string input) {
  12.   unordered_set<string> visited;
  13.   auto comp = [](
  14.                  const pair<string, int>& a,
  15.                  const pair<string, int>& b
  16.                  ) {
  17.     return a.second + weight(a.first) > b.second + weight(b.first);
  18.   };
  19.   priority_queue<pair<string, int>, vector<pair<string, int> >, decltype(comp) > pq(comp);
  20.   pq.push({input, 0});
  21.   unordered_map<string, string> prev;
  22.   int di[] = {1, 0, -1, 0};
  23.   int dj[] = {0, 1, 0, -1};
  24.   bool found = false;
  25.   while (not pq.empty() && !found) {
  26.     auto p = pq.top();
  27.     pq.pop();
  28.     string cur = p.first;
  29.     visited.insert(cur);
  30.     int steps = p.second;
  31.     int id = cur.find_first_of(' ');
  32.     int i = id / 3;
  33.     int j = id % 3;
  34.     for (int k = 0; k < 4; ++k) {
  35.       string next = cur;
  36.       int next_i = i + di[k];
  37.       int next_j = j + dj[k];
  38.       if (next_i < 0 || next_i >= 3 || next_j < 0 || next_j >= 3)
  39.         continue;
  40.       int next_id = next_i * 3 + next_j;
  41.       swap(next[id], next[next_id]);
  42.       if (visited.count(next))
  43.         continue;
  44.       pq.push({next, steps + 1});
  45.       prev[next] = cur;
  46.       if (next == "12345678 ") {
  47.         found = true;
  48.         break;
  49.       }
  50.     }
  51.     if (found)
  52.       break;
  53.   }
  54.   vector<string> res;
  55.   string tmp = "12345678 ";
  56.   while (tmp != input) {
  57.     res.push_back(tmp);
  58.     tmp = prev[tmp];
  59.   }
  60.   reverse(res.begin(), res.end());
  61.   return res;
  62. }
复制代码
不知道有没有问题。。。

评分

参与人数 1大米 +3 收起 理由
jennywx + 3 666

查看全部评分

回复

使用道具 举报

推荐
kqxqx 2018-1-7 03:25:14 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

推荐
 楼主| 打倒小怪兽yeah 2017-5-13 12:39:42 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
amaze 2017-5-12 10:27:57 | 只看该作者
全局:
问一下什么是Integers are not stored. 每次swap是会把这个位置的integer 存上么,可以给个例子么?
回复

使用道具 举报

🔗
amaze 2017-5-12 11:21:39 | 只看该作者
全局:
看错了是not sorted lol, ignore my question:)
回复

使用道具 举报

🔗
say543 2017-5-12 14:53:16 | 只看该作者
全局:
第一题有好的解法吗? 感觉 DFS 似乎太暴力... 求讨论...
回复

使用道具 举报

🔗
 楼主| 打倒小怪兽yeah 2017-5-13 12:35:54 | 只看该作者
全局:
amaze 发表于 2017-5-12 10:27
问一下什么是Integers are not stored. 每次swap是会把这个位置的integer 存上么,可以给个例子么?

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

使用道具 举报

🔗
say543 2017-5-14 14:45:06 | 只看该作者
全局:
打倒小怪兽yeah 发表于 2017-5-13 12:39
不大会用T_T。。我试试在这里看看能不能补充个例子~ input: [[5, 8, 4, 2], [11, 3, 7, 15], [14, 10, 1,  ...

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

使用道具 举报

🔗
Seventh 2017-5-14 16:22:58 | 只看该作者
全局:
请问楼主是怎么投的呀?内推吗?
回复

使用道具 举报

🔗
 楼主| 打倒小怪兽yeah 2017-5-15 08:37:55 | 只看该作者
全局:
say543 发表于 2017-5-14 14:45
楼主有想到好的解法吗 swap 这题...

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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