一亩三分地论坛

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

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

热乎乎的fb店面

[复制链接] |试试Instant~ |关注本帖
cocaptainco 发表于 2015-11-4 03:56:54 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 博士 全职@Facebook - 猎头 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚刚结束的店面,面经如下。
1. given a sorted array 1, 1 , 2, 2, 3, 3, 5, 5, 5, 5, 5 , find the frequency of a given target.
example target = 5, return 5. target = 2 return 2.
就讲了一下可以binary search 到 最左边和最右边的边界,然后减一下加一就是 结果。烙印就问我是不是做过。我说这题就是常见的binary search的变形而已。 然后就没写代码,换了第二题
2. Given the root of a binary search tree of integers and another integer ‘target’, find the number which is just smaller and just larger than the target.
其实就是找inorder traversal的predecessor 和 successor。但是这样的complexity是linear的,问能不能优化,我就说可以binary search 到target, 说不定能到O(log(n))。当时犹豫的点是,找到了inorder succesor, 还得记录parent啥的。总之大脑一片混乱。。讨论了不少example,花费了很多时间。。。最后还是没搞清,说不如直接写code吧。
写着其实就明白了,就是search到target, 同时update相应的smaller number 和 larger number。代码如下。 最后找到的时候,还要看看children的情况。。。。
差点没写出来,写完了之后,好多需要优化,比如largestoftree啥的我一开始还逐个比较。。。其实直接找到最右边的child就好了。。。

结论是脑子真不好使。。。fb的题真心要把很多细节做到熟练啊。。。 写的这么慢,还是烙印,看来是没戏了。。. Waral 鍗氬鏈夋洿澶氭枃绔,

int largestoftree(Node *root){
   if(root==NULL)
       return INT_MIN;
-google 1point3acres
   while(root->right)-google 1point3acres
       root = root->right;. from: 1point3acres.com/bbs

   return root->number;
}

int smallestoftree(Node *root){
   if(root==NULL)
      return INT_MAX;

   while(root->left)
       root = root->left;. more info on 1point3acres.com

   return root->number;
}



void findnumbers(Node *root, int target){
    if(root == NULL). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        return;
. from: 1point3acres.com/bbs
    if(root->number < target){
        smallernum = max(smallernum, root->number);
        findnumbers(root->right, target). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    } else if (root->number > target) {
        largernum = min(largernum, root->number);
        findnumbers(root->left, target). From 1point 3acres bbs
    } else { // root->number == target
        // Process
        // largernum = 3. 1point3acres.com/bbs
        // smallnumer = INT_MIN

        smallernum = max(smallernum, largestoftree(root->left)); // INT_MIN;
        largernum = min(laregernum, smallestoftree(root->right)); // 3
    }
} 鏉ユ簮涓浜.涓夊垎鍦拌鍧.





补充内容 (2015-11-7 07:15):
已跪,就知道烙印不会有啥好话
dylanwen 发表于 2015-11-4 04:16:43 | 显示全部楼层
楼主已经不错了啊!还是有希望的!面试的时候一紧张确实思路容易乱。
回复 支持 反对

使用道具 举报

jy_121 发表于 2015-11-4 05:06:34 | 显示全部楼层
感觉就是search到target后,还要找它的中序前驱,可能要保存父节点来实现?另外就是像leetcode那题一样找中序后继了
回复 支持 反对

使用道具 举报

smallpig1988 发表于 2015-11-4 08:23:30 | 显示全部楼层
感谢LZ分享。能不能用morris traversal 把node连到左subtree的最右节点,空间 O(1)
回复 支持 反对

使用道具 举报

 楼主| cocaptainco 发表于 2015-11-4 08:31:16 | 显示全部楼层
smallpig1988 发表于 2015-11-4 08:23 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
感谢LZ分享。能不能用morris traversal 把node连到左subtree的最右节点,空间 O(1)

感觉对time complexity 比较严格
回复 支持 反对

使用道具 举报

akluffy 发表于 2015-11-4 12:23:30 | 显示全部楼层
有一个case是,如果target比BST里面最小的值还小或者比最大值还大,那么是不是只需要返回其中一个就行了,另外一个不存在?
回复 支持 反对

使用道具 举报

 楼主| cocaptainco 发表于 2015-11-4 13:13:30 | 显示全部楼层
akluffy 发表于 2015-11-4 12:23
有一个case是,如果target比BST里面最小的值还小或者比最大值还大,那么是不是只需要返回其中一个就行了, ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
默认是target一定会找到。
回复 支持 反对

使用道具 举报

DJ963 发表于 2015-11-4 13:59:17 | 显示全部楼层
非常感谢楼主分享~ 我有点小疑问啊,在findnumber里面 我感觉是不是不需要加 smallernum = max(smallernum, root->number); 和largernum = min(largernum, root->number); ~ 因为每次新走到的根节点一定比原先的跟节点的number 更靠近target~
回复 支持 反对

使用道具 举报

akluffy 发表于 2015-11-4 22:33:01 | 显示全部楼层
cocaptainco 发表于 2015-11-4 13:13
默认是target一定会找到。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
如果默认一定找到target,那直接在树里找到target的node,那么

仅仅小于target的node的值一定是findLargest(node->left)
仅仅大于target的node的值一个是findSmallest(node->right)
不对么,不需要更新其他的啊
回复 支持 反对

使用道具 举报

 楼主| cocaptainco 发表于 2015-11-4 23:22:42 | 显示全部楼层
DJ963 发表于 2015-11-4 13:59. Waral 鍗氬鏈夋洿澶氭枃绔,
非常感谢楼主分享~ 我有点小疑问啊,在findnumber里面 我感觉是不是不需要加 smallernum = max(smallernum, ...

对啊,其实不需要。。。
回复 支持 反对

使用道具 举报

 楼主| cocaptainco 发表于 2015-11-4 23:23:01 | 显示全部楼层
akluffy 发表于 2015-11-4 22:33
如果默认一定找到target,那直接在树里找到target的node,那么

仅仅小于target的node的值一定是findLa ...

因为不一定有left child 和 right child
回复 支持 反对

使用道具 举报

akluffy 发表于 2015-11-5 07:31:31 | 显示全部楼层
这题说简单,简单,没有复杂的算法数据机构,说难也有点难,代码很多。
我把我写的发一下,test case跑了下,没有问题。
  1. class Node{
  2. public:
  3.     int val;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  4.     Node *left, *right;
  5.     Node(int val) {
  6.         this->val = val;
  7.         left = NULL;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  8.         right = NULL;
  9.     }
  10. };

  11. Node* findMinNode(Node *root) {
  12.     if(!root) return NULL;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  13.     while(root->left) root = root->left;
  14.     return root;
  15. }

  16. Node* findMaxNode(Node *root) {
  17.     if(!root) return NULL;
  18.     while(root->right) root = root->right;
  19.     return root;
  20. }

  21. void findNumbers(Node *root, int target, Node *&minNode, Node *&maxNode) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  22.     if(!root) return;
  23.     if(root->val < target) {
  24.         minNode = root;. From 1point 3acres bbs
  25.         findNumbers(root->right, target, minNode, maxNode);. Waral 鍗氬鏈夋洿澶氭枃绔,
  26.     } else if(root->val > target) {
  27.         maxNode = root;.1point3acres缃
  28.         findNumbers(root->left, target, minNode, maxNode);
  29.     } else if(root->val == target) {
  30.         if(root->left) minNode = findMaxNode(root->left);
  31.         if(root->right) maxNode = findMinNode(root->right);
  32.     }
  33. }

  34. void inordrerPrint(Node *root) {
  35.     if(!root) return;.1point3acres缃
  36.     if(root->left) inordrerPrint(root->left);
  37.     cout << root->val << ", ";
  38.     if(root->right) inordrerPrint(root->right);
  39. }

  40. int main(char **argv, int argc)
  41. {
  42.     Node *root = new Node(10);
  43.     root->left = new Node(5);. visit 1point3acres.com for more.
  44.     root->left->left = new Node(3);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  45.     root->left->right = new Node(8);. from: 1point3acres.com/bbs

  46.     root->right = new Node(15);
  47.     root->right->left = new Node(12);
  48.     root->right->left->left = new Node(11);
  49.     root->right->left->right = new Node(14);
  50.     root->right->right = new Node(18);. 1point3acres.com/bbs
  51.     root->right->right->left = new Node(16);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  52.     root->right->right->right = new Node(19);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  53. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  54. inordrerPrint(root);
  55. cout << endl;

  56.     Node *prev = NULL, *next = NULL; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  57.     for(int i = 4; i <= 18; ++i) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  58.         int target = i;
  59.         findNumbers(root, target, prev, next);
  60.         cout << "prev : " << prev->val << "  target : " << target << "  next : " << next->val << endl;
  61.     }

  62.     return 0;.1point3acres缃
  63. }
复制代码

                               
登录/注册后可看大图
回复 支持 反对

使用道具 举报

 楼主| cocaptainco 发表于 2015-11-5 08:18:25 | 显示全部楼层
akluffy 发表于 2015-11-5 07:31. 鍥磋鎴戜滑@1point 3 acres
这题说简单,简单,没有复杂的算法数据机构,说难也有点难,代码很多。
我把我写的发一下,test case跑了 ...

也对,predecessor 和 successor of BST node, 网上有这个代码。。。可惜之前没看到
回复 支持 反对

使用道具 举报

akluffy 发表于 2015-11-5 13:07:10 | 显示全部楼层
cocaptainco 发表于 2015-11-5 08:18
也对,predecessor 和 successor of BST node, 网上有这个代码。。。可惜之前没看到

嗯面试还是很看运气的。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 18:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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