传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 583|回复: 3
收起左侧

zenefits电面 stringmatch正确解法

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

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

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

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

x
面试官给我出了道老题, 我用了一亩三分地上的dp解答,挂了;来源如下. visit 1point3acres.com for more.
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". from: 1point3acres.com/bbs
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.鏈枃鍘熷垱鑷1point3acres璁哄潧
private String getToken(char c, char op) {
   String s = c + "" + c;
   if (op == '+')
      return s;
   return s + s;. 1point 3acres 璁哄潧
}

private boolean match(String s1, int s1EndIndex, String token) {. 鍥磋鎴戜滑@1point 3 acres
   for (int i = token.length() - 1; i >= 0; i--, s1EndIndex--) {
      if (s1EndIndex < 0)
         return false;
            . From 1point 3acres bbs
      if (s1.charAt(s1EndIndex) != token.charAt(i))
         return false;
   }

   return true;
}
. from: 1point3acres.com/bbs    
public int findMatches(String s1, String s2) {. more info on 1point3acres.com
   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++) {
         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)) {
            int s1LastEndIndex = i - s2Token.length();
                    
            if (j == 0). visit 1point3acres.com for more.
               results[j] += 1; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
            else if (s1LastEndIndex >= 0)
               results[j] += results[s1LastEndIndex][j - 1];
         }
      }
   }.鏈枃鍘熷垱鑷1point3acres璁哄潧

   return results[s1Len - 1][s2Len - 1];.1point3acres缃
}.1point3acres缃

2. python
def match(s, p):
    #invalid input
    if len(p) % 2 != 0:
        return -1-google 1point3acres

    #reconstruct p
    temp = ''
    i = 0. Waral 鍗氬鏈夋洿澶氭枃绔,
    while i < len(p):
        #add '*' first
        temp += '*'
        
        #add char pattern. Waral 鍗氬鏈夋洿澶氭枃绔,
        if p[i+1] == '+':. visit 1point3acres.com for more.
            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)
    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)]. 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])
                #match   0 times  1 times    > 1 times
            else:
                now[j] = pre[j-1] if p[i-1] == s[j-1] else 0. From 1point 3acres bbs

            #update result if p is all matched
            if i == len(p):
                res += now[j]
        #iterate to match next i
        pre, now = now, pre
        #print i, pre. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    #return reuslt
    return res

3. recursive
    private String getToken(char c, char op) {
        String s = c + "" + c;
-google 1point3acres        if (op == '+')
            return s;
        return s + s;
    }. 1point3acres.com/bbs

    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);. visit 1point3acres.com for more.
        
        int result = 0;
        
        if (s1.startsWith(s2Token, begin)) {
            result += findMatches(s1, s2WithoutCurToken, begin + s2Token.
length(), cache);
        }. 1point3acres.com/bbs
        result += findMatches(s1, s2, begin + 1, cache);
        
        cache.put(cacheKey, result);
        return result;
    }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
   
    public int findMatches(String s1, String s2) {. 鍥磋鎴戜滑@1point 3 acres
        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-9-22 21:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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