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


一亩三分地论坛

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

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

LinkedIn一面攒人品

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

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

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

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

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

评分

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 {
  6.     public static void main(String[] args) {
  7.         int[] test = {5, 2, 4, 8, 0};
  8.         System.out.println(findValidTriangle(test));
  9.     }
  10.    
  11.     public static ArrayList findValidTriangle(int[] A) {. 鍥磋鎴戜滑@1point 3 acres
  12.         if (A == null || A.length < 3)
  13.             return null;        

  14.         ArrayList res = new ArrayList();
  15.         
  16.         Arrays.sort(A);
  17.         
  18.         for (int i = 0; i <= A.length - 3; i++) {
  19.             if (A[i] + A[i + 1] > A[i + 2]) {. 鍥磋鎴戜滑@1point 3 acres
  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 | 显示全部楼层
帮我也看看哈
. from: 1point3acres.com/bbs
https://gist.github.com/gaoyike/c6e4eef993a19f80b385
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-8-1 09:30:43 | 显示全部楼层
tiexiong 发表于 2014-7-31 16:36. 1point 3acres 璁哄潧
Valid triangle 类似的是找到所有的Triangle,我的code是这样的,不知道是不是所有的case都cover了?
. From 1point 3acres bbs
很多情况没考虑到吧, 限定了i, i+1和i+2的位置关系, 如果i, i+2, i+5可以组成呢?
回复 支持 反对

使用道具 举报

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

https://gist.github.com/gaoyike/c6e4eef993a19f80b385

比楼上那个好, 但直觉你漏了一些情况, start ++ 和 end -- 你都绑定在一块了, 会不会存在end -- start不变, 或者start ++ end不变依旧能组成三角形的情况?. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
. Waral 鍗氬鏈夋洿澶氭枃绔,
没仔细想counter cases.
回复 支持 反对

使用道具 举报

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

...我怎么感觉这题是npc... 这不是线性不等式可满足性么....
假设数组为[1,2,3,....n], 满足几个个不等式的全部解集
回复 支持 反对

使用道具 举报

readman 发表于 2014-8-1 10:28:09 | 显示全部楼层
北美农民 发表于 2014-8-1 09:36.鏈枃鍘熷垱鑷1point3acres璁哄潧
比楼上那个好, 但直觉你漏了一些情况, 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) {. more info on 1point3acres.com
  3.         s = s.trim();
  4.         if (s == null || s.length() == 0)
  5.             return false;
  6. . more info on 1point3acres.com
  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.              鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  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.             .鏈枃鍘熷垱鑷1point3acres璁哄潧
  19.         if (s.charAt(s.length() - 1) == '.' && !Character.isDigit(s.charAt(s.length() - 2))) // "1e." is false.
  20.             return false;
  21. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  22.         int dotCount = 0;
  23.         int eCount = 0;
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  24.         int plusCount = 0;
  25.         int minusCount = 0;
  26.         if (s.charAt(0) == '.')
  27.             dotCount++;
  28.         if (s.charAt(0) == '+')
  29.             plusCount++;
  30.         if (s.charAt(0) == '-')
  31.             minusCount++;

  32.         for (int i = 1; i < s.length(); i++) {
  33.             if (!Character.isDigit(s.charAt(i)) && s.charAt(i) != '.' && s.charAt(i) != 'e' && s.charAt(i) != '+' && s.charAt(i) != '-')
  34.                 return false;
  35.                 . Waral 鍗氬鏈夋洿澶氭枃绔,
  36.             if (s.charAt(i) == '.')
  37.                 dotCount++;
  38.             if (s.charAt(i) == 'e'). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  39.                 eCount++;
  40.             if (s.charAt(i) == '+').鏈枃鍘熷垱鑷1point3acres璁哄潧
  41.                 plusCount++;
  42.             if (s.charAt(i) == '-')
  43.                 minusCount++;
  44.             
  45.             if (plusCount == 1 && s.indexOf('+') != 0 && eCount == 0)
  46.                 return false;
  47.             if (minusCount == 1 && s.indexOf('-') != 0 && eCount == 0)
  48.                 return false;
  49.             if (dotCount == 1 && eCount == 1 && s.indexOf('.') > s.indexOf('e')) // "6e6.5" is false.
  50.                 return false;
  51.             if (dotCount > 1 || eCount > 1 || plusCount > 2 || minusCount > 2)
  52.                 return false;
  53.             
  54.         }
  55.         
  56.         return true;
  57.     }
  58. }
复制代码
回复 支持 反对

使用道具 举报

北美农民 发表于 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):. From 1point 3acres bbs
而且好想刚才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?
. Waral 鍗氬鏈夋洿澶氭枃绔,
不是,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. From 1point 3acres bbs

补充内容 (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

. From 1point 3acres bbshttps://gist.github.com/gaoyike/40df1e0ec5a6c95e0014

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-19 08:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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