San Jose各个房价 <1.5m 区域买房总结

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 6194|回复: 38
收起左侧

FB两轮面经

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

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

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

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

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

.留学论坛-一亩-三分地

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

评分

3

查看全部评分

本帖被以下淘专辑推荐:

  • · Facebook|主题: 605, 订阅: 222
  • · Google|主题: 54, 订阅: 47
sealove999 发表于 2016-4-3 13:51:12 | 显示全部楼层
一面二
  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. . 一亩-三分-地,独家发布
  18.   public static void main(String[] args) {
  19.     TreeNode tn1 = new TreeNode(1);
  20.     TreeNode tn2 = new TreeNode(2);
  21.     TreeNode tn3 = new TreeNode(3);. more info on 1point3acres
  22.     TreeNode tn4 = new TreeNode(4);
  23.     TreeNode tn5 = new TreeNode(5);
  24.     TreeNode tn6 = new TreeNode(6);
  25.     TreeNode tn7 = new TreeNode(7);
  26.     TreeNode tn8 = new TreeNode(8);
  27.     TreeNode tn9 = new TreeNode(9);
  28.     tn5.left = tn2;
  29.     tn5.right = tn8;
  30.     tn2.left = tn1;
  31.     tn2.right = tn4;-google 1point3acres
  32.     tn4.left = tn3;
  33.     tn8.left = tn7;
  34.     tn8.right = tn9;
  35.     tn7.left = tn6;

  36.     Solution s = new Solution();. Waral 博客有更多文章,
  37.     s.inThreading(tn5);
  38.     for (TreeNode p = s.head; p != null; p = p.next) {. from: 1point3acres
  39.       System.out.println(p.val);
  40.     }.1point3acres网
  41.     return;
  42.   }
  43. }
复制代码
回复 支持 2 反对 0

使用道具 举报

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.                 }
    .1point3acres网
  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;. visit 1point3acres for more.
  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. . From 1point 3acres bbs
  22.                 return res;
    来源一亩.三分地论坛.
  23.         }

  24.         public static void findPalindrome(List<String> res, String s, int left, int right) {
  25.                 while (left >= 0 && right < s.length()) {
  26.                         if (s.charAt(left) != s.charAt(right)) {
  27.                                 break;
  28.                         }. 留学申请论坛-一亩三分地

  29.                         left--;. visit 1point3acres for more.
  30.                         right++;. 牛人云集,一亩三分地
  31.                         if (s.substring(left + 1, right).length() > 1) {
  32.                                 res.add(s.substring(left + 1, right));
  33.                         }. From 1point 3acres bbs
  34.                 }
  35.         }
  36. }
复制代码
回复 支持 1 反对 1

使用道具 举报

sealove999 发表于 2016-4-3 13:50:52 | 显示全部楼层
一面一
  1. public class Solution {. 围观我们@1point 3 acres
  2.   Integer nextVal(TreeNode root, int target) {. more info on 1point3acres
  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;
  9.       } else if (p.val < target) {
  10.         p = p.right;
  11.       }.留学论坛-一亩-三分地
  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;. From 1point 3acres bbs
  19.   }

  20.   public static void main(String[] args) {
  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;
  46.   }. Waral 博客有更多文章,
  47. }
复制代码
回复 支持 0 反对 1

使用道具 举报

mingzhou1987 发表于 2016-3-27 02:06:23 | 显示全部楼层
第一题是这样吗?input指是树节点还是任意一个数啊?
int findNextBigger(TreeNode *root, int target)
{
  if(!root)return INT_MAX;. 1point 3acres 论坛
  if(!root->left && !root->right)
  {
    if(root->val > target)return root->val;
    else  return INT_MAX;
. visit 1point3acres for more.  }
  int left = findNextBigger(root->left, target);. 1point 3acres 论坛
  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,岂不用了额外内存?. 1point3acres

Integer getNext(Node root,int target) {
    Node cur=root;
    Node greater=null;.本文原创自1point3acres论坛
    while(cur!=null) {
       if(cur.val>target) {
            greater=cur;
            cur=cur.left;
       } else {
              cur=cur.right;. 1point 3acres 论坛
      }
   }
   if(greater!=null) return greater.val;
    return null;
}
. 围观我们@1point 3 acres
回复 支持 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
楼主的面试有什么update的消息了吗?

offer了,强运
Mobile Apps Category (English)728x90
回复 支持 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小时内就收到了

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

使用道具 举报

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,抱歉打错

第一面的第二题比第一题难吧?
lz怎么做的?
morris traverse?
回复 支持 反对

使用道具 举报

 楼主| theWANDERER 发表于 2016-3-27 12:18:40 | 显示全部楼层
freemail165 发表于 2016-3-27 11:28
第一面的第二题比第一题难吧?. visit 1point3acres for more.
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:
        return find_next(root.right, target)
    if root.val > target:
        return min(root.val, find_next(root.left, target)

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

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-27 01:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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