一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 2616|回复: 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大的值
做过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的变体
.....这也太诡异了吧,二面出的题目比一面简单! ?半个小时不到就结束了,该不会要用英文不好来拒我吧
. Waral 鍗氬鏈夋洿澶氭枃绔,

. From 1point 3acres bbs
补充内容 (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");
    .1point3acres缃
  4.                 for (String s : res) {
  5.                         System.out.println(s);
  6.                 }
  7.         }
  8. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  9.         public static List<String> getPalindromicSubstringLongerThanOne(String s) {. 1point 3acres 璁哄潧
  10.                 List<String> res = new ArrayList<String>();
    . 1point 3acres 璁哄潧
  11.                 if (s == null || s.length() == 0) {
  12.                         return res;
  13.                 }
  14.                 for (int i = 0; i < s.length() * 2 - 1; i++) {
  15.                         int left = i / 2;
  16.                         int right = i / 2;
  17.                         if (i % 2 == 1) {
  18.                                 right++;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  19.                         }
  20.                         findPalindrome(res, s, left, right);
  21.                 }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  22.                 return res;-google 1point3acres
  23.         }. from: 1point3acres.com/bbs

  24.         public static void findPalindrome(List<String> res, String s, int left, int right) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  25.                 while (left >= 0 && right < s.length()) {. 1point 3acres 璁哄潧
  26.                         if (s.charAt(left) != s.charAt(right)) {
  27.                                 break;
  28.                         }

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

使用道具 举报

sealove999 发表于 2016-4-3 13:51:12 | 显示全部楼层
一面二
  1. public class Solution {
  2.   TreeNode pre = null;. 1point 3acres 璁哄潧
  3.   TreeNode head = null;. 1point3acres.com/bbs
  4. . Waral 鍗氬鏈夋洿澶氭枃绔,
  5.   void inThreading(TreeNode root) {
  6.     if (root == null)
  7.       return;
  8.     inThreading(root.left);
  9.     if (head == null) {
  10.       head = root;
  11.     }
  12.     if (pre != null) {
  13.       pre.next = root;
  14.     }
  15.     pre = root;
  16.     inThreading(root.right);
  17.   }
  18. . 1point3acres.com/bbs
  19.   public static void main(String[] args) {
  20.     TreeNode tn1 = new TreeNode(1);
  21.     TreeNode tn2 = new TreeNode(2);
  22.     TreeNode tn3 = new TreeNode(3);
  23.     TreeNode tn4 = new TreeNode(4);
  24.     TreeNode tn5 = new TreeNode(5);
  25.     TreeNode tn6 = new TreeNode(6);
  26.     TreeNode tn7 = new TreeNode(7);. 鍥磋鎴戜滑@1point 3 acres
  27.     TreeNode tn8 = new TreeNode(8);
  28.     TreeNode tn9 = new TreeNode(9);
  29.     tn5.left = tn2;
  30.     tn5.right = tn8;
  31.     tn2.left = tn1;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  32.     tn2.right = tn4;
  33.     tn4.left = tn3;
  34.     tn8.left = tn7;. 1point3acres.com/bbs
  35.     tn8.right = tn9;
  36.     tn7.left = tn6;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  37.     Solution s = new Solution();
  38.     s.inThreading(tn5);
  39.     for (TreeNode p = s.head; p != null; p = p.next) {
  40.       System.out.println(p.val);
  41.     }-google 1point3acres
  42.     return;
  43.   }
  44. }
复制代码
回复 支持 1 反对 0

使用道具 举报

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) {
  6.       if (target < p.val) {
  7.         ret = p.val; // candidate
  8.         p = p.left;. 1point3acres.com/bbs
  9.       } else if (p.val < target) {
  10.         p = p.right;-google 1point3acres
  11.       }. 鍥磋鎴戜滑@1point 3 acres
  12.     }
  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;. 鍥磋鎴戜滑@1point 3 acres
  19.   }
  20. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  21.   public static void main(String[] args) {
  22.     TreeNode tn1 = new TreeNode(1);. Waral 鍗氬鏈夋洿澶氭枃绔,
  23.     TreeNode tn2 = new TreeNode(2);
  24.     TreeNode tn3 = new TreeNode(3);
  25.     TreeNode tn4 = new TreeNode(4);.1point3acres缃
  26.     TreeNode tn5 = new TreeNode(5);.1point3acres缃
  27.     TreeNode tn6 = new TreeNode(6);
  28.     TreeNode tn7 = new TreeNode(7);
  29.     TreeNode tn8 = new TreeNode(8);
  30.     TreeNode tn9 = new TreeNode(9);
  31.     tn5.left = tn2;
  32.     tn5.right = tn8;. Waral 鍗氬鏈夋洿澶氭枃绔,
  33.     tn2.left = tn1;
  34.     tn2.right = tn4;
  35.     tn4.left = tn3;
  36.     tn8.left = tn7;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  37.     tn8.right = tn9;
  38.     tn7.left = tn6;

  39.     Solution s = new Solution();
  40.     System.out.println(s.nextVal(tn5, 4));
  41.     System.out.println(s.nextVal(tn5, 2)); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  42.     System.out.println(s.nextVal(tn5, 8));
  43.     System.out.println(s.nextVal(tn5, 5));
  44.     System.out.println(s.nextVal(tn5, -1));
  45.     System.out.println(s.nextVal(tn5, 10));
  46.     return;
  47.   }
  48. }
复制代码
回复 支持 0 反对 1

使用道具 举报

mingzhou1987 发表于 2016-3-27 02:06:23 | 显示全部楼层
第一题是这样吗?input指是树节点还是任意一个数啊?
int findNextBigger(TreeNode *root, int target)
{. from: 1point3acres.com/bbs
  if(!root)return INT_MAX;
  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);
}
回复 支持 0 反对 1

使用道具 举报

freemail165 发表于 2016-3-27 22:50:12 | 显示全部楼层
theWANDERER 发表于 2016-3-27 12:18
就真的做一个inorder traversal然后把所有的node放到一个vector里面,然后从头连到尾而已
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
这个比第二题难?
而且你说的放在vendor,岂不用了额外内存?

Integer getNext(Node root,int target) {
    Node cur=root;. 1point 3acres 璁哄潧
    Node greater=null;
    while(cur!=null) {
       if(cur.val>target) {
            greater=cur;
            cur=cur.left;
       } else {
              cur=cur.right;
      }
   }
   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-google 1point3acres
楼主的面试有什么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 | 显示全部楼层
theWANDERER 发表于 2016-3-27 00:37. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
23小时内就收到了
.鏈枃鍘熷垱鑷1point3acres璁哄潧
看样子我悲剧了,都一天了还没消息。。。
回复 支持 反对

使用道具 举报

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没招满~~
.鐣欏璁哄潧-涓浜-涓夊垎鍦
我也希望妥妥的, 但我不敢这样想.....怕失望
回复 支持 反对

使用道具 举报

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)
{ ...

这个解法不太对吧。应该是纪录一个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,抱歉打错

第一面的第二题比第一题难吧?.鏈枃鍘熷垱鑷1point3acres璁哄潧
lz怎么做的?. Waral 鍗氬鏈夋洿澶氭枃绔,
morris traverse?
回复 支持 反对

使用道具 举报

 楼主| theWANDERER 发表于 2016-3-27 12:18:40 | 显示全部楼层
freemail165 发表于 2016-3-27 11:28
第一面的第二题比第一题难吧?.鐣欏璁哄潧-涓浜-涓夊垎鍦
lz怎么做的?. Waral 鍗氬鏈夋洿澶氭枃绔,
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 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
我大致上是这样做的,没有用recursion
回复 支持 反对

使用道具 举报

ok123 发表于 2016-3-27 12:24:06 | 显示全部楼层
def find_next(root, target):
    if root is None: return float("INF")
    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):
第一题
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-17 21:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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