一亩三分地论坛

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

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

Zenefits电面

[复制链接] |试试Instant~ |关注本帖
nibuxing 发表于 2015-4-10 04:05:21 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Zenefits - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
面试官是个三哥,人蛮好,也没啥口音。
就问了一道题:
String s1 = "waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc";
String s2 = "a+b+c-";
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
s2的形式是一个字母加上一个符号,正号代表有两个前面的字符,负号代表有四个,也就是说s2其实是"aabbcccc",不考虑invalid。
在s1中,找出连续或者不连续的s2,也就是说从s1中找出"aa....bb.....cccc",abc顺序不能变,但是之间可以有零个或多个字符,返回共有多少个。在上面这个例子中,有四个。

大家有什么好方法。

评分

4

查看全部评分

本帖被以下淘专辑推荐:

 楼主| nibuxing 发表于 2015-4-11 00:07:43 | 显示全部楼层
lijl900805 发表于 2015-4-10 12:31
每次把要匹配的子串拿出来,看s1里面有没有,有的话递归。递归里面s1把刚刚的子串前面的都去掉,s2去掉子 ...

你说的做法我明白了,我当时的做法就是你这种。但我之前没用过indexOf,所以写的麻烦了点。能否写一下你的recursion做法,感谢!
这是我DP的做法,先要把s1和s2都做转化,s2 = "a+b+c-"变成"abc", s1 = "waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc";变成"abcabc",然后再用LC的115题的dp做法做,代码如下:
  1. public static int numDistinctDP(String s1, String s2){
  2.                 StringBuffer sb1 = new StringBuffer();
  3.                 StringBuffer sb2 = new StringBuffer();
  4.                 HashMap<Character, Integer> map = new HashMap<Character, Integer>();
  5.                 //transform s2
  6.                 for(int i = 0; i < s2.length(); i += 2){
  7.                         char c = s2.charAt(i);
  8.                         sb2.append(c);
  9.                         map.put(c, s2.charAt(i + 1) == '+'? 1: 3);
  10.                 }
  11.                 s2 = sb2.toString();
  12.                 //transform s1
  13.                 for(int i = 0; i < s1.length() - 1; i++){.鏈枃鍘熷垱鑷1point3acres璁哄潧
  14.                         char c = s1.charAt(i);
  15.                         if(map.containsKey(c)){
  16.                                 int value = map.get(c);
  17.                                 if(isValid(s1, i, value, c)){
  18.                                         sb1.append(c);
  19.                                 }-google 1point3acres
  20.                         }. visit 1point3acres.com for more.
  21.                 }. more info on 1point3acres.com
  22.                 s1 = sb1.toString();
  23.                 //start DP. from: 1point3acres.com/bbs
  24.                 int[][] num = new int[s1.length() + 1][s2.length() + 1];
  25.         for(int i = 0; i <= s1.length(); i++){
  26.             num[i][0] = 1;
  27.         }
  28.         for(int i = 1; i <= s1.length(); i++){
  29.             for(int j = 1; j <= s2.length(); j++){
  30.                 num[i][j] += num[i - 1][j]; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  31.                 if(s1.charAt(i - 1) == s2.charAt(j - 1)){
  32.                     num[i][j] += num[i - 1][j - 1];. 鍥磋鎴戜滑@1point 3 acres
  33.                 }
  34.             }
  35.         }
  36.         return num[s1.length()][s2.length()];. 鍥磋鎴戜滑@1point 3 acres
  37.         }
复制代码
如果不做转化会多算很多种情况,recursion也可以先做转化。
  1. public static int numDistinctRecursion(String s1, String s2){
  2.                 StringBuffer sb1 = new StringBuffer();
  3.                 StringBuffer sb2 = new StringBuffer();
  4.                 HashMap<Character, Integer> map = new HashMap<Character, Integer>();
  5.                 //transform s2
  6.                 for(int i = 0; i < s2.length(); i += 2){.鏈枃鍘熷垱鑷1point3acres璁哄潧
  7.                         char c = s2.charAt(i);-google 1point3acres
  8.                         sb2.append(c);. more info on 1point3acres.com
  9.                         map.put(c, s2.charAt(i + 1) == '+'? 1: 3);. 鍥磋鎴戜滑@1point 3 acres
  10.                 }
  11.                 s2 = sb2.toString();
  12.                 //transform s1
  13.                 for(int i = 0; i < s1.length() - 1; i++){
  14.                         char c = s1.charAt(i);
  15.                         if(map.containsKey(c)){
  16.                                 int value = map.get(c);
  17.                                 if(isValid(s1, i, value, c)){
  18.                                         sb1.append(c);
  19.                                 }
  20.                         }
  21.                 }
  22.                 s1 = sb1.toString();
  23.                 return withRecursionHelper(s1, s2);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  24.         }. 1point 3acres 璁哄潧
  25.        
  26.         private static boolean isValid(String s1, int i, int value, char c){
  27.                 if(i + value > s1.length() - 1) return false;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  28.                 for(int j = 1; j <= value; j++){
  29.                         if(s1.charAt(i + j) != c) return false;
  30.                 } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  31.                 return true;
  32.         }
  33.         private static int withRecursionHelper(String s1, String s2){
  34.                 if(s2.length() == 0) return 1;
  35.                 if(s1.length() == 0) return 0;. 鍥磋鎴戜滑@1point 3 acres
  36.                 if(s1.length() < s2.length()) return 0;
  37.                 if(s1.charAt(0) != s2.charAt(0)){
  38.                         return withRecursionHelper(s1.substring(1), s2);
  39.                 }
  40.                 return withRecursionHelper(s1.substring(1), s2) + withRecursionHelper(s1.substring(1), s2.substring(1));
  41.         }
复制代码

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

houqingniao 发表于 2015-4-10 04:08:51 | 显示全部楼层
这个不是跟 leetcode distinct subsequence 差不多, dp
回复 支持 1 反对 0

使用道具 举报

 楼主| nibuxing 发表于 2015-4-10 04:14:39 | 显示全部楼层
houqingniao 发表于 2015-4-10 04:08
这个不是跟 leetcode distinct subsequence 差不多, dp

好像很有道理
回复 支持 反对

使用道具 举报

houqingniao 发表于 2015-4-10 05:05:17 | 显示全部楼层
. 1point 3acres 璁哄潧
刚写了下,差不多,只是情况更多些
回复 支持 反对

使用道具 举报

yuxrose 发表于 2015-4-10 05:31:02 | 显示全部楼层
Z家题好难。。。。直接跪了。。。
回复 支持 反对

使用道具 举报

 楼主| nibuxing 发表于 2015-4-10 06:00:28 | 显示全部楼层
houqingniao 发表于 2015-4-10 05:05
刚写了下,差不多,只是情况更多些

恩,我也写了一下,没问题。当时考官让我用recursion写,我写得不好,目测要跪。
回复 支持 反对

使用道具 举报

gaohannk 发表于 2015-4-10 07:00:25 | 显示全部楼层
这已经是比hard级别还要在复杂一点的题啊。
回复 支持 反对

使用道具 举报

 楼主| nibuxing 发表于 2015-4-10 07:02:18 | 显示全部楼层
gaohannk 发表于 2015-4-10 07:00
这已经是比hard级别还要在复杂一点的题啊。
.1point3acres缃
其实还好,是我自己对LC的distinct subsequences不熟悉,稍微变化一点就不知怎么做了。最后用recursion写觉得可以做但容易stack overflow,也容易写错。
回复 支持 反对

使用道具 举报

lijl900805 发表于 2015-4-10 07:15:01 | 显示全部楼层
用recursion的话就DFS,每次调用indexOf找s1中是否还有s2某个条件的子串~
我刚刚写了一下DFS解法,也很快出来。和lz一起加油!!!
回复 支持 反对

使用道具 举报

 楼主| nibuxing 发表于 2015-4-10 07:33:53 | 显示全部楼层
lijl900805 发表于 2015-4-10 07:15
用recursion的话就DFS,每次调用indexOf找s1中是否还有s2某个条件的子串~
我刚刚写了一下DFS解法,也很快 ...

indexOf我从来没用过,可否具体说一下,感谢!
回复 支持 反对

使用道具 举报

gaohannk 发表于 2015-4-10 07:46:16 | 显示全部楼层
nibuxing 发表于 2015-4-10 07:02
其实还好,是我自己对LC的distinct subsequences不熟悉,稍微变化一点就不知怎么做了。最后用recursion写 ...

recusive相对来说简单一些,无非就是DFS,BFS,但是用DP做就很难想吧。
回复 支持 反对

使用道具 举报

gaohannk 发表于 2015-4-10 07:46:55 | 显示全部楼层
gaohannk 发表于 2015-4-10 07:46
recusive相对来说简单一些,无非就是DFS,BFS,但是用DP做就很难想吧。

刚刚面完,题目不难。
回复 支持 反对

使用道具 举报

 楼主| nibuxing 发表于 2015-4-10 07:55:04 | 显示全部楼层
gaohannk 发表于 2015-4-10 07:46
刚刚面完,题目不难。

我DP倒是掌握的好点
回复 支持 反对

使用道具 举报

houqingniao 发表于 2015-4-10 11:40:38 | 显示全部楼层
楼主怎么拿到的面试啊
回复 支持 反对

使用道具 举报

 楼主| nibuxing 发表于 2015-4-10 12:02:55 | 显示全部楼层
houqingniao 发表于 2015-4-10 11:40
楼主怎么拿到的面试啊
. 鍥磋鎴戜滑@1point 3 acres
我找的内推
回复 支持 反对

使用道具 举报

lijl900805 发表于 2015-4-10 12:31:39 | 显示全部楼层
nibuxing 发表于 2015-4-10 07:33
indexOf我从来没用过,可否具体说一下,感谢!

每次把要匹配的子串拿出来,看s1里面有没有,有的话递归。递归里面s1把刚刚的子串前面的都去掉,s2去掉子串,继续递归。

倒是DP我还没想出来,求问怎么解决连续子串出现(如aaaa)的问题?求DP的解法...
回复 支持 反对

使用道具 举报

lijl900805 发表于 2015-4-11 00:33:23 | 显示全部楼层
我的Recursion解法里没有对s1进行处理,然后对于s2,每次只处理一个字母,比如解析出aa,然后在s1里面找s1.indexOf("aa"),每次找到第一个"aa"出现的地方后,进入递归。递归参数里面s1变成s1.substring(s1.indexOf("aa") + 2(即aa长度)),s2变成s2.substring(2)(即解析掉了a+),递归直到s2 变没或者s1 变没即可。递归回到原来的地方后,把s1削去前面检验过的那一段,继续调用indexOf直到找不到为止。
回复 支持 反对

使用道具 举报

 楼主| nibuxing 发表于 2015-4-11 00:33:43 | 显示全部楼层
lijl900805 发表于 2015-4-10 12:31
每次把要匹配的子串拿出来,看s1里面有没有,有的话递归。递归里面s1把刚刚的子串前面的都去掉,s2去掉子 ...

如果这道题是"a+",那么我们只考虑s1里的"aa"的情况,假设s1不会出现aaa或者aaaa的情况。(考官这个意思)
如果会出现"aaa""aaaa",我转换"aaa"为"aa",意思是这里要考虑两种"aa"的情况。上面的代码里也写了,可以handle这种。然后这种情况下你的indexOf做法是不是就没法做了。求教啊
回复 支持 反对

使用道具 举报

lijl900805 发表于 2015-4-11 00:42:00 | 显示全部楼层
nibuxing 发表于 2015-4-11 00:07
你说的做法我明白了,我当时的做法就是你这种。但我之前没用过indexOf,所以写的麻烦了点。能否写一下你 ...

lz, 貌似我发现了你这样做会有一个bug... 比如说s2里面多次出现了同一个字母的话,你这样就貌似不太OK囖.... more info on 1point3acres.com
e.g.: s2 = a+b+c-a-b-c+;. visit 1point3acres.com for more.
这样的话你的map里面存的都是最后面的要求了囖...
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 17:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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