一亩三分地论坛

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

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

Snapchat 电面面经 求讨论!

[复制链接] |试试Instant~ |关注本帖
waye_tt 发表于 2016-5-2 07:56:29 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Snapchat - 网上海投 - 技术电面 |Other在职跳槽

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

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

x
上周电面snachat, 来地里保面经顺便求followup问题的讨论。。。上题:

array里只有一个数字出现超过50%,其他都只有一次。1. return超过50%次的数字。 follow up: array里只有一个数字出现超过一次,其他都只有一次。返回超过超过一次的数字的出现概率。要求:constant space, time: O(n).

follow up 到现在还没想明白,求地里大牛们指导~~



. visit 1point3acres.com for more.

评分

1

查看全部评分

billb 发表于 2016-5-2 08:46:34 | 显示全部楼层
是不是那个投票算法啊
回复 支持 反对

使用道具 举报

randrand1 发表于 2016-5-2 09:11:20 | 显示全部楼层
follow up里面会不会有额外的条件?比如数字的range
回复 支持 反对

使用道具 举报

waikai 发表于 2016-5-2 10:00:51 | 显示全部楼层
这follow up 我连读 都没读明白。。“超过超过一次”什么意思呀
回复 支持 反对

使用道具 举报

tldxk 发表于 2016-5-2 10:07:58 | 显示全部楼层
同问是否有其他条件
回复 支持 反对

使用道具 举报

 楼主| waye_tt 发表于 2016-5-2 11:12:26 | 显示全部楼层
一起回复一下哈
第一问:array里只有一个数字出现超过50%,其他数字都只有一次 return超过50%次的数字。
譬如: [1,2,3,4,1,1,5,1,1] 除了 1别的数字都只出现了一次,而且1出现概率超过了50%, return 1 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

followup:  array里只有一个数字出现超过一次,其他数字都只有一次。return这个数字的出现概率。
譬如: [1,2,3,4,1,1,5] 在这个数组里 1就不一定是出现概率超过50%的数了,求1的出现概率。
回复 支持 反对

使用道具 举报

 楼主| waye_tt 发表于 2016-5-2 11:13:15 | 显示全部楼层
Followup 要求space O(1) time O(n)
回复 支持 反对

使用道具 举报

 楼主| waye_tt 发表于 2016-5-2 11:14:02 | 显示全部楼层
waikai 发表于 2016-5-2 10:00
这follow up 我连读 都没读明白。。“超过超过一次”什么意思呀

[1, 2, 3, 1, 4] 譬如这个数组,除了1别的数字都是出现一次的
回复 支持 反对

使用道具 举报

 楼主| waye_tt 发表于 2016-5-2 11:14:33 | 显示全部楼层
tldxk 发表于 2016-5-2 10:07
同问是否有其他条件

除了一个数其余数都只出现一次 这样
回复 支持 反对

使用道具 举报

忆梦前尘 发表于 2016-5-2 11:43:16 | 显示全部楼层
感觉思路可能是bucket sorting,先扫一遍数组拿到最大值和最小值,比如{1,2,3,1,4},最大值是4,最小值是1.

然后有n-2个数字,说明有n-1个区间,就是{1,2,3,1,4}中,有5个数字,就是四个间隔,(像五根手指的四条缝),用(4-1)/4 拿到四个区间的范围。. 1point 3acres 璁哄潧

这样的话,1-1.75里面就是两个数字,1.75-2.5是一个数字,2.5-3.25是1个数字,3.25-4是1个数字。

说明1-1.75里面有重复,那么这个唯一多余1次的数字,就是1.. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

有点儿类似maximum gap,(leetcode第164题),可能是我想复杂了,而且空间复杂度不太符合要求。
回复 支持 反对

使用道具 举报

kemeng1314 发表于 2016-5-2 13:09:57 | 显示全部楼层
这个题和他们intern 有个电面题一样
回复 支持 反对

使用道具 举报

forteller 发表于 2016-5-2 13:49:36 | 显示全部楼层
waikai 发表于 2016-5-2 10:00
这follow up 我连读 都没读明白。。“超过超过一次”什么意思呀

别钻牛角尖啊 朋友
回复 支持 反对

使用道具 举报

menderr 发表于 2016-5-2 14:12:59 | 显示全部楼层
第一题就是majority number 原题

第二题不是太理解,什么叫返回概率
回复 支持 反对

使用道具 举报

Yoyo00 发表于 2016-5-2 14:16:32 | 显示全部楼层
menderr 发表于 2016-5-2 14:12
第一题就是majority number 原题

第二题不是太理解,什么叫返回概率

majority element. 第二题也是majority element,因为这个数字肯定是频率最高的,别的都是一次。返回出现的概率?扫一遍找到这个elelment,扫第二遍找到出现的次数count,然后 count/size?

补充内容 (2016-5-2 14:32):
之前的回复好像不对,请忽略。
回复 支持 反对

使用道具 举报

 楼主| waye_tt 发表于 2016-5-2 15:42:48 | 显示全部楼层
Yoyo00 发表于 2016-5-2 14:16
majority element. 第二题也是majority element,因为这个数字肯定是频率最高的,别的都是一次。返回出现 ...

followup部分 如果这个数出现的比较分散就不行诶 譬如 [1, 3, 6, 1, 2, 10, 9, 1] 这样找1 投票是投不出来的诶~~
回复 支持 反对

使用道具 举报

kemeng1314 发表于 2016-5-2 15:50:37 | 显示全部楼层
waye_tt 发表于 2016-5-2 15:42
followup部分 如果这个数出现的比较分散就不行诶 譬如 [1, 3, 6, 1, 2, 10, 9, 1] 这样找1 投票是投不出 ...
-google 1point3acres
请问楼主电面主要时间都是coding吗,还有注重其他考量的内容吗?谢谢!
回复 支持 反对

使用道具 举报

 楼主| waye_tt 发表于 2016-5-2 15:55:24 | 显示全部楼层
kemeng1314 发表于 2016-5-2 15:50
请问楼主电面主要时间都是coding吗,还有注重其他考量的内容吗?谢谢!

对啊 就是很常规的电面 上来互相介绍一下 然后做题 最后再让你问他一些问题 但是是用的google hangout
回复 支持 反对

使用道具 举报

kemeng1314 发表于 2016-5-2 16:40:59 | 显示全部楼层
就一个题是吧,那现在有后续消息了吗
回复 支持 反对

使用道具 举报

xbbjames1 发表于 2016-5-2 18:01:52 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

ericlee27 发表于 2016-10-3 10:48:43 | 显示全部楼层
waye_tt 发表于 2016-5-2 15:42
followup部分 如果这个数出现的比较分散就不行诶 譬如 [1, 3, 6, 1, 2, 10, 9, 1] 这样找1 投票是投不出 ...

楼主第二题我还是没看明白,找题目描述扫两遍数组不就知道出现的概率了吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 07:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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