废柴的我该如何谈恋爱?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 4705|回复: 25
收起左侧

SnapChat电面跪经

[复制链接] |试试Instant~
我的人缘0
ginues109 发表于 2016-11-2 06:32:55 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (41)
 
 
2% (1)  踩

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

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

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

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


补充内容 (2016-11-2 07:22):. 1point 3acres 论坛
只能用一个Tree,所以two heaps的方法是不行的

补充内容 (2016-11-2 07:30):
当我说用BST然后每次读一个数就重建BST的时候,面试官说你这个有点难要不要想其他办法。所以应该有其他思路。

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

评分

参与人数 1大米 +10 收起 理由
忆梦前尘 + 10 感谢分享!

查看全部评分


上一篇:11月首发 Google电面
下一篇:狗家店面

本帖被以下淘专辑推荐:

我的人缘0
liurudahai 发表于 2016-11-14 08:27:02 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  97% (47)
 
 
2% (1)  踩
huai10 发表于 2016-11-2 07:04.本文原创自1point3acres论坛
建2^32 个格子,然后一个一个数, 告诉他这是O(1), 因为全是constant....................................

感觉就用BST吧,不用重建树,每个NODE保存一个他左子树节点的个数,全局保存一个总节点个数,每次找到一半的那个节点就行,CC150第五版有个类似的题
回复

使用道具 举报

我的人缘0
304671127 发表于 2016-11-2 13:39:33 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  93% (14)
 
 
6% (1)  踩
我自己写了个 放leetcode上跑过了,代码楼主贴出来的链接里的短一点,其实还可以改好看点,我写的实在太丑了。

public class MedianFinder {
           public static class TreeNode{. From 1point 3acres bbs
                int val;.本文原创自1point3acres论坛
                TreeNode left;
                TreeNode right;. 1point3acres
                int t;
                TreeNode(int x){ this.val = x; this.t = 1;}. 1point3acres
            }
            -google 1point3acres
            TreeNode root = null;
            int count = 0;
            
            public void add(int num){
                count++;.留学论坛-一亩-三分地
                . 围观我们@1point 3 acres
           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 {. 围观我们@1point 3 acres
                   root.right = insertNode(root.right, num);
               }
               root.t++;
               return root;. 1point3acres
           }
            . From 1point 3acres bbs
       public int find(int k){

           TreeNode cur = root;. 1point 3acres 论坛
           int rst = 0;
           while(cur != null){
               int l = 0;

               if(cur.left == null){. from: 1point3acres
                   l = 0;
               }else{
                   l = cur.left.t;
               }
         if(cur.left != null && l >= k){ 来源一亩.三分地论坛.
                   cur  = cur.left;
               }
               else if(cur.right != null && l < k - 1){
                   cur = cur.right;. from: 1point3acres
                   k = k - 1 - l;. 1point3acres
               }
               else{
                   rst = cur.val;
                   break;
               }
           }
           return rst;
       }
            
            public int size(){
                return count;
            }
            // Adds a number into the data structure.
            public void addNum(int num) {
                this.add(num);
            } 来源一亩.三分地论坛.
. 围观我们@1point 3 acres
            // 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);. visit 1point3acres for more.
               }else{
                       int f1 = this.find(s/2);
                   int f2 =  this.find(s/2 + 1);
                   rst = (f1 + f2) /2.0;
               }
                return rst;
            }. from: 1point3acres
};
回复

使用道具 举报

我的人缘0
cjyacmilan 发表于 2016-11-2 06:35:56 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (16)
 
 
11% (2)  踩
woca...他们家现在越来越严格了。。。。。
回复

使用道具 举报

我的人缘0
wtcupup 发表于 2016-11-2 06:42:30 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  61% (346)
 
 
38% (215)  踩
用tree怎么建heap呢?只想到用array implement

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
小A要当码农 发表于 2016-11-2 06:47:50 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (52)
 
 
7% (4)  踩
应该是实现两个BST吧? 每次remove最小的或者最大的元素。
回复

使用道具 举报

我的人缘0
 楼主| ginues109 发表于 2016-11-2 06:52:22 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (41)
 
 
2% (1)  踩
小A要当码农 发表于 2016-11-2 06:47
应该是实现两个BST吧? 每次remove最小的或者最大的元素。
. From 1point 3acres bbs
明确要求只能用一个Tree,不能两个

评分

参与人数 1大米 +10 收起 理由
忆梦前尘 + 10 感谢分享!

查看全部评分

回复

使用道具 举报

我的人缘0
小A要当码农 发表于 2016-11-2 06:53:36 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (52)
 
 
7% (4)  踩
ginues109 发表于 2016-11-2 06:52
明确要求只能用一个Tree,不能两个

。。。这样。就是类似于给一个Node类?二叉的嘛? . 一亩-三分-地,独家发布

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

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.

回复

使用道具 举报

我的人缘0
神罗天征 发表于 2016-11-2 06:59:14 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (525)
 
 
2% (16)  踩
这还能怎么做……求大神解答
回复

使用道具 举报

我的人缘0
 楼主| ginues109 发表于 2016-11-2 07:03:26 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (41)
 
 
2% (1)  踩
小A要当码农 发表于 2016-11-2 06:53. 留学申请论坛-一亩三分地
。。。这样。就是类似于给一个Node类?二叉的嘛?

补充内容 (2016-11-2 06:55):

意思就是不能按照two heaps的方法来做了,不要期待抛出原题了……

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

评分

参与人数 1大米 +10 收起 理由
忆梦前尘 + 10 感谢分享!

查看全部评分

回复

使用道具 举报

我的人缘0
huai10 发表于 2016-11-2 07:04:36 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (26)
 
 
7% (2)  踩
建2^32 个格子,然后一个一个数, 告诉他这是O(1), 因为全是constant....................................

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
cjyacmilan 发表于 2016-11-2 07:12:29 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (16)
 
 
11% (2)  踩
huai10 发表于 2016-11-2 07:04. from: 1point3acres
建2^32 个格子,然后一个一个数, 告诉他这是O(1), 因为全是constant....................................
. 一亩-三分-地,独家发布
66666666666666
回复

使用道具 举报

我的人缘0
小A要当码农 发表于 2016-11-2 07:13:26 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (52)
 
 
7% (4)  踩
ginues109 发表于 2016-11-2 07:03
意思就是不能按照two heaps的方法来做了,不要期待抛出原题了……

补充内容 (2016-11-2 07:05):

我觉得 可以造BST, 然后给这个Node类加三个attribute,leftsize, rightsize,  dup. 然后每次插入更新相应的值。 然后每次要找median可以从root开始根据leftsize和rightsize的差值找。
回复

使用道具 举报

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

使用道具 举报

我的人缘0
忆梦前尘 发表于 2016-11-2 07:44:43 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (1099)
 
 
3% (36)  踩
感觉这题用中文说。。。都没什么想法。。本来想的是root当做median,然后left subtree和right subtree分别当做两个heap,但好像不好做。。
回复

使用道具 举报

我的人缘0
 楼主| ginues109 发表于 2016-11-2 11:08:11 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (41)
 
 
2% (1)  踩
wtcupup 发表于 2016-11-2 06:42
用tree怎么建heap呢?只想到用array implement

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

评分

参与人数 1大米 +10 收起 理由
忆梦前尘 + 10 感谢分享!

查看全部评分

回复

使用道具 举报

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

使用道具 举报

我的人缘0
31415926 发表于 2016-11-3 06:48:02 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
现在题那么难了。。 还能面吗。。
回复

使用道具 举报

我的人缘0
slarkzz 发表于 2016-11-3 06:57:14 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (31)
 
 
11% (4)  踩
这个真是变态啊
回复

使用道具 举报

我的人缘0
31415926 发表于 2016-11-3 07:39:34 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
查面经。。貌似原来出过 tree map 这样的题。看来,sc 还真会让人实现bst... 留学申请论坛-一亩三分地
回复

使用道具 举报

我的人缘0
keytion 发表于 2016-11-3 07:48:31 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (25)
 
 
0% (0)  踩
一定是binary tree吗?不是binary的话能想到很多solution.
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地论坛声明

GMT+8, 2018-9-21 16:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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