买新车如何让dealer直接竞价?

一亩三分地论坛

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

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 2414|回复: 21
收起左侧

Facebook电面

[复制链接] |试试Instant~ |关注本帖
我的人缘0
cli94 发表于 2017-7-14 07:23:30 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

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

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

x
7.13的电面

扫雷地图,给一个地图的长和宽,以及雷的数量,要求返回一个让雷随机分布的grid,雷用-1表示,随机函数直接用random函数就行
. 留学申请论坛-一亩三分地
应该是像这样. 1point3acres

public int[][] getGrid(int H, int W, int M) {
    // 返回M个雷随机分布的地图
}

写完了代码问了complexity,我回答Space是O(H*W), Time on average是O(M) 前提是Sparse Grid, 如果是Dense Grid那Time Complexity 就是O(M^2) 或者O(M * W * H), 因为这个时候M基本上等于Grid的size

follow up: 如果一个位置没有雷,要求在没有雷的地方标出周围雷的数量,周围就是指上下左右对角线一共八个位置

我就写了一个遍历整个地图的function,面试官又问:如果是sparse grid该怎么样?当时很紧张,时间还剩5分钟没有答出来,然后就是问还有没有问题,我说没有就挂了电话。

挂了电话才想出来,如果是sparse grid可以把随机生成的雷的坐标保存在一个list里面,这样标雷数量的时候就只用遍历雷的坐标就可以了.留学论坛-一亩-三分地

我想可能是跪了

评分

参与人数 3大米 +13 收起 理由
dobbin + 5 感谢分享!
luckycat123 + 5 感谢分享!
2011051305 + 3 感谢分享!不好意思我权限只能加3个米。。

查看全部评分


上一篇:PocketGem 二面
下一篇:Wells fargo phone screen

本帖被以下淘专辑推荐:

我的人缘0
edyyy 发表于 2017-7-14 07:34:24 来自手机 | 显示全部楼层
  此人我要顶:
 
100% (4) 【我投】
  此人我要踩:
 
0% (0) 【我投】
这题明显比以往的题难。楼主答得很好了 加油
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| cli94 发表于 2017-7-14 07:45:15 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
edyyy 发表于 2017-7-14 07:34
这题明显比以往的题难。楼主答得很好了 加油

谢谢安慰啊 太紧张容易脑子短路
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| cli94 发表于 2017-7-14 08:07:50 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
我现在没有回复消息的权限 所以回答不了短消息
回复 支持 反对

使用道具 举报

我的人缘0
zephyryin 发表于 2017-7-14 08:11:33 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
这应该是用水塘抽样把,时间复杂度O(H*W)
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| cli94 发表于 2017-7-14 08:15:40 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
zephyryin 发表于 2017-7-14 08:11
这应该是用水塘抽样把,时间复杂度O(H*W)
. 留学申请论坛-一亩三分地
只是电面,我估计没有你说的这么复杂
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| cli94 发表于 2017-7-14 08:20:24 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
zephyryin 发表于 2017-7-14 08:11. 牛人云集,一亩三分地
这应该是用水塘抽样把,时间复杂度O(H*W)
. 牛人云集,一亩三分地
而且如果是sparse grid的话M很小复杂度只有O(M),水塘复杂度O(H*W)就有点不太好了吧
回复 支持 反对

使用道具 举报

我的人缘0
2011051305 发表于 2017-7-14 08:23:28 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
cli94 发表于 2017-7-14 08:07
我现在没有回复消息的权限 所以回答不了短消息

感谢楼主 我想问一下您是PhD的new grad么? 我以为fb的"fresh grad"ms及以下的head count好像还没开始呢?

还是说您的简历很多前端和mobile的project ?
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
zhuyinghua1203 发表于 2017-7-14 08:24:28 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
Time complexity 是不是应该永远是O(M)

生成雷的过程和生成随机数列的算法类似,每一次生成一个雷的时间是一样的?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| cli94 发表于 2017-7-14 08:27:44 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
2011051305 发表于 2017-7-14 08:23
感谢楼主 我想问一下您是PhD的new grad么? 我以为fb的"fresh grad"ms及以下的head count好像还没开始呢?
...

是吗?我不太清楚 我是本科毕业有两年工作经验 然后在读一个Online Master,所以我也不知道被分为哪种,recruiter是负责校招的
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| cli94 发表于 2017-7-14 08:33:38 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
zhuyinghua1203 发表于 2017-7-14 08:24
Time complexity 是不是应该永远是O(M)

生成雷的过程和生成随机数列的算法类似,每一次生成一个雷的时间 ...

我不太清楚,我写的就是用hashset记录之前雷的位置,如果hashset里面有这个数再生成一个新的。我说完complexity之后,面试官也没有让优化,估计写成这样就是可以了,然后就直接是followup了
回复 支持 反对

使用道具 举报

我的人缘0
zhuyinghua1203 发表于 2017-7-14 08:39:30 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
你这样dart throwing 的算法complexity 是会变高

如果格子是10*20的,雷的位置就是0, 1..., 199
把这个数列随机化,每O(1)可以得到一个数字,重复M次就是M个雷的位置
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| cli94 发表于 2017-7-14 08:43:07 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
zhuyinghua1203 发表于 2017-7-14 08:39
你这样dart throwing 的算法complexity 是会变高
.1point3acres网
如果格子是10*20的,雷的位置就是0, 1..., 199

可是生成0,1...199的过程Complexity是不是还是O(H*W)呢?
回复 支持 反对

使用道具 举报

我的人缘0
zhuyinghua1203 发表于 2017-7-14 08:45:49 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
试试用类似洗扑克牌的方法?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| cli94 发表于 2017-7-14 08:47:14 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
我写完了第一问的代码,然后面试官问完complexity,听面试官说话的感觉还算挺满意的,所以感觉用HashSet记录之前出现的雷就足够了
回复 支持 反对

使用道具 举报

我的人缘0
zhuyinghua1203 发表于 2017-7-14 08:47:41 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第一次生成一个0到199的随机数,那个位置的数字就是第一个雷的位置,然后把这个数和倒数第一个数字交换

第二次生成一个0到198的随机数,那个位置的数字就是第二个雷的位置,然后把这个数和倒数第二个数字交换

重复M次
回复 支持 反对

使用道具 举报

我的人缘0
forteller 发表于 2017-7-14 10:15:41 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
同意水塘抽样。
楼主投的是什么岗?能说一下吗?这边new grad都等这投/推呢~~谢谢啦
回复 支持 反对

使用道具 举报

我的人缘0
returning 发表于 2017-9-25 07:06:55 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
dense graph的话应该用resovir samping, 复杂度是H*W。
sparse的话估计有O(M)的做法,因为H*W>>M,所以直接生成M个0-H*W之间的随机数,应该就不会重复,当然可以hashset存一下,如果重复的话再生成一次。
回复 支持 反对

使用道具 举报

我的人缘0
张欣 发表于 2017-9-26 11:06:53 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
zhuyinghua1203 发表于 2017-7-14 08:47
第一次生成一个0到199的随机数,那个位置的数字就是第一个雷的位置,然后把这个数和倒数第一个数字交换
. 1point3acres
...
. 1point 3acres 论坛
请问这样的复杂度是o(m)吗
回复 支持 反对

使用道具 举报

我的人缘0
zhuyinghua1203 发表于 2017-9-26 13:13:16 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
张欣 发表于 2017-9-26 11:06
请问这样的复杂度是o(m)吗

. 留学申请论坛-一亩三分地
字数补丁
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-6-21 22:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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