一亩三分地论坛

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

snapchat一道错题

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

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

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

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

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。-google 1point3acres
譬如(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

查看全部评分

cooldogrj 发表于 2017-7-31 02:14:15 | 显示全部楼层
```
import java.util.*;. 1point3acres.com/bbs

public class completeSquare{
        public static List<List<Integer>> getCompleteSquares(int[] nums) {
                List<List<Integer>> res = new ArrayList<>();
                if(nums == null || nums.length < 3) return res;
. From 1point 3acres bbs
                Arrays.sort(nums);. Waral 鍗氬鏈夋洿澶氭枃绔,
                //[1,2,3,4,5,6,7,8,9,10];
                //a^ + b^ = c^
                for(int i = nums.length - 1; i >= 2; i--) {.1point3acres缃
                        if(i != nums.length - 1 && nums[i] == nums[i+1]) continue;
                        int left = 0, right = i - 1;
                        while(left < right) {. more info on 1point3acres.com
                                int sum = nums[left] * nums[left] + nums[right] * nums[right];
                                if(sum < nums[i] * nums[i]) {
                                        left++;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                                }else if(sum > nums[i] * nums[i]) {
                                        right--;.鏈枃鍘熷垱鑷1point3acres璁哄潧
                                }else{
                                        List<Integer> path = new ArrayList<>();
                                        path.add(nums[left]);-google 1point3acres
                                        path.add(nums[right]);
                                        path.add(nums[i]);
                                        res.add(path);
                                        left++;
                                        right--;
                                        while(nums[left] == nums[left-1]) left++;
                                        while(nums[right] == nums[right+1]) right--;
                                }
                        }
                }

                return res;
        }

        public static void main(String[] args) {
                int[] nums = {1,1,2,2,3,3,4,4,5,6,7,8,8,9,10,10};
                System.out.println(getCompleteSquares(nums));
        }. From 1point 3acres bbs
}. Waral 鍗氬鏈夋洿澶氭枃绔,
```

就是 3sum嘛。
回复 支持 1 反对 0

使用道具 举报

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

使用道具 举报

bitzyq 发表于 2017-7-8 02:20:16 | 显示全部楼层
这个数组都是正数吗。。。如果abc都是正数的话,c肯定是最大的,数组排序后是不是可以倒着找c?ab肯定在c之前的那段数组里面,然后假设a是开头,b是结尾,然后用逼近的方法看有没有解?这样应该是O(n^2)。
. 鍥磋鎴戜滑@1point 3 acres
不都是正数的话应该要先建一个平方值构成的数组再找吧。
回复 支持 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-12-15 22:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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