【通知】7月22,工业界资深数据科学家教你破解各大公司面试!


一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 1443|回复: 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., 不能将输入字符串处理保存为另一个新的字符串。
. 1point 3acres 璁哄潧
面完之后两天还没有反馈,虚了,不是说当天就通知结果吗?
hrl1991 发表于 2016-11-7 11:22:57 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
不虚 我也是面完之后两天才有的结果
回复 支持 反对

使用道具 举报

graininear 发表于 2016-11-9 06:56:08 | 显示全部楼层
关注一亩三分地微博:
Warald
请问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);
  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
  9. // input: "# 123 , @", output: 0
  10. int num_palindrome_substring(string str) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  11.         int n = str.size();
  12.         if (n == 0) return 0;

  13.         int total = 0, i, j;. 1point 3acres 璁哄潧
  14.         for (i = 0; i < n; i++) {
  15.                 if (get(str[i]) == 0) continue;
  16.                 for (j = i; j < n; j++) {
  17.                         if (get(str[j]) == 0) continue;
  18.                         if (get(str[i]) == get(str[j])) total++;. more info on 1point3acres.com
  19.                         else break;
  20.                 }. from: 1point3acres.com/bbs

  21.                 int l = i - 1, r = j;
  22.                 while (l >= 0 && r < n) {
  23.                         while (l >= 0 && get(str[l]) == 0) l--;
  24.                         while (r < n && get(str[r]) == 0) r++;
  25.                         if (l >= 0 && r < n) {
  26.                                 if (get(str[l]) == get(str[r])) total++;
  27.                                 else break;
  28.                                 l--, r++;
  29.                         }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  30.                 }
  31.         }
  32. .1point3acres缃
  33.         return total;. Waral 鍗氬鏈夋洿澶氭枃绔,
  34. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| 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 这个?

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-21 00:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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