May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

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

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

FB两轮面经

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

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

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

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

x
第一面
一个很耐死的老印,一开始自介,然后我介绍自己,这部分花了15分钟上下
第一题:binary tree,给定一个value,return bin tree里面下一个比value大的值
做过binary tree iterator,但没做过这题
一开始想法就是inorder traversal之后一个一个吐出来到找到value.1point3acres缃
当然这不是最佳解,很naive的解法,面试官叫我想能不能改进
我想那就binary search,犯了一些小错,但最后有搞出来
第二题:binary tree的node加一个ptr next,point到inorder traversal的下一个node,比上一个简单

二面,一个口音应该是白女的面试官,一开始就让我自介
我讲了几分钟吧,没注意
他自介了三十秒,基本什么都没讲,直接开始题目
第一题:valid palindrome,我一下子都混乱了,这不刷题都应该要会做的题目,我还跟他确认了一下细节,他要求我no extra string/space,即便这样,还是太简单吧...?
第二题:给一个string,列出所有长度大于一的palindromic substring,LC longest palindromic substring的变体
.....这也太诡异了吧,二面出的题目比一面简单! ?半个小时不到就结束了,该不会要用英文不好来拒我吧


. more info on 1point3acres.com
补充内容 (2016-3-27 23:22):
一面第一题是bst才对,抱歉

评分

3

查看全部评分

本帖被以下淘专辑推荐:

sealove999 发表于 2016-4-3 13:51:12 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
一面二. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  1. public class Solution {
  2.   TreeNode pre = null;
  3.   TreeNode head = null;

  4.   void inThreading(TreeNode root) {
  5.     if (root == null)
  6.       return;
  7.     inThreading(root.left);
  8.     if (head == null) {
  9.       head = root;
  10.     }
  11.     if (pre != null) {
  12.       pre.next = root;
  13.     }
  14.     pre = root;
  15.     inThreading(root.right);
  16.   }

  17.   public static void main(String[] args) {
  18.     TreeNode tn1 = new TreeNode(1);
    .1point3acres缃
  19.     TreeNode tn2 = new TreeNode(2);
  20.     TreeNode tn3 = new TreeNode(3);. From 1point 3acres bbs
  21.     TreeNode tn4 = new TreeNode(4);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  22.     TreeNode tn5 = new TreeNode(5);
  23.     TreeNode tn6 = new TreeNode(6);
  24.     TreeNode tn7 = new TreeNode(7);
  25.     TreeNode tn8 = new TreeNode(8);
  26.     TreeNode tn9 = new TreeNode(9);
  27.     tn5.left = tn2;
  28.     tn5.right = tn8;
  29.     tn2.left = tn1;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  30.     tn2.right = tn4;. 1point3acres.com/bbs
  31.     tn4.left = tn3;
  32.     tn8.left = tn7;
  33.     tn8.right = tn9;. 1point3acres.com/bbs
  34.     tn7.left = tn6;
  35. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  36.     Solution s = new Solution();
  37.     s.inThreading(tn5);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  38.     for (TreeNode p = s.head; p != null; p = p.next) {
  39.       System.out.println(p.val);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  40.     }
  41.     return;
  42.   }
  43. }
复制代码
回复 支持 2 反对 0

使用道具 举报

bobzhang2004 发表于 2016-4-3 06:46:53 | 显示全部楼层
关注一亩三分地微博:
Warald
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.                 }. visit 1point3acres.com for more.
  7.         }

  8.         public static List<String> getPalindromicSubstringLongerThanOne(String s) {
  9.                 List<String> res = new ArrayList<String>();
  10.                 if (s == null || s.length() == 0) {
  11.                         return res;
  12.                 }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  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;
  22.         }. From 1point 3acres bbs

  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.                         }.鏈枃鍘熷垱鑷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 反对 1

使用道具 举报

sealove999 发表于 2016-4-3 13:50:52 | 显示全部楼层
一面一
  1. public class Solution {
  2.   Integer nextVal(TreeNode root, int target) {
  3.     Integer ret = null; // if NA, return null
  4.     TreeNode p = root;
  5.     while (p != null && p.val != target) {-google 1point3acres
  6.       if (target < p.val) {
  7.         ret = p.val; // candidate
  8.         p = p.left;. 鍥磋鎴戜滑@1point 3 acres
  9.       } else if (p.val < target) {. 鍥磋鎴戜滑@1point 3 acres
  10.         p = p.right;
  11.       }
  12.     }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  13.     if (p != null) { // target found
  14.       for (TreeNode q = p.right; q != null; q = q.left) { // find the left in right subtree
  15.         ret = q.val;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  16.       }
  17.     }
  18.     return ret;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  19.   }. 1point3acres.com/bbs

  20.   public static void main(String[] args) {. From 1point 3acres bbs
  21.     TreeNode tn1 = new TreeNode(1);
  22.     TreeNode tn2 = new TreeNode(2);
  23.     TreeNode tn3 = new TreeNode(3);
  24.     TreeNode tn4 = new TreeNode(4);
  25.     TreeNode tn5 = new TreeNode(5);
  26.     TreeNode tn6 = new TreeNode(6);
  27.     TreeNode tn7 = new TreeNode(7); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  28.     TreeNode tn8 = new TreeNode(8);
  29.     TreeNode tn9 = new TreeNode(9);
  30.     tn5.left = tn2;
  31.     tn5.right = tn8;
  32.     tn2.left = tn1;
  33.     tn2.right = tn4;
  34.     tn4.left = tn3;
  35.     tn8.left = tn7;
  36.     tn8.right = tn9;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  37.     tn7.left = tn6;

  38.     Solution s = new Solution();
  39.     System.out.println(s.nextVal(tn5, 4));
  40.     System.out.println(s.nextVal(tn5, 2));
  41.     System.out.println(s.nextVal(tn5, 8));
  42.     System.out.println(s.nextVal(tn5, 5));
  43.     System.out.println(s.nextVal(tn5, -1));
  44.     System.out.println(s.nextVal(tn5, 10));
  45.     return;-google 1point3acres
  46.   }
  47. }
复制代码
回复 支持 0 反对 1

使用道具 举报

mingzhou1987 发表于 2016-3-27 02:06:23 | 显示全部楼层
第一题是这样吗?input指是树节点还是任意一个数啊?
int findNextBigger(TreeNode *root, int target)
{
  if(!root)return INT_MAX;
  if(!root->left && !root->right). Waral 鍗氬鏈夋洿澶氭枃绔,
  {
    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);
}
回复 支持 0 反对 1

使用道具 举报

freemail165 发表于 2016-3-27 22:50:12 | 显示全部楼层
theWANDERER 发表于 2016-3-27 12:18
就真的做一个inorder traversal然后把所有的node放到一个vector里面,然后从头连到尾而已

这个比第二题难?. more info on 1point3acres.com
而且你说的放在vendor,岂不用了额外内存?

. From 1point 3acres bbsInteger getNext(Node root,int target) {-google 1point3acres
    Node cur=root;
    Node greater=null;
    while(cur!=null) {
       if(cur.val>target) {
            greater=cur;
            cur=cur.left;
       } else {
              cur=cur.right;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
      }. from: 1point3acres.com/bbs
   }
   if(greater!=null) return greater.val;
    return null;
}

回复 支持 1 反对 0

使用道具 举报

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

使用道具 举报

 楼主| theWANDERER 发表于 2016-4-3 10:15:28 | 显示全部楼层
honeyBear142857 发表于 2016-3-31 10:34. 1point3acres.com/bbs
楼主的面试有什么update的消息了吗?
. 1point 3acres 璁哄潧
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: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没招满~~
. from: 1point3acres.com/bbs
我也希望妥妥的, 但我不敢这样想.....怕失望
回复 支持 反对

使用道具 举报

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
. from: 1point3acres.com/bbs 第一题是这样吗?input指是树节点还是任意一个数啊?
int findNextBigger(TreeNode *root, int target)
{ ...

这个解法不太对吧。应该是纪录一个node.val 比target要大。 这样如果找到target的node, 并且node的right node为null时, 输出那个value, 即ignorer successor。
回复 支持 反对

使用道具 举报

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
对要BST,抱歉打错
. visit 1point3acres.com for more.
第一面的第二题比第一题难吧?
lz怎么做的?
morris traverse?
回复 支持 反对

使用道具 举报

 楼主| theWANDERER 发表于 2016-3-27 12:18:40 | 显示全部楼层
freemail165 发表于 2016-3-27 11:28
第一面的第二题比第一题难吧?. 1point 3acres 璁哄潧
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").鏈枃鍘熷垱鑷1point3acres璁哄潧
    if root.val <= target:
        return find_next(root.right, target)
    if root.val > target:
        return min(root.val, find_next(root.left, target)

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-30 15:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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