求问有什么站立式办公桌推荐?

一亩三分地论坛

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

最近看过此主题的会员

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

snapchat一道错题

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

2017(7-9月) 码农类General 本科 全职@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。
譬如(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 进行判断。-google 1point3acres
所以这个解法是错的。不知道大家有什么想法。但很显然,面试官没有发现这个错,否则在写之前就应该否定。. 一亩-三分-地,独家发布

评分

参与人数 1大米 +30 收起 理由
candy_shmily + 30

查看全部评分


上一篇:亚麻电面
下一篇:狗狗加面
我的人缘0
cooldogrj 发表于 2017-7-31 02:14:15 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
```. 一亩-三分-地,独家发布
import java.util.*;

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;

                Arrays.sort(nums);
                //[1,2,3,4,5,6,7,8,9,10];
                //a^ + b^ = c^
                for(int i = nums.length - 1; i >= 2; i--) {. 留学申请论坛-一亩三分地
                        if(i != nums.length - 1 && nums[i] == nums[i+1]) continue; 来源一亩.三分地论坛.
                        int left = 0, right = i - 1;
                        while(left < right) {
                                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--;. 一亩-三分-地,独家发布
                                }else{
                                        List<Integer> path = new ArrayList<>();
                                        path.add(nums[left]);
.1point3acres网                                        path.add(nums[right]);. Waral 博客有更多文章,
                                        path.add(nums[i]);
                                        res.add(path);. visit 1point3acres for more.
                                        left++;
                                        right--;-google 1point3acres
                                        while(nums[left] == nums[left-1]) left++;
                                        while(nums[right] == nums[right+1]) right--;
                                }
                        }-google 1point3acres
                }

                return res;
        }

        public static void main(String[] args) {. visit 1point3acres for more.
                int[] nums = {1,1,2,2,3,3,4,4,5,6,7,8,8,9,10,10};
                System.out.println(getCompleteSquares(nums));
        }.1point3acres网
}. 一亩-三分-地,独家发布
```

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

使用道具 举报

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

使用道具 举报

我的人缘0
bitzyq 发表于 2017-7-8 02:20:16 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
这个数组都是正数吗。。。如果abc都是正数的话,c肯定是最大的,数组排序后是不是可以倒着找c?ab肯定在c之前的那段数组里面,然后假设a是开头,b是结尾,然后用逼近的方法看有没有解?这样应该是O(n^2)。

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

使用道具 举报

我的人缘0
 楼主| ThinkDeeper2 发表于 2017-7-8 02:24:53 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
bitzyq 发表于 2017-7-8 02:20
这个数组都是正数吗。。。如果abc都是正数的话,c肯定是最大的,数组排序后是不是可以倒着找c?ab肯定在c之 ...

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

使用道具 举报

我的人缘0
dukecat0613 发表于 2017-7-8 03:00:27 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
bitzyq 发表于 2017-7-8 02:20
这个数组都是正数吗。。。如果abc都是正数的话,c肯定是最大的,数组排序后是不是可以倒着找c?ab肯定在c之 ...

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

使用道具 举报

我的人缘0
asdfyou6 发表于 2017-7-8 03:16:12 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
这个题还使用3sum吧 采用 hashmap 只是多一些考虑的条件而已 比如 选出来的 3个数 是xyz xzy zxy 3种情况 以及相应的去重
回复 支持 反对

使用道具 举报

我的人缘0
byrlhb 发表于 2017-7-9 22:49:34 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
就是有负数也没有关系,把每个值的平方算一下重新排个序就好了
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
justin 发表于 2017-7-11 11:14:19 | 显示全部楼层
  此人我要顶:
 
100% (3) 【我投】
  此人我要踩:
 
0% (0) 【我投】
asdfyou6 发表于 2017-7-7 14:16
这个题还使用3sum吧 采用 hashmap 只是多一些考虑的条件而已 比如 选出来的 3个数 是xyz xzy zxy 3种情况  ...

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

使用道具 举报

游客
请先登录

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-6-18 06:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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