一亩三分地论坛

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

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

zillow两轮电面面经

[复制链接] |试试Instant~ |关注本帖
jxyfwrj 发表于 2015-11-11 08:44:03 | 显示全部楼层 |阅读模式

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

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

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

x
刚面完二面,来把上次面的也补上,攒攒人品。。。

一面听口音是个华裔小哥,问的第一题是reverse words in a string, leetcode原题。我当时用没有额外空间的方法做了一下,小哥说你这个two pass能不能优化,果断说用栈。
第二题是地里有面经的,给你n个点,坐标(x,y,z),找一个点离其他点的距离之和是最小的。这个题地里面经的答案说是算xyz平均值然后取离这个最近的那个点,我一开始非常嗨皮的给了这个答案,结果面试官说你这个不对,然后要我写了个On2的解法做优化,我当时想了一会儿确实想不出来怎么优化,结果小哥说用全局变量存当前最小距离,如果当前距离和已经比最小距离小就直接看下一个点。。。 这个优化暂且不说,我想问下神通广大的一亩三分地ers, 这个题能有线性时间的解法吗?我问过我一个acm的同学,他说曼哈顿距离确实没有线性的。。。. From 1point 3acres bbs

二面是个美国大叔,上来第一个问题是java static关键字的意义并且拿例子问了下,第二个是给一个20*20的matrix,点代表通#号代表不通,从左上角走到右下角,能不能找到一条可行的路径。这里和lc里面path find不太一样,上下左右只要通的话都是可以走的,并且不是计算多少条路径,而是能不能至少有一条路径。其实还是蛮简单的用bfs即可,只是这里面试官不让用递归,说是数据量大容易栈溢出,于是要我用栈来实现,我中间写错一个小地方还是搞出来了,然后就问我要怎么给这个例子写单元测试,我以前根本没搞过这个,就说写一个随机生成通或者不通的map的生成器来测试,最后才知道他的意思是写用例的时候要按结果分类。。。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
求西雅图一游。。。

评分

1

查看全部评分

he2004365 发表于 2015-11-13 08:33:55 | 显示全部楼层
楼主你确定你BFS用的栈做的?不是DFS么?
回复 支持 反对

使用道具 举报

 楼主| jxyfwrj 发表于 2015-11-13 13:08:09 | 显示全部楼层
he2004365 发表于 2015-11-13 08:33
楼主你确定你BFS用的栈做的?不是DFS么?

噗。。。 打错了 dfs 。。。 不过这题dfs和bfs都能做是真的
回复 支持 反对

使用道具 举报

he2004365 发表于 2015-11-13 22:28:36 | 显示全部楼层
jxyfwrj 发表于 2015-11-13 13:08. 鍥磋鎴戜滑@1point 3 acres
噗。。。 打错了 dfs 。。。 不过这题dfs和bfs都能做是真的

那楼主,最后找最小距离坐标那个题,最优就是n^2了?感觉就是暴力啊~
回复 支持 反对

使用道具 举报

 楼主| jxyfwrj 发表于 2015-11-14 02:30:55 | 显示全部楼层
he2004365 发表于 2015-11-13 22:28
那楼主,最后找最小距离坐标那个题,最优就是n^2了?感觉就是暴力啊~
. from: 1point3acres.com/bbs
面试官说他暂时也想不到更好的方法。。
回复 支持 反对

使用道具 举报

ningchris 发表于 2015-11-30 11:53:56 | 显示全部楼层
还有一个优化的地方是
把当前的点和之后的点的距离存起来
这样之后就不用重复计算距离
回复 支持 反对

使用道具 举报

 楼主| jxyfwrj 发表于 2015-11-30 12:55:18 | 显示全部楼层
ningchris 发表于 2015-11-30 11:53
还有一个优化的地方是
把当前的点和之后的点的距离存起来
这样之后就不用重复计算距离

我提了这个优化 但其实杯水车薪。。 其实作用不大。。。
回复 支持 反对

使用道具 举报

Iancss 发表于 2015-12-30 15:47:24 | 显示全部楼层
Hi, 楼主,那个test case的 按结果分类是什么意思?是指测试例子要按照结果来划分吗?
回复 支持 反对

使用道具 举报

 楼主| jxyfwrj 发表于 2015-12-30 16:02:52 | 显示全部楼层
Iancss 发表于 2015-12-30 15:47
Hi, 楼主,那个test case的 按结果分类是什么意思?是指测试例子要按照结果来划分吗?

对 大概是这个意思
回复 支持 反对

使用道具 举报

Iancss 发表于 2015-12-31 10:57:59 | 显示全部楼层
LZ,那个N个点,寻找一点 距离和最小,有发现nlog(n)方法吗?
回复 支持 反对

使用道具 举报

 楼主| jxyfwrj 发表于 2015-12-31 11:59:22 | 显示全部楼层
Iancss 发表于 2015-12-31 10:57. 1point 3acres 璁哄潧
LZ,那个N个点,寻找一点 距离和最小,有发现nlog(n)方法吗?

不知道诶。。。没人回复我
回复 支持 反对

使用道具 举报

SophieCheng 发表于 2016-1-9 07:24:14 | 显示全部楼层
lz, n个点找距离最小的题目,刚开始提出的那个做法是O(N),为什么不对呢?
回复 支持 反对

使用道具 举报

 楼主| jxyfwrj 发表于 2016-1-9 10:27:07 | 显示全部楼层
面试官说欧几里得距离这么做不一定是最短 具体数学证明我就不知道了
回复 支持 反对

使用道具 举报

ningchris 发表于 2016-1-10 05:17:55 | 显示全部楼层
楼主后来有拿到zillow offer么?
回复 支持 反对

使用道具 举报

 楼主| jxyfwrj 发表于 2016-1-10 15:05:31 | 显示全部楼层
ningchris 发表于 2016-1-10 05:17
楼主后来有拿到zillow offer么?

木有 被拒了
回复 支持 反对

使用道具 举报

SophieCheng 发表于 2016-1-11 15:51:21 | 显示全部楼层
jxyfwrj 发表于 2016-1-9 10:27
面试官说欧几里得距离这么做不一定是最短 具体数学证明我就不知道了

额,有点疑问,这道题的距离定义是欧几里得距离,求平方和的根还是曼哈顿距离,求绝对值和的距离? 谢谢~
回复 支持 反对

使用道具 举报

SophieCheng 发表于 2016-1-11 15:51:31 | 显示全部楼层
jxyfwrj 发表于 2016-1-9 10:27
面试官说欧几里得距离这么做不一定是最短 具体数学证明我就不知道了

额,有点疑问,这道题的距离定义是欧几里得距离,求平方和的根还是曼哈顿距离,求绝对值和的距离? 谢谢~
回复 支持 反对

使用道具 举报

ningchris 发表于 2016-1-11 22:08:40 | 显示全部楼层
jxyfwrj 发表于 2016-1-10 15:05. 1point 3acres 璁哄潧
木有 被拒了

他们的bar真的很奇怪
回复 支持 反对

使用道具 举报

coolgod 发表于 2016-10-26 13:09:54 | 显示全部楼层
如果当前距离和已经比最小距离小就直接看下一个点。。。

这里有点不明白,为啥不是当前距离和比最小距离,就跳过这个点,计算下一个点吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 18:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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