## Saturday, November 28, 2015

### Zenefits Interview Misc

/*//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*/

1. Longest Chain

int longest_chain(String[] w) {
int len = w.length;
if (len == 0) return 0;
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);
else{
Set<String> curSet = new HashSet();
allWd.put(curLen, curSet);
}
}
// search from certain length of words
for (int i = maxLen; i > maxCLen; 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;
}

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