一亩三分地论坛

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

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

Airbnb 电面

[复制链接] |试试Instant~ |关注本帖
kelvinzhong 发表于 2015-9-30 01:53:09 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Airbnb - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
题目不难, given a list of word, output all pair of words that can be formed as a palindrome. 不允许用枚举法。。
不知道lz是不是太紧张....一时实在是想不出来。。只好问hint, 结果面试官提示说可以遇到一个word 把所有能与这个word组成palindrome的词放进map里面,后面的word就去查找map里面是否有这个词。。我心想这不就是枚举法吗。。。也是醉了。。。最后还遇到些careless的bug...忘记return 了。。调了半天。。。
Airbnb就不求Pass了....之后的其他家的onsite求pass 啊~~~

评分

3

查看全部评分

本帖被以下淘专辑推荐:

pyemma 发表于 2015-9-30 02:31:45 | 显示全部楼层
种♂神不虚。
这道题可以用leetcode上shortest palindrome最为基础单元来解。找出从头或者从尾开始的所有palindrome然后看remain的substring。找palindrome可以用N^2或者N的来解。
或者直接先上暴力解法也可以。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

cjlm007 发表于 2015-9-30 03:06:32 | 显示全部楼层
话说我也是这个题,估计是一个面试官?
这题挺蛋疼的,不难但是有几个情况不容易想到,当时我就忘记了abcccc/ba,ccccba/ab这种配对。
回复 支持 反对

使用道具 举报

 楼主| kelvinzhong 发表于 2015-9-30 03:10:18 | 显示全部楼层
cjlm007 发表于 2015-9-30 03:06
话说我也是这个题,估计是一个面试官?
这题挺蛋疼的,不难但是有几个情况不容易想到,当时我就忘记了abcc ...
. 鍥磋鎴戜滑@1point 3 acres
我的面试官叫丹尼尔,估计是白人。。。。糟糕了...我木有想到这种情况。。。面试官给的test case也没有这种情况...要跪要跪了...
回复 支持 反对

使用道具 举报

 楼主| kelvinzhong 发表于 2015-9-30 03:11:06 | 显示全部楼层
cjlm007 发表于 2015-9-30 03:06.鏈枃鍘熷垱鑷1point3acres璁哄潧
话说我也是这个题,估计是一个面试官?
这题挺蛋疼的,不难但是有几个情况不容易想到,当时我就忘记了abcc ...

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴这种情况应该怎么做啊?

补充内容 (2015-9-30 03:14):
经@pyemma提醒。。要从头和从尾两边各算一次
回复 支持 反对

使用道具 举报

cjlm007 发表于 2015-9-30 03:23:03 | 显示全部楼层
kelvinzhong 发表于 2015-9-30 03:10
我的面试官叫丹尼尔,估计是白人。。。。糟糕了...我木有想到这种情况。。。面试官给的test case也没有这 ...

那不是一个面试官,这题应该就是他们家高频了。
回复 支持 反对

使用道具 举报

cjlm007 发表于 2015-9-30 03:26:40 | 显示全部楼层
贴一下我代码吧,也不知道是不是cover所有情况了。
  1. vector<pair<string, string>> find_pairs(const unordered_set<string>& words) {
  2. vector<pair<string, string>> result;
  3. unordered_map<string,string> map;

  4. for (auto& str : words) {
  5.    for (int l = 0; l < (int) str.length() && str[l] == str.front(); ++l) {
  6.      string key = string(str.begin() + l + 1, str.end());
  7.      reverse(key.begin(), key.end());
  8.      if (words.count(key)) map[key] = str;     . from: 1point3acres.com/bbs
  9.    }   
  10.    for (int r = (int) str.length() - 1; r >= 0 && str[r] == str.back(); --r) {
  11.      string key = string(str.begin(), str.begin() + r);
  12.      reverse(key.begin(), key.end());
  13.      if (words.count(key)) map[key] = str;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  14.    }   .1point3acres缃
  15.    string reversed = string(str.rbegin(), str.rend());
  16.    if (words.count(reversed)) map[str] = reversed;. 1point 3acres 璁哄潧
  17. }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  18. for (auto& str : words) {
  19.    if (map.count(str)) {
  20.      result.emplace_back(map[str], str);
  21.    }
  22. }
  23. return result;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  24. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| kelvinzhong 发表于 2015-9-30 03:37:15 | 显示全部楼层
cjlm007 发表于 2015-9-30 03:26
贴一下我代码吧,也不知道是不是cover所有情况了。
. From 1point 3acres bbs
那你的面试过了吗?
回复 支持 反对

使用道具 举报

 楼主| kelvinzhong 发表于 2015-9-30 03:48:27 | 显示全部楼层
cjlm007 发表于 2015-9-30 03:26
贴一下我代码吧,也不知道是不是cover所有情况了。
.1point3acres缃
然后你这个代码是不是会误判  ababc / abc ?  
因为你在对 “ababc” 用string key = string(str.begin() + l + 1, str.end());
的时候会产生 abc?
回复 支持 反对

使用道具 举报

cjlm007 发表于 2015-9-30 03:53:51 | 显示全部楼层
kelvinzhong 发表于 2015-9-30 03:37
那你的面试过了吗?

侥幸过了
回复 支持 反对

使用道具 举报

cjlm007 发表于 2015-9-30 03:56:27 | 显示全部楼层
kelvinzhong 发表于 2015-9-30 03:48
然后你这个代码是不是会误判  ababc / abc ?  
因为你在对 “ababc” 用string key = string(str.begin( ...

不会啊,这里只会产生bc和babc
回复 支持 反对

使用道具 举报

sywad 发表于 2015-9-30 04:29:50 | 显示全部楼层
cjlm007 发表于 2015-9-30 03:26
贴一下我代码吧,也不知道是不是cover所有情况了。
. more info on 1point3acres.com
这种情况是不是没有cover: "bbaab", "b"?
回复 支持 反对

使用道具 举报

cjlm007 发表于 2015-9-30 04:33:50 | 显示全部楼层
sywad 发表于 2015-9-30 04:29
这种情况是不是没有cover: "bbaab", "b"?

对,感谢提醒,我再改改,果然是侥幸过了 哈哈
回复 支持 反对

使用道具 举报

哈哈哈大雄 发表于 2015-9-30 12:36:55 | 显示全部楼层
与任意一个word能构成回文的应该有无穷多吧, 比如s,     s + t + reverse(s),当t是回文的时候,这个肯定也是回文啊
回复 支持 反对

使用道具 举报

woaibai 发表于 2015-9-30 13:37:56 | 显示全部楼层
cjlm007 发表于 2015-9-29 14:26. from: 1point3acres.com/bbs
贴一下我代码吧,也不知道是不是cover所有情况了。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
你这个会把[21, 1234], [abc, 1ccccba]  这种也group成pair, 在words那个判断revese后的string存不存在时还要判断剩下的一半string是不是palindrome
回复 支持 反对

使用道具 举报

cjlm007 发表于 2015-9-30 15:15:40 | 显示全部楼层
woaibai 发表于 2015-9-30 13:37.1point3acres缃
你这个会把[21, 1234], [abc, 1ccccba]  这种也group成pair, 在words那个判断revese后的string存不存在时 ...

yep, thanks
回复 支持 反对

使用道具 举报

emmarong 发表于 2015-10-8 14:30:58 | 显示全部楼层
哈哈哈大雄 发表于 2015-9-30 12:36
与任意一个word能构成回文的应该有无穷多吧, 比如s,     s + t + reverse(s),当t是回文的时候,这个肯定 ...

说的有道理,这个不知道面试官是不是clarify了,楼主出来解答一下吧!
回复 支持 反对

使用道具 举报

 楼主| kelvinzhong 发表于 2015-10-8 15:14:58 | 显示全部楼层
emmarong 发表于 2015-10-8 14:30
说的有道理,这个不知道面试官是不是clarify了,楼主出来解答一下吧!

。。。。。也是醉了。。。当然是由限制的,限制就是长度不能长于原来的词
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-9-20 03:49:38 | 显示全部楼层
这题貌似leetcode有
回复 支持 反对

使用道具 举报

xxiiiii 发表于 2016-9-20 04:30:15 | 显示全部楼层
前几天intern电面也面了这道...
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 15:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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