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


一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 13552|回复: 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:.1point3acres缃

1. boggle game, 但是呢比如你现在走了一个词apple, 那么a, p, p, l, e这几个char的位置不能继续用了。于是给你一个board, 一个dict让你计算最多能有多少个valid单词出现在这个Board上面
.1point3acres缃
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%的所有朋友,并且根据这个相似度对朋友排序

3. 给一组meetings(每个meeting由start和end时间组成)。求出在所有输入meeting时间段内没有会议,也就是空闲的时间段。. Waral 鍗氬鏈夋洿澶氭枃绔,
每个subarray都已经sort好
举例:
[
  [[1, 3], [6, 7]],. 鍥磋鎴戜滑@1point 3 acres
  [[2, 4]],
  [[2, 3], [9, 12]]
]
返回
[[4, 6], [7, 9]]
. from: 1point3acres.com/bbs
4. behavior: 要表现爱bnb

5. behavior: 要表现爱bnb


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

.鐣欏璁哄潧-涓浜-涓夊垎鍦


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

本帖被以下淘专辑推荐:

  • · 2016 Airbnb|主题: 65, 订阅: 37
  • · AB|主题: 9, 订阅: 0
kevindx1120 发表于 2016-11-3 10:17:03 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
我写了一个 boogle game.
  1. #include <iostream>
  2. #include <vector>. Waral 鍗氬鏈夋洿澶氭枃绔,
  3. #include <string>. 1point3acres.com/bbs

  4. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  5. using namespace std;
  6. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  7. class BoggleGame {
  8. public:.鐣欏璁哄潧-涓浜-涓夊垎鍦
  9.     struct Node {
  10.         bool hasWord = false;
  11.         Node *next[26];
  12.         Node() {}
  13.     };. more info on 1point3acres.com

  14.     struct Trie {. visit 1point3acres.com for more.
  15.         Node *root;
  16.         Trie(){
  17.             root = new Node();
  18.         }
  19.         
  20.         void buildTree(vector<string> &words){
  21.             for(string &s : words){
  22.                 int n = s.size();
  23.                 Node *node = root;
  24.                 for(char c : s){
  25.                     int k = c - 'a';
  26.                     if(node->next[k] == NULL)
  27.                         node->next[k] = new Node();
  28.                     node = node->next[k];
  29.                 }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  30.                 node->hasWord = true;
  31.             }
  32.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  33.     };. visit 1point3acres.com for more.
  34.    
  35.     vector<string> maxNumofWords(vector<vector<char>> board, vector<string> dict){
  36.         Trie trie;
  37.         trie.buildTree(dict);
  38. .1point3acres缃
  39.         int rows = board.size(), cols = board[0].size();
  40.         vector<vector<bool>> visited(rows, vector<bool>(cols, false));
  41.         vector<string> finalResult, curtResult;
  42.         dfs2(board, finalResult, curtResult, visited, 0, 0, trie);
  43.         . visit 1point3acres.com for more.
  44.         return         finalResult;
  45.     }

  46.     void dfs2(vector<vector<char>> &board, vector<string> &finalResult, vector<string> &curtResult, vector<vector<bool>> &visited, int x, int y, Trie &trie){
  47.         int rows = board.size(), cols = board[0].size();
  48.         if(x == rows && y == 0){
  49.             if(curtResult.size() > finalResult.size()) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  50.                 finalResult = curtResult;
  51.             return;
  52.         }

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

  72.     void dfs(vector<vector<char>> &board, vector<vector<bool>> &visited,
  73.              vector<string> &result, string &curtWord,
  74.              vector<vector<int>> &paths, vector<int> &curtPath, Node *node, int x, int y){
  75.         int rows = board.size(), cols = board[0].size();
  76.         if(x < 0 || x >= rows || y < 0 || y >= cols || visited[x][y] || node->next[board[x][y]-'a'] == NULL)
  77.             return;
  78.         node = node->next[board[x][y] - 'a'];
  79.        
  80.         curtPath.push_back(x * cols + y);
  81.         curtWord.push_back(board[x][y]);
  82.         if( node->hasWord){
  83.             paths.push_back(curtPath);
  84.             result.push_back(curtWord);
  85.         }
  86.         visited[x][y] = true;
  87.         for(int i = 0; i < 4; i++){
  88.             int newx = x + dxy[i][0], newy = y + dxy[i][1];
  89.             dfs(board, visited, result, curtWord, paths, curtPath, node, newx, newy);
  90.         }
  91.         visited[x][y] = false;
  92.         curtPath.pop_back();
  93.         curtWord.pop_back();       
  94.     }
  95. . 鍥磋鎴戜滑@1point 3 acres
  96.    
  97. private:
  98.     int dxy[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

  99. };

  100. int main(){
  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.     };. from: 1point3acres.com/bbs
  107.     vector<string> dict = {"oath","pea","eat","rain", "ihk"};
  108.     BoggleGame bg;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  109.     auto result = bg.maxNumofWords(board, dict);
  110.    
  111.     for(string s : result)
  112.         cout << s << endl;

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

使用道具 举报

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

使用道具 举报

 楼主| 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. more info on 1point3acres.com
能说说啥提示吗。。。
这和LC的word search II完全不在一个档次上啊

感觉暴力搞?然后每次找到个词有两种可能:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

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

2. 这个词 不存在. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. 1point 3acres 璁哄潧
有人能想出来吗
请给我代码看看
回复 支持 反对

使用道具 举报

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
嗯,好人啊 :)
不过我俩都不知道咋做,他进去了差点哭了,最后只能暴力撸
.鏈枃鍘熷垱鑷1point3acres璁哄潧
哈哈哈哈哈哈哈笑死 是不是碰到一个面试官了
回复 支持 反对

使用道具 举报

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-google 1point3acres
楼主觉得这道题能不能这么解  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-7-25 00:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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