一亩三分地论坛

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

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

zenefits电面 stringmatch正确解法

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

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, 请自己把*换成.)
题目如下:. Waral 鍗氬鏈夋洿澶氭枃绔,
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,sln.findMatches("aabbaaaa", "a+a-") ,出来结果还为0,不对,挂了

mitbbs上大牛们给出正确解答,包括dp解答,整理如下(麻烦给大米):
1. dp. 鍥磋鎴戜滑@1point 3 acres
private String getToken(char c, char op) {-google 1point3acres
   String s = c + "" + c;
   if (op == '+')
      return s;
   return s + s;
}

private boolean match(String s1, int s1EndIndex, String token) {
   for (int i = token.length() - 1; i >= 0; i--, s1EndIndex--) {.1point3acres缃
      if (s1EndIndex < 0)
         return false;
            
      if (s1.charAt(s1EndIndex) != token.charAt(i))
         return false;
   }

   return true;
}
   
public int findMatches(String s1, String s2) {
   int s1Len = s1.length();-google 1point3acres
   int s2Len = s2.length() / 2;
        .鏈枃鍘熷垱鑷1point3acres璁哄潧
   // 'results[j]' stores the number of matches of first 'j + 1' tokens.鐣欏璁哄潧-涓浜-涓夊垎鍦
   // from 's2' in sub-string of s1: 's1[0, i]'.. 1point 3acres 璁哄潧
   int[][] results = new int[s1Len][s2Len];
        
   for (int i = 0; i < s1Len; i++) {
      for (int j = 0; j < s2Len; j++) {
         if (i == 0) {
            results[j] = 0;
            continue;
         }
                . 鍥磋鎴戜滑@1point 3 acres
         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];
               
         if (match(s1, i /*s1's end index*/, s2Token)) {
            int s1LastEndIndex = i - s2Token.length();
                    
            if (j == 0). from: 1point3acres.com/bbs
               results[j] += 1;
            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:. visit 1point3acres.com for more.
        return -1. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

    #reconstruct p
    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
        #iterate to next char
        i += 2. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    p = temp
    print p.鏈枃鍘熷垱鑷1point3acres璁哄潧

    #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
. 鍥磋鎴戜滑@1point 3 acres    #if p[i-1] != '*': dp(i,j) = dp(i-1,j-1) if p[i-1]==s[j-1] else 0
.鏈枃鍘熷垱鑷1point3acres璁哄潧
    res = 0
.鏈枃鍘熷垱鑷1point3acres璁哄潧
    #i=0
    pre = [0] * (len(s) + 1)
    pre[0] = 1  #i=0, j=0
. visit 1point3acres.com for more.
    now = [0] * (len(s) + 1)
    for i in xrange(1, len(p) + 1):
        #i in [1, len(p)]. Waral 鍗氬鏈夋洿澶氭枃绔,
        #j = 0
        now[0] = pre[0] if p[i-1] == '*' else 0
        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]).1point3acres缃
                #match   0 times  1 times    > 1 times
            else:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                now[j] = pre[j-1] if p[i-1] == s[j-1] else 0. Waral 鍗氬鏈夋洿澶氭枃绔,

            #update result if p is all matched
            if i == len(p):
                res += now[j]
        #iterate to match next i.鏈枃鍘熷垱鑷1point3acres璁哄潧
        pre, now = now, pre 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        #print i, pre. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    #return reuslt
    return res

3. recursive . 1point 3acres 璁哄潧
    private String getToken(char c, char op) {
        String s = c + "" + c;. 1point3acres.com/bbs
        if (op == '+')
            return s;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        return s + s;
    }

    private int findMatches(String s1, String s2, int begin, HashMap<String,
Integer> cache) {
        if (s2.length() == 0)
            return 1;
        if (begin >= s1.length() - 1)
            return 0;
        
        String cacheKey = s2 + "_" + begin;
        if (cache.containsKey(cacheKey))
            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.
length(), cache);
        }
        result += findMatches(s1, s2, begin + 1, cache);
        
        cache.put(cacheKey, result);
        return result;. visit 1point3acres.com for more.
    }
   
    public int findMatches(String s1, String s2) {
        HashMap<String, Integer> cache = new HashMap<>();.1point3acres缃
        return findMatches(s1, s2, 0 /*begin*/, cache); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    }.1point3acres缃

评分

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
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 13:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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