近期论坛无法登录的解决方案


一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 13158|回复: 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. 鍥磋鎴戜滑@1point 3 acres


onsite:

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

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%的所有朋友,并且根据这个相似度对朋友排序. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. from: 1point3acres.com/bbs
3. 给一组meetings(每个meeting由start和end时间组成)。求出在所有输入meeting时间段内没有会议,也就是空闲的时间段。
每个subarray都已经sort好
举例:.鏈枃鍘熷垱鑷1point3acres璁哄潧
[
  [[1, 3], [6, 7]],. more info on 1point3acres.com
  [[2, 4]],
  [[2, 3], [9, 12]]
]
返回
[[4, 6], [7, 9]]

4. behavior: 要表现爱bnb-google 1point3acres

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>
  3. #include <string>

  4. using namespace std;

  5. class BoggleGame {
  6. public:
  7.     struct Node {
  8.         bool hasWord = false;
  9.         Node *next[26];
  10.         Node() {}
  11.     };

  12.     struct Trie {. 1point3acres.com/bbs
  13.         Node *root;.1point3acres缃
  14.         Trie(){. 1point3acres.com/bbs
  15.             root = new Node();
  16.         }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  17.         
  18.         void buildTree(vector<string> &words){
  19.             for(string &s : words){
  20.                 int n = s.size();
  21.                 Node *node = root;
  22.                 for(char c : s){
    -google 1point3acres
  23.                     int k = c - 'a';
  24.                     if(node->next[k] == NULL)
  25.                         node->next[k] = new Node();
  26.                     node = node->next[k];
  27.                 }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  28.                 node->hasWord = true;
  29.             }
  30.         }
  31.     };
  32.    
  33.     vector<string> maxNumofWords(vector<vector<char>> board, vector<string> dict){. 鍥磋鎴戜滑@1point 3 acres
  34.         Trie trie;. 鍥磋鎴戜滑@1point 3 acres
  35.         trie.buildTree(dict);

  36.         int rows = board.size(), cols = board[0].size();
  37.         vector<vector<bool>> visited(rows, vector<bool>(cols, false));-google 1point3acres
  38.         vector<string> finalResult, curtResult;
  39.         dfs2(board, finalResult, curtResult, visited, 0, 0, trie);
  40.        
  41.         return         finalResult;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  42.     }

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

  50.         vector<string> result;-google 1point3acres
  51.         vector<vector<int>> paths;
  52.         string curtWord;
  53.         vector<int> curtPath; . more info on 1point3acres.com
  54.         dfs(board, visited, result, curtWord, paths, curtPath, trie.root, x, y); . Waral 鍗氬鏈夋洿澶氭枃绔,
  55.        
  56.         int newx = y == cols -1 ? x + 1 : x;
  57.         int newy = y == cols -1 ? 0: y+1;
  58.         dfs2(board, finalResult, curtResult, visited, newx, newy, trie); // discard current found. from: 1point3acres.com/bbs
  59.         for(int i = 0; i < result.size(); i++){
  60.             curtResult.push_back(result[i]);
  61.             for(int loc : paths[i])
  62.                 visited[loc/cols][loc%cols] = true;
  63.             dfs2(board, finalResult, curtResult, visited, newx, newy, trie); // use each found
  64.             for(int loc : paths[i])
  65.                 visited[loc/cols][loc%cols] = false;
  66.             curtResult.pop_back();
  67.         }
  68.     }

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

  92.    
  93. private:
  94.     int dxy[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

  95. };

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

  109.     return 0;
  110. }
复制代码
回复 支持 2 反对 0

使用道具 举报

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

使用道具 举报

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

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

使用道具 举报

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

能说说啥提示吗。。。. 1point 3acres 璁哄潧
这和LC的word search II完全不在一个档次上啊
回复 支持 反对

使用道具 举报

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

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

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,纯暴力求解. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
-google 1point3acres
最后也不知道怎么做,求地里牛人解释
回复 支持 反对

使用道具 举报

 楼主| 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
哈哈哈哈哈哈哈笑死 是不是碰到一个面试官了

哈哈哈 听他讲了之后,我也差点笑死. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

.鏈枃鍘熷垱鑷1point3acres璁哄潧复杂度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-6-28 07:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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