一亩三分地论坛

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

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

10月底AIRBNB ONSITE面经

[复制链接] |试试Instant~ |关注本帖
majiamajia 发表于 2015-12-9 15:13:14 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Airbnb - 内推 - Onsite |Failfresh grad应届毕业生

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

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

x
好久以前的忘记发出来了。
. more info on 1point3acres.com
电面: nested iterator, follow-up: remove function

.1point3acres缃
onsite:

1. boggle game, 但是呢比如你现在走了一个词apple, 那么a, p, p, l, e这几个char的位置不能继续用了。于是给你一个board, 一个dict让你计算最多能有多少个valid单词出现在这个Board上面

2.
john's travel city: a1 a2 c2 h8 j9
tom's travel city: b1 a1 c3 z5
kate travel city: a2 a1 h8 x8

给你一个人john, 以及他的一堆朋友,让你计算出来和他travel的city相似度大于75%的所有朋友,并且根据这个相似度对朋友排序
.鏈枃鍘熷垱鑷1point3acres璁哄潧
3. 给一组meetings(每个meeting由start和end时间组成)。求出在所有输入meeting时间段内没有会议,也就是空闲的时间段。
每个subarray都已经sort好. From 1point 3acres bbs
举例:
[
  [[1, 3], [6, 7]],
  [[2, 4]],
  [[2, 3], [9, 12]]
]
返回
[[4, 6], [7, 9]]

4. behavior: 要表现爱bnb

5. behavior: 要表现爱bnb


饭不是很好吃,最后被拒。

. 1point3acres.com/bbs


. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴补充内容 (2015-12-9 15:25):
那个第一题,我现在还没明白怎么做才是对的。第二题应该是要倒排索引。

本帖被以下淘专辑推荐:

  • · 2016 Airbnb|主题: 65, 订阅: 31
  • · AB|主题: 9, 订阅: 0
kevindx1120 发表于 2016-11-3 10:17:03 | 显示全部楼层
我写了一个 boogle game.
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. .1point3acres缃
  5. using namespace std;

  6. class BoggleGame {
  7. public:
  8.     struct Node {
  9.         bool hasWord = false;
  10.         Node *next[26];
  11.         Node() {}. 1point3acres.com/bbs
  12.     };

  13.     struct Trie {
  14.         Node *root;
  15.         Trie(){
  16.             root = new Node();
  17.         }
  18.         
  19.         void buildTree(vector<string> &words){
  20.             for(string &s : words){. From 1point 3acres bbs
  21.                 int n = s.size();
  22.                 Node *node = root;
    . from: 1point3acres.com/bbs
  23.                 for(char c : s){
  24.                     int k = c - 'a';
  25.                     if(node->next[k] == NULL)
  26.                         node->next[k] = new Node();
  27.                     node = node->next[k];
  28.                 }-google 1point3acres
  29.                 node->hasWord = true;
  30.             }
  31.         }
  32.     };. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  33.    
  34.     vector<string> maxNumofWords(vector<vector<char>> board, vector<string> dict){. From 1point 3acres bbs
  35.         Trie trie;. Waral 鍗氬鏈夋洿澶氭枃绔,
  36.         trie.buildTree(dict);

  37.         int rows = board.size(), cols = board[0].size();
  38.         vector<vector<bool>> visited(rows, vector<bool>(cols, false));
  39.         vector<string> finalResult, curtResult;
  40.         dfs2(board, finalResult, curtResult, visited, 0, 0, trie);
  41.        
  42.         return         finalResult;
  43.     }.1point3acres缃

  44.     void dfs2(vector<vector<char>> &board, vector<string> &finalResult, vector<string> &curtResult, vector<vector<bool>> &visited, int x, int y, Trie &trie){
  45.         int rows = board.size(), cols = board[0].size();
  46.         if(x == rows && y == 0){
  47.             if(curtResult.size() > finalResult.size())
  48.                 finalResult = curtResult;. 1point 3acres 璁哄潧
  49.             return;
  50.         }

  51.         vector<string> result;
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  52.         vector<vector<int>> paths;
  53.         string curtWord;
  54.         vector<int> curtPath;
  55.         dfs(board, visited, result, curtWord, paths, curtPath, trie.root, x, y);
  56.        
  57.         int newx = y == cols -1 ? x + 1 : x;
  58.         int newy = y == cols -1 ? 0: y+1;
  59.         dfs2(board, finalResult, curtResult, visited, newx, newy, trie); // discard current found
  60.         for(int i = 0; i < result.size(); i++){. 1point 3acres 璁哄潧
  61.             curtResult.push_back(result[i]);. 1point3acres.com/bbs
  62.             for(int loc : paths[i])
  63.                 visited[loc/cols][loc%cols] = true;
  64.             dfs2(board, finalResult, curtResult, visited, newx, newy, trie); // use each found
  65.             for(int loc : paths[i]). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  66.                 visited[loc/cols][loc%cols] = false;
  67.             curtResult.pop_back();. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  68.         }
  69.     }. From 1point 3acres bbs

  70.     void dfs(vector<vector<char>> &board, vector<vector<bool>> &visited,
  71.              vector<string> &result, string &curtWord,
    . more info on 1point3acres.com
  72.              vector<vector<int>> &paths, vector<int> &curtPath, Node *node, int x, int y){
  73.         int rows = board.size(), cols = board[0].size();.1point3acres缃
  74.         if(x < 0 || x >= rows || y < 0 || y >= cols || visited[x][y] || node->next[board[x][y]-'a'] == NULL). Waral 鍗氬鏈夋洿澶氭枃绔,
  75.             return;
  76.         node = node->next[board[x][y] - 'a'];
  77.        
  78.         curtPath.push_back(x * cols + y);
  79.         curtWord.push_back(board[x][y]);
  80.         if( node->hasWord){. 1point3acres.com/bbs
  81.             paths.push_back(curtPath);
  82.             result.push_back(curtWord);
  83.         }
  84.         visited[x][y] = true;
  85.         for(int i = 0; i < 4; i++){
  86.             int newx = x + dxy[i][0], newy = y + dxy[i][1];
  87.             dfs(board, visited, result, curtWord, paths, curtPath, node, newx, newy);
  88.         }
  89.         visited[x][y] = false;
  90.         curtPath.pop_back();
  91.         curtWord.pop_back();       
  92.     }

  93. . 1point 3acres 璁哄潧
  94.     . from: 1point3acres.com/bbs
  95. private:
  96.     int dxy[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  97. . 1point 3acres 璁哄潧
  98. };

  99. int main(){
  100.     vector<vector<char>> board = {
  101.         {'o','a','a','n'},
  102.         {'e','t','a','e'},
  103.         {'i','h','k','r'},
  104.         {'i','f','l','v'}
  105.     };
  106.     vector<string> dict = {"oath","pea","eat","rain", "ihk"};
  107.     BoggleGame bg;
  108.     auto result = bg.maxNumofWords(board, dict);
  109.     -google 1point3acres
  110.     for(string s : result)
  111.         cout << s << endl;. 1point3acres.com/bbs

  112.     return 0;
  113. }
复制代码
回复 支持 2 反对 0

使用道具 举报

eeyyabc 发表于 2015-12-10 12:08:57 | 显示全部楼层
第一题好难。想了好久不会做。如果被问到等死。。。
回复 支持 反对

使用道具 举报

 楼主| majiamajia 发表于 2015-12-10 12:10:32 | 显示全部楼层
eeyyabc 发表于 2015-12-10 12:08
第一题好难。想了好久不会做。如果被问到等死。。。

我就开心等死。。。给了一点提示 还是不太会
回复 支持 反对

使用道具 举报

eeyyabc 发表于 2015-12-10 12:21:24 | 显示全部楼层
majiamajia 发表于 2015-12-10 12:10
我就开心等死。。。给了一点提示 还是不太会

能说说啥提示吗。。。
这和LC的word search II完全不在一个档次上啊
回复 支持 反对

使用道具 举报

 楼主| majiamajia 发表于 2015-12-10 12:23:16 | 显示全部楼层
eeyyabc 发表于 2015-12-10 12:21
能说说啥提示吗。。。
这和LC的word search II完全不在一个档次上啊

感觉暴力搞?然后每次找到个词有两种可能:

1. 这个词 存在最优的结果里面

2. 这个词 不存在. from: 1point3acres.com/bbs

有人能想出来吗
请给我代码看看
回复 支持 反对

使用道具 举报

eeyyabc 发表于 2015-12-10 12:42:31 | 显示全部楼层
majiamajia 发表于 2015-12-10 12:23
感觉暴力搞?然后每次找到个词有两种可能:

1. 这个词 存在最优的结果里面

仔细想想有点像背包问题,难道是DP?
回复 支持 反对

使用道具 举报

eeyyabc 发表于 2015-12-11 11:20:26 | 显示全部楼层
今天我去onsite,碰见以前同学,同一天onsite 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
进去之前在讨论你第一题,进去之后他立刻被问了第一个boggle game,纯暴力求解

最后也不知道怎么做,求地里牛人解释
回复 支持 反对

使用道具 举报

 楼主| majiamajia 发表于 2015-12-11 11:29:18 | 显示全部楼层
eeyyabc 发表于 2015-12-11 11:20
今天我去onsite,碰见以前同学,同一天onsite
进去之前在讨论你第一题,进去之后他立刻被问了第一个boggle ...

我这也算积攒人品了啊哭了
回复 支持 反对

使用道具 举报

eeyyabc 发表于 2015-12-11 11:30:37 | 显示全部楼层
majiamajia 发表于 2015-12-11 11:29
我这也算积攒人品了啊哭了

嗯,好人啊 :)
不过我俩都不知道咋做,他进去了差点哭了,最后只能暴力撸
回复 支持 反对

使用道具 举报

 楼主| majiamajia 发表于 2015-12-11 11:32:30 | 显示全部楼层
eeyyabc 发表于 2015-12-11 11:30
嗯,好人啊 :)
不过我俩都不知道咋做,他进去了差点哭了,最后只能暴力撸

哈哈哈哈哈哈哈笑死 是不是碰到一个面试官了
回复 支持 反对

使用道具 举报

eeyyabc 发表于 2015-12-11 11:35:04 | 显示全部楼层
majiamajia 发表于 2015-12-11 11:32. from: 1point3acres.com/bbs
哈哈哈哈哈哈哈笑死 是不是碰到一个面试官了

哈哈哈 听他讲了之后,我也差点笑死

复杂度2^N哈哈哈哈
回复 支持 反对

使用道具 举报

coolidgelyt 发表于 2015-12-13 09:00:40 | 显示全部楼层
楼主觉得这道题能不能这么解  http://exceptional-code.blogspot ... cursion-prefix.html
回复 支持 反对

使用道具 举报

 楼主| majiamajia 发表于 2015-12-13 12:39:45 | 显示全部楼层
coolidgelyt 发表于 2015-12-13 09:00
楼主觉得这道题能不能这么解  http://exceptional-code.blogspot.com/2012/02/solving-boggle-game-recursi ...

不行,我这个题目有个变种。就是比如你在MATRIX里面找到了 A P P L E,那么这几个单词所在的这个位置,就等于给锁住了,不能被其他单词所用。
回复 支持 反对

使用道具 举报

Rudy 发表于 2015-12-21 15:55:24 | 显示全部楼层
第一题每次找到一个单词以后,在trie里面把这个单词整个(所有的字母)都删除掉就行了吧,这样在dfs的时候trie里面就查不到了。
回复 支持 反对

使用道具 举报

eeyyabc 发表于 2015-12-22 02:35:52 | 显示全部楼层
Rudy 发表于 2015-12-21 15:55
第一题每次找到一个单词以后,在trie里面把这个单词整个(所有的字母)都删除掉就行了吧,这样在dfs的时候t ...

关键是你怎么保证找到/最多/的词,现在还是不知道出了brute force之外还能怎么搞
回复 支持 反对

使用道具 举报

neal1st 发表于 2015-12-22 14:03:05 | 显示全部楼层
弱弱地问一句,,第三题怎么做。。。
回复 支持 反对

使用道具 举报

xbbjames1 发表于 2015-12-22 15:47:55 | 显示全部楼层
楼主 请问有说 board多大么? 什么样的时空复杂度是可以接受的呢?  感觉DP 状态太难转移了 和 暴力搞没什么区别,直接搜+剪枝 估计还快些  祝楼主其它面试顺利!
回复 支持 反对

使用道具 举报

LifeGoesOn 发表于 2015-12-27 14:00:06 | 显示全部楼层
第2 题相似度的定义是什么 怎么算相似度呢?
回复 支持 反对

使用道具 举报

lianjinggao 发表于 2015-12-27 14:45:52 | 显示全部楼层
感觉第一题就只能暴力解吧。如果说Boggle board 如果board不是很大,可能写个递归都行。
回复 支持 反对

使用道具 举报

LifeGoesOn 发表于 2016-1-3 04:22:21 | 显示全部楼层
第一题会不会是LZ理解错了 只是一个word里不能reuse same letter, 然后就转成 Word search II 了, 不然一个面试应该做不出来这题
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 08:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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