Hello friends,
Just got informed that I have passed the phone interview from Facebook, so I want to share the phone interview experience with you all.
1. Introduce yourself and past work experience to start things off.
2. Code questions:
A. Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. For example, given s = "leetcode", dict = ["leet", "code"]. Return true because "leetcode" can be segmented as "leet code".
public class Solution {
private int getMaxLength(Set<String> dict) {
int maxLength = 0;
for (String word : dict) {
maxLength = Math.max(maxLength, word.length());
}
return maxLength;
}

public boolean wordBreak(String s, Set<String> dict) {
if (s == null || s.length() == 0) {
return true;
}

int maxLength = getMaxLength(dict);
boolean[] canSegment = new boolean[s.length() + 1];

canSegment[0] = true;
for (int i = 1; i <= s.length(); i++) {
canSegment[i] = false;
for (int lastWordLength = 1;
lastWordLength <= maxLength && lastWordLength <= i;
lastWordLength++) {
if (!canSegment[i - lastWordLength]) {
continue;
}
String word = s.substring(i - lastWordLength, i);
if (dict.contains(word)) {
canSegment[i] = true;
break;
}
}
}

return canSegment[s.length()];
}
}
B.Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) The solution set must not contain duplicate triplets. For example, given array S = {-1 0 1 2 -1 -4}, A solution set is: (-1, 0, 1) (-1, -1, 2)
public class Solution {

public ArrayList<ArrayList><Integer>> threeSum(int[] num) {

ArrayList<ArrayList><Integer>> rst = new ArrayList<ArrayList><Integer>>();
if(num == null || num.length < 3) {
return rst;
}
Arrays.sort(num);
for (int i = 0; i < num.length - 2; i++) {
if (i != 0 && num[i] == num[i - 1]) {
continue; // to skip duplicate numbers; e.g [0,0,0,0]
}

int left = i + 1;
int right = num.length - 1;
while (left < right) {
int sum = num[left] + num[right] + num[i];
if (sum == 0) {
ArrayList<Integer> tmp = new ArrayList<Integer>();
tmp.add(num[i]);
tmp.add(num[left]);
tmp.add(num[right]);
rst.add(tmp);
left++;
right--;
while (left < right && num[left] == num[left - 1]) { // to skip duplicates
left++;
}
while (left < right && num[right] == num[right + 1]) { // to skip duplicates
right--;
}
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return rst;
}
}
3. last but not least give reasons why do you want to work for Facebook?
These are basically the questions that I encountered during the interview, hope they will help you all in some way. Peace!