FB interview

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();
}

第二道题:
面试官说是道新题 finding ali baba
就是ali baba是个怪兽,他可能在[0,1, …, numCaves-1]出现,他每隔一天就要换
一个地方,但他每次只能移左右一格。
然后给你一个strategy[]数组,数组里面是猜测每天ali baba的位置。如果里面有一个
猜中了,这个strategy就是正确的。
问题就是让你写一个判断函数 alibaba(int numCaves, int[] strategy)来判别这个
strategy数组是不是稳赢的策略。写完后问时间复杂度,然后问了下大概怎么样可以优.
化~~~

因为这个策略必须要cover所有的情况才算稳赢,所以我们要假设怪兽可以在任何一个cave里出现。

for (int i=0; i<numCaves; i++) {
  if (!isCovered(i, numCaves, 0, strategy)) {
    return false;
  }
}
return true;

private boolean isCovered(int i, int numCaves, int day, int[] strategy) {
  if (day >= strategy.length) {
     return false;
  }
  if (strategy[day] == i) {
    return true;
  }
  if (i+1 < numCaves && isCovered(i+1, numCaves, day+1, strategy) {
    return true;
  }
  if (i-1 >= 0 && isCovered(i-1, numCaves, day+1, strategy) {
    return true;
  }
  return false;
}

但是这样会有很多重复的计算,因为某一天怪物在某个位置如果知道他可以/不可以cover,就没必要再算一遍了,所以可以用dp优化。

covered[i][j] 表示怪兽在第i天位置j是否被strategy cover了, 他是true的条件就是covered[i+1][j-1] && covered[i+1][j+1] (他的第二天的所有可能位置都被cover了),或者是strategy[i] == j (就被当前strategy cover了)

所以code写出来就是

boolean[][] covered = new boolean[strategy.length][numCaves];
boolean res = true;
for (int i=strategy.length-1; i>=0; i++) {
  for(int j=0; j<numCaves; j++) {
    if (strategy[i] == j) {
      covered[i][j] = true;
    } else {
      boolean left = true;
      boolean right = true;
      if (i+1 < strategy.length) {
        if (j > 0) {
          left = covered[i+1][j-1];
        }
        if (j < numCaves-1) {
          right = covered[i+1][j+1];
        }
      }
      covered[i][j] = left && right;
    }
    if (i == 0) {
      //all the possible positions at day 0 should be covered 
      res &= covered[i][j];
    }
  }
}
return res;

刚刚面完的一个Facebook电面 感觉很不好 应该挂了 没有见过的题 面试官是个俄罗斯或者欧洲人 Site Integrity Infrastructure team
口音过得去 但是还是听了挺久问题

给一个vector 里面的元素表示task type,给一个N,表示执行相同task时要等上N个单位时间 例子中用‘_’表示

// [1,2,1,2], N=3
// 1,2,_,_,1,_,_,2–> 6

// [1,2,1,2], N=2
// 1, 2, _, 1,2–> 5

public int getMinTime(int[] tasks, int n) {
  Map<Integer, Integer> map = new HashMap<Integer, Integer>();
  int time = 0;
  for (int i=0; i<tasks.length; i++) {
    int t = tasks[i];
    if (map.containsKey(t)) {
      if (time - map.get(t) > n) {
        map.put(t, time);
      } else {
        i--;
      }
    } else {
      map.put(t, time);
    }
    time++;
  }
  return time;
}

validate BST

TreeNode pre = null
public boolean validateBST(TreeNode root) {
  //in order traversal to search
  return validHelper(pre root);
}

private boolean validHelper(TreeNode root) {
  if (root == null) {
    return true;
  }
  if (!validHelper(pre, root.left)) {
    return false;
  }
  if (pre != null) && (pre.val < root.val) {
    pre = root;
  } else {
    return false;
  }
  return validHelper(pre, root.right);
}

Given a string with parentheses, return a string with balanced parentheses by removing the fewest characters possible. You cannot add anything to the string.

Examples:

balance(“()”) -> “()”
balance(“)(“) -> “”
balance(“(((((“) -> “”
balance(“(()()(“) -> “()()”
balance(“)(())(“) -> “(())”
balance(“)(())(“) != “()()”

就是删去string里面没有close的括号, 值留下close的括号,其实和leetcode的valid parentheses是一样的做法。

public String balance(String s) {
  StringBuilder res = new StringBuilder();
  Stack<Integer> stack = new Stack<Integer>();
  Set<Integer> valid = new HashSet<Integer>();
  for (int i=0; i<s.length(); i++) {
    char c = s.charAt(i);
    if (c == '(') {
      stack.push(i);
    } else {
      if (!stack.isEmpty()) {
         valid.add(stack.pop());
         valid.add(i);
      }       
    }
  }
  for (int i=0; i<s.length(); i++) {
    if (valid.contains(i)) {
      res.append(s.charAt(i));
    }
  }
  return res.toStirng();
}

一道很简单的题,结果自己脑抽,绕进去了
string 有多少palindrome substring。
exp: ‘aba’ 返回4 , ‘abba’ 返回6
一开始想的是用dp做,但是实际上直接遍历即可,但是注意遍历的时候要按每个对称轴,每个半径遍历,这样可以利用palindrome的结果而不用重复计算。

public int countPal(String s) {
int res;
for (int c=0; c= 0 && end = 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
res++;
start–;
end++;
}
}
return res;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s