优步面经
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
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。
做tiny url
其实就是转换成base 62的数。
Spiral Array Print
1，Run-Length Encoding，就是把aaabbcccaaaa变成3a2b3c4a这样，要求encode后的信息要比原来的短。
首先暴力扫描之。然后问有什么问题，答曰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
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层面 – 摊手）
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);}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的数。
Spiral Array Print
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; }}
形式化来说，给N个未排序的数组，找出全局中位数。
应用场景是，有N个hosts，每隔一段时间就会报告一些参数，比如qps和平均延迟等，现有某个用于monitor的机器收集信息，并且返回特定时间段内同一参数所有数据的的中位数。
先给brute force，对所有数据排序然后找中位数。
应用场景是，有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
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。
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(); }4. design一个uber eat。说是system design结果我感觉更像product design
5. engineering manager. 一个老中 刚来没多久。问了我许多问题结果感觉对我不大满意。比如问我写service到底理解到多deep。data storage平时接触没（确实没怎么 – 都在application层面 – 摊手）
