Email domain address typo, need to figure out and return correct domain name. e.g. yhaoo–> yahoo, giaml –> gmail, hmailot–> hotmail.
Solution: HashMap, key as sorted string, value as correct email domain.
其实是anagram
public String getEmail(String s) {
Map<String, String> map = new HashMap<String, String>();
//init the map with the string
String[] email = {"yahoo", "gmail", "hotmail" ..};
for (String e : email) {
map.put(sortByChar(e), e);
}
if (map.containsKey(sortByChar(s)) {
return map.get(sortByChar(s));
}
return null;
}
private String sortByChar(String s) {
char[] charArray = s.toCharArray();
Arrays.sort(charArray);
return new String(charArray);
}
Elevator Design
Design Uber, web service, API, database.
given a > b, b > c, if pass in c > a return false, if a > c return true
感觉像是topological sort，实际上直接dfs就可以，因为只要找到了back edge，就说明顺序是不对的
如果对于cross edge，假设我们认为cross edge return false的话，就好办了，我们只需要按顺序搜，搜到了的话就return true，不然就return false。如果相反的话，我们就要把input反过来，如果搜到了就return false，不然就return true。这里假设input保证没有loop。
public boolean checkOrder(char c1, char c2, List<Char[]> orders) {
Map<Character, Set<Character>> adjMatrix = new HashMap<Character, Set<Character>>();
for (Char[] pair : orders) {
char from = pair[0];
char to = pair[1];
Set<Character> set = null;
if (!adjMatrix.containsKey(from)) {
set = new HashSet<Character>();
adjMatrix.put(from , set);
} else {
set = adjMatrix.get(from);
}
set.add(to);
}
Set<Character> visited = new HashSet<Character> visited;
return dfsFind(adjMatrix, c1, c2);
}
private boolean dfsFind(adjMatrix, char start, char target) {
if (start == target) {
return true;
}
Set<Character> curr = adjMatrix.get(start);
for (Character c : curr) {
if (dfsFind(adjMatrix, c, target)) {
return true;
}
}
return false;
}
做tiny url
其实就是转换成base 62的数。
public String getUrl(int id) {
if (id == 0) {
return null;
}
List<Character> list = new ArrayList<Character>();
for (char c = '0'; c <= '9'; c++) {
list.add(c);
}
for (char c = 'a'; c <= 'z'; c++) {
list.add(c);
}
for (char c = 'A'; c <= 'Z'; c++) {
list.add(c);
}
StringBuilder sb = new StringBuilder();
while (id != 0) {
int idx = id%62;
sb.insert(0, list.get(idx));
id /= 62;
}
return sb.toString();
}
Spiral Array Print
public void printSpirialMatrix(int [][] matrix) {
if (matrix == null || matrix.length == 0) {
return
}
int sR = 0;
int eR = matrix.length-1;
int sC = 0;
int eC = matrix[0].length-1;
while(sR <= eR && sC <= eC) {
//first row
for (int i=sC; i<eC; i++) {
print(matrix[sR][i]);
}
//right col
for (int i=sR; i<eR; i++) {
print(matrix[i][eC]);
}
//bottom row
if (sR < eR) {
for(int i=eC; i>sC; i--) {
print(matrix[eR][i];
}
}
//left col
if (sC < eC) {
for (int i=eR; i>sR; i--) {
print(matrix[i][sC]);
}
}
sR++;
eR--;
sC++;
eC--;
}
}
电面：
String Break
将一个String分成若干个substring，每个substring有大小限制k，且在末尾有固定格式代表这是第几个substring
Example: “this is a string” -> “this is (1/2)” “a string (2/2)”
这道题就是数学题了
如果总的长度是n，假设每个string 分别是k个那么大，但是由于需要在后面append长度信息。所以不可以直接除以k, 而要加上append的信息，那么我们假设append的信息的长度是l, 那么最多可以将整个string 分成power（10， l） 份。
l*2 + 3 + n/(10^l) <= k
int n = s.length();
int l = 1;
while(l*2 + 3 + n/(10^l) > k) {
l++;
}
List<String> res = new ArrayList<String>();
//now we have l (the space to store extra)
int parts = Math.ceiling(n/(float)(k-l)); //make sure to use float otherwise int division will be used
int start = 0;
int count = 1;
StringBuilder sb = new StringBuilder();
for (int i=0; i<s.length() && start<s.length(); i++) {
if (s.charAt(i) == ' ') {
String tmp = s.substring(start, i);
if (sb.length() + tmp.length() + 1 > k - 2*l - 3) {
sb.append(String.valueOf(count));
sb.append('/');
sb.append(String.valueOf(parts));
count++;
res.add(sb.toString());
sb = new StringBuilder();
}
sb.append(tmp);
sb.append(" ");
start = i+1;
}
}
//what was left in sb;
if (sb.length() != 0) {
sb.append(String.valueOf(count));
sb.append('/');
sb.append(String.valueOf(parts));
res.add(sb.toString());
}
return res;
}
题目就是flatten json to a list of map, 有一段json，比如说如下：
{
“uuid”: “abc”,
“properties”: {
“sessionName”: “Test session name”
“waypoints”: [
{“uuid”: “def”, “properties”: {“latitude”: 3}}
]
}
}
把它转化成List<Map>， map里面uuid是key, properties是value。 所以结果应该像下面
[
{“uuid”: “abc”, “properties”: {“sessionName”: “Test session name”, “waypoints”: [“def”]}},
{“uuid”: “def”, “properties”: {“latitude”: 3}},
…
]
其实就是recursion求，每次把一个object放进map以后，要用一个recursive的function 处理一下每个attribute。如果是array的话要recursive的把array里的所有object都放进res里面，并且对每个object再进行recursion
public class Solution {
public List<Map<String, Object>> flatternJSON(String jsonString) {
JSONParser parser = new JSONParser();
List<Map<String, Object>> res = new ArrayList<Map<String, Object>>();
try {
JSONObject jObj = (JSONObject)parser.parse(jsonString);
Map<String, Object> map = new HashMap<String, Object>();
String key = (String) jObj.get("uuid");
Object value = jObj;
map.put(key, jObj);
recursiveProcess(jObj, res);
return res;
} catch (ParseException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
return null;
}
private void recursiveProcess(JSONObject jObj, List<Map<String, Object>>res) {
Iterator iter = jObj.keySet().iterator();
while(iter.hasNext()) {
String key = (String) iter.next();
Object obj = jObj.get(key);
if (obj instanceof String) {
continue;
} else if (obj instanceof JSONArray) {
JSONArray array = (JSONArray)obj;
Iterator arrIter = array.iterator();
JSONArray newArray = new JSONArray();
while(arrIter.hasNext()) {
JSONObject o = (JSONObject) arrIter.next();
newArray.add(o.get("uuid"));
Map<String, Object> map = new HashMap<String, Object>();
map.put((String) o.get("uuid"), obj);
res.add(map);
recursiveProcess(o, res);
}
jObj.put(key, newArray);
} else {
recursiveProcess((JSONObject)obj, res);
}
}
}
}
}
1，Run-Length Encoding，就是把aaabbcccaaaa变成3a2b3c4a这样，要求encode后的信息要比原来的短。
public String encode(String s) {
int start = 0;
StringBuilder res = new StringBuilder();
for (int i=1; i<=s.length(); i++) {
if (i == s.length() || s.charAt(i) != s.charAt(start)) {
if (i - start > 2) {
res.append(String.valueOf(i-start));
res.append(s.charAt(start));
} else {
res.append(s.substring(start, i));
}
start = i;
}
}
return res.toString();
}
首先暴力扫描之。然后问有什么问题，答曰decode的时候111aaa会encode成313a然后decode成313个a。提出每encode一个就插入一个特殊符号标记，他说可以。然后追加问是否可以不用特殊符号，答曰创建新的计数单位，比如用A代表1B代表2，然后aaa就变成Ca（you get the idea），这样就不需要插入额外符号了。
3. Coding Question，用的coderPad, 比较两个Map Object，Map的Value可能有两种情况
1. Strings; 2. Map objects
public boolean compare(Object obj1, Object obj2) {
if (obj1 instance of String && obj2 instance of String) {
return (String)obj1.equals((String)obj2);
}
if(obj1 instance of Map<String, Object> && obj2 instance of Map<String, Object>) {
Map<String, Object> map1 = (Map<String, Object>) obj1;
Map<String, Object> map2 = (Map<String, Object>) obj2;
if (map1.size() != map2.size()) {
return false;
}
Iterator iter = map1.keySet().iterator();
while (iter.hasNext()) {
String key = (String)iter.next();
if (!map2.containsKey(key)) {
return false;
}
if (!compare(map1.get(key), map2.get(key)) {
return false;
}
}
return true;
}
}
Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.
The input string does not contain leading or trailing spaces and the words are always separated by a single space.
For example,
Given s = “the sky is blue”,
return “blue is sky the”.
Could you do it in-place without allocating extra space?
public String reverse(String s) {
//reverse the whole string
int start = 0;
int end = s.length()-1;
StringBuilder sb = new StringBuilder(s);
while (start < end) {
swap(sb, start, end);
start++;
end--;
}
//reverse word by word separated by space
int start = 0;
for (int i=0; i=<sb.length(); i++) {
if (i==s.length() || s.charAt(i) == ' ') {
reverseBetween(sb, start, i-1);
start = i+1;
}
}
return sb.toString();
}
private void swap(StringBuilder sb, int i, int j) {
char tmp = sb.charAt(i);
sb.setCharAt(i, sb.charAt(j);
sb.setCharAt(j, tmp);
}
private void reverseBetween(StringBuilder sb, int s, int e) {
while(s < e) {
swap(sb, s, e)；
s++;
e--;
}
}
形式化来说，给N个未排序的数组，找出全局中位数。
应用场景是，有N个hosts，每隔一段时间就会报告一些参数，比如qps和平均延迟等，现有某个用于monitor的机器收集信息，并且返回特定时间段内同一参数所有数据的的中位数。
先给brute force，对所有数据排序然后找中位数。
一个stream找中位数的话，可以用两个heap，一个minHeap保存大一半的数，另外一个maxHeap保存小的一半的中位数。如果新来一个数的话，我们看他是比minHeap和maxHeap最大的数比较，然后加进其中一个heap，如果在两个之间的话，假设我们就放进minHeap里，然后需要平衡一下两个heap，保证minHeap和maxHeap的size是相同的。
class MedianFinder {
PriorityQueue<Integer> minHeap;
PriorityQueue<Integer> maxHeap;
public MedianFinder() {
this.minHeap = new PriorityQueue();
this.maxHeap = new PriorityQueue(10, Collections.reverseOrder());
}
public void addData(int i) {
if (i >= minHeap.getFirst()) {
minHeap.add(i);
} else (
maxHeap.add(i);
}
//rebalance two heaps
if (minHeap.size() - maxHeap.size() == 2) {
int tmp = minHeap.removeFirst();
maxHeap.add(tmp);
} else if (maxHeap.size() - minHeap.size() == 2) {
int tmp = maxHeap.removeFirst();
minHeap.add(tmp);
}
}
public int getMedian() {
if (minHeap.size() == maxHeap.size()) {
return (minHeap.getFirst() + maxHeap.getFirst())/2
}
return minHeap.size() > maxHeap.size() ? minHeap.getFirst() : maxHeap.getFirst();
}
}
search element in a roated sorted array. leetcode
Word Ladder II
这道题的idea是先用bfs找到最短路径，然后dfs找出所有的结果。
第一轮： Happy number
第二轮： 罗马数字 -> 阿拉伯数字
Happy number就是按照happy number的算法一直算，但是要注意已经visited过了的要记下来，
罗马数字转换成阿拉伯数字的话，就是要一个Map，然后注意每次greedy pick最大的那个数append到结果的右边即可
1. 设计excel， 先实现基本功能再优化（比如存图片怎么弄）
2. 给一个tuple list, 按weight random select. 比如给 [(“hello”, 2.34), (“world”, 4.68)…] world出现的概率是hello的两倍.
第二题, reverse string的变种。 只reverse word不reverse punctuation。比如 “this,,,is.a word” -> “word,,,a.is this”
这道题可以考虑用两个stack，一个用来reverse word，另外一个保存punctuation。
public String reverse(String s) {
Stack<String> wStack = new Stack<String>();
Queue<String> pQueue= new LinkedList<String>();
int start = 0;
boolean isChar = true;
int end = 0;
for (int i=0; i<s.length(); i++) {
char c = s.charAt(i);
if (!Character.isLetter(c)) {
if (isChar) {
wStack.push(s.substring(start, i));
start = i;
isChar = false;
} else {
continue;
}
} else {
if (isChar) {
continue;
} else {
pQueue.add(s.substring(start, i));
start = i;
isChar = true;
}
}
}
//last word or punctuation
if (isChar) {
wStack.push(s.substring(start));
} else {
pQueue.add(s.substring(start));
}
//form the new string, assuming always start with a word
StringBuilder sb = new StringBuilder();
while (!wStack.isEmpty()) {
sb.append(wStack.pop());
if (!pQueue.isEmpty()) {
sb.append(pQueue.remove());
}
}
return sb.toString();
}
3. bar raiser. 是一个front end engineer （我面的是backend）但要我把我的project给他讲清楚。结果不讲不知道一讲吓一跳，backend懂得比我还多
4. design一个uber eat。说是system design结果我感觉更像product design
5. engineering manager. 一个老中 刚来没多久。问了我许多问题结果感觉对我不大满意。比如问我写service到底理解到多deep。data storage平时接触没（确实没怎么 – 都在application层面 – 摊手）。
Delete and insert in a binary tree
class TreeNode {
TreeNode left;
TreeNode right;
int val;
public TreeNode(int v) {
this.val = v;
}
}
class Solution {
public static void main(String[] args) {
Solution s = new Solution();
TreeNode root = new TreeNode(3);
s.insert(root, 2);
s.insert(root, 3);
s.insert(root, 4);
s.insert(root, 5);
s.insert(root, 6);
assert s.contains(root, 6) != null;
s.delete(root, s.contains(root, 6));
assert s.contains(root, 6) == null;
System.out.println("Success");
}
public TreeNode insert(TreeNode n, int v) {
if (n == null) {
return new TreeNode(v);
}
if (v > n.val) {
TreeNode t = insert(n.right, v);
n.right = t;
} else if (v < n.val) {
TreeNode t = insert(n.left, v);
n.left = t;
}
return n;
}
public TreeNode delete(TreeNode root, TreeNode n) {
if (root.val == n.val) {
if (root.left == null) {
return root.right;
}
if (root.right == null) {
return root.left;
}
TreeNode l = findLeft(root.right);
int tmp = root.val;
root.val = l.val;
l.val = tmp;
delete(root.right, l);
return root;
} else {
if (n.val < root.val) {
root.left = delete(root.left, n);
} else {
root.right = delete(root.right, n);
}
return root;
}
}
public TreeNode contains(TreeNode root, int value) {
if (root == null) {
return null;
}
if (root.val == value) {
return root;
}
if (value > root.val) {
return contains(root.right, value);
}
return contains(root.left, value);
}
private TreeNode findLeft(TreeNode root) {
if (root.left == null) {
return root;
}
return findLeft(root.left);
}
}
mirror tree
class Solution {
public static void main(String[] args) {
Solution s = new Solution();
TreeNode root = new TreeNode(1);
TreeNode l1 = new TreeNode(2);
TreeNode r1 = new TreeNode(3);
root.left = l1;
root.right = r1;
TreeNode l2 = new TreeNode(4);
TreeNode r2 = new TreeNode(5);
TreeNode r3 = new TreeNode(6);
l1.left = l2;
l1.right = r2;
r1.right = r3;
//api under test
s.mirror(root);
//assertion
assert root.val == 1;
assert root.left.val == 3;
assert root.right.val == 2;
assert root.left.left.val == 6;
assert root.left.right == null;
assert root.right.left.val == 5;
assert root.right.right.val == 4;
System.out.println("Success");
}
public void mirror(TreeNode n) {
if (n == null) {
return;
}
TreeNode tmp = n.left;
n.left = n.right;
n.right = tmp;
mirror(n.left);
mirror(n.right);
}
}
shorten url base 62
Matrix Region Sum
http://www.ardendertat.com/2011/09/20/programming-interview-questions-2-matrix-region-sum/
First preprocess so each matrix contains the sum from left most to the current index, then calculating the sum of a certain region will be the sum bottom right – bottom left – top right + top left.
http://www.ardendertat.com/2011/09/20/programming-interview-questions-2-matrix-region-sum/
subsets
class Solution {
public static void main(String[] args) {
Solution s = new Solution();
List<Integer> test = new ArrayList<Integer>();
test.add(1);
test.add(2);
test.add(3);
List<List<Integer>> res = s.subsets(test);
for (List<Integer> l : res) {
for(int i : l) {
System.out.print(i);
System.out.print(',');
}
System.out.print('\n');
}
System.out.println("Success");
}
public List<List<Integer>> subsets(List<Integer> input) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if (input.size() == 0) {
res.add(new ArrayList<Integer>());
return res;
}
for (int i=0; i<input.size(); i++) {
List<Integer> next = new ArrayList<Integer>(input);
next.remove(i);
List<List<Integer>> list = subsets(next);
for(List<Integer> l : list) {
l.add(0, input.get(i));
res.add(l);
}
}
return res;
}
}
combination:
class Solution {
public static void main(String[] args) {
Solution s = new Solution();
List<Integer> test = new ArrayList<Integer>();
test.add(1);
test.add(2);
test.add(3);
List<List<Integer>> res = s.combination(test, 2);
for (List<Integer> l : res) {
for(int i : l) {
System.out.print(i);
System.out.print(',');
}
System.out.print('\n');
}
System.out.println("Success");
}
public List<List<Integer>> combination(List<Integer> input, int k) {
if (k > input.size()) {
return null;
}
List<List<Integer>> res = new ArrayList<List<Integer>>();
if (k == input.size()) {
res.add(input);
return res;
}
if (k == 0) {
res.add(new ArrayList<Integer>());
return res;
}
for (int i=0; i<input.size(); i++) {
int curr = input.get(i);
List<Integer> next = new ArrayList<Integer>();
for (int j=i+1; j<input.size(); j++) {
next.add(input.get(j));
}
List<List<Integer>> list = combination(next, k-1);
if (list != null) {
for (List<Integer> l : list) {
l.add(0, curr);
res.add(l);
}
} {
}
return res;
}
}
1. regex match (假设*match to any number of character proceeding it while ? match any character) use dynamic programming.
public boolean regMatch(String s, String p) {
int [][] match = new int[p.length()+1][s.length()+1];
for (int i = 0; i<p.length(); i++) {
for (int j=0; jyes,
lockern->false.
6. HM闲聊，问项目哪里吸引我，为什么Uber。
1. 3个长度一样的array a1, a2, a3, 找出所有 A + B = C 的组合，A在a1里，B在a2，C在a3里；扩展到4个数组 a2, a2, a3, a4，找出A+B+C=D的组合。。 然后扩展到n各数组；做完了又给了一道题目，不难，忘了。。
这道题就可以从两个array开始，有两种办法，一种是将其中一个arry做成hashset,然后用另外一个array去一个一个尝试，或者将两个array都sort，然后一个从start开始，一个从end开始，分别从前往后和从后往前走，看能不能碰到target的值
public List<List> getSum(List a1, List a2, int target) {
Set set = new HashSet();
List<List> res = new ArrayList<List>();
for(int i=0; i<a1.length; i++) {
set.add(a1[i]);
}
for(int i=0; i<a2.length; i++) {
if (set.containsKey(target – a2[i])) {
List r = new ArrayList();
r.add(target – a2[i]);
r.add(a2[i]);
res.add(r);
}
}
return res;
}
public List<List> getArraySum(List a1, List a2, List a3) {
List<List> res = new ArrayList<List>();
for(int i=0; i<a3.length; i++) {
List<List> r = getSum(a3[i]);
res.addAll(r);
}
return res;
}
2. 一个系统里面，有user 在不断的login and logout, 现在给你几组user的（username, login_time, logout_time)的数据，打印出各个时间
点系统有几个active user；follow-up，修改我的实现，让我的函数支持 类似JS的callback机制.
//first sort by startTime, then by endTime. Use a heap to calculate the number of active users at the same time.
class User {
int uid;
int start;
int end;
}
class void printActiveUser(List users) {
Collection.sort(users, new Comparator(){
@Override
public int compare
3. 面我的是一个中国人神牛。因为我说我用c++,然后感觉他临时选了这道题给我。。 reader-writer problem. 用mutex 实现user-writer problem。 follow-up，问会有什么问题，其实会有starving 的情况发生，然后一起商量怎么处理.
Hello World 