[八我司] 半导体公司工作5年以上谈谈感想

一亩三分地论坛

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

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业诚聘
机器学习/数据统计/教育等职位
码农求职神器Triplebyte:
不用海投
内推多家公司面试
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
锦晖律师事务所
12月16日
H1B讲座通知
查看: 4858|回复: 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构建一万遍。
对不起面馆对
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
-82-of-submissions" target="_blank">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)   【踩】
全局: 顶  98% (50)
 
 
1% (1)  踩
huai10 发表于 2016-11-2 07:04
建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{
                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++;
                
           root = insertNode(root, num);
            }
           public TreeNode insertNode(TreeNode root, int num) {. 1point3acres
               if (root == null) {
                   return new TreeNode(num);
               }
               if (root.val > num) {
                   root.left = insertNode(root.left, num);
               } else {
                   root.right = insertNode(root.right, num);
               }
               root.t++;
               return root;
           }
            . From 1point 3acres bbs
       public int find(int k){

           TreeNode cur = root;
           int rst = 0;
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
ndMedian() {
                int s = this.size();
                
                double rst = 0;. 1point3acres
               
               if(s % 2 == 1){
                   rst =  this.find(s/2 + 1);
               }else{
                       int f1 = this.find(s/2);
                   int f2 =  this.find(s/2 + 1);. check 1point3acres for more.
                   rst = (f1 + f2) /2.0;
               }
                return rst;
            }. From 1point 3acres bbs
};
回复

使用道具 举报

我的人缘0
cjyacmilan 发表于 2016-11-2 06:35:56 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (20)
 
 
9% (2)  踩
woca...他们家现
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
。。。。
回复

使用道具 举报

我的人缘0
wtcupup 发表于 2016-11-2 06:42:30 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  61% (397)
 
 
38% (249)  踩
用tree怎么建heap呢?
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
ement
回复

使用道具 举报

我的人缘0
小A要当码农 发表于 2016-11-2 06:47:50 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (52)
 
 
7% (4)  踩
应该是实现两个BST吧?
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
大的元素。
回复

使用道具 举报

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

明确要求只能用一个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了?
回复

使用道具 举报

我的人缘0
神罗天征 发表于 2016-11-2 06:59:14 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (532)
 
 
2% (16)  踩
这还能怎么
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
解答

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


回复

使用道具 举报

我的人缘0
 楼主| ginues109 发表于 2016-11-2 07:03:26 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (41)
 
 
2% (1)  踩
小A要当码农 发表于 2016-11-2 06:53
。。。这样。就是类似于给一个Node类?二叉的嘛?
. check 1point3acres for more.
补充内容 (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)   【踩】
全局: 顶  93% (27)
 
 
6% (2)  踩
建2^32 个格子,然后一个一个数, 告诉他这是O(1), 因为
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
............
回复

使用道具 举报

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

66666666666666
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

手机版|小黑屋|一亩三分地留学网

GMT+8, 2018-12-14 13:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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