San Jose各个房价 <1.5m 区域买房总结

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 1301|回复: 4
收起左侧

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

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

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

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

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

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顺序不能变,但是之间可以有零个或多个字符,返回共有多少个。在上面这个例子中,有四个。
结果测试sln.findMatches("aaaaaa", "a+a-") ,出来结果为0,不对,挂了
另外System.out.println(sln.findMatches("waeginsapnaabangpisebbasccepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c+c-")); 跑出来是5,感觉正确结果应该是2
不知道用dp正确的解答应该是什么?有人能给出正确的dp代码吗?
. 1point3acres
以下是从拷贝的测试用例不通过的代码:
public class Solution {. from: 1point3acres
        public int findMatches(String s1, String s2){
       int len1 = s1.length(), len2 = s2.length();. From 1point 3acres bbs
       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]
       for (int i = 1; i < len1; i++){
           dp[i + 1][0] = 1;
           for (int j = 0; j < len2 / 2; j++){. Waral 博客有更多文章,
               dp[i + 1][j + 1] = dp[i][j + 1];
               if (isMatch(s1, s2, i, j)){
                   if (s2.charAt(2*j + 1) == '+')
. 围观我们@1point 3 acres                       dp[i + 1][j + 1] += dp[i - 1][j];
                   else
                       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;
       }
       return true;
   }

   public static void main(String[] args){
           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!
   }
}



评分

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. 一亩-三分-地,独家发布
System.out.println(sln.findMatches("waeginsapnaabangpisebbasccepgnccccapisdnfngaabndlrjngeuiogbbegbu ...

还是很多case出错. From 1point 3acres bbs
比如 System.out.println(sln.findMatches("aaaaaa", "a+a-"));//0  wrong!
System.out.println(sln.findMatches("aabbaaaa", "a+a-"));//0  wrong! 来源一亩.三分地论坛.
回复 支持 反对

使用道具 举报

spacelis 发表于 2018-1-9 06:30:06 | 显示全部楼层
我的想法是用dp,但dp记录的是有多少个子pattern已经出现了,严格一点说是有多少个pattern的prefix match了。代码如下,不好意思python写的。
counts就是dp pattern prefix的match数。running只是用来避免反向找每一个pattern的counts。. 牛人云集,一亩三分地
  1. def string_match(s, p):
  2.     ptn = []
  3.     for i in range(0, len(p), 2):. more info on 1point3acres
  4.         if p[i+1] == '+':
  5.             ptn.append(p[i]*2)
  6.         elif p[i+1] == '-':
  7.             ptn.append(p[i]*4)
  8.     counts = [[0] * (len(s)+1) for _ in  range(len(ptn) + 1)]
  9.     counts[0][0] = 1
  10.     running = [0] * len(ptn). 留学申请论坛-一亩三分地
  11.     running = [1] + running
  12.     for i in range(len(s)):
  13.         for j, p in enumerate(ptn, 1):. 留学申请论坛-一亩三分地
  14.             running[j] += counts[j][i]
  15.             if s[i:].startswith(p):
  16.                 counts[j][i+len(p)] = running[j-1]
  17.     for j in range(len(running)):
  18.         running[j] += counts[j][-1]
  19.     return running[-1]


  20. def test():
  21.     assert string_match('aaaaaa', 'a+a-') == 1. 围观我们@1point 3 acres
  22.     assert string_match('aaaaaa', 'a-a+') == 1
  23.     assert string_match('aaaaaaaa', 'a-a+') == 6. 1point 3acres 论坛
  24.     assert string_match('aabbaaaa', 'a+a-') == 1
  25.     assert string_match('waeginsapnaabangpisebbasccepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc',
  26.                         'a+b+c+c-') == 5
  27.     assert string_match("waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc",
  28.                         "a+b+c-") == 4
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-26 10:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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