一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1517|回复: 14
收起左侧

11/9 Qumulo 电面

[复制链接] |试试Instant~ |关注本帖
又见紫风铃 发表于 2015-11-10 21:46:20 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Qumulo - 网上海投 - 技术电面 |Passfresh grad应届毕业生

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

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

x
没有遇到大家都碰到的populate next pointer II,聊了聊简历后collabedit上直接贴了好长的一道题
// #############   Legend: J = Joe, * = fire, # = wall, |_ = exit
// #  J                      #   It will take Joe 14 minutes to exit this maze.
// ####    #####   #   The fire will be right behind him.
// |      #    #       #   #
// |      #*  #       #   #
// |___#________#__|

简单的说就是J表示Joe,*表示火,#表示墙, |或者_表示出口,每分钟J移动一格, 火向四周蔓延一格,求J能不能跑出去,跑出去最短的时间. more info on 1point3acres.com

用BFS做的,同时计算每分钟火势蔓延后的新地图

做得都还比较顺利,被白人小哥指出了一个bug改了以后他表示很满意,面完过了不久就通知Onsite了. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

代码发在沙发

评分

5

查看全部评分

cc11328 发表于 2015-11-11 09:15:45 | 显示全部楼层
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5. vector<pair<int,int>> direct = {{0,1},{0,-1},{1,0},{-1,0}};
  6. int getMin(vector<string> &maze, pair<int,int> &person, pair<int,int> &fire) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  7.     if(maze.size() == 0 || maze[0].size() == 0) return -1;
  8.     int m = maze.size(), n = maze[0].size(), minPath = 0;
  9.     //record the position of person. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  10.     queue<pair<int,int>> q_person;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  11.     q_person.push(person);
  12.     //record the position of fire
  13.     queue<pair<int,int>> q_fire;
  14.     q_fire.push(fire);
  15.     while(!q_person.empty()) {
  16.         //update maze
  17.         minPath++;
  18.         int u = q_fire.size();
  19.         while(u > 0) {
  20.             u--;
  21.             auto cur_fire = q_fire.front();
  22.             q_fire.pop();
  23.             for(int i = 0; i < direct.size(); i++) {
  24.                 int row = direct[i].first + cur_fire.first;
  25.                 int col = direct[i].second + cur_fire.second;
  26.                 if(row >= 0 && row < m && col >= 0 && col < n && maze[row][col] != '#') {
  27.                     maze[row][col] = '*';
  28.                     q_fire.push({row,col});
  29.                 }. 1point 3acres 璁哄潧
  30.             }
  31.         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  32.         //findPath. from: 1point3acres.com/bbs
  33.         int v = q_person.size();
  34.         while(v > 0){
  35.             v--;
  36.             auto cur = q_person.front();
  37.             q_person.pop();
  38.             for(int i = 0; i < direct.size(); i++) {
  39.                 int row = direct[i].first + cur.first;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  40.                 int col = direct[i].second + cur.second;
  41.                 if(row >= 0 && row < m && col >= 0 && col < n) {
  42.                     if(maze[row][col] == ' ') {
  43.                        maze[row][col] = '@';
  44.                        q_person.push({row,col});
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  45.                     }
  46.                     if(maze[row][col] == '_' || maze[row][col] == '|') {
  47.                        return minPath;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  48.                     }
  49.                 }
  50.             }
  51.         }
  52.     }
  53.     return -1;
  54. }
  55. int main() {
  56.         vector<string> maze = {"#############",-google 1point3acres
  57.                                "# @         #",
  58.                                "## #  ##### #",
  59.                            "|  #  #   # #",
  60.                            "|   * #   # #",
  61.                            "|__#______#_|"};
  62.     pair<int,int> person = {1,2};
    . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  63.     pair<int,int> fire = {4,4};
  64.     cout << getMin(maze,person,fire);
  65.         return 0;
  66. }
复制代码
回复 支持 2 反对 0

使用道具 举报

 楼主| 又见紫风铃 发表于 2015-11-10 21:46:43 | 显示全部楼层
  1. class Maze:
  2.     def __init__(self, cells):
  3.         self.cells = cells. more info on 1point3acres.com
  4.         self.fireMap = [cells]

  5.     def escapeTheMaze(self):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  6.         m = len(self.cells). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  7.         n = len(self.cells[0])

  8.         for i in range(m):. from: 1point3acres.com/bbs
  9.             for j in range(n):
  10.                 if self.cells[i][j] == 'J':
  11.                     jX, jY = i, j
  12.                     break

  13.         visited = set()-google 1point3acres
  14.         queue = [(jX, jY, 0)]

  15.         while queue:
  16.             x, y, curMin = queue.pop(0)

  17.             curMap = self.fireMap[curMin]

  18.             if x < 0 or x >= m or y < 0 or y >= n or curMap[x][y] == '#' \. from: 1point3acres.com/bbs
  19.                 or curMap[x][y] == '*' or (x, y) in visited:. from: 1point3acres.com/bbs
  20.                 continue. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  21.             visited.add((x, y))
  22.             if curMap[x][y] in '|_':
  23.                 return curMin + 1
  24. . From 1point 3acres bbs
  25.             if curMin + 1 >= len(self.fireMap):
  26.                 self.fireMap.append(self.constructNewMap(curMin)). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  27.             queue.append((x+1, y, curMin + 1)). Waral 鍗氬鏈夋洿澶氭枃绔,
  28.             queue.append((x-1, y, curMin + 1))
  29.             queue.append((x, y+1, curMin + 1))
  30.             queue.append((x, y-1, curMin + 1))

  31.         return -1

  32.     def constructNewMap(self, curMin):. 1point3acres.com/bbs
  33.         oldMap = self.fireMap[curMin]
  34.         m = len(oldMap)
  35.         n = len(oldMap[0])
  36.         newMap = [[' '] * n for x in range(m)]
  37.         directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
  38.         for i in range(m):
  39.             for j in range(n):
  40.                 if oldMap[i][j] == ' ':
  41.                     continue
  42.                 newMap[i][j] = oldMap[i][j]
  43.                 if oldMap[i][j] == '*':
  44.                     for k in directions:. 鍥磋鎴戜滑@1point 3 acres
  45.                         if oldMap[i+k[0]][j+k[1]] == ' ':
  46.                             newMap[i+k[0]][j+k[1]] = '*'
  47.         return newMap

  48. cells = ['#############', \
  49.          '# J         #', \. 鍥磋鎴戜滑@1point 3 acres
  50.          '####  ##### #', \
  51.          '|  #  #   # #', \
  52.          '|  #* #   # #', \
  53.          '|__#______#_|']
  54. cells = ['######', \
  55.          '#J #*|', \. Waral 鍗氬鏈夋洿澶氭枃绔,
  56.          '#  # |', \
  57.          '######']
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  58. myMaze = Maze(cells)
复制代码
回复 支持 反对

使用道具 举报

Ulu2005 发表于 2015-11-10 23:29:22 | 显示全部楼层
qumulo想我OA就做挂了。。回头到地里看了下发现面筋都有。。。
回复 支持 反对

使用道具 举报

 楼主| 又见紫风铃 发表于 2015-11-10 23:51:13 | 显示全部楼层
Ulu2005 发表于 2015-11-10 23:29
qumulo想我OA就做挂了。。回头到地里看了下发现面筋都有。。。

这确实有点可惜,oa都是原题。。。
回复 支持 反对

使用道具 举报

pennlio 发表于 2015-11-10 23:56:10 | 显示全部楼层
感谢楼主分享
回复 支持 反对

使用道具 举报

cao123 发表于 2015-11-11 00:40:00 | 显示全部楼层
请问你是mike面的吗?我也是面的这个题目,我当时也做出来了,但是还没有消息。
回复 支持 反对

使用道具 举报

 楼主| 又见紫风铃 发表于 2015-11-11 00:42:29 | 显示全部楼层
cao123 发表于 2015-11-11 00:40
请问你是mike面的吗?我也是面的这个题目,我当时也做出来了,但是还没有消息。

不是,名字忘了,但肯定不是Mike。。。
回复 支持 反对

使用道具 举报

cao123 发表于 2015-11-11 00:45:22 | 显示全部楼层
又见紫风铃 发表于 2015-11-11 00:42
不是,名字忘了,但肯定不是Mike。。。

哦哦,好的,我面完了面试官说cool,我觉得应该问题不大, 但是我还没有收到onsite,忧虑中。。。。
回复 支持 反对

使用道具 举报

 楼主| 又见紫风铃 发表于 2015-11-11 00:48:51 | 显示全部楼层
cao123 发表于 2015-11-11 00:45 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
哦哦,好的,我面完了面试官说cool,我觉得应该问题不大, 但是我还没有收到onsite,忧虑中。。。。

恩恩,应该没有问题的
回复 支持 反对

使用道具 举报

心澈非文 发表于 2016-1-6 07:31:40 | 显示全部楼层
我也遇到同样的问题,貌似回答的还不错。
回复 支持 反对

使用道具 举报

BrilliantBean 发表于 2016-2-5 00:33:38 | 显示全部楼层
楼主可以分享你一下你的oa代码吗? huangrui6556@gmail.com 拜谢楼主
回复 支持 反对

使用道具 举报

无名氏 发表于 2016-2-15 05:54:13 | 显示全部楼层
怎么那么少onsite的?
回复 支持 反对

使用道具 举报

haling27188 发表于 2016-2-22 15:00:21 | 显示全部楼层
真不想遇到这个题,最近面试太多,不想准备这道。。。
回复 支持 反对

使用道具 举报

zhibolau 发表于 2016-2-23 01:32:10 | 显示全部楼层
谢谢楼主啊啊啊
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-1-21 01:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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