推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 554|回复: 3
收起左侧

zenefits电面 stringmatch正确解法

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

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

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

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

x
面试官给我出了道老题, 我用了一亩三分地上的dp解答,挂了;来源如下
1point3acres*com/bbs/thread-145290-2-1*html   (无权限加URL, 请自己把*换成.). visit 1point3acres.com for more.
massivealgorithms*blogspot.com/2015/11/zenefits-interview-count-of-possible_28*html   (无权限加URL, 请自己把*换成.)
题目如下:. from: 1point3acres.com/bbs
String s1 = "waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc"
String s2 = "a+b+c-";. 1point3acres.com/bbs

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解答,整理如下(麻烦给大米):. visit 1point3acres.com for more.
1. dp. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
private String getToken(char c, char op) {
   String s = c + "" + c;
   if (op == '+')
      return s;
   return s + s;
}.鏈枃鍘熷垱鑷1point3acres璁哄潧
. From 1point 3acres bbs
private boolean match(String s1, int s1EndIndex, String token) {
   for (int i = token.length() - 1; i >= 0; i--, s1EndIndex--) {
      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();
   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];. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        . visit 1point3acres.com for more.
   for (int i = 0; i < s1Len; i++) {
      for (int j = 0; j < s2Len; j++) {
         if (i == 0) {
            results[j] = 0;
            continue;
         }
               
         char character = s2.charAt(j * 2);
         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)) {
            int s1LastEndIndex = i - s2Token.length();
                    . from: 1point3acres.com/bbs
            if (j == 0)
               results[j] += 1;.鏈枃鍘熷垱鑷1point3acres璁哄潧
            else if (s1LastEndIndex >= 0)
               results[j] += results[s1LastEndIndex][j - 1];. From 1point 3acres bbs
         }
      }
   }

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

2. python
def match(s, p):.鏈枃鍘熷垱鑷1point3acres璁哄潧
    #invalid input
    if len(p) % 2 != 0:
        return -1
. 1point 3acres 璁哄潧
    #reconstruct p
    temp = ''.1point3acres缃
    i = 0
    while i < len(p):
        #add '*' first
        temp += '*'
        
        #add char pattern 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        if p[i+1] == '+':. more info on 1point3acres.com
            temp += p * 2
        else:
            #p[i+1] == '-'
            temp += p * 4
        #iterate to next char
        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). 1point 3acres 璁哄潧
    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
        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):.1point3acres缃
                res += now[j]
        #iterate to match next i. Waral 鍗氬鏈夋洿澶氭枃绔,
        pre, now = now, pre-google 1point3acres
        #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;
    }

    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)).鏈枃鍘熷垱鑷1point3acres璁哄潧
            return cache.get(cacheKey);
        . more info on 1point3acres.com
        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);
        }. from: 1point3acres.com/bbs
        result += findMatches(s1, s2, begin + 1, cache);
        
        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
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-18 15:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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