Massive Algorithms: Zenefits Interview

http://shibaili.blogspot.com/2015/09/zenefits-interview-questions.html
问个Zenefits电面题目，他家好难。。。 - 未名空间(mitbbs.com)
String s1 = "
waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc";
String s2 = "a+b+c-";

s2的形式是一个字母加上一个符号，正号代表有两个前面的字符，负号代表有四个，也
就是说s2其实是"aabbcccc"，不考虑invalid。
在s1中，找出连续或者不连续的s2，也就是说从s1中找出"aa....bb.....cccc"，abc顺
序不能变，但是之间可以有零个或多个字符，返回共有多少个。在上面这个例子中，有
四个。

But the trick here is you need to group some chars together and treat them
as ONE element. For example, group aa, bb, and cccc together.

And for S1, bbb needs to break down as "bb" and "bb".
bbbb needs to break down as "bb", "bb", and "bb".
http://www.mitbbs.com/article_t1/JobHunting/32952623_0_1.html

如果 m << n，用贪心法加堆实现O(mlogn)更好

OA只要能过就行了，选最容易编程的，未必要最优化

第一道，用heap，每次选最大的出来，相加就可以了
这题没啥好说的，先排序，从最多的开始卖，因为票价规律递减，所以用了等差数列公
式；需要考虑类似于只需买一张票，但能从多个窗口买的这种情况...
第一题用最大堆maxheap，
每次取top的值val，max = max + val； val = val - 1; 将val插入maxheap。

这样的动作重复m次，return max.

2.第二题，给一组String[](容量<10000)，求每一个String(长度<100)在其自己的
Permutation Sequence中的序号

Input: // String[]
cab
babc

Output: //返回 int[], index starting from 0
4        //{abc, acb, bac, bca, 【cab】, cba}
3        //{abbc, abcb, acbb, 【babc】,.....}

//注意，String内有重复的Character，但 Permutation Sequence 只保留distinct记录

http://www.mitbbs.com/article_t/JobHunting/33043355.html
A, B两个String
//example
A = XYZ;
A^2 = XXYYZZ;
A^3 = XXXYYYZZZ;

B = XXadhflakjhelXXzzqqkkpoYYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhh

A^2 是B的subsequence, 所以
return k = 2;
对于某一个特定的k，判断B中有没有A^k是一个线性O(n)的问
题。并且k有解则对于所有的i<k，i都有解。所以可以用二分查找来找到k。先看k = 1
有乜解，然后看k = 2, 4, 8, ...一直找到最终的k. O(n*log(k))。

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.
Read full article from 问个Zenefits电面题目，他家好难。。。 - 未名空间(mitbbs.com)

Zenefits Interview - mitbbs

Labels

Popular Posts