一亩三分地论坛

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

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

Airbnb 电面

[复制链接] |试试Instant~ |关注本帖
wegnahz 发表于 2015-10-9 04:21:51 | 显示全部楼层 |阅读模式

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

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

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

x
刚随便一点开一个面经就看到重复的题了……血泪史告诉后人一定要记住这个题怎么做:

第一个题很水忘了,第二题其实很简单,就是给你一堆词,找出所有的pair拼起来能组成palindrome,比如["aabc", "cbaa"] 这种。

这个题忘了是在leetcode还是hackerrank做过,但是一时间竟然没想起来……. more info on 1point3acres.com

正确的普通做法是,把每个词的倒序放进一个hashset,然后枚举每词word :
1. 枚举所有前缀,如果前缀在hashset里 AND 当前后缀是回文,那么拼起来(word是pair的第一个). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
2. 枚举所有后缀,如果后缀在hashset里 AND 当前前缀是回文,那么拼起来(word是pair的第二个)
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
更好的做法是用trie加速枚举,这样一旦trie里面找不到了就不用枚举更长的前/后缀了。但是时间复杂度是一样的,是O(NL^2),L是平均长度

我这个题弄了大概半小时花了比较长的时间一点点想出算法,后来又各种编译不过,做oj习惯了main里面不大会写了……还老是忘记在main里调用自己的函数一直以为有死循环,囧死。比较紧张最后只写了1忘记了2的情况,不过面试官没说什么。估计是挂了吧,在这里提醒一下大家。面试官是中国人一直慢慢引导我……


评分

3

查看全部评分

本帖被以下淘专辑推荐:

哈哈哈大雄 发表于 2015-10-9 09:28:20 | 显示全部楼层
感觉1和2两种只要考虑一个就可以了,不然就重复了。
比如对a遍历的时候  a + b是palindrome, 那么对b遍历的时候,a + b也一定是
回复 支持 1 反对 0

使用道具 举报

cjlm007 发表于 2015-10-9 04:26:18 | 显示全部楼层
最近空气床的高频题啊
回复 支持 反对

使用道具 举报

CescTom 发表于 2015-10-13 14:58:07 | 显示全部楼层
同意 哈哈哈大雄.  
我会这么写
Set<String, Stirng> m = xxxxxxx;
for(String s : inputStringArray) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    if(m.contains(s)) . 鍥磋鎴戜滑@1point 3 acres
        //add (s.reverse + s) to solution. from: 1point3acres.com/bbs
   m.put(s)
}
回复 支持 反对

使用道具 举报

CescTom 发表于 2015-10-13 15:00:06 | 显示全部楼层
CescTom 发表于 2015-10-13 14:58. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
同意 哈哈哈大雄.  
我会这么写.1point3acres缃
Set m = xxxxxxx;

写错了..
. 鍥磋鎴戜滑@1point 3 acres
最后应该是
m.put(s.reverse)
回复 支持 反对

使用道具 举报

majiamajia 发表于 2015-10-29 14:49:09 | 显示全部楼层
sevensevens 发表于 2015-10-29 13:46. 1point3acres.com/bbs
逗。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
. visit 1point3acres.com for more.
......hello
回复 支持 反对

使用道具 举报

pyemma 发表于 2015-10-30 00:42:56 | 显示全部楼层
可以用manacher算法加速枚举,用O(N)时间找出这个单词的所有前缀或者后缀是回文的部分
回复 支持 反对

使用道具 举报

alvinca123 发表于 2015-10-30 01:01:44 | 显示全部楼层
YOU ARE LUCKY, HOPE YOU GET IT! GOOD LUCK
回复 支持 反对

使用道具 举报

jyang_2015 发表于 2015-11-2 15:46:29 | 显示全部楼层
哈哈哈大雄 发表于 2015-10-9 09:28
感觉1和2两种只要考虑一个就可以了,不然就重复了。
比如对a遍历的时候  a + b是palindrome, 那么对b遍历 ...

但可能遍历a的时候还发现不了b,因为pivot在b里。这样是不是就漏了?

比如 str1 = "ab", str2 = "bbbba"  => 遍历str1的时候是不是不会想到str2的情况?
回复 支持 反对

使用道具 举报

jyang_2015 发表于 2015-11-2 15:54:19 | 显示全部楼层
想问下楼主这个trie为什么会加速呢? 比如str1 = "abc"; str2 可以是 "ba", "cba", "ccba", "cdccba", etc.  这里我感觉可能加速的也就只有"cba" 和 “ccba”, 但这种概率很小的吧? 感觉不一定会加速吧? 是不是我理解错了什么呢?
回复 支持 反对

使用道具 举报

 楼主| wegnahz 发表于 2015-11-2 23:45:10 | 显示全部楼层
trie的好处是一旦当前前缀匹配不上就立刻退出。你这里需要检查a,ab,abc三次,每次相当于是O(len_word),而用trie的话走一次就行了。当然这个case里trie的优势并不明显
回复 支持 反对

使用道具 举报

jyang_2015 发表于 2015-11-3 00:01:06 | 显示全部楼层
wegnahz 发表于 2015-11-2 23:45
trie的好处是一旦当前前缀匹配不上就立刻退出。你这里需要检查a,ab,abc三次,每次相当于是O(len_word), ...

oh, I see. 我的想法和你的可能不太一样。我不是从头开始匹配。我想的是找pivot。

比如str1 = "abcd" 我先从c (i.e. 1/2的位置)开始找,然后变成"abcdx", "x" 来自suffix。所以用dictionary直接看有没有一个“a", 这样abcda 就成了;

然后我再向后移,开始看"abcdxx" => 显然不可能是回文了, 所以过

然后我再向后移动,开始看"abcdxxx" => 再从dictionary里找 "cba"
. more info on 1point3acres.com
然后继续, 看"abcdxxxx" => 从dictionary里找"dcba"

所以我这样做好像不用trie吧?事件复杂度应该是O(2 * N * len) ~ O(Nlen)  2是来自prefix,suffix各一遍
回复 支持 反对

使用道具 举报

 楼主| wegnahz 发表于 2015-11-3 05:17:52 | 显示全部楼层
jyang_2015 发表于 2015-11-3 00:01
oh, I see. 我的想法和你的可能不太一样。我不是从头开始匹配。我想的是找pivot。 . 1point3acres.com/bbs

比如str1 = "abcd" ...

我大概明白你的思路了,可是这里:
. 鍥磋鎴戜滑@1point 3 acres
                所以用dictionary直接看有没有一个“a"

这里你看a我可以理解,然后第二次你看的是ab,第三次是abc,第四次是abcd,对不对?这样的话,你会发现如果用trie,在trie里走到ab的时候没路可走了,那后面的abc、abcd都不用看了。
回复 支持 反对

使用道具 举报

jyang_2015 发表于 2015-11-4 00:43:22 | 显示全部楼层
wegnahz 发表于 2015-11-3 05:17
我大概明白你的思路了,可是这里:
. visit 1point3acres.com for more.
                所以用dictionary直接看有没有一个“a"

hm.. 不是呀,第二次我是看ba,第三次看cba, 第四次dcba。这样没有prefix的存在的 :o
回复 支持 反对

使用道具 举报

小柯西 发表于 2015-11-4 01:21:00 | 显示全部楼层
pyemma 发表于 2015-10-30 00:42. 1point 3acres 璁哄潧
可以用manacher算法加速枚举,用O(N)时间找出这个单词的所有前缀或者后缀是回文的部分
-google 1point3acres
能具体说说不?
回复 支持 反对

使用道具 举报

 楼主| wegnahz 发表于 2015-11-4 04:13:58 | 显示全部楼层
jyang_2015 发表于 2015-11-4 00:43
hm.. 不是呀,第二次我是看ba,第三次看cba, 第四次dcba。这样没有prefix的存在的 :o

嗯也是啊……那这样似乎确实就一样了
回复 支持 反对

使用道具 举报

 楼主| wegnahz 发表于 2015-11-4 04:14:26 | 显示全部楼层

不需要这么高级的算法,但是很显然他也不会问你裸的palindrome
回复 支持 反对

使用道具 举报

 楼主| wegnahz 发表于 2015-11-4 04:14:44 | 显示全部楼层
补充个DP,LZ onsite已挂……
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 10:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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