一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 890|回复: 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的题真心要把很多细节做到熟练啊。。。 写的这么慢,还是烙印,看来是没戏了。。

int largestoftree(Node *root){
   if(root==NULL). more info on 1point3acres.com
       return INT_MIN;
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
   while(root->right)
       root = root->right;
.鐣欏璁哄潧-涓浜-涓夊垎鍦
   return root->number;
}. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

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

   while(root->left)
       root = root->left;

   return root->number;
}



void findnumbers(Node *root, int target){. more info on 1point3acres.com
    if(root == NULL). from: 1point3acres.com/bbs
        return;. 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). 鍥磋鎴戜滑@1point 3 acres
    } else { // root->number == target. Waral 鍗氬鏈夋洿澶氭枃绔,
        // Process
        // largernum = 3
        // 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那题一样找中序后继了
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

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)
. From 1point 3acres bbs
感觉对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. Waral 鍗氬鏈夋洿澶氭枃绔,
默认是target一定会找到。

如果默认一定找到target,那直接在树里找到target的node,那么
.1point3acres缃
仅仅小于target的node的值一定是findLargest(node->left). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
仅仅大于target的node的值一个是findSmallest(node->right)
不对么,不需要更新其他的啊
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

 楼主| cocaptainco 发表于 2015-11-4 23:22:42 | 显示全部楼层
DJ963 发表于 2015-11-4 13:59
非常感谢楼主分享~ 我有点小疑问啊,在findnumber里面 我感觉是不是不需要加 smallernum = max(smallernum, ...
. 1point3acres.com/bbs
对啊,其实不需要。。。
回复 支持 反对

使用道具 举报

 楼主| 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:. Waral 鍗氬鏈夋洿澶氭枃绔,
  3.     int val;
  4.     Node *left, *right;
  5.     Node(int val) {
  6.         this->val = val;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  7.         left = NULL;
  8.         right = NULL;
  9.     }
  10. };.鐣欏璁哄潧-涓浜-涓夊垎鍦

  11. Node* findMinNode(Node *root) {
  12.     if(!root) return NULL;
  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;. 鍥磋鎴戜滑@1point 3 acres
  20. }
  21. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  22. void findNumbers(Node *root, int target, Node *&minNode, Node *&maxNode) {
  23.     if(!root) return;-google 1point3acres
  24.     if(root->val < target) {
  25.         minNode = root;
  26.         findNumbers(root->right, target, minNode, maxNode);
  27.     } else if(root->val > target) {
  28.         maxNode = root;
  29.         findNumbers(root->left, target, minNode, maxNode);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  30.     } else if(root->val == target) {
  31.         if(root->left) minNode = findMaxNode(root->left);
  32.         if(root->right) maxNode = findMinNode(root->right);
  33.     }
  34. }. 鍥磋鎴戜滑@1point 3 acres

  35. void inordrerPrint(Node *root) {
  36.     if(!root) return;
  37.     if(root->left) inordrerPrint(root->left);
  38.     cout << root->val << ", ";
  39.     if(root->right) inordrerPrint(root->right);
  40. }. Waral 鍗氬鏈夋洿澶氭枃绔,

  41. int main(char **argv, int argc)
  42. {
  43.     Node *root = new Node(10);
  44.     root->left = new Node(5);
  45.     root->left->left = new Node(3);
  46.     root->left->right = new Node(8);

  47.     root->right = new Node(15);
  48.     root->right->left = new Node(12);
  49.     root->right->left->left = new Node(11);
  50.     root->right->left->right = new Node(14);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  51.     root->right->right = new Node(18);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  52.     root->right->right->left = new Node(16);
  53.     root->right->right->right = new Node(19);

  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.     }. visit 1point3acres.com for more.

  62.     return 0;
  63. }
复制代码

                               
登录/注册后可看大图
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-25 05:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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