一亩三分地论坛

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

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

LinkedIn一面攒人品

[复制链接] |试试Instant~ |关注本帖
qshen1989 发表于 2014-8-1 01:37:36 | 显示全部楼层 |阅读模式

2014(7-9月) 码农类 硕士 全职@Linkedin - 网上海投 - 技术电面 |Pass

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

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

x
发个一面题攒人品,前几天面的,太紧张第二题没答好,没想到居然给过了~继续准备二面,顺便回报社会!
(1) Valid Number,说烂了的题,和Leetcode不同不用考虑指数,但面试官要求写出所有边界情况的test case,而且对代码clean这点要求很高. 1point3acres.com/bbs
(2) Valid Triangle,给个数组找三角形,超简单的其实,刷题刷傻了开始往3sum方向考虑了。。。其实更简单,只要求找一个就好. 鍥磋鎴戜滑@1point 3 acres

评分

3

查看全部评分

tiexiong 发表于 2014-8-1 05:36:16 | 显示全部楼层
Valid triangle 类似的是找到所有的Triangle,我的code是这样的,不知道是不是所有的case都cover了?
  1. /*
  2. Given an integer array, find all valid triangles.
  3. */

  4. import java.util.*;

  5. public class ValidTriangle {. 1point 3acres 璁哄潧
  6.     public static void main(String[] args) {
  7.         int[] test = {5, 2, 4, 8, 0};
  8.         System.out.println(findValidTriangle(test));. 1point3acres.com/bbs
  9.     }
  10.     . 1point3acres.com/bbs
  11.     public static ArrayList findValidTriangle(int[] A) {
  12.         if (A == null || A.length < 3)
  13.             return null;        

  14.         ArrayList res = new ArrayList();
  15.         
  16.         Arrays.sort(A);
  17.         
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  18.         for (int i = 0; i <= A.length - 3; i++) {
  19.             if (A[i] + A[i + 1] > A[i + 2]) {
  20.                 ArrayList temp = new ArrayList();
  21.                 temp.add(A[i]);
  22.                 temp.add(A[i + 1]);
  23.                 temp.add(A[i + 2]);
  24.                 res.add(temp);
  25.             }
  26.         }
  27.         return res;
  28.     }
  29. }
复制代码
回复 支持 反对

使用道具 举报

notbad 发表于 2014-8-1 09:17:45 | 显示全部楼层
不知道需不需要考虑包含0和负数的情况。
回复 支持 反对

使用道具 举报

readman 发表于 2014-8-1 09:20:07 | 显示全部楼层
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-8-1 09:30:43 | 显示全部楼层
tiexiong 发表于 2014-7-31 16:36
Valid triangle 类似的是找到所有的Triangle,我的code是这样的,不知道是不是所有的case都cover了?

很多情况没考虑到吧, 限定了i, i+1和i+2的位置关系, 如果i, i+2, i+5可以组成呢?
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-8-1 09:36:48 | 显示全部楼层
readman 发表于 2014-7-31 20:20
帮我也看看哈. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

. 鍥磋鎴戜滑@1point 3 acreshttps://gist.github.com/gaoyike/c6e4eef993a19f80b385
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
比楼上那个好, 但直觉你漏了一些情况, start ++ 和 end -- 你都绑定在一块了, 会不会存在end -- start不变, 或者start ++ end不变依旧能组成三角形的情况?

没仔细想counter cases.
回复 支持 反对

使用道具 举报

readman 发表于 2014-8-1 10:27:02 | 显示全部楼层
北美农民 发表于 2014-8-1 09:36
比楼上那个好, 但直觉你漏了一些情况, start ++ 和 end -- 你都绑定在一块了, 会不会存在end -- start ...

...我怎么感觉这题是npc... 这不是线性不等式可满足性么.....鏈枃鍘熷垱鑷1point3acres璁哄潧
假设数组为[1,2,3,....n], 满足几个个不等式的全部解集
回复 支持 反对

使用道具 举报

readman 发表于 2014-8-1 10:28:09 | 显示全部楼层
北美农民 发表于 2014-8-1 09:36
比楼上那个好, 但直觉你漏了一些情况, start ++ 和 end -- 你都绑定在一块了, 会不会存在end -- start ...

你看lz描述. 估计只让找一个..要找全部解就是npc了..
回复 支持 反对

使用道具 举报

tiexiong 发表于 2014-8-1 10:30:54 | 显示全部楼层
第一题需要怎样的clean程度呢? 我的能过leetcode,但是是补充了好几次才过的。如果要一次写完整还是挺难的。
  1. public class Solution {
  2.     public boolean isNumber(String s) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  3.         s = s.trim();
  4.         if (s == null || s.length() == 0)
  5.             return false;
  6. . visit 1point3acres.com for more.
  7.         if (s.length() == 1 && !Character.isDigit(s.charAt(0))) // Signal character, must be a digit.
  8.             return false;
  9.             . from: 1point3acres.com/bbs
  10.         if (!Character.isDigit(s.charAt(0)) && s.charAt(0) != '-' && s.charAt(0) != '.' && s.charAt(0) != '+') // ".3" is true, "+.8" is true.
  11.             return false;
  12.             
  13.         if (!Character.isDigit(s.charAt(s.length() - 1)) && s.charAt(s.length() - 1) != '.') // "3." is true.
  14.             return false;-google 1point3acres
  15.             
  16.         if ((s.charAt(0) == '.' || s.charAt(0) == '+' || s.charAt(0) == '-') && s.charAt(1) == 'e') // ".e1" is false.
  17.             return false;
  18.             
  19.         if (s.charAt(s.length() - 1) == '.' && !Character.isDigit(s.charAt(s.length() - 2))) // "1e." is false.
  20.             return false;. more info on 1point3acres.com

  21.         int dotCount = 0;
  22.         int eCount = 0;
  23.         int plusCount = 0;
  24.         int minusCount = 0;
  25.         if (s.charAt(0) == '.')
  26.             dotCount++;
  27.         if (s.charAt(0) == '+')
  28.             plusCount++;. from: 1point3acres.com/bbs
  29.         if (s.charAt(0) == '-')-google 1point3acres
  30.             minusCount++;

  31.         for (int i = 1; i < s.length(); i++) {
  32.             if (!Character.isDigit(s.charAt(i)) && s.charAt(i) != '.' && s.charAt(i) != 'e' && s.charAt(i) != '+' && s.charAt(i) != '-')
  33.                 return false;
  34.                
  35.             if (s.charAt(i) == '.')
  36.                 dotCount++;
  37.             if (s.charAt(i) == 'e')
  38.                 eCount++;
  39.             if (s.charAt(i) == '+')
  40.                 plusCount++;
  41.             if (s.charAt(i) == '-')
  42.                 minusCount++;
  43.             
  44.             if (plusCount == 1 && s.indexOf('+') != 0 && eCount == 0)
  45.                 return false;
  46.             if (minusCount == 1 && s.indexOf('-') != 0 && eCount == 0)
  47.                 return false;
  48.             if (dotCount == 1 && eCount == 1 && s.indexOf('.') > s.indexOf('e')) // "6e6.5" is false.
  49.                 return false;
  50.             if (dotCount > 1 || eCount > 1 || plusCount > 2 || minusCount > 2). from: 1point3acres.com/bbs
  51.                 return false;
  52.             
  53.         }
  54.         
  55.         return true;
  56.     }
  57. }
复制代码
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-8-1 10:31:01 | 显示全部楼层
readman 发表于 2014-7-31 21:27
...我怎么感觉这题是npc... 这不是线性不等式可满足性么....
假设数组为[1,2,3,....n], 满足几个个不等 ...

怎么可能是npc? 找3个数满足三角形的条件, 每个数都枚举n次也就n^3。
回复 支持 反对

使用道具 举报

readman 发表于 2014-8-1 10:59:58 | 显示全部楼层
北美农民 发表于 2014-8-1 10:31
怎么可能是npc? 找3个数满足三角形的条件, 每个数都枚举n次也就n^3。

https://gist.github.com/gaoyike/4b1ead516d705e7dc4f2

..确实会miss一些...

这次我满足的时候往前移动start, 不满足的时候都减少end.
因为感觉只要是不满足三角形, 不管是哪种情况(共三个不等式), 都可以通过减少end解决..

补充内容 (2014-8-1 11:02):
而且好想刚才miss了很多....
回复 支持 反对

使用道具 举报

shire1989 发表于 2014-8-1 11:46:08 | 显示全部楼层
你是new grad吗/
回复 支持 反对

使用道具 举报

readman 发表于 2014-8-1 11:49:43 | 显示全部楼层
北美农民 发表于 2014-8-1 10:31. from: 1point3acres.com/bbs
怎么可能是npc? 找3个数满足三角形的条件, 每个数都枚举n次也就n^3。

https://gist.github.com/gaoyike/26f738493ad5b72a4a77

补充内容 (2014-8-1 12:06):
两个都是枚举n3...感觉不能同时移动start和end. 所以复杂度下不来吧...
回复 支持 反对

使用道具 举报

 楼主| qshen1989 发表于 2014-8-1 15:02:27 | 显示全部楼层
第一题根据这个改一下:http://answer.ninechapter.com/solutions/valid-number/ 这个网站的答案大都很精练~. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第二题其实就考虑a<b<c,然后a+b>c就好了,排完序后a,b两重循环搞定,c始终是b后面那一个,不然肯定不满足╮(╯▽╰)╭
回12L,毕业半年了
回复 支持 反对

使用道具 举报

CTH 发表于 2014-8-1 15:08:38 | 显示全部楼层
请问楼主面的是new grad?
回复 支持 反对

使用道具 举报

 楼主| qshen1989 发表于 2014-8-1 15:39:56 | 显示全部楼层
CTH 发表于 2014-8-1 15:08
请问楼主面的是new grad?
. 鍥磋鎴戜滑@1point 3 acres
不是,Application,不过毕业一年内的貌似都能算new grad
回复 支持 反对

使用道具 举报

readman 发表于 2014-8-1 15:44:51 | 显示全部楼层
qshen1989 发表于 2014-8-1 15:02
第一题根据这个改一下:http://answer.ninechapter.com/solutions/valid-number/ 这个网站的答案大都很精练 ...

{1,2,3}中,{1,1,1} 等边三角形
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-8-1 21:21:54 | 显示全部楼层
readman 发表于 2014-7-31 22:49
https://gist.github.com/gaoyike/26f738493ad5b72a4a77
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2014-8-1 12:06):

然后可以发散一下, 如果要求解不相同, 怎么判断重复解。
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-8-1 21:25:51 | 显示全部楼层
qshen1989 发表于 2014-8-1 02:02 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第一题根据这个改一下:http://answer.ninechapter.com/solutions/valid-number/ 这个网站的答案大都很精练 ...

为啥c始终是b后面的一个? 必须找到c' 使得 a + b <= c', 这样 b 到 c' (开区间)之间的c都可以成为三角形吧?
回复 支持 反对

使用道具 举报

readman 发表于 2014-8-1 21:37:53 | 显示全部楼层
北美农民 发表于 2014-8-1 21:25
为啥c始终是b后面的一个? 必须找到c' 使得 a + b

https://gist.github.com/gaoyike/40df1e0ec5a6c95e0014

做出来了
如果{1,2,3} 中{1,1,1} 也是等边三角形. 以上为答案..(-  = 不是我想的..问别人的...)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 17:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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