一亩三分地论坛

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

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

Linkedin 电面 9/8

[复制链接] |试试Instant~ |关注本帖
zoufengboy 发表于 2015-9-12 01:46:31 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 博士 全职@Linkedin - 内推 - 技术电面 |Fail在职跳槽

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

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

x
发个面经攒攒人品,最近运气不是特别好,老遇到些没见过的新题。
写得磕磕绊绊,还提示了好久,最后虽然写出来了,不过可想而知~~~
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

Tournament tree 找secMin;.1point3acres缃

Tournament tree 的定义是parent 是孩子node的最小值, 如下例 return 5. 1point3acres.com/bbs

                2
              /  \
            2    7
          /  \    | \
        5    2  8  7
.1point3acres缃



补充内容 (2015-10-1 11:44):
我当时是这么写的. from: 1point3acres.com/bbs

int getSecMin(TreeNode* root)
{. 鍥磋鎴戜滑@1point 3 acres
   int res = INT_MAX;
   findSecMin(root, res);
   return res;
}

void findSecMin(TreeNode* root, int & res)
{
   if (!root) return;
   . 鍥磋鎴戜滑@1point 3 acres
   if (root->left && root->left->val == root->val) //继续访问的条件是当前值等于孩子值,这样要往下遍历,看是否有孩子比当前值大, 只要有比当前结点大的都是一个candidate
      findSecMin(root->left, res);

   if (root->right && root->right->val == root->val)
      findSecMin(root->right, res);

. from: 1point3acres.com/bbs    if (root->left && root->left->val > root->val) // possible left candidate
       res = min(res, root->left->val);

   if (root->right && root->right->val > root->val) // possible right candidate
       res = min(res, root->right->val);

}

补充内容 (2015-10-1 11:47):
最近运气不好啊,求内推啊

评分

3

查看全部评分

tyr034 发表于 2015-9-23 07:32:04 | 显示全部楼层
我觉得这道题说白了就是 给你一个list of integers,找second_min. . Waral 鍗氬鏈夋洿澶氭枃绔,
常规的方法,就是一个个比较,比较的次数为 2*N-3, time complexity 是 O(N).
Optimize的方法就是1)一开始两两比较,每次取小,最后还剩一个的时候就是 最小. from: 1point3acres.com/bbs
2)然后找第二小,要抓住的一点就是,第二小只会出现在,之前已经跟最小数比较过的 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
数中。. more info on 1point3acres.com

比如这道题就是7和5 : 在第一层的时候,我们知道最小值是2.;
进入第二层,我们发现left childer.val 是2,right.childreb是7,7比2大,就有可能是sec_min.
但是7底下的sub tree就都不用考虑了,因为这个sub tree的所有值都肯定比7大;
所以我们就继续往left sub tree 考虑,发现5>2,所以5也是我们的candidate之一;如果5. 1point 3acres 璁哄潧
下面还有subtree,同理也不需要考虑(因为它们都比5大)。
用这个方法找 最小值还是O(N). 找第二小的值是 O(log(N). 因为树的一层比较一次。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
贴一下代码,不知道有没有考虑所有情况:import sys
class TreeNode:
    def __init__(self,val):
        self.left  = None
        self.right = None. 鍥磋鎴戜滑@1point 3 acres
        self.val   = val

def second_min(root):
    if not root.left and not root.right:
        return sys.maxsize
    if root.left.val == root.val:
        p = second_min(root.left)
        q = root.right.val
    else:
        p = second_min(root.right)
. visit 1point3acres.com for more.        q = root.left.val
    return min(p,q)




回复 支持 3 反对 0

使用道具 举报

小柯西 发表于 2015-9-22 22:44:12 | 显示全部楼层
这个题的时间复杂应该是O(h), h是树的高度。
secmin只可能在root晋升的路径上被pk掉,所以把root从底层到顶层的路径traverse一遍就好了。
其次啊,tournament tree不是heap。。。。根本就没满足bst的定义,怎么会是heap。
回复 支持 2 反对 0

使用道具 举报

laurie洁 发表于 2015-9-12 02:32:52 | 显示全部楼层
M_Jason 发表于 2015-9-12 01:58
应该可以用递归,检查左右子树的值,找到最小的那个然后返回,如果左右子树最小的值与根节点相同,就继续向 ...

同意这个思路~~大家看看这样行吗
  1. public class Solution {
  2.     public static class TreeNode {. Waral 鍗氬鏈夋洿澶氭枃绔,
  3.             int val;. From 1point 3acres bbs
  4.             TreeNode left;
  5.             TreeNode right;
  6.             public TreeNode(int v) {
  7.                     val = v;
  8.             }
  9.     }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  10.    
  11.     public static int secMin(TreeNode root) {
  12.             if (root == null || (root.left == null && root.right == null)) {
  13.                     return -1;
  14.             }
  15.             int left = -1, right = -1;
  16.             if (root.left.val == root.val) {. From 1point 3acres bbs
  17.                     left = secMin(root.left);
  18.             } else {. more info on 1point3acres.com
  19.                     left = root.left.val;
  20.             }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  21.             if (root.right.val == root.val) {
    -google 1point3acres
  22.                     right = secMin(root.right);
  23.             } else {
  24.                     right = root.right.val;
    . from: 1point3acres.com/bbs
  25.             }
  26.             if (left == -1 || right == -1) {
  27.                     return left == -1 ? right : left;
  28.             }
  29.             return Math.min(left, right);
  30.     }
  31.     . 鍥磋鎴戜滑@1point 3 acres
  32.     public static void main(String[] args) {
  33.         TreeNode root = new TreeNode(2);
  34.         root.left = new TreeNode(2);
  35.         root.right = new TreeNode(7);. 1point3acres.com/bbs
  36.         root.left.left = new TreeNode(5);
  37.         root.left.right = new TreeNode(2);
  38.         root.right.left = new TreeNode(8); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  39.         root.right.right = new TreeNode(7);
  40.         System.out.println(secMin(root));
  41.     }
  42. }
复制代码
回复 支持 2 反对 0

使用道具 举报

AndyLiu0429 发表于 2015-9-13 02:50:21 | 显示全部楼层
jiebour 发表于 2015-9-13 02:17
复杂度是多少?

我感觉应该是树的高度吧。每次都会减掉一半的枝。
回复 支持 1 反对 0

使用道具 举报

M_Jason 发表于 2015-9-12 01:48:34 | 显示全部楼层
这个Tournament tree一定是binary
回复 支持 反对

使用道具 举报

M_Jason 发表于 2015-9-12 01:49:06 | 显示全部楼层
M_Jason 发表于 2015-9-12 01:48
这个Tournament tree一定是binary

我去。。。。点的太快了,不好意思,一定是binary tree是吧?
回复 支持 反对

使用道具 举报

M_Jason 发表于 2015-9-12 01:50:13 | 显示全部楼层
额,还有一点,叶子节点会有重复的吗?应该不会有吧?
回复 支持 反对

使用道具 举报

 楼主| zoufengboy 发表于 2015-9-12 01:50:50 | 显示全部楼层
M_Jason 发表于 2015-9-12 01:49
我去。。。。点的太快了,不好意思,一定是binary tree是吧?

恩,是binary
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-9-12 01:51:26 | 显示全部楼层
难道这个真的不能理解为最小堆?
回复 支持 反对

使用道具 举报

eamon_felix4213 发表于 2015-9-12 01:51:35 | 显示全部楼层
lz感谢分享,请问lz是投简历之后多久约的电面呢
回复 支持 反对

使用道具 举报

M_Jason 发表于 2015-9-12 01:54:03 | 显示全部楼层
jiebour 发表于 2015-9-12 01:51
难道这个真的不能理解为最小堆?
.鐣欏璁哄潧-涓浜-涓夊垎鍦
我估计不是让用O(nlogn)的时间
回复 支持 反对

使用道具 举报

M_Jason 发表于 2015-9-12 01:58:45 | 显示全部楼层
应该可以用递归,检查左右子树的值,找到最小的那个然后返回,如果左右子树最小的值与根节点相同,就继续向下遍历,如果已经是叶子节点,并且依然与根节点相同,那就返回MAX_VALUE,然后最终返回两个值中的最小值应该就是secMin了吧?
回复 支持 反对

使用道具 举报

liudaisuda 发表于 2015-9-12 01:58:54 | 显示全部楼层
什么是secMin
回复 支持 反对

使用道具 举报

M_Jason 发表于 2015-9-12 01:59:54 | 显示全部楼层
.鏈枃鍘熷垱鑷1point3acres璁哄潧
应该是第二小的意思吧
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-9-12 02:00:09 | 显示全部楼层

second minimum
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-9-12 02:08:40 | 显示全部楼层
M_Jason 发表于 2015-9-12 01:54
我估计不是让用O(nlogn)的时间

遍历一遍能不能找到第二小?能吧?遍历的复杂度是O(N)
回复 支持 反对

使用道具 举报

hanchen999 发表于 2015-9-12 02:34:03 | 显示全部楼层
这个不是让写个iterator之类的东西吧?
回复 支持 反对

使用道具 举报

g_fighter 发表于 2015-9-13 02:11:43 | 显示全部楼层
laurie洁 发表于 2015-9-12 02:32. more info on 1point3acres.com
同意这个思路~~大家看看这样行吗

同意 不过每次做left和right要先判断下是否null,别的都对~
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-9-13 02:17:41 | 显示全部楼层
g_fighter 发表于 2015-9-13 02:11
同意 不过每次做left和right要先判断下是否null,别的都对~

复杂度是多少?
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-9-13 02:52:50 | 显示全部楼层
AndyLiu0429 发表于 2015-9-13 02:50
我感觉应该是树的高度吧。每次都会减掉一半的枝。

假设所有的node的value相等,再假设是full binary tree,但是最最右边的那个叶子的value不相等。复杂度是多少?
回复 支持 反对

使用道具 举报

ac/dc 发表于 2015-9-13 03:24:16 | 显示全部楼层
  1. int dfs(TreeNode* node, int min) {. 1point 3acres 璁哄潧
  2.   if (node->val > min) return node->val;
  3.   if (node->left == nullptr && node->right == nullptr) return INT_MAX;
  4.   return min(secMin(node->left, min), secMin(node->right, min));.鏈枃鍘熷垱鑷1point3acres璁哄潧
  5. }

  6. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  7. int secMin(TreeNode* root) {
  8.   assert(root != nullptr);. visit 1point3acres.com for more.
  9.   return dfs(root, root->val);. 鍥磋鎴戜滑@1point 3 acres
  10. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 06:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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