推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 13883|回复: 42
收起左侧

10月底AIRBNB ONSITE面经

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
好久以前的忘记发出来了。

电面: nested iterator, follow-up: remove function
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
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. visit 1point3acres.com for more.

给你一个人john, 以及他的一堆朋友,让你计算出来和他travel的city相似度大于75%的所有朋友,并且根据这个相似度对朋友排序. 鍥磋鎴戜滑@1point 3 acres

3. 给一组meetings(每个meeting由start和end时间组成)。求出在所有输入meeting时间段内没有会议,也就是空闲的时间段。
每个subarray都已经sort好
举例:
[
  [[1, 3], [6, 7]],
  [[2, 4]],. visit 1point3acres.com for more.
  [[2, 3], [9, 12]]
]
返回
[[4, 6], [7, 9]]

4. behavior: 要表现爱bnb

5. behavior: 要表现爱bnb


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


. From 1point 3acres bbs

补充内容 (2015-12-9 15:25):
那个第一题,我现在还没明白怎么做才是对的。第二题应该是要倒排索引。

本帖被以下淘专辑推荐:

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

  4. using namespace std; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  5. . more info on 1point3acres.com
  6. class BoggleGame {
  7. public:
  8.     struct Node {
  9.         bool hasWord = false;
  10.         Node *next[26];
  11.         Node() {}
  12.     };

  13.     struct Trie {
  14.         Node *root;
  15.         Trie(){
  16.             root = new Node();. From 1point 3acres bbs
  17.         }
  18.         
  19.         void buildTree(vector<string> &words){
  20.             for(string &s : words){
  21.                 int n = s.size();
  22.                 Node *node = root;
  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];. 鍥磋鎴戜滑@1point 3 acres
  28.                 }
  29.                 node->hasWord = true;. from: 1point3acres.com/bbs
  30.             }
  31.         }
  32.     };
  33.    
  34.     vector<string> maxNumofWords(vector<vector<char>> board, vector<string> dict){
  35.         Trie trie;
  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.     }

  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){. more info on 1point3acres.com
  47.             if(curtResult.size() > finalResult.size())
  48.                 finalResult = curtResult;
  49.             return;
  50.         }
  51. . Waral 鍗氬鏈夋洿澶氭枃绔,
  52.         vector<string> result;
  53.         vector<vector<int>> paths;
  54.         string curtWord;
  55.         vector<int> curtPath;
  56.         dfs(board, visited, result, curtWord, paths, curtPath, trie.root, x, y);
  57.        
  58.         int newx = y == cols -1 ? x + 1 : x;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  59.         int newy = y == cols -1 ? 0: y+1;
  60.         dfs2(board, finalResult, curtResult, visited, newx, newy, trie); // discard current found
  61.         for(int i = 0; i < result.size(); i++){
  62.             curtResult.push_back(result[i]);
  63.             for(int loc : paths[i]). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  64.                 visited[loc/cols][loc%cols] = true;
  65.             dfs2(board, finalResult, curtResult, visited, newx, newy, trie); // use each found
  66.             for(int loc : paths[i])
  67.                 visited[loc/cols][loc%cols] = false;
  68.             curtResult.pop_back();
  69.         }
  70.     }

  71.     void dfs(vector<vector<char>> &board, vector<vector<bool>> &visited,
  72.              vector<string> &result, string &curtWord,. 1point 3acres 璁哄潧
  73.              vector<vector<int>> &paths, vector<int> &curtPath, Node *node, int x, int y){. from: 1point3acres.com/bbs
  74.         int rows = board.size(), cols = board[0].size();
  75.         if(x < 0 || x >= rows || y < 0 || y >= cols || visited[x][y] || node->next[board[x][y]-'a'] == NULL)
  76.             return;
  77.         node = node->next[board[x][y] - 'a'];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  78.         -google 1point3acres
  79.         curtPath.push_back(x * cols + y);
  80.         curtWord.push_back(board[x][y]);
  81.         if( node->hasWord){
  82.             paths.push_back(curtPath);
  83.             result.push_back(curtWord);. Waral 鍗氬鏈夋洿澶氭枃绔,
  84.         }
  85.         visited[x][y] = true;
  86.         for(int i = 0; i < 4; i++){
  87.             int newx = x + dxy[i][0], newy = y + dxy[i][1];
  88.             dfs(board, visited, result, curtWord, paths, curtPath, node, newx, newy);
  89.         }
  90.         visited[x][y] = false; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  91.         curtPath.pop_back();
  92.         curtWord.pop_back();       
  93.     }

  94.     -google 1point3acres
  95. private:
  96.     int dxy[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  97. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  98. };
  99. -google 1point3acres
  100. int main(){. 鍥磋鎴戜滑@1point 3 acres
  101.     vector<vector<char>> board = {
  102.         {'o','a','a','n'},
  103.         {'e','t','a','e'},
  104.         {'i','h','k','r'},
  105.         {'i','f','l','v'}
  106.     };
  107.     vector<string> dict = {"oath","pea","eat","rain", "ihk"};. Waral 鍗氬鏈夋洿澶氭枃绔,
  108.     BoggleGame bg;
  109.     auto result = bg.maxNumofWords(board, dict);
  110.    
  111.     for(string s : result)
  112.         cout << s << endl;. Waral 鍗氬鏈夋洿澶氭枃绔,
  113. . from: 1point3acres.com/bbs
  114.     return 0;
  115. }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
复制代码
回复 支持 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-google 1point3acres
我就开心等死。。。给了一点提示 还是不太会

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

使用道具 举报

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

感觉暴力搞?然后每次找到个词有两种可能:. From 1point 3acres bbs

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

2. 这个词 不存在

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

使用道具 举报

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. 鍥磋鎴戜滑@1point 3 acres
今天我去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
哈哈哈哈哈哈哈笑死 是不是碰到一个面试官了

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

复杂度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 了, 不然一个面试应该做不出来这题
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-8-23 14:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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