推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 1469|回复: 6
收起左侧

FB 一轮电面

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

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
Follow up: 输入字符串会包含无关字符,计算时应忽略非字母字符和大小写,例如"A@,_b123a",等同于"aba",输出为4。要求O(1) space解,i.e., 不能将输入字符串处理保存为另一个新的字符串。

面完之后两天还没有反馈,虚了,不是说当天就通知结果吗?. 1point3acres.com/bbs
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. Waral 鍗氬鏈夋洿澶氭枃绔,
请问folow-up楼主能说说说思路么? 谢谢了!
  1. int get(char c) {
  2.         if (isalpha(c)) return tolower(c);
  3.         return 0;
  4. }.鐣欏璁哄潧-涓浜-涓夊垎鍦

  5. // input: "A B,  a!", output: 4
  6. // input: "A b,_B a!", output: 6
  7. // input: "a _ A, 23@A", output: 6
  8. // input: "A #,a! a, B b", output: 9. From 1point 3acres bbs
  9. // input: "# 123 , @", output: 0
  10. int num_palindrome_substring(string str) {
  11.         int n = str.size();
  12.         if (n == 0) return 0;
  13. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  14.         int total = 0, i, j;. 1point 3acres 璁哄潧
  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++;.1point3acres缃
  20.                         else break;
  21.                 }-google 1point3acres

  22.                 int l = i - 1, r = j;
  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.                 }. 鍥磋鎴戜滑@1point 3 acres
  32.         }
  33. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  34.         return total;
  35. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| cuiyi 发表于 2016-11-9 07:58:09 | 显示全部楼层
hrl1991 发表于 2016-11-7 11:22
不虚 我也是面完之后两天才有的结果

我去,好几天没消息,今天直接通知我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 这个?
. 1point 3acres 璁哄潧
不是,leetcode貌似没有这个题
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-8-19 17:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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