Zenefits 一道面试题 | 书脊

Zenefits 一道面试题 | 书脊
A, B两个String
//example
A = XYZ;
A^2 = XXYYZZ;
A^3 = XXXYYYZZZ;

B = XXadhflakjhelXXzzqqkkpoYYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhh

A^2 是B的subsequence, 所以
return k = 2;

A可能有重复的char, B可能有其他字符, 求k.

我用的run-length encode做的, 先找下a的count, 然后找下b的count, 这里的技巧是把在b但是不在a的字符存成负数. 这样encode的时候, 我们只encode a和b中共同的字符. 然后走一下数字的最小值就好了, 时间o(n).

http://www.mitbbs.com/article_t/JobHunting/33043355.html
Test if A^k is in B takes simple O(n), as follows:

var test = function(A, k, B) {
    var i = 0;
    var next = A[i];
    var quota = k;

    for(j = 0; j < B.length; j++) {
        if (B[j] == next) {
            quota--;
        }
        if (quota == 0) {
            i++;
            if (i >= A.length) {
                return true;
            } else {
                next = A[i];
                quota = k;
            }
        }
    }
    return false;
};

Then apply binary search to find the largest k, as follows:

var searchK = function(A, B) {
    var bot = 1;
    var top = Math.floor(B.length / A.length);

    while (bot < top) {
        var mid = (bot + top) / 2;
        if (test(A, mid, B)) {
            bot = mid;
        } else {
            top = mid;
        }
    }

    return test(A, top, B);
};

This take O(n*log(k)), overall.

建立一个一维dp table，大小为A的size；
开始dp表都是0，遇到A中一个元素，查看dp table的对应value和dp［i－1］的value。
如果dp［i －1］ 》 dp［i］ ，dp［i］＋＋；
都完事了dp［n － 1］就是结果。

-- don't think this works

    public int findK(String a, String b) {

        int[] count_a = new int[256];

        int[] count_b = new int[256];

        for (int i = 0; i < a.length(); i++) {

            count_a[a.charAt(i)]++;

        }

        for (int i = 0; i < b.length(); i++) {

            if (count_a[b.charAt(i)] == 0)

                count_b[b.charAt(i)] --;

            else

                count_b[b.charAt(i)] ++;

        }

        StringBuffer sb_b = new StringBuffer();

        for (int i = 0; i < b.length(); i++) {

            if (count_b[b.charAt(i)] > 0)

                sb_b.append(b.charAt(i));

        }

        String t_b = encode(sb_b.toString());

        int min = Integer.MAX_VALUE;

        for (int i = 0; i <t_b.length(); i++) {

            if (t_b.charAt(i) <= '9' && t_b.charAt(i) >= '0')

                min = Math.min(min, t_b.charAt(i) - '0');

        }

        return min;

    }

    public String encode(String s) {

        StringBuffer sb = new StringBuffer();

        for (int i = 0; i < s.length(); i++) {

            int counter = 1;

            while (i+1 < s.length() && s.charAt(i) == s.charAt(i+1)) {

                counter++;

                i++;

            }

            sb.append(counter);

            sb.append(s.charAt(i));

        }

        return sb.toString();

    }

    public static void main(String[] args) {

        String a = "XYX";

        String b = "XXadhflakjhelXXzzqqkkpoYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhhXX";

        System.out.println(new Zenefits().findK(a,b));

    }

https://instant.1point3acres.com/thread/133828
Read full article from Zenefits 一道面试题 | 书脊