Archive for August 2013
- In: 面经
- Leave a Comment
想random只能用array,insert remove全O(1)只有hashmap,结合一下就可以了。
public class RandomSetStructure { Map<Integer, Integer> map; List<Integer> array; Random random; public void insert(int a) { if (map.containsKey(a)) return; array.add(a); map.put(a, array.size() - 1); } public void remove(int a) throws Exception{ if (!map.containsKey(a)) throw new RuntimeException(); int index = map.get(a); map.remove(a); array.set(index, array.get(array.size() - 1)); map.put(array.get(index), index); array.remove(array.size() - 1); } public int rand() { if (map.isEmpty()) throw new RuntimeException(); return array.get(random.nextInt(array.size())); } }
- In: 面经
- Leave a Comment
Given a string, find longest substring which contains just two unique characters. 比如ABACDDCB, 返回CDDC。
自己做的O(n)的解法,不用额外空间,但是需要additional data structure。测了几个没问题。
思路:假设d[i – 1]是以arr[i – 1]为结尾的data,已经做好了。那d[i] =
- 如果arr[i]属于d[i – 1]的那个substring中的两个元素中的某一个,那么d[i]的长度直接是上一个加一。
- 不属于的话,要把arr[i]和上一个的“最后一段由一个字母组成的sequance“连起来。比如d[i – 1]的结果是BABB,然后arr[i]是C,就想把BB和C连起来生成新的substring BBC然后放在d[i]里。
- 这样的话,需要记录四个数据:length, index of last sequence ‘s beginning m, the char that is not the last (in above case, is A), and last letter (B)(这个不是必要的,可以用m来读,但是看着方便。
public class Data { int len; Character last; Character notLast; int m;// beginning index of last sequense } String findLongestSubString(String s) { if (s.length() == 0) return null; Data prev = new Data(1, s.charAt(0), null, 0); Data maxData = prev; int maxEnd = 0; for (int i = 1; i < s.length(); i++) { Data curr = new Data(); Character charAtI = s.charAt(i); if (charAtI.equals(prev.last) || prev.notLast == null || charAtI.equals(prev.notLast)) { curr.len = prev.len + 1; curr.notLast = charAtI.equals(prev.last) ? prev.notLast : prev.last; curr.last = s.charAt(i); curr.m = charAtI.equals(prev.last) ? curr.m : i; } else { curr.len = i - prev.m + 1; curr.notLast = prev.last; curr.last = s.charAt(i); curr.m = i; } if (curr.len > maxData.len) { maxData = curr; maxEnd = i; } prev = curr; } String result = s.substring(maxEnd - maxData.len + 1, maxEnd + 1); return result; }
- In: 面经
- Leave a Comment
别用傻乎乎的additional data structure,那样可以做,但是写起来太长。这个题上来的思路就是用左中右的inorder,这样一路下来,prev.next = curr,不断update当前的node为prev。但是写了半天,不知道怎么传prev,因为担心传java reference的问题;又回到了那个IntWrapper tree serialization的题。都是一个类型:https://leetcodenotes.wordpress.com/2013/08/24/phone-serializede-serialize-a-tree/
public void addSuccessor(Node node, Node[] prev) { if (node == null) return; addSuccessor(node.left, prev); if (prev[0] != null) prev[0].next = node; prev[0] = node; addSuccessor(node.right, prev); }
类似题:找tree的in order traversal第x个节点:keep一个current node的index counter,同样是inorder的pattern,到当前node的时候counter++。这个init的i应该是-1,因为第一次找到最左边的节点的时候,i先+1,然后和x比较。
public TreeNode getNthNode(TreeNode node, IntWrapper i, int x) { if (node == null) return null; TreeNode foundAtLeft = getNthNode(node.left, i, x); i.val++; if (i.val == x) return node; if (foundAtLeft != null) return foundAtLeft; return getNthNode(node.right, i, x); }
- In: 面经
- Leave a Comment
对这类题型其实不够熟悉,写了有15分钟才出来,太差了。总结一下。
BST一般找不到就null了,没办法keep track of走到哪个位置的信息。所以多传两个参数,leftBoundary和rightBoundary,分别表示“当前node为root的子树的left boundary – 当前子树的immediate prev)“和“immediate next”。因为你是top down的往下算,所以左右两边的boundary不断narrow down。当node == null时,此时的最靠近自己的boundary就起作用了,找他们之间最接近x的就行了。
这题和判断一棵树是不是BST是一个套路(后面有对比):
public TreeNode getClosest(TreeNode node, TreeNode leftBoundary, TreeNode rightBoundary, int x) { if (node == null) return getClosest(leftBoundary, rightBoundary, x); if (node.val < x) { return getClosest(node.right, node, rightBoundary, x); } else { return getClosest(node.left, leftBoundary, node, x); } } private TreeNode getClosest(TreeNode prev, TreeNode next, int x) { if (prev == null || next == null) return prev == null ? next : prev; if (next.val - x < x - prev.val) return next; else return prev; }
附加:判断一棵树是不是BST,也是一路传下来boundary,不断看当前节点是不是满足上面传下来的左右boundary, 然后往下传的时候narrow down。最开始left, right, node都是null(没有左右节点限制)。
boolean isBST(Node node, Node leftBoundary, Node rightBoundary) { if (node == null) return true; if ((leftBoundary != null && node.val < leftBoundary.val) || (rightBoundary != null && node.val > rightBoundary.val)) return false; if (!isBST(node.left, leftBoundary, node)) return is BST(node.right, node, rightBoundary); }
http://www.mitbbs.com/article_t1/JobHunting/32184907_0_1.html
思路(这个没怎么测试,不知道对不对,也想不明白time)。。
从头开始顺着摸,摸到摸过的,说明有loop。
什么时候结束?摸到下一个index out of boundry了,说明当前绳子结束。但是可能数组里中间还剩一大堆元素没动呢,所以要keep一个currRopeHead variable (当前绳子的头);从这个头的下一个开始往右找(左边不用找了,既然当前绳子在这开头,说明左边的小绳结早就处理过了),找到第一个没visited过的绳头,接着做。
test: {2, -1, 1, 4, 5, 0}这算是loop吗?感觉应该不算,所以一个visited array还不行,得用Map<Index, HashSet<ropeIndex>>才行。顺着当前绳子摸到的节点若在当前绳子上visit过才叫visit过。所以每次新生成绳子的时候,要把ropeIndex++。卧槽这越来越复杂了。
boolean hasCycle(int[] arr) { int[] visited = new int[arr.length]; int i = 0; int currRopeHead = i; while (i < arr.length) { if (visited[i]) return true; visited[i] = true; int next = arr[i]; if (next < 0 || next >= arr.length) { //rope is broken, will start a new one //find the first unvisited rope start boolean foundRopeHead; for (int j = currRopeHead + 1; j < arr.length; j++) { if (!visited[j]) { i = j; foundRopeHead = true; currRopehead = i; break; } } if (!foundRopeHead) return false; } else { i = next; } } return false; }
太复杂了,还是用runner technique吧。两个runner用来看当前绳字有木有loop,外加一个set代表所有没vsit过的“绳头”。
这样的话,其实并不慢,原因是runner fast跑到绳子尽头为止,不多往后跑(如果没loop的话);如果有loop,那肯定在当前绳结跑两次之前也能追上slow而停止,所以还是O(k + k)的速度(k是当前绳结的长度)。然后这个绳子跑完了,上面所有经过的节点都从set里remove掉了,set就可以接着随便找一个当绳头,接着recursion。有一个怀疑就是然后从set里面random拿的一个节点不是绳头,而是绳子中间某个部分怎么办;后来想想那就相当于把一个长绳子分两半做,要是有loop怎么都分不开,要是没loop那分成的两半也各自没loop,时间还是一样的。
boolean hasLoop(int[] arr) { Set<Integer> unvisitedIndexSet = new HashSet<Integer>(); for (int i = 0; i < arr.length; i++) { unvisitedIndexSet.add(i); } return hasLoop(arr, unvisitedIndexSet); } boolean hasLoop(int[] arr, Set<Integer> set) { if (set.isEmpty()) return false; int randomHead = getRandomElement(set); int fast = randomHead; int slow = randomHead; set.remove(fast); while (fast != -1) { fast = arr[fast]; set.remove(fast); if (fast == -1) break; else { fast = arr[fast]; set.remove(fast); } slow = arr[slow]; if (fast == slow) return true; } return hasLoop(arr, set); }
example: aabc matches c*a*b.
思路:
- 两个指针i, j,i指regular expression,j指真的string。
- 观察p[i+1],
- 如果它不是*,说明没法skip p[i],则p[i]和s[j]必须match(相等或者p[i]是’.’ which matches everything)。如果不满足,直接返回false,没法matche了。
- 如果它是*,说明当前位置可以是0个p[i], 1个p[i], 2个p[i]..
- 先试试“用0个p[i]“,即把p[i]和他后面的* skip掉。若recurse (i + 2, j)成功了,直接返回true,不成功,接着做第二步。
- 从“用1个p[i]“开始while循环,若p[i]和s[j] match, recurse on (i + 2, j + 1)(把*用掉了所以i+2),如果返回true就直接成了,否则就while继续循环“用2个p[i]“,即recurse on (i + 2, j + 2), recurse on (i + 2, j + 3)…循环的终止条件是p[i]和s[j]不match了,直接返回false。
public boolean isMatch(String s, String p) { return tryMatch(p, s, 0, 0); } private boolean tryMatch(String p, String s, int i, int j) { if (i == p.length()) return j == s.length(); if (i == p.length() - 1 || p.charAt(i + 1) != '*') { //下一个字母不是*,当前字母必须match if (matchChar(p, s, i, j)) return tryMatch(p, s, i + 1, j + 1); else return false; } else { // p[i + 1] is * boolean skip = tryMatch(p, s, i + 2, j); //把当前字母去掉能行,就直接返回 if (skip) return true; while (matchChar(p, s, i, j)) {//*当一个p[i]开始,当两个,当三个。。 if (tryMatch(p, s, i + 2, j + 1)) return true; j++; } return false; } } private boolean matchChar(String p, String s, int i, int j) { if (i >= p.length() || j >= s.length()) return false; return p.charAt(i) == s.charAt(j) || p.charAt(i) == '.'; }
[design pattern] Observer Pattern
Posted August 25, 2013
on:花一个小时看完了书,自己写了一遍,基本明白咋回事了。需要两个接口,Source and Listener(我自己瞎起的名字),Source是那个变的,Listener是那个被通知的。
- Source:
- 一个private List<Listener> listeners;
- 一个registerListener(Listener l)函数,把l加到listeners里面去
- 一个removeListener(Listener l)函数,把l从listeners里面删掉
- 一个notifyAllListeners()函数,里面对于每个listener, call listener的update()。不需要加parameter,只是通知list里面的监听者“有东西改了”, 具体改的是啥,让Listener里面的update函数自己从source reference里面pull去。
- Listener:
- 一个private Source s
- 一个constructor that takes a Source obj, 初始的时候就把“听谁”(source)给联系上。
- 一个update()函数,里面把Source s cast成自己真监听的concrete type(比如“杂志”),然后从这个s里面pull data。
重点:
- Source的notify函数只是负责告诉listeners,有变动了,你们来pull我的data吧。不用真把动的是哪个data传过去。当然也可以pass一个para说明到底是哪个data变了,client好知道具体pull哪个data。
- Listener的update()函数只被source的notify叫,然后函数里面取出当前obj的source reference, cast, pull data and use it.
- Register这些东西都是在main函数里叫的。
public class Magazine implements Source { private List<Listner> subscribers; private String editorName; public String getEditorName() { return editorName; } public Magazine () { this.subscribers = new ArrayList<Listner>(); this.editorName = "Christina"; } public void changeEditorName(String newEditor) { this.editorName = newEditor; notifyListners(); } @Override public void registerListner(Listner l) { subscribers.add(l); } @Override public void removeListner(Listner l) { if (subscribers.contains(l)) subscribers.remove(l); } @Override public void notifyListners() { for (Listner subscriber : subscribers) { subscriber.update(); } } public static void main(String[] args) { Magazine m = new Magazine(); Subscriber sub1 = new Subscriber(m, "sub1"); Subscriber sub2 = new Subscriber(m, "sub2"); m.registerListner(sub1); m.registerListner(sub2); m.changeEditorName("Meredith"); m.removeListner(sub2); m.changeEditorName("Alex"); } } public class Subscriber implements Listner { private Source magazine; private String name; private String currentEditorName; public Subscriber(Source s, String name) {//this is how one listner bind to one subject. this.name = name; this.magazine = s; } @Override public void update() { //each subscriber knows the subject is a magazine, so it can cast it's subject to magazine and use this subject's properties. String newEditor = ((Magazine) this.magazine).getEditorName(); this.currentEditorName = newEditor; System.out.println(name + ": Updating editor name to " + newEditor); }
没啥可说的,对于每个cell,如过和word的开头字母一致,就生成一个新的全是false的visited[][], 进去原matrix开始前后左右的找。直到word的每个字母都找到为止。
要点:之前做的是直接
// left, right, up, down return find(board, i, j - 1, word, index + 1, visited) || find(board, i, j + 1, word, index + 1, visited) || find(board, i - 1, j, word, index + 1, visited) || find(board, i + 1, j, word, index + 1, visited);
这样就挂了!因为往左走的一路已经Update visited[][]了,然后没人去undo它,往右走的一支就直接拿来用了,不就乱套了么!所以在mark true的时候,函数结尾给undo一下,就可以保证一对儿出现,路径在反上来的被清理。
public boolean exist(char[][] board, String word) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == word.charAt(0)) {
boolean found = find(board, i, j, word, 0, new boolean[board.length][board[0].length]);
if (found)
return true;
}
}
}
return false;
}
private boolean find(char[][] board, int i, int j, String word, int index, boolean[][] visited) {
if (i < 0 || j < 0 || i >= board.length || j >= board[0].length)
return false;
if (board[i][j] != word.charAt(index) || visited[i][j])
return false;
visited[i][j] = true;
if (index == word.length() - 1)
return true;
// left, right, up, down
boolean found = find(board, i, j - 1, word, index + 1, visited) || find(board, i, j + 1, word, index + 1, visited)
|| find(board, i - 1, j, word, index + 1, visited) || find(board, i + 1, j, word, index + 1, visited);
visited[i][j] = false;//这样就能保证每次true的能给false回来
return found;
}
- In: 面经
- Leave a Comment
五分钟bug free,忍不住有成就感。
思路:root <= x,说明肯定不在左边,往右找;root >x,有可能是本身:如果root.left没找到,那就是本身了;如果找到了,那就返回找到那个。
public TreeNode getImmediateNext(TreeNode node, int x) { if (node == null) return null; if (node.val <= x) { return getImmediateNext(node.right, x); } else { TreeNode parent = node; TreeNode findAtLeft = getImmediateNext(node.left, x); return findAtLeft== null ? parent : findAtLeft; } }
[onsite] 找两个排好序的数组中的第k大的数
Posted August 24, 2013
on:private int findKth(int[] A, int[] B, int k) {
if (A.length == 0 && B.length == 0)
return 0;
return findKth(A, B, 0, 0, k);
}
private int findKth(int[] A, int[] B, int i, int j, int k) {
if (A.length – i > B.length – j)
return findKth(B, A, j, i, k);
if (i == A.length)
return B[j – 1 + k]; // the kth starting from j
if (k == 1) //when trying to find the first, just return the smaller head
return Math.min(A[i], B[j]);
int m1, m2; // section size
if (A.length – i < k / 2) { // A’s left over (start from A[i] to A[last]) can’t slice a size k/2 section
m1 = A.length – i;
} else {
m1 = k / 2;
}
m2 = k – m1;
int i1 = i + m1 – 1; // the pivot’s index in A
int j1 = j + m2 – 1;
if (A[i1] < B[j1]) // abandon A’s left section including A[i1]
return findKth(A, B, i1 + 1, j, k – m1);
else if (A[i1] > B[j1]) {// abandon B’s left section including B[j1],
return findKth(A, B, i, j1 + 1, k – m2);
} else {
return A[i1];
}
}