一亩三分地论坛

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

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

FB 一轮电面

[复制链接] |试试Instant~ |关注本帖
cuiyi 发表于 2016-11-7 11:14:23 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 博士 全职@Facebook - 内推 - 技术电面 |Passfresh grad应届毕业生

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

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

x
白人小哥,上来先自我介绍说是infrastructure某个组的manager,然后让我自我介绍10分钟。聊完之后,开始做题。给一个字符串,计算有多少个substring是palindrome。例如:输入“aba”,是palindrome的substring一共有"a", "b", "a", "aba",所以输出4。
暴力解法为O(n^3),小哥期望的解法是从每个下标开始,往两边延伸,复杂度为O(n^2)。类似的题目参考LC 5. Longest Palindromic Substring. visit 1point3acres.com for more.
Follow up: 输入字符串会包含无关字符,计算时应忽略非字母字符和大小写,例如"A@,_b123a",等同于"aba",输出为4。要求O(1) space解,i.e., 不能将输入字符串处理保存为另一个新的字符串。. Waral 鍗氬鏈夋洿澶氭枃绔,

面完之后两天还没有反馈,虚了,不是说当天就通知结果吗?
hrl1991 发表于 2016-11-7 11:22:57 | 显示全部楼层
不虚 我也是面完之后两天才有的结果
回复 支持 反对

使用道具 举报

graininear 发表于 2016-11-9 06:56:08 | 显示全部楼层
请问folow-up楼主能说说说思路么? 谢谢了!
回复 支持 反对

使用道具 举报

 楼主| cuiyi 发表于 2016-11-9 07:56:46 | 显示全部楼层
graininear 发表于 2016-11-9 06:56
请问folow-up楼主能说说说思路么? 谢谢了!
  1. int get(char c) {
  2.         if (isalpha(c)) return tolower(c);
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  3.         return 0;
  4. }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  5. // input: "A B,  a!", output: 4. from: 1point3acres.com/bbs
  6. // input: "A b,_B a!", output: 6. from: 1point3acres.com/bbs
  7. // input: "a _ A, 23@A", output: 6. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  8. // input: "A #,a! a, B b", output: 9
  9. // input: "# 123 , @", output: 0
  10. int num_palindrome_substring(string str) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  11.         int n = str.size();.1point3acres缃
  12.         if (n == 0) return 0;
  13. . 鍥磋鎴戜滑@1point 3 acres
  14.         int total = 0, i, j;
  15.         for (i = 0; i < n; i++) {
  16.                 if (get(str[i]) == 0) continue;
  17.                 for (j = i; j < n; j++) {
  18.                         if (get(str[j]) == 0) continue;
  19.                         if (get(str[i]) == get(str[j])) total++;
  20.                         else break;-google 1point3acres
  21.                 }

  22.                 int l = i - 1, r = j;. 鍥磋鎴戜滑@1point 3 acres
  23.                 while (l >= 0 && r < n) {
  24.                         while (l >= 0 && get(str[l]) == 0) l--;
  25.                         while (r < n && get(str[r]) == 0) r++;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  26.                         if (l >= 0 && r < n) {
  27.                                 if (get(str[l]) == get(str[r])) total++;
  28.                                 else break;
  29.                                 l--, r++;
  30.                         }
  31.                 }
  32.         }.鐣欏璁哄潧-涓浜-涓夊垎鍦

  33.         return total;
  34. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| cuiyi 发表于 2016-11-9 07:58:09 | 显示全部楼层
hrl1991 发表于 2016-11-7 11:22
不虚 我也是面完之后两天才有的结果
. from: 1point3acres.com/bbs
我去,好几天没消息,今天直接通知我onsite,电面居然只要一轮。
回复 支持 反对

使用道具 举报

Cats881119 发表于 2016-11-25 13:48:42 | 显示全部楼层
131. Palindrome Partitioning 这个?
回复 支持 反对

使用道具 举报

 楼主| cuiyi 发表于 2016-11-25 13:55:46 | 显示全部楼层
Cats881119 发表于 2016-11-25 13:48
131. Palindrome Partitioning 这个?

不是,leetcode貌似没有这个题
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 08:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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