📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: 菡萏之默
跳转到指定楼层
上一主题 下一主题
收起左侧

FaceBook Onsite

🔗
averillzheng 2014-11-6 03:37:43 | 只看该作者
全局:
csgtc 发表于 2014-10-23 11:09
第三题是O(Kn),linear time但是基数很大。。 fb的on campus也有这题,正解是把每个词拆成两半,前一半reve ...

你这个idea怎么做。有没有code?
回复

使用道具 举报

🔗
Interviwer 2014-11-6 03:39:32 | 只看该作者
全局:
贴一个我的O(n)解法,
  1. #include<iostream>
  2. #include<vector>
  3. #include<string>
  4. #include<unordered_set>
  5. using namespace std;

  6. bool isPal(string word) {
  7.     int len = word.size();
  8.     for(int i = 0; i < len/2; i ++) {
  9.         if(word[i] != word[len-1-i]) {
  10.             return false;
  11.         }   
  12.     }   
  13.     return true;
  14. }

  15. vector<pair<string, string> > palindomPair(vector<string> &words) {
  16.     vector<pair<string, string> > rst;
  17.     unordered_set<string> dict;
  18.     for(int i = 0; i < words.size(); i ++) {
  19.         dict.insert(words[i]);
  20.     }   
  21.     for(int i = 0; i < words.size(); i ++) {
  22.         int len = words[i].size();
  23.         for(int l = 0; l <= len; l ++) {
  24.             string sub1 = words[i].substr(0, l);
  25.             string sub2 = words[i].substr(l, len-l);
  26.             if(isPal(sub2)){
  27.                 string tmp = sub1;
  28.                 reverse(tmp.begin(), tmp.end());
  29.                 if(dict.find(tmp) != dict.end() && words[i] != tmp) {
  30.                     rst.push_back(pair<string, string>(words[i], tmp));
  31.                 }   
  32.             }   
  33.             if(isPal(sub1)){
  34.                 string tmp = sub2;
  35.                 reverse(tmp.begin(), tmp.end());
  36.                 if(dict.find(tmp) != dict.end() && words[i] != tmp) {
  37.                     rst.push_back(pair<string,string>(tmp, words[i]));
  38.                 }   
  39.             }   
  40.         }
  41.     }
  42.     return rst;
  43. }


  44. int main() {
  45.     vector<string> words;
  46.     words.push_back("abc");
  47.     words.push_back("ba");
  48.     words.push_back("aaa");
  49.     words.push_back("a");
  50.     words.push_back("cb");
  51.     words.push_back("cba");
  52.     words.push_back("ccab");

  53.     vector<pair<string, string> > rst = palindomPair(words);

  54.     for(int i = 0; i < rst.size(); i ++) {
  55.         cout << rst[i].first << "  ___  " << rst[i].second << endl;
  56.     }
  57. }
复制代码
回复

使用道具 举报

🔗
Linzertorte 2014-11-6 04:03:03 | 只看该作者
全局:
Interviwer 发表于 2014-11-6 03:39
贴一个我的O(n)解法,

C++的map是TreeMap, 查找是logN.有个unordered_map
回复

使用道具 举报

🔗
csgtc 2014-11-7 03:40:46 | 只看该作者
全局:
adiggo 发表于 2014-11-4 19:53
真样做,也是把所有的切开的词放进hashmap么, 另外如果length是odd, 那又得加一些条件判断了。

把所有给的词放进hashmap就行了。。 另外和length没关系
回复

使用道具 举报

🔗
adiggo 2014-11-7 05:07:49 | 只看该作者
全局:
csgtc 发表于 2014-11-7 03:40
把所有给的词放进hashmap就行了。。 另外和length没关系

谢谢懂了, 和42楼的code想法应该是一样的把,,,==
回复

使用道具 举报

🔗
richardzrc 2014-12-15 15:53:07 | 只看该作者
全局:
我咋感觉暴力的和你这个是一样的复杂度= =
暴力A(n,2) 然后两个append的串盘下回文,设最长的串为L,则复杂度是O(L* n^2) 你的代码也是两重循环 外加一个isPal,
回复

使用道具 举报

🔗
richardzrc 2014-12-15 16:00:41 | 只看该作者
全局:
我错了,我没看清楚代码。抱歉哈。应该是O(L^2 * n)的复杂度,但是有一个疑问。如果解都有O(N^2)个,那么复杂度是不是就还是O(N^2)了呢
回复

使用道具 举报

🔗
richardzrc 2014-12-15 17:22:59 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
richardzrc 2015-1-15 18:28:32 | 只看该作者
全局:
42楼这个代码会不会出现重复解呀~~~~
回复

使用道具 举报

🔗
samurai_sz 2015-1-16 01:53:09 | 只看该作者
全局:
moophis 发表于 2014-10-15 09:09
第三题可以把每个word劈成两半,如果一半自身是palindrome并且另一半的reverse过来的词在字典里存在,就找 ...

我没太看懂为啥每个单词直接劈一半就行了?
应该对每一个单词分割成第0位到第i位、第i+1到末尾,然后来看吧?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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