一亩三分地论坛

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

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

zenefits电面 用了一亩三分地上的dp解答,不对,挂了

[复制链接] |试试Instant~ |关注本帖
yi1san3fendi 发表于 2016-1-29 06:49:50 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@zenefits - 网上海投 - 技术电面 |Failfresh grad应届毕业生

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

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

x

面试官给我出了道老题, 我用了一亩三分地上的dp解答,来源如下
1point3acres*com/bbs/thread-145290-2-1*html   (无权限加URL, 请自己把*换成.)
massivealgorithms*blogspot.com/2015/11/zenefits-interview-count-of-possible_28*html   (无权限加URL, 请自己把*换成.)
题目如下:
String s1 = "waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc"
String s2 = "a+b+c-";
.鏈枃鍘熷垱鑷1point3acres璁哄潧
s2的形式是一个字母加上一个符号,正号代表有两个前面的字符,负号代表有四个,也就是说s2其实是"aabbcccc",不考虑invalid。
在s1中,找出连续或者不连续的s2,也就是说从s1中找出"aa....bb.....cccc",abc顺序不能变,但是之间可以有零个或多个字符,返回共有多少个。在上面这个例子中,有四个。. 1point3acres.com/bbs
结果测试sln.findMatches("aaaaaa", "a+a-") ,出来结果为0,不对,挂了
另外System.out.println(sln.findMatches("waeginsapnaabangpisebbasccepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c+c-")); 跑出来是5,感觉正确结果应该是2
不知道用dp正确的解答应该是什么?有人能给出正确的dp代码吗?

以下是从拷贝的测试用例不通过的代码:
public class Solution {
        public int findMatches(String s1, String s2){
       int len1 = s1.length(), len2 = s2.length();. 鍥磋鎴戜滑@1point 3 acres
       if (len2 > len1) return 0;
       if (len2 == 0 || len2 %2 != 0) return 0;
       // DP matches each pattern
       // number of matches between s1.substring(0, i + 1) and s2.substring(j * 2, j * 2 + 2)
       int[][] dp = new int[len1 + 1][len2 / 2 + 1];
       // no match for dp[0][j].鏈枃鍘熷垱鑷1point3acres璁哄潧
       for (int i = 1; i < len1; i++){
           dp[i + 1][0] = 1;
           for (int j = 0; j < len2 / 2; j++){
               dp[i + 1][j + 1] = dp[i][j + 1];
               if (isMatch(s1, s2, i, j)){
                   if (s2.charAt(2*j + 1) == '+')
                       dp[i + 1][j + 1] += dp[i - 1][j];
                   else. more info on 1point3acres.com
                       dp[i + 1][j + 1] += dp[i - 3][j];
               }
           }
       }
       return dp[len1][len2 / 2];
  }

   boolean isMatch(String s1, String s2, int i, int j){
       char c = s2.charAt(j * 2);
       char p = s2.charAt(j * 2 + 1);
       int len = p == '+' ? 2 : 4;
       if (i - len < -1) return false;
       for (int h = i - len + 1; h <= i; h++){
           if (s1.charAt(h) != c) return false;.鐣欏璁哄潧-涓浜-涓夊垎鍦
       }
. more info on 1point3acres.com       return true;
   }.鏈枃鍘熷垱鑷1point3acres璁哄潧

   public static void main(String[] args){. more info on 1point3acres.com
           Solution sln = new Solution();
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
           System.out.println(sln.findMatches("waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c-"));  // 4

           System.out.println(sln.findMatches("waeginsapnaabangpisebbasccepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c+c-")); // 5 ???  I think it should be 2
           System.out.println(sln.findMatches("aaaaaa", "a+a-"));//0  wrong!. visit 1point3acres.com for more.
   }
}

. more info on 1point3acres.com

评分

1

查看全部评分

 楼主| yi1san3fendi 发表于 2016-1-29 06:52:44 | 显示全部楼层
不知道用dp正确的解答应该是什么?有人能给出正确的dp代码吗?
回复 支持 反对

使用道具 举报

feiyanzhandui 发表于 2016-2-3 18:13:08 | 显示全部楼层
System.out.println(sln.findMatches("waeginsapnaabangpisebbasccepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c+c-"));是5个
第一个aa,第一个bb,第一个cc 可以和两个cccc 分别组成pattern,这就两个了。第一个aa,第一个bb,和第一个cccc(拆分成三种cc)可以和第二个cccc组成三种,这一共5个
回复 支持 反对

使用道具 举报

 楼主| yi1san3fendi 发表于 2016-2-17 06:45:43 | 显示全部楼层
feiyanzhandui 发表于 2016-2-3 18:13. 鍥磋鎴戜滑@1point 3 acres
System.out.println(sln.findMatches("waeginsapnaabangpisebbasccepgnccccapisdnfngaabndlrjngeuiogbbegbu ...

还是很多case出错
比如 System.out.println(sln.findMatches("aaaaaa", "a+a-"));//0  wrong! 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
System.out.println(sln.findMatches("aabbaaaa", "a+a-"));//0  wrong!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 14:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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