一亩三分地论坛

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

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

SnapChat电面跪经

[复制链接] |试试Instant~ |关注本帖
ginues109 发表于 2016-11-2 06:32:55 | 显示全部楼层 |阅读模式

2017(10-12月) 码农类 硕士 全职@Snapchat - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
一个很牛的国人小哥。问了15分钟左右简历题:
Find Median from Data Stream. 类似LC 295. 但是只能用一个Tree作为数据结构(如果你想用PriorityQueue,要手动用Tree实现;如果要用heap,要手动用Tree实现)。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
没有什么很straightforward的想法,硬着头皮想维护一个balanced BST发现写不出来。真心戳短板,回去手写heap构建一万遍。
对不起面馆对不起内推人啊TT

. 1point 3acres 璁哄潧
补充内容 (2016-11-2 07:22):
只能用一个Tree,所以two heaps的方法是不行的
. From 1point 3acres bbs
补充内容 (2016-11-2 07:30):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
当我说用BST然后每次读一个数就重建BST的时候,面试官说你这个有点难要不要想其他办法。所以应该有其他思路。

补充内容 (2016-11-2 08:23):
这里有个BST用法,https://discuss.leetcode.com/top ... 9-82-of-submissions

评分

1

查看全部评分

cjyacmilan 发表于 2016-11-2 06:35:56 | 显示全部楼层
woca...他们家现在越来越严格了。。。。。
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-11-2 06:42:30 | 显示全部楼层
用tree怎么建heap呢?只想到用array implement
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-2 06:47:50 | 显示全部楼层
应该是实现两个BST吧? 每次remove最小的或者最大的元素。
回复 支持 反对

使用道具 举报

 楼主| ginues109 发表于 2016-11-2 06:52:22 | 显示全部楼层
小A要当码农 发表于 2016-11-2 06:47. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
应该是实现两个BST吧? 每次remove最小的或者最大的元素。

明确要求只能用一个Tree,不能两个

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-2 06:53:36 | 显示全部楼层
ginues109 发表于 2016-11-2 06:52. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
明确要求只能用一个Tree,不能两个
. visit 1point3acres.com for more.
。。。这样。就是类似于给一个Node类?二叉的嘛?

补充内容 (2016-11-2 06:55):
可是就算用Tree手动实现了Heap, 最后还是需要两个Heap啊,这样不算用到两个Tree了?
回复 支持 反对

使用道具 举报

神罗天征 发表于 2016-11-2 06:59:14 | 显示全部楼层
这还能怎么做……求大神解答
回复 支持 反对

使用道具 举报

 楼主| ginues109 发表于 2016-11-2 07:03:26 | 显示全部楼层
小A要当码农 发表于 2016-11-2 06:53. more info on 1point3acres.com
。。。这样。就是类似于给一个Node类?二叉的嘛?

补充内容 (2016-11-2 06:55):
. from: 1point3acres.com/bbs
意思就是不能按照two heaps的方法来做了,不要期待抛出原题了……

补充内容 (2016-11-2 07:05):
什么都不给,要实现什么自己从零写。我觉得BST是可行的,只不过是每一个数字进来都要重建BST很麻烦。但是这个方法他万一followup有重复数字怎么办就难搞了

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

huai10 发表于 2016-11-2 07:04:36 | 显示全部楼层
建2^32 个格子,然后一个一个数, 告诉他这是O(1), 因为全是constant....................................
回复 支持 反对

使用道具 举报

cjyacmilan 发表于 2016-11-2 07:12:29 | 显示全部楼层
huai10 发表于 2016-11-2 07:04
建2^32 个格子,然后一个一个数, 告诉他这是O(1), 因为全是constant....................................

66666666666666
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-2 07:13:26 | 显示全部楼层
ginues109 发表于 2016-11-2 07:03
意思就是不能按照two heaps的方法来做了,不要期待抛出原题了……

补充内容 (2016-11-2 07:05):
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
我觉得 可以造BST, 然后给这个Node类加三个attribute,leftsize, rightsize,  dup. 然后每次插入更新相应的值。 然后每次要找median可以从root开始根据leftsize和rightsize的差值找。
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-11-2 07:18:56 | 显示全部楼层
用bst,来一个插入一个,然后每次分奇偶查找第n/2 n/2+1大的数字,插入和查找复杂度 logn, worst case o(n), 如果想worst case还是logn,那只能rb tree或者avl tree...但rb tree和avl tree就算搞acm得人没有模板当场裸敲估计45分钟也很难写出来吧....
回复 支持 反对

使用道具 举报

忆梦前尘 发表于 2016-11-2 07:44:43 | 显示全部楼层
感觉这题用中文说。。。都没什么想法。。本来想的是root当做median,然后left subtree和right subtree分别当做两个heap,但好像不好做。。
回复 支持 反对

使用道具 举报

 楼主| ginues109 发表于 2016-11-2 11:08:11 | 显示全部楼层
wtcupup 发表于 2016-11-2 06:42
用tree怎么建heap呢?只想到用array implement

估计不是用tree来建heap这种方法了,我在一楼贴了可能的solution

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

zwcelesta 发表于 2016-11-2 11:49:29 | 显示全部楼层
维护一个binary search tree。不难啊。node多存一个左边有多少点,右边有多少点。平均是logn的操作。但是最坏是O(n)。
要保证logn的复杂度只能写balanced的了。可以看看avl。写四个操作,左旋,右旋,左右旋,右左旋。。。其实也还好。
不过出题者的意图肯定不是让你写一个avl tree(虽然是可以写的)
回复 支持 反对

使用道具 举报

304671127 发表于 2016-11-2 13:39:33 | 显示全部楼层
我自己写了个 放leetcode上跑过了,代码楼主贴出来的链接里的短一点,其实还可以改好看点,我写的实在太丑了。

public class MedianFinder {
           public static class TreeNode{
                int val;
                TreeNode left;
                TreeNode right;
                int t;
                TreeNode(int x){ this.val = x; this.t = 1;}
            }
            
            TreeNode root = null;
            int count = 0;
            
            public void add(int num){
                count++;
                . From 1point 3acres bbs
           root = insertNode(root, num);
            }
           public TreeNode insertNode(TreeNode root, int num) {
               if (root == null) {
                   return new TreeNode(num);
               }
               if (root.val > num) {
                   root.left = insertNode(root.left, num);
               } else {
                   root.right = insertNode(root.right, num);. 鍥磋鎴戜滑@1point 3 acres
               }
               root.t++;
               return root;
           }
            .鐣欏璁哄潧-涓浜-涓夊垎鍦
       public int find(int k){

           TreeNode cur = root;
           int rst = 0;
           while(cur != null){
               int l = 0;
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
               if(cur.left == null){
                   l = 0;
               }else{. 鍥磋鎴戜滑@1point 3 acres
                   l = cur.left.t;
               }
         if(cur.left != null && l >= k){
                   cur  = cur.left;
               }
               else if(cur.right != null && l < k - 1){
                   cur = cur.right;
                   k = k - 1 - l;
               }
               else{
                   rst = cur.val;
                   break;
               }
           }
           return rst;
       }
            
            public int size(){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                return count;. 1point3acres.com/bbs
            }
            // Adds a number into the data structure.
            public void addNum(int num) {
                this.add(num);
            }

            // Returns the median of current data stream
            public double findMedian() {
                int s = this.size();
                
                double rst = 0;
               
               if(s % 2 == 1){
                   rst =  this.find(s/2 + 1);
               }else{
                       int f1 = this.find(s/2);
                   int f2 =  this.find(s/2 + 1);
                   rst = (f1 + f2) /2.0;
               }
                return rst;
            }. 1point3acres.com/bbs
};
回复 支持 反对

使用道具 举报

31415926 发表于 2016-11-3 06:48:02 | 显示全部楼层
现在题那么难了。。 还能面吗。。
回复 支持 反对

使用道具 举报

slarkzz 发表于 2016-11-3 06:57:14 | 显示全部楼层
这个真是变态啊
回复 支持 反对

使用道具 举报

31415926 发表于 2016-11-3 07:39:34 | 显示全部楼层
查面经。。貌似原来出过 tree map 这样的题。看来,sc 还真会让人实现bst..
回复 支持 反对

使用道具 举报

keytion 发表于 2016-11-3 07:48:31 | 显示全部楼层
一定是binary tree吗?不是binary的话能想到很多solution.
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 01:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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