F onsite interview | Hello World

F onsite interview | Hello World

Palindrome with spaces, what if the string is super long.

Design a system that find the places near given coordinates. What if there are billions of places.

Merge Intervals

In order traversal all the leaves of two arbitrary tree, see if two trees are the same.

print binary tree in vertical order
这道题的要点在于记下每个node到root的距离，左边记为负右边记为正。我们需要traverse一次tree，如果我们能够traverse一次，那么（不论用什么顺序）都可以记录下每个node的距离,然后可以把这个距离放在一个hashmap里。通过这个过程我们还可以找到最小的距离（负最大的距离）。然后我们只要再traverse一次tree，这次用level order traversal，每次traverse一层的话就把那一层的node都按照之前的dist放入一个array中（array 的index只要用当前距离减去（负的）最小距离即可算出）。然后就完成了。

或者可以有更好的办法，我们第一遍就用level order traversal计算距离，每次计算出的距离存进一个以距离为key，list of treenode为value的map里。因为是level order traversal，所以我们可以保证同一个距离加入list的顺序一定是从上到下的。同样我们计算最大和最小距离。最后iterate 所有的从最大到最小的key，然后打印每个key存的list即可
find the first bad version

Design question：
被问到update一个手机app的new feature和一个web service的new feature有啥差别；按时间deploy还是按feature deploy等。
我想出来的就是如果deploy 手机app的new feature，要经过apple store或者android store的审核，这个new feature是compiled， 所以需要非常慎重，一旦release但是发现了bug的话会非常难修复。
web service的release的好处在于可以随时release和修复bug，因为deployment就在自己的server上。但是同样有问题，如果你有很多server的话，怎样保证同步，怎样保证server的连续性，以前的代码和新的代码要互相兼容。

一道coding是寻找第一个bad version。

给一个dataset，将它转化成Json format 不考虑括号和考虑括号的情况。
这个问题可以这样看，给一个Object，这个object可能是primitive type的，假设就是string，也可能是一个包含primitive type和其他Object的一个合集，怎样把它encode成一个长的string。方法就是用DFS，用recursion的写法写出来很简单。
假设一个Object class
public class Object {
boolean isPrimitive //can be replaced by attributes.isEmpty();
String value;
List attributes;
}

public String jsonEncode(Object o) {
if (o.isPrimitive) {
return o.value;
}
StringBuilder result = new StringBuilder();
foreach(Object a : o.attributes) {
result.append(jsonEncode(a));
}
return result.toString();
}

Read full article from F onsite interview | Hello World