📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
回复: 4
跳转到指定楼层
上一主题 下一主题
收起左侧

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

全局:

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

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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-";

s2的形式是一个字母加上一个符号,正号代表有两个前面的字符,负号代表有四个,也就是说s2其实是"aabbcccc",不考虑invalid。
在s1中,找出连续或者不连续的s2,也就是说从s1中找出"aa....bb.....cccc",abc顺序不能变,但是之间可以有零个或多个字符,返回共有多少个。在上面这个例子中,有四个。
结果测试sln.findMatches("aaaaaa", "a+a-") ,出来结果为0,不对,挂了
另外System.out.println(sln.findMatches("
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
abangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "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!
   }
}




上一篇:报个25号Amazon group offer并求问怎么跟HR说换工作地点
下一篇:某小Financial SDE面经
🔗
 楼主| yi1san3fendi 2016-1-29 06:52:44 | 只看该作者
全局:
不知道用dp正确的解答应该是什么?有人能给出正确的dp代码吗?
回复

使用道具 举报

全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
 楼主| yi1san3fendi 2016-2-17 06:45:43 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
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):
  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
  22.     assert string_match('aaaaaa', 'a-a+') == 1
  23.     assert string_match('aaaaaaaa', 'a-a+') == 6
  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
复制代码
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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