聊聊跟三哥三姐面试和共事的经历

一亩三分地论坛

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

zenefits电面 stringmatch正确解法

[复制链接] |试试Instant~ |关注本帖
yi1san3fendi 发表于 2016-2-17 07:13:04 | 显示全部楼层 |阅读模式

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

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

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

x
面试官给我出了道老题, 我用了一亩三分地上的dp解答,挂了;来源如下. 1point3acres
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"-google 1point3acres
String s2 = "a+b+c-";

s2的形式是一个字母加上一个符号,正号代表有两个前面的字符,负号代表有四个,也就是说s2其实是"aabbcccc",不考虑invalid。
在s1中,找出连续或者不连续的s2,也就是说从s1中找出"aa....bb.....cccc",abc顺序不能变,但是之间可以有零个或多个字符,返回共有多少个。在上面这个例子中,有四个。
结果测试sln.findMatches("aaaaaa", "a+a-") ,出来结果为0,sln.findMatches("aabbaaaa", "a+a-") ,出来结果还为0,不对,挂了 来源一亩.三分地论坛.

mitbbs上大牛们给出正确解答,包括dp解答,整理如下(麻烦给大米):
1. dp
private String getToken(char c, char op) {
   String s = c + "" + c;
   if (op == '+')
      return s;
. 牛人云集,一亩三分地   return s + s;. more info on 1point3acres
}

private boolean match(String s1, int s1EndIndex, String token) {
   for (int i = token.length() - 1; i >= 0; i--, s1EndIndex--) {
      if (s1EndIndex < 0)
         return false;
            . from: 1point3acres
      if (s1.charAt(s1EndIndex) != token.charAt(i))
         return false;
   }. from: 1point3acres
. 1point3acres
   return true;
}
   
public int findMatches(String s1, String s2) {
   int s1Len = s1.length();
   int s2Len = s2.length() / 2;
        
   // 'results[j]' stores the number of matches of first 'j + 1' tokens
   // from 's2' in sub-string of s1: 's1[0, i]'.
   int[][] results = new int[s1Len][s2Len];
        
   for (int i = 0; i < s1Len; i++) {
      for (int j = 0; j < s2Len; j++) {. From 1point 3acres bbs
         if (i == 0) {
            results[j] = 0;
            continue;
         }
                . From 1point 3acres bbs
         char character = s2.charAt(j * 2);. 1point3acres
         char op = s2.charAt(j * 2 + 1);
         String s2Token = getToken(character, op);
               
         results[j] = results[i - 1][j];. Waral 博客有更多文章,
               
         if (match(s1, i /*s1's end index*/, s2Token)) {. 1point3acres
            int s1LastEndIndex = i - s2Token.length();
                    
            if (j == 0)
               results[j] += 1;.本文原创自1point3acres论坛
            else if (s1LastEndIndex >= 0)
               results[j] += results[s1LastEndIndex][j - 1];
         }
      }
   }.留学论坛-一亩-三分地

   return results[s1Len - 1][s2Len - 1];
}

2. python
def match(s, p):
    #invalid input
    if len(p) % 2 != 0:
        return -1
. 1point 3acres 论坛
    #reconstruct p. Waral 博客有更多文章,
    temp = ''
    i = 0. 牛人云集,一亩三分地
    while i < len(p):
        #add '*' first. 留学申请论坛-一亩三分地
        temp += '*'
        
        #add char pattern. 一亩-三分-地,独家发布
        if p[i+1] == '+':
            temp += p * 2
        else:
            #p[i+1] == '-'
            temp += p * 4
. Waral 博客有更多文章,        #iterate to next char . 1point 3acres 论坛
        i += 2
    p = temp
    print p

    #wildcard matching
    #dp(i,j) the number of ways p[1,i] is matched to s[1,j]
    #if p[i-1] == '*': dp(i,j) = dp(i-1,j) + max(dp(i-1,j-1), dp(i,j-1))
    #                        match 0 times      1 times     >1 times
    #if p[i-1] != '*': dp(i,j) = dp(i-1,j-1) if p[i-1]==s[j-1] else 0

    res = 0

    #i=0
    pre = [0] * (len(s) + 1)
    pre[0] = 1  #i=0, j=0. 牛人云集,一亩三分地

    now = [0] * (len(s) + 1)
    for i in xrange(1, len(p) + 1):
        #i in [1, len(p)]
        #j = 0
        now[0] = pre[0] if p[i-1] == '*' else 0. from: 1point3acres
        for j in xrange(1, len(s) + 1):
            #j in [1, len(s)]
            if p[i-1] == '*':
                now[j] = pre[j] + max(pre[j-1], now[j-1])
                #match   0 times  1 times    > 1 times
            else:
                now[j] = pre[j-1] if p[i-1] == s[j-1] else 0

            #update result if p is all matched
            if i == len(p):
                res += now[j]
        #iterate to match next i
-google 1point3acres        pre, now = now, pre
        #print i, pre
    #return reuslt
    return res 来源一亩.三分地论坛.

3. recursive
    private String getToken(char c, char op) {
        String s = c + "" + c;
        if (op == '+')
            return s;
        return s + s;
    }
. from: 1point3acres
    private int findMatches(String s1, String s2, int begin, HashMap<String,. 围观我们@1point 3 acres
Integer> cache) {
        if (s2.length() == 0)
            return 1;
        if (begin >= s1.length() - 1)
            return 0;
        
        String cacheKey = s2 + "_" + begin;
        if (cache.containsKey(cacheKey))-google 1point3acres
            return cache.get(cacheKey);
        
        char character = s2.charAt(0);
        char op = s2.charAt(1);
        String s2Token = getToken(character, op);
        String s2WithoutCurToken = s2.substring(2);.留学论坛-一亩-三分地
        
        int result = 0;. 一亩-三分-地,独家发布
        
        if (s1.startsWith(s2Token, begin)) {
            result += findMatches(s1, s2WithoutCurToken, begin + s2Token.. 围观我们@1point 3 acres
length(), cache);. From 1point 3acres bbs
        }
        result += findMatches(s1, s2, begin + 1, cache);. 围观我们@1point 3 acres
        
        cache.put(cacheKey, result);
        return result;
    }
   
    public int findMatches(String s1, String s2) {
        HashMap<String, Integer> cache = new HashMap<>();
        return findMatches(s1, s2, 0 /*begin*/, cache);
    }

评分

1

查看全部评分

 楼主| yi1san3fendi 发表于 2016-2-20 08:44:11 | 显示全部楼层
JermaineDing 发表于 2016-2-18 05:59. 留学申请论坛-一亩三分地
楼主你好,那个recursive方法里面“String cacheKey = s2 + "_" + begin;. ”,为什么给cacheKey加下划线和 ...

我的理解 只是用来产生一个 unique key的,随你
回复 支持 1 反对 0

使用道具 举报

JermaineDing 发表于 2016-2-18 05:59:11 | 显示全部楼层
楼主你好,那个recursive方法里面“String cacheKey = s2 + "_" + begin;. ”,为什么给cacheKey加下划线和begin?
回复 支持 反对

使用道具 举报

freetrek 发表于 2016-2-25 00:40:22 | 显示全部楼层
LZ, py版本的有误, +=p*2 和 += p*4应该是 p[i],不是p
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-22 09:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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