优步面经 | Hello World

优步面经 | Hello World

Solution: HashMap, key as sorted string, value as correct email domain. 其实是anagram 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 orders) { Map> adjMatrix = new HashMap>(); for (Char[] pair : orders) { char from = pair[0]; char to = pair[1]; Set set = null; if (!adjMatrix.containsKey(from)) { set = new HashSet(); adjMatrix.put(from , set); } else { set = adjMatrix.get(from); } set.add(to); } Set visited = new HashSet visited; return dfsFind(adjMatrix, c1, c2); } private boolean dfsFind(adjMatrix, char start,

Read full article from 优步面经 | Hello World