Zenefits Interview Misc

http://www.1point3acres.com/bbs/thread-145166-1-1.html
一个matrix, 1代表机器人，0代表通路，x代表路障，求到所有机器人距离和最小的一点
需要注意的是机器人本身也是通路的一部分，可以通过他到达其他机器人，甚至最小点
也可以和机器人在同一个点上。
另外如果被路障围起来的点不能被算进来

面试时先介绍一下自己，问几个行为问题，然后讲题目思路，这样就差不多过了半小时，后面写程序时间有点紧，
所以介绍时尽量简短一点。
说思路的时候，说了bfs, dfs，面试官说bfs好，又问内存用多少，答O(m*n), 要求节省内存，但我没有想出来不用queue做bfs，
现在想内存最多是O(m + n)应该已经很好了。不过后来又用了一个存距离和判断访问过的二维数组，所以应该还是需要O(m*n),
不知道有什么办法节省。后来面试官没有深究。
基本思路就是找到一个机器人位置，从这点开始bfs, 把所有点到这个机器人的距离加到dis数组，最后扫一遍看看谁距离最短就返回
这点。

/*//problem: robot merge point
//input:
//robot: 1
//obstacle: X
[
0   0   0   M   1
0   1   X   0   0
0   X   0   0   0
0   0   0   1   0
0   0   0   0   0
//output:
//best merge point: M
3 + 1 + 3 = 7
Definition: Best merge point: minimal sum of path num between robots and merge point*/

这个题最优解法就是以每个robot为源点都做一遍bfs，然后把和加起来找个最小的
http://www.1point3acres.com/bbs/thread-145290-1-1.html
1. Longest Chain
给定一个词典， 对于里面单词删掉任何一个字母，如果新单词还在词典里，就形成一个 chain：old word -> new word, 求最长长
比如给List<String> dict = {a,ba,bca,bda,bdca} 最长是4：bdca->bda->ba->a；


我用的map<Integer (length)，set<String>> 先字典里的词放到map里，然后从最长的词的set里开始recursive call，直到搜到长度是1的里面或者找不到了，int变量记录最长结果。

        int longest_chain(String[] w) {
        int len = w.length;
        if (len == 0) return 0;
        Queue<String> cBuf = new LinkedList();
        Map<Integer, Set<String>> allWd = new HashMap();
        int maxLen = 0;
        int maxCLen = 0;
        // find the longest length of strings in w
        for (int i = 0; i < w.length; i++){
            int curLen = w[i].length();
            maxLen = Math.max(maxLen, curLen);
            if (allWd.containsKey(curLen)) allWd.get(curLen).add(w[i]);
            else{
                Set<String> curSet = new HashSet();
                curSet.add(w[i]);
                allWd.put(curLen, curSet);
            }
        }
        // search from certain length of words
        for (int i = maxLen; i > maxCLen; i--){
            cBuf = new LinkedList(allWd.get(i));
            // start from initial set of words to search for chain
            int clen = 0;
            while (!cBuf.isEmpty()){
                clen++;
                Set<String> nextSet = allWd.get(i - clen);
                if (nextSet == null) break;
                int count = cBuf.size();
                for (int h = 0; h < count; h++){
                    String t = cBuf.poll();
                    // get next string by deleting one letter
                    for (int l = 0; l < t.length(); l++){
                        String tt = t.substring(0, l) + t.substring(l + 1);
                        if (nextSet.contains(tt)){
                            cBuf.offer(tt);
                            nextSet.remove(tt);
                        }
                    }
                }
            }
            maxCLen = Math.max(maxCLen, clen);
            i -= Math.max(clen - 1, 0);
        }
        return maxCLen;
    }

http://www.1point3acres.com/bbs/thread-147870-1-1.html
一道是比较绕的kth permutation，一道是分数化简，主要考greatest common divsor

find lake。想必大家应该耳熟能详。0表示水，1表示陆地，小哥一直强调lake是只被同一个island围绕的水，边界不算lake。后来冷静了想想，如果是lake的话，也只能被同一个island包围吧。
http://www.jiuzhang.com/qa/19/

第一步，从边缘处将所有的0用bfs遍历，标记成1，即把所以的大海变成陆地。
第二步，从边缘处将所有的1（包括大海变过来的1）用bfs遍历，标记成2，即去掉所有的陆地。（这样可以去掉大海中的小岛）
第三部，再对剩下所有为1的小岛进行遍历，找到一个，结果加一。（剩下的0全部为湖，剩下的1全部为湖中小岛）

设计data structure，里面含有两个函数 add(int x)，表示值x出现。 int rank(int y)， 返回当前时刻比y小的所有值，大家参见这个题目：http://www.lintcode.com/en/probl ... mber-before-itself/我用segment tree做的，不满意。说spatial cost太大。然后说可以用binary tree with count做（我是看了这篇文章的想法 http://www.geeksforgeeks.org/cou ... ents-on-right-side/），但是烙印不置可否。

1+2-3/4*5"  算结果，老题了。follow up是加上括号以后怎么处理，没写code。然后recurring decimal，没写完code