一亩三分地论坛

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

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

LinkedIn一面攒人品

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

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

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

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

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

评分

3

查看全部评分

tiexiong 发表于 2014-8-1 05:36:16 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
Valid triangle 类似的是找到所有的Triangle,我的code是这样的,不知道是不是所有的case都cover了?
  1. /*
  2. Given an integer array, find all valid triangles.. visit 1point3acres.com for more.
  3. */
  4. . from: 1point3acres.com/bbs
  5. import java.util.*;
  6. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  7. public class ValidTriangle {
  8.     public static void main(String[] args) {
  9.         int[] test = {5, 2, 4, 8, 0};
  10.         System.out.println(findValidTriangle(test));
  11.     }
  12.    
  13.     public static ArrayList findValidTriangle(int[] A) {
  14.         if (A == null || A.length < 3)
  15.             return null;        

  16.         ArrayList res = new ArrayList();
  17.         . more info on 1point3acres.com
  18.         Arrays.sort(A);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  19.         . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  20.         for (int i = 0; i <= A.length - 3; i++) {
  21.             if (A[i] + A[i + 1] > A[i + 2]) {
  22.                 ArrayList temp = new ArrayList();. 鍥磋鎴戜滑@1point 3 acres
  23.                 temp.add(A[i]);
  24.                 temp.add(A[i + 1]);
  25.                 temp.add(A[i + 2]);. visit 1point3acres.com for more.
  26.                 res.add(temp);
  27.             }
  28.         }
  29.         return res;
  30.     }
  31. }. 1point3acres.com/bbs
复制代码
回复 支持 反对

使用道具 举报

notbad 发表于 2014-8-1 09:17:45 | 显示全部楼层
关注一亩三分地微博:
Warald
不知道需不需要考虑包含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可以组成呢?
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-8-1 09:36:48 | 显示全部楼层
readman 发表于 2014-7-31 20:20
帮我也看看哈

https://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... 这不是线性不等式可满足性么....
假设数组为[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. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  7.         if (s.length() == 1 && !Character.isDigit(s.charAt(0))) // Signal character, must be a digit.
  8.             return false;
  9.             
  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.             . more info on 1point3acres.com
  13.         if (!Character.isDigit(s.charAt(s.length() - 1)) && s.charAt(s.length() - 1) != '.') // "3." is true.
  14.             return false;
  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;
  21. -google 1point3acres
  22.         int dotCount = 0;
  23.         int eCount = 0;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  24.         int plusCount = 0;
  25.         int minusCount = 0;
  26.         if (s.charAt(0) == '.')
  27.             dotCount++;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  28.         if (s.charAt(0) == '+')
  29.             plusCount++;. 鍥磋鎴戜滑@1point 3 acres
  30.         if (s.charAt(0) == '-')
  31.             minusCount++;
  32. . 1point 3acres 璁哄潧
  33.         for (int i = 1; i < s.length(); i++) {
  34.             if (!Character.isDigit(s.charAt(i)) && s.charAt(i) != '.' && s.charAt(i) != 'e' && s.charAt(i) != '+' && s.charAt(i) != '-')
  35.                 return false;
  36.                
  37.             if (s.charAt(i) == '.')
  38.                 dotCount++;
  39.             if (s.charAt(i) == 'e')
  40.                 eCount++;
  41.             if (s.charAt(i) == '+')
  42.                 plusCount++;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  43.             if (s.charAt(i) == '-')
  44.                 minusCount++;
  45.             
  46.             if (plusCount == 1 && s.indexOf('+') != 0 && eCount == 0)
  47.                 return false;
  48.             if (minusCount == 1 && s.indexOf('-') != 0 && eCount == 0). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  49.                 return false;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  50.             if (dotCount == 1 && eCount == 1 && s.indexOf('.') > s.indexOf('e')) // "6e6.5" is false.
  51.                 return false;
  52.             if (dotCount > 1 || eCount > 1 || plusCount > 2 || minusCount > 2)
  53.                 return false;
  54.             
  55.         }. more info on 1point3acres.com
  56.         
  57.         return true;
  58.     }
  59. }
复制代码
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-8-1 10:31:01 | 显示全部楼层
readman 发表于 2014-7-31 21:27
...我怎么感觉这题是npc... 这不是线性不等式可满足性么..... Waral 鍗氬鏈夋洿澶氭枃绔,
假设数组为[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。
-google 1point3acres
https://gist.github.com/gaoyike/4b1ead516d705e7dc4f2

..确实会miss一些...

这次我满足的时候往前移动start, 不满足的时候都减少end.
因为感觉只要是不满足三角形, 不管是哪种情况(共三个不等式), 都可以通过减少end解决...鏈枃鍘熷垱鑷1point3acres璁哄潧

补充内容 (2014-8-1 11:02):.鏈枃鍘熷垱鑷1point3acres璁哄潧
而且好想刚才miss了很多....
回复 支持 反对

使用道具 举报

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

使用道具 举报

readman 发表于 2014-8-1 11:49:43 | 显示全部楼层
北美农民 发表于 2014-8-1 10:31
怎么可能是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?

不是,Application,不过毕业一年内的貌似都能算new grad
回复 支持 反对

使用道具 举报

readman 发表于 2014-8-1 15:44:51 | 显示全部楼层
qshen1989 发表于 2014-8-1 15:02.1point3acres缃
第一题根据这个改一下: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. visit 1point3acres.com for more.

补充内容 (2014-8-1 12:06):

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

使用道具 举报

北美农民 发表于 2014-8-1 21:25:51 | 显示全部楼层
qshen1989 发表于 2014-8-1 02:02
第一题根据这个改一下:http://answer.ninechapter.com/solutions/valid-number/ 这个网站的答案大都很精练 ...
. 鍥磋鎴戜滑@1point 3 acres
为啥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
. from: 1point3acres.com/bbs
做出来了
如果{1,2,3} 中{1,1,1} 也是等边三角形. 以上为答案..(-  = 不是我想的..问别人的...)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-30 15:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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