《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 415|回复: 15
收起左侧

口袋(PG)2, 3 面

[复制链接] |试试Instant~ |关注本帖
wto2184557 发表于 2017-11-9 08:54:01 | 显示全部楼层 |阅读模式

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

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

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

x
发一个这段时间的口袋2,3面吧。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

第二面:(三哥)
1. Sort 3 Colors, 颜色是用enum给出来的-google 1point3acres
2. follow Up: Sort 4 Colors
3. BST Inorder Successor -- No value, given parent
------------------以下非经典题-------------------
4.给定一个数组,随机抽取k个样本,要求保证每一次的k size的样本概率相同。   (shuffle,或者k - permutation). visit 1point3acres.com for more.
5.给定一个getMax()函数,能随机等可能生成0-Max -1的数,要求生成一个getIntRange(int range),可以等可能返回0 - range - 1之间的数。    (就是相当于给你random(bigNum) ,要你生成random(smallNum)). from: 1point3acres.com/bbs
6.reservoir sampling, 给定一个数据流,让你随机抽样k个元素,每个元素被抽到的概率是k/n。(思路就是reservoir sampling)

二面问了这么多题,都答上来了,结果只换回来一个三面。。。可怕。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷


第三面:(美国小哥? A开头的)
介绍了一下自己,让我介绍一下自己,说一下自己的简历,然后就上题了。
一道题:找到矩阵最左边的1

这道题在lc有类似的,也有思路。但是没有认真练过多遍,导致现场写的时候没有bug free。。。估计小哥看我写的太烂,都没问第二题。。估计就是挂在这一轮上的吧。

建议大家一定要吧面经多刷几遍才行,即便是自己有思路的题也是。千万不可大意。。

评分

4

查看全部评分

 楼主| wto2184557 发表于 2017-11-9 09:02:32 | 显示全部楼层
jiayi411 发表于 2017-11-9 09:01
2面都答上来还加面。。。

他家最近感觉都要三面,才有可能onsite
回复 支持 0 反对 1

使用道具 举报

 楼主| wto2184557 发表于 2017-11-9 08:54:39 | 显示全部楼层
另外求加米,谢谢~
回复 支持 反对

使用道具 举报

jiayi411 发表于 2017-11-9 09:01:18 | 显示全部楼层
2面都答上来还加面。。。
回复 支持 反对

使用道具 举报

KevinLuke 发表于 2017-11-10 02:26:26 | 显示全部楼层
求问楼主5的思路是什么呀?明天二面,多谢多谢!!
回复 支持 反对

使用道具 举报

 楼主| wto2184557 发表于 2017-11-10 03:01:33 | 显示全部楼层
KevinLuke 发表于 2017-11-10 02:26
求问楼主5的思路是什么呀?明天二面,多谢多谢!!

比如说,给定random7,能够随机生成0-6,让你生成random5,你就在random5里面不断call random7,当返回值小于5时就返回具体值,否则继续call random7
回复 支持 反对

使用道具 举报

KevinLuke 发表于 2017-11-10 04:17:30 | 显示全部楼层
wto2184557 发表于 2017-11-10 03:01
比如说,给定random7,能够随机生成0-6,让你生成random5,你就在random5里面不断call random7,当返回值 ...

哦哦,明白啦,多谢多谢!!祝offer多多
回复 支持 反对

使用道具 举报

nagisafight 发表于 2017-11-13 10:30:44 | 显示全部楼层
谢谢楼主。啥叫no value,given parent?????
回复 支持 反对

使用道具 举报

asd101200 发表于 2017-11-15 02:51:12 | 显示全部楼层
lz 4、5题可以分享下思路吗?谢啦
回复 支持 反对

使用道具 举报

asd101200 发表于 2017-11-15 06:52:38 | 显示全部楼层
把第五题的思路写下来了,麻烦lz看看,谢啦
int get_max_random(){
    //return a val from[0...max_number]-google 1point3acres
}
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
int getIntRange(int range){
    int t = get_max_random();
    while( t >= range){
        t = get_max_random();
    }
    return t;
}
回复 支持 反对

使用道具 举报

 楼主| wto2184557 发表于 2017-11-15 07:42:33 | 显示全部楼层
asd101200 发表于 2017-11-15 06:52 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
把第五题的思路写下来了,麻烦lz看看,谢啦
int get_max_random(){. from: 1point3acres.com/bbs
    //return a val from[0...max_num ...

对的,就是这样
回复 支持 反对

使用道具 举报

 楼主| wto2184557 发表于 2017-11-15 07:43:54 | 显示全部楼层
nagisafight 发表于 2017-11-13 10:30
谢谢楼主。啥叫no value,given parent?????

就是给你的是BST的节点,但是不知道节点中的具体值,不能通过value比较来判断。给了parent的reference。借助parent来找nextNode
回复 支持 反对

使用道具 举报

asd101200 发表于 2017-11-15 14:41:40 | 显示全部楼层
lz,三面的题我的思路是这样。 首先对第一行进行二分查找,找到最左边的1,记录此时的列值target。然后对第二行进行查找,此时先判断第二行第target列值是否为1,如果是,继续二分查找,得到新的列值target;如果不是开始查找第三行。思路就是对每一行进行二分查找,low永远是0,high要根据之前遍历列得到的最小target来决定。 时间复杂度应该是nlogn。你觉得这样对吗?
回复 支持 反对

使用道具 举报

 楼主| wto2184557 发表于 2017-11-16 02:53:10 | 显示全部楼层
asd101200 发表于 2017-11-15 14:41
lz,三面的题我的思路是这样。 首先对第一行进行二分查找,找到最左边的1,记录此时的列值target。然后对第 ...

nlogn思路可以,有更好的n+n的。这是lc 2D矩阵搜索II的 变体。你从第一行的最后一个数开始搜索就行啦。就是n+n的
回复 支持 反对

使用道具 举报

asd101200 发表于 2017-11-16 04:02:30 | 显示全部楼层
wto2184557 发表于 2017-11-16 02:53
nlogn思路可以,有更好的n+n的。这是lc 2D矩阵搜索II的 变体。你从第一行的最后一个数开始搜索就行啦。就 ...

好的,理解啦~还有这个题:. From 1point 3acres bbs
“给定一个数组,随机抽取k个样本,要求保证每一次的k size的样本概率相同。”
意思是给定一个数组,返回k个样本,每个样本是原数组的一个shuffle吗?
. Waral 鍗氬鏈夋洿澶氭枃绔,我的思路是,写一个shuffle函数,返回一个permutation,调用这个shuffle函数k次,是这样吗?
回复 支持 反对

使用道具 举报

ps2che 发表于 3 天前 | 显示全部楼层
求一下楼主的timeline
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-24 01:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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