【通知】7月22,工业界资深数据科学家教你破解各大公司面试!


一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 545|回复: 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, 请自己把*换成.)
massivealgorithms*blogspot.com/2015/11/zenefits-interview-count-of-possible_28*html   (无权限加URL, 请自己把*换成.)
题目如下:
String s1 = "waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc"
String s2 = "a+b+c-";. visit 1point3acres.com for more.
.1point3acres缃
s2的形式是一个字母加上一个符号,正号代表有两个前面的字符,负号代表有四个,也就是说s2其实是"aabbcccc",不考虑invalid。. 1point3acres.com/bbs
在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;. from: 1point3acres.com/bbs
   return s + s;. 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;.鏈枃鍘熷垱鑷1point3acres璁哄潧
            
      if (s1.charAt(s1EndIndex) != token.charAt(i))
         return false;
   }. From 1point 3acres bbs

   return true;
}
   
public int findMatches(String s1, String s2) {
   int s1Len = s1.length();. Waral 鍗氬鏈夋洿澶氭枃绔,
   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]'.
   int[][] results = new int[s1Len][s2Len];
        
   for (int i = 0; i < s1Len; i++) {. From 1point 3acres bbs
      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];.鐣欏璁哄潧-涓浜-涓夊垎鍦
               
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴         if (match(s1, i /*s1's end index*/, s2Token)) {-google 1point3acres
            int s1LastEndIndex = i - s2Token.length();
                    
            if (j == 0)
               results[j] += 1;. 1point 3acres 璁哄潧
            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

    #reconstruct p-google 1point3acres
    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
    #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
. from: 1point3acres.com/bbs
    now = [0] * (len(s) + 1)
    for i in xrange(1, len(p) + 1):
        #i in [1, len(p)]
        #j = 0. Waral 鍗氬鏈夋洿澶氭枃绔,
        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]). visit 1point3acres.com for more.
                #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. From 1point 3acres bbs
        pre, now = now, pre. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        #print i, pre-google 1point3acres
    #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,. visit 1point3acres.com for more.
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);. Waral 鍗氬鏈夋洿澶氭枃绔,
        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;.鏈枃鍘熷垱鑷1point3acres璁哄潧
    }
   
    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 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
JermaineDing 发表于 2016-2-18 05:59
楼主你好,那个recursive方法里面“String cacheKey = s2 + "_" + begin;. ”,为什么给cacheKey加下划线和 ...
. 1point3acres.com/bbs
我的理解 只是用来产生一个 unique key的,随你
回复 支持 1 反对 0

使用道具 举报

JermaineDing 发表于 2016-2-18 05:59:11 | 显示全部楼层
关注一亩三分地微博:
Warald
楼主你好,那个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-7-21 15:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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