推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 476|回复: 7
收起左侧

snapchat一道错题

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

2017(7-9月) 码农类 本科 全职@Snapchat - 内推 - 其他 |Fail在职跳槽

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

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

x
seattle电面,已跪。遇到了一道题,在提示下提出了一种错误的解法。上来分享一下。题目是给出一个数组,输出符合a^2+b^2=c^2 的(a,b,c)组合。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
brute force很简单,三个for循环, O(n^3). 要求优化,提出了用3sum的想法去解,然后让写code。写完了之后,讨论了一些edge case, 然后挂了。
问题在于,3sum 的思想不适用于这里, 这个问题是a^2+b^2 -c^2 =0, 而不是a^2+b^2 +c^2 =0。
譬如(x, y, z, t) 选中 x, 然后 x^2 + y^2 < t^2, 这时既可以选择x^2 +z^2 和 t^2比较,也可以选择x^2 + y^2 和 z^2比较。假如是3sum, x + y +t <0, 只能是选择x + z+t 进行判断。
所以这个解法是错的。不知道大家有什么想法。但很显然,面试官没有发现这个错,否则在写之前就应该否定。

评分

1

查看全部评分

cynthiazp 发表于 2017-7-8 02:32:26 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
其实这是个数学题,跟算法没多大关系。优化的方法应该是找出 3 4 5, 5 12 13这类基础勾股数,然后他们的倍数也是勾股数。
楼主看这里: http://bbs.csdn.net/topics/320021598
回复 支持 1 反对 0

使用道具 举报

bitzyq 发表于 2017-7-8 02:20:16 | 显示全部楼层
关注一亩三分地微博:
Warald
这个数组都是正数吗。。。如果abc都是正数的话,c肯定是最大的,数组排序后是不是可以倒着找c?ab肯定在c之前的那段数组里面,然后假设a是开头,b是结尾,然后用逼近的方法看有没有解?这样应该是O(n^2)。

不都是正数的话应该要先建一个平方值构成的数组再找吧。
回复 支持 1 反对 0

使用道具 举报

 楼主| ThinkDeeper2 发表于 2017-7-8 02:24:53 | 显示全部楼层
bitzyq 发表于 2017-7-8 02:20
这个数组都是正数吗。。。如果abc都是正数的话,c肯定是最大的,数组排序后是不是可以倒着找c?ab肯定在c之 ...

正解。那是我的想法错了。
回复 支持 反对

使用道具 举报

dukecat0613 发表于 2017-7-8 03:00:27 | 显示全部楼层
bitzyq 发表于 2017-7-8 02:20
这个数组都是正数吗。。。如果abc都是正数的话,c肯定是最大的,数组排序后是不是可以倒着找c?ab肯定在c之 ...

正解 on2 判断第三个数是不是完全平方数就ok 了
回复 支持 反对

使用道具 举报

asdfyou6 发表于 2017-7-8 03:16:12 | 显示全部楼层
这个题还使用3sum吧 采用 hashmap 只是多一些考虑的条件而已 比如 选出来的 3个数 是xyz xzy zxy 3种情况 以及相应的去重
回复 支持 反对

使用道具 举报

byrlhb 发表于 2017-7-9 22:49:34 | 显示全部楼层
就是有负数也没有关系,把每个值的平方算一下重新排个序就好了
回复 支持 反对

使用道具 举报

justin 发表于 2017-7-11 11:14:19 | 显示全部楼层
asdfyou6 发表于 2017-7-7 14:16
这个题还使用3sum吧 采用 hashmap 只是多一些考虑的条件而已 比如 选出来的 3个数 是xyz xzy zxy 3种情况  ...

我觉得这个才是正解。去重的情况通过排序就可以解决了。排序之后再扫描的时候,跳过相邻相同的数。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-25 07:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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