一亩三分地论坛

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

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

BloomBerg电话面经

[复制链接] |试试Instant~ |关注本帖
wcongying 发表于 2016-1-16 09:13:26 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Bloomberg - 内推 - 技术电面 |Pass在职跳槽

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

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

x
流程如下:
1,问我现在的工作情况。Project喜欢哪个,然后请介绍我喜欢的那个项目。追问我选的那个项目上写的RSA的算法细节。
2,写代码,只有一题:总论是找一个二叉树中第K大的树。没错是二叉树。
      然后给的例子是同时找二叉树中最大的第二大的元素。我写的时候很注意corner case,而且写出的代码能够最后测试运行。
      测试阶段,面试官给我画了个二叉搜索树,我当场指出那是二叉搜索树。
     这道题这么出用iterative的方法遍历树会比较简单,暂时没想到好的recursive解法。开始面试官不理解我的解法,还说我写的是错的。但是我写的代码能把结果打印出来,所以我当场迅速写好他给的范例的测试,并且测试成功。最后面试官在面试结束后又测试了很多例子。我知道都成功了。
3,我问面试官问题。
总结:1,面试官是印度半岛部分的口音。印度和中国关系不差。而我现任同事是孟加拉人,口音和印度人如出一辙,孟加拉人对中国人印象应该算好吧。
2,我写的时候完全没偷懒,让我的代码能顺利测试,而且体现了我对JAVA的理解,而且我写测试用例很快。
3,问项目和讨论代码无时无刻在考察你的交流能力。
10天后左右收到邮件NY面试邀请,太开心能去看自由女神,中央公园和各大博物馆了!希望这篇文章对大家有所帮助。



补充内容 (2016-1-19 02:47):
2,写代码,只有一题:总论是找一个二叉树中第K大的树。没错是二叉树。----这里有错。应该是找一个treenode,这个treenode的value是这棵树中第k大的。

补充内容 (2016-3-2 13:54):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
请看最后一楼我的代码

补充内容 (2016-3-2 13:55):
16楼代码。。。

评分

2

查看全部评分

e6175423 发表于 2016-2-28 14:52:20 | 显示全部楼层
楼主,应该是二叉搜索树吧?
回复 支持 反对

使用道具 举报

 楼主| wcongying 发表于 2016-2-28 14:54:18 | 显示全部楼层
e6175423 发表于 2016-2-28 14:52
楼主,应该是二叉搜索树吧?

当时题目是binary tree. 假定不是Binary search tree。 我是直接上了O(N)的写法
回复 支持 反对

使用道具 举报

e6175423 发表于 2016-2-28 15:49:21 | 显示全部楼层
如果只是binary tree的话,O(n)肯定搞不定吧,数组中找第k大的数才是O(N)kth-largest-element-in-an-arra求楼主解释一下您的方法

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| wcongying 发表于 2016-2-29 03:21:52 | 显示全部楼层
因为我最终写的代码是在程序中同时找第一大和第二大的元素,所以能实现O(n),核心代码是
if(root.val>max){
                    secondMax=max;//minimal integer>3
                    max=root.val;//3>7. 1point3acres.com/bbs
}else if(root.val>secondMax){//Handling the situation that the max element is the first element we scan.
                     secondMax=root.val;
}
回复 支持 反对

使用道具 举报

jzysheep 发表于 2016-2-29 03:59:04 | 显示全部楼层
我猜面试官本来想说是BST的,在二叉树中找第K大和在array中找第K大没有什么两样, 你把二叉树所有节点(value, treenode)当作tuple放到array后找第K大不就行了
回复 支持 反对

使用道具 举报

 楼主| wcongying 发表于 2016-2-29 04:51:39 | 显示全部楼层
jzysheep 发表于 2016-2-29 03:59
我猜面试官本来想说是BST的,在二叉树中找第K大和在array中找第K大没有什么两样, 你把二叉树所有节点(valu ...

BT和BT找第K大能实现的最优算法复杂度不同。BST是O(lg h), h是 BST的高度; BT最好用quick sort.. from: 1point3acres.com/bbs
而我现在用的办法比quick sort写起来简单很多,也容易理解得多,而且是绝对O(n).. visit 1point3acres.com for more.

补充内容 (2016-2-29 06:32):
BST的算法复杂度错误,应该是 O(Tree's Height). 没有lg。
回复 支持 反对

使用道具 举报

jzysheep 发表于 2016-2-29 05:44:08 | 显示全部楼层
wcongying 发表于 2016-2-29 04:51
BT和BT找第K大能实现的最优算法复杂度不同。BST是O(lg h), h是 BST的高度; BT最好用quick sort.
而我现 ...

如果BST之前没有在节点结构中加入额外的count的话,复杂度还是O(n)吧。比较感兴趣楼主对BT的第K大解法
回复 支持 反对

使用道具 举报

 楼主| wcongying 发表于 2016-2-29 06:31:24 | 显示全部楼层
jzysheep 发表于 2016-2-29 05:44
如果BST之前没有在节点结构中加入额外的count的话,复杂度还是O(n)吧。比较感兴趣楼主对BT的第K大解法

BST没有必要在结构中加入额外的count,如果是BST,这道题的相似题目是LC的230. Kth Smallest Element in a BST。 计算孩子数量的时候改成计算右子树的孩子数量即可。  至于BT的情况,参考 215. Kth Largest Element in an Array 的讨论区的quick sort 解法,以及为什么用quick sort 解法。

我本身用的是Iterative的方式中序遍历的BT,所以在遍历的同时就同时更新最大和第二大的数值,因此复杂度是O(n)。 并且请看我对我上一个对您的回复的更正。
回复 支持 反对

使用道具 举报

jzysheep 发表于 2016-2-29 07:09:32 | 显示全部楼层
wcongying 发表于 2016-2-29 06:31
BST没有必要在结构中加入额外的count,如果是BST,这道题的相似题目是LC的230. Kth Smallest Element in  ...

BST的第K大应该是o(n)吧,评论区也没看到o(height)的解法。hint说的o(height)只是在改变节点结构后才能达到的。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

singledog2016 发表于 2016-2-29 11:38:47 | 显示全部楼层
230. Kth Smallest Element in a BST 那题复杂度肯定是O(n). 因为你先找到最小就是O(h), h不平衡情况下就已经可能是n了。 然后还要遍历k找到第k小。k有可能等于n.就遍历了所有元素。
O(height)是follow up.给每个node加了一个rank. 这样等于在search rank. 如果是平衡bst,就是logn. 求加米。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| wcongying 发表于 2016-2-29 12:19:45 | 显示全部楼层
我看到的hint是
Hint:
Try to utilize the property of a BST.
What if you could modify the BST node's structure?-------好吧,这里说可以修改BST的node的结构
The optimal runtime complexity is O(height of BST).
回复 支持 反对

使用道具 举报

hison7463 发表于 2016-3-2 04:17:21 | 显示全部楼层
还是不太理解楼主为什么要maintain max和secondMax这两个值,我最直观的解法是遍历BT,把所有的node存在一个list里面【O(n)】,然后quickselect找到Kth largest node 【average O(n), worse O(n ^ 2)】
回复 支持 反对

使用道具 举报

 楼主| wcongying 发表于 2016-3-2 10:01:51 | 显示全部楼层
hison7463 发表于 2016-3-2 04:17
还是不太理解楼主为什么要maintain max和secondMax这两个值,我最直观的解法是遍历BT,把所有的node存在一 ...

从程序的后续维护性存List,然后quick sort的方法更好
回复 支持 反对

使用道具 举报

hison7463 发表于 2016-3-2 10:35:55 | 显示全部楼层
wcongying 发表于 2016-3-2 10:01
从程序的后续维护性存List,然后quick sort的方法更好

quick select 和quick sort本质上是一个东西,只不过quick select会比quick sort早点结束而已,对了,能看下楼主代码吗?
回复 支持 反对

使用道具 举报

 楼主| wcongying 发表于 2016-3-2 13:54:21 | 显示全部楼层
// This is the text editor interface. . 鍥磋鎴戜滑@1point 3 acres
// Anything you type or change here will be seen by the other person in real time.


// how to find the Nth largest node in a binary tree..鐣欏璁哄潧-涓浜-涓夊垎鍦

// for e.g. find the largest and second largest member in a binary tree.

//             13. 鍥磋鎴戜滑@1point 3 acres
//     7               27
   
// 3       9       20       29
//                       28   32


// This is the text editor interface.
// Anything you type or change here will be seen by the other person in real time.


// how to find the Nth largest node in a binary tree.

// for e.g. find the largest and second largest member in a binary tree.. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

//             13 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
//     7               27
   
// 3       9       20       29
//                       28   32
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
import java.util.Stack;
public class Solution{
    public static void main(String[] args) {
       TreeNode root= new TreeNode(13);
       root.left=new TreeNode(7);
      // root.right=new TreeNode(27);
        root.left.left=new TreeNode(3);
        root.left.right=new TreeNode(9);
        Solution.lagestSecondLargestMember(root);-google 1point3acres
      
    }
. 1point3acres.com/bbs   
    //inorder traversal
    public static void lagestSecondLargestMember(TreeNode root){
        if(root==null) {//corner case;
            System.out.println("There is no root.");
            return;
        }
        if(root.left ==null&&root.right==null){//corner case;
            System.out.println("The largest member is " + root.val);
            System.out.println("There is no second largest member here.");.鐣欏璁哄潧-涓浜-涓夊垎鍦
            return;
        }
        
        helper(root);
    }
    //inorder traversal
    private static void helper(TreeNode root){
       int max=Integer.MIN_VALUE;
        int secondMax=Integer.MIN_VALUE;
        Stack<TreeNode> stack= new Stack<TreeNode>();. 1point3acres.com/bbs
        
        
        
        while(root!=null||!stack.isEmpty()){
            
            if(root!=null){
                stack.push(root);//13,7,3 //13,9. 鍥磋鎴戜滑@1point 3 acres
                root=root.left;//null
            }else{. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                root=stack.pop();//3 >7//13//9
                if(root.val>max){
                    secondMax=max;//minimal integer>3 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                    max=root.val;//3>7
                }else if(root.val>secondMax){//Handling the situation that the max element is the first element we scan..鐣欏璁哄潧-涓浜-涓夊垎鍦
                     secondMax=root.val;
                }.鐣欏璁哄潧-涓浜-涓夊垎鍦
                root=root.right;//9//null
            }
        }. more info on 1point3acres.com
       System.out.println("The largest member is " + max);
       System.out.println("The second largest member is " + secondMax);
    }
   
}. 1point3acres.com/bbs
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
class TreeNode{
    int val;
    TreeNode left,right;
    TreeNode(int x){val=x;}
}
回复 支持 反对

使用道具 举报

hison7463 发表于 2016-3-3 04:17:18 | 显示全部楼层
wcongying 发表于 2016-3-2 13:54
// This is the text editor interface.
// Anything you type or change here will be seen by the othe ...

题目不是要找第K大的节点吗?但是LZ得代码只能找到最大和第二大的呀。。。是不是我理解题目有问题。。。
回复 支持 反对

使用道具 举报

 楼主| wcongying 发表于 2016-3-3 05:22:55 | 显示全部楼层
// for e.g. find the largest and second largest member in a binary tree.
最后面试官要求我完成这个要求
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 06:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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