一亩三分地论坛

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

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

FB两轮面经

[复制链接] |试试Instant~ |关注本帖
theWANDERER 发表于 2016-3-26 17:28:14 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 博士 实习@Facebook - 网上海投 - 技术电面 |Other其他

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

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

x
第一面
一个很耐死的老印,一开始自介,然后我介绍自己,这部分花了15分钟上下
第一题:binary tree,给定一个value,return bin tree里面下一个比value大的值. from: 1point3acres.com/bbs
做过binary tree iterator,但没做过这题
一开始想法就是inorder traversal之后一个一个吐出来到找到value
当然这不是最佳解,很naive的解法,面试官叫我想能不能改进
我想那就binary search,犯了一些小错,但最后有搞出来. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第二题:binary tree的node加一个ptr next,point到inorder traversal的下一个node,比上一个简单
.鏈枃鍘熷垱鑷1point3acres璁哄潧
二面,一个口音应该是白女的面试官,一开始就让我自介
我讲了几分钟吧,没注意
他自介了三十秒,基本什么都没讲,直接开始题目
第一题:valid palindrome,我一下子都混乱了,这不刷题都应该要会做的题目,我还跟他确认了一下细节,他要求我no extra string/space,即便这样,还是太简单吧...?. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第二题:给一个string,列出所有长度大于一的palindromic substring,LC longest palindromic substring的变体
.....这也太诡异了吧,二面出的题目比一面简单! ?半个小时不到就结束了,该不会要用英文不好来拒我吧



补充内容 (2016-3-27 23:22):
一面第一题是bst才对,抱歉

评分

3

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 54, 订阅: 45
bobzhang2004 发表于 2016-4-3 06:46:53 | 显示全部楼层
all palindrome
  1. public class PalindromicSubstringLongerThanOne {

  2.         public static void main(String[] args) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  3.                 List<String> res = getPalindromicSubstringLongerThanOne("substrsrrs");
  4.                 for (String s : res) {
  5.                         System.out.println(s);
  6.                 }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  7.         }

  8.         public static List<String> getPalindromicSubstringLongerThanOne(String s) {
  9.                 List<String> res = new ArrayList<String>();. From 1point 3acres bbs
  10.                 if (s == null || s.length() == 0) {
  11.                         return res;. From 1point 3acres bbs
  12.                 }-google 1point3acres
  13.                 for (int i = 0; i < s.length() * 2 - 1; i++) {
  14.                         int left = i / 2;
  15.                         int right = i / 2;
  16.                         if (i % 2 == 1) {
  17.                                 right++;
  18.                         }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  19.                         findPalindrome(res, s, left, right);
  20.                 }

  21.                 return res;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  22.         }

  23.         public static void findPalindrome(List<String> res, String s, int left, int right) {
  24.                 while (left >= 0 && right < s.length()) {
  25.                         if (s.charAt(left) != s.charAt(right)) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  26.                                 break;
  27.                         }-google 1point3acres

  28.                         left--;
  29.                         right++;
  30.                         if (s.substring(left + 1, right).length() > 1) {
  31.                                 res.add(s.substring(left + 1, right));
  32.                         }
  33.                 }
  34.         }
  35. }
复制代码
回复 支持 1 反对 0

使用道具 举报

 楼主| theWANDERER 发表于 2016-4-3 10:15:28 | 显示全部楼层
honeyBear142857 发表于 2016-3-31 10:34
楼主的面试有什么update的消息了吗?

offer了,强运
回复 支持 1 反对 0

使用道具 举报

BostonYang 发表于 2016-3-26 20:25:01 | 显示全部楼层
楼主一面后多久接到二面通知的
回复 支持 反对

使用道具 举报

 楼主| theWANDERER 发表于 2016-3-27 00:37:05 来自手机 | 显示全部楼层
23小时内就收到了
回复 支持 反对

使用道具 举报

BostonYang 发表于 2016-3-27 01:02:06 | 显示全部楼层

看样子我悲剧了,都一天了还没消息。。。
回复 支持 反对

使用道具 举报

nuanuan1208 发表于 2016-3-27 01:12:58 | 显示全部楼层
lz是phd肯定妥妥的offer!据说现在phd headcount没招满~~
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2016-3-27 02:06:23 | 显示全部楼层
第一题是这样吗?input指是树节点还是任意一个数啊?
int findNextBigger(TreeNode *root, int target)
{
  if(!root)return INT_MAX;. From 1point 3acres bbs
  if(!root->left && !root->right)
  {
    if(root->val > target)return root->val;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    else  return INT_MAX;
  } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  int left = findNextBigger(root->left, target);
  int right = findNextBigger(root->right, target);
  return min(left,right);
}
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2016-3-27 02:18:03 | 显示全部楼层
第一面的第二题要求o(1)空间么?
回复 支持 反对

使用道具 举报

 楼主| theWANDERER 发表于 2016-3-27 04:14:04 来自手机 | 显示全部楼层
findNextBig我不确定你的解法对不对,target value他说假设是存在binary tree里面的,但不存在我想应该差不多。一面第二题我沒做成O(1)空间,有可能O(1) in order
回复 支持 反对

使用道具 举报

 楼主| theWANDERER 发表于 2016-3-27 04:14:39 来自手机 | 显示全部楼层
Traversal吗? (抱歉,手机回文按错了)
回复 支持 反对

使用道具 举报

 楼主| theWANDERER 发表于 2016-3-27 04:25:24 | 显示全部楼层
nuanuan1208 发表于 2016-3-27 01:12
lz是phd肯定妥妥的offer!据说现在phd headcount没招满~~

我也希望妥妥的, 但我不敢这样想.....怕失望
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-3-27 04:31:20 | 显示全部楼层
第一面第一题要bst才能binary search吧?binary tree似乎就是要inorder traverse?
回复 支持 反对

使用道具 举报

dimi 发表于 2016-3-27 05:10:15 | 显示全部楼层
都很簡單阿。楼主好运气 赞了。
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-3-27 05:33:43 | 显示全部楼层
mingzhou1987 发表于 2016-3-27 02:06.鐣欏璁哄潧-涓浜-涓夊垎鍦
第一题是这样吗?input指是树节点还是任意一个数啊?
int findNextBigger(TreeNode *root, int target)
. From 1point 3acres bbs{ ...
. 1point3acres.com/bbs
这个解法不太对吧。应该是纪录一个node.val 比target要大。 这样如果找到target的node, 并且node的right node为null时, 输出那个value, 即ignorer successor。
回复 支持 反对

使用道具 举报

daniel_hl 发表于 2016-3-27 06:04:37 | 显示全部楼层
lz第一题是不是这样做的?用一个变量记录nextVal,然后binary search的时候如果往左走就更新nextVal为当前root的值,往右走不变,找到后看看这个node有没有right child,有的话就是right child里的值,没有就是记录的nextVal
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2016-3-27 08:04:21 | 显示全部楼层
改了一下,这样呢?题目并没有说是bst, inorder的下一个未必是最小的比target大的值
我之前解法有问题,最后应该return root->val > target ? min(min(left, right), root->val) : min(left, right); 不过没测试过,不知道对不对。。
回复 支持 反对

使用道具 举报

 楼主| theWANDERER 发表于 2016-3-27 10:46:41 | 显示全部楼层
johnjavabean 发表于 2016-3-27 04:31. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第一面第一题要bst才能binary search吧?binary tree似乎就是要inorder traverse?

对要BST,抱歉打错
回复 支持 反对

使用道具 举报

freemail165 发表于 2016-3-27 11:28:11 | 显示全部楼层
theWANDERER 发表于 2016-3-27 10:46. visit 1point3acres.com for more.
对要BST,抱歉打错
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第一面的第二题比第一题难吧?
lz怎么做的?
morris traverse?
回复 支持 反对

使用道具 举报

 楼主| theWANDERER 发表于 2016-3-27 12:18:40 | 显示全部楼层
freemail165 发表于 2016-3-27 11:28
第一面的第二题比第一题难吧?
lz怎么做的?
morris traverse?

就真的做一个inorder traversal然后把所有的node放到一个vector里面,然后从头连到尾而已
回复 支持 反对

使用道具 举报

 楼主| theWANDERER 发表于 2016-3-27 12:19:41 | 显示全部楼层
daniel_hl 发表于 2016-3-27 06:04
lz第一题是不是这样做的?用一个变量记录nextVal,然后binary search的时候如果往左走就更新nextVal为当前r ...

我大致上是这样做的,没有用recursion
回复 支持 反对

使用道具 举报

ok123 发表于 2016-3-27 12:24:06 | 显示全部楼层
def find_next(root, target):
    if root is None: return float("INF")
    if root.val <= target:. visit 1point3acres.com for more.
        return find_next(root.right, target) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    if root.val > target:
        return min(root.val, find_next(root.left, target)

补充内容 (2016-3-27 12:24):
第一题
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 14:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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