Facebook intern 二面面经 攒人品！

刚刚面完facebook intern, 二面。面经如下：

Given a set of words find a

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

的算法，叫改进。 只面了这一道题，感觉虚得很。攒人品，攒人品, 攒人品！！！

我的想法是用一个hashmap，对于每个访问到的word，判断其整体的reverse的形式是否在map中，如果在，则找到一个。另外再判断截掉第一个字母的reverse形式是否在map中，如果也在，并且这个key并不是别的word截掉了一个字母的形式，那么又找到一组。（判断是否是另外的word是否截掉第一个字母的可以用set来判断）。然后保存两种状态，一个是截掉头一个字母放入map，并把这个放入set，另一个是直接原生的word放入set。
如此一个loop可以完成吧，如果算上reverse的时间，平均每个单词长度L，n个单词。时间复杂度O（nL）

补充内容 (2016-2-19 06:56):
额。是原生的word放入map= =

补充内容 (2016-2-19 07:06):
另外duplicate的时候出现了aaa，aaa，aaaa的情况直接判断一下map的key下面有没有value就可以了

一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！
Good Lucy
想支持楼主，请点击帖子下方的"好苗""分享""收藏"键，酌情给楼主加大米（系统不扣你自己的分）。
积分不够看不了帖子，请参考论坛导航里的"帮助"，"新手提纲"里有攒积分指南

invinsibility 发表于 2016-2-25 00:18
哦，你理解错了。最后要求返回List, 只是用一个linkedlist把所有的pair链接起来示意图而已。[(cigar, tra ...

如果说(cigar, tragic)一组可以理解，cigartragic确实是一个pair，但是 (none, xenone)这一组没办法理解啊，nonexenone并不是一个palindrome啊

喜马拉雅疯子 发表于 2016-2-19 06:55
我的想法是用一个hashmap，对于每个访问到的word，判断其整体的reverse的形式是否在map中，如果在，则找到 ...

可以直接存所有的形式啊，比如abc,直接存abc, cb,cba,ba 4个key ,然后判断之后有没相同的key.

暂时只想到对于每个字符串，逆序加入trie tree，然后对每个字符串在trie tree里查是否存在前缀为字符串的逆序字符串，然后再进行判断。

dendi 发表于 2016-2-19 14:56
可以直接存所有的形式啊，比如abc,直接存abc, cb,cba,ba 4个key ,然后判断之后有没相同的key.

都可以其实。。。不过duplicate的时候可能判断起来麻烦些吧

喜马拉雅疯子 发表于 2016-2-20 02:43
都可以其实。。。不过duplicate的时候可能判断起来麻烦些吧

嗯，找到一个match的话其实就可见判断这对pair是否已经搜到过。。。
还有楼主说的截掉一个字母没怎么看懂，比如 abcbc，ba这种。。
同样楼上那个逆序trie 优化的话，还需要把每个字母从新修改。

同学你好，facebook面试需要特定的语言吗，看到了你用的数据结构，感觉如果用面试官了解的语言，会让面试官有一种 “啊，这正是我所想要的” 的感觉。你觉得用python 面试会不会吃亏呢？

pivotal 发表于 2016-2-20 13:29
同学你好，facebook面试需要特定的语言吗，看到了你用的数据结构，感觉如果用面试官了解的语言，会让面试官 ...

不限制语言，用你最自信，最熟悉的语言答题。

请问楼主有比较好的答案了吗？求指教

就是和two sum一样的思路？只不过数变成了word，sum target变成了palindrome，instead of saving target-sum, save the palindrome of word in hashmap