NO.1
http://www.mitbbs.com/article_t/JobHunting/32503241.html
昨天面的,面试官首先迟到了将近五分钟,上来面试官简单介绍了他自己,然后就直接
进入主题,也没有让我做自我介绍啥的,上来问我有没有用过 java iterator pattern,
我给听成 intepreter, 回答没用过,他不相信,又问了一遍,恍然大悟,赶紧说用过
用过,用过很多,然后他还说用 java 的人不可能没用过
然后问为什么用 iterator, 有啥好处
答了之后接着问 java 里面有几种 list, 答 arraylist 和 linkedlist
又问实现这两种不同 list 的 iterator 有什么不同,到此为止都是对答如流,问他我答的
是不是他想要的答案,他说 exactly
答完以后开始出题,先是写个 data structure, 让我 guess 这是什么 data structure,
class N {
private N l; // can be null
private N r; // can be null
private String data;
}
一紧张说成 linkedlist, 赶紧改口说是 tree,
然后就是描述问题,要求写一个 Iterator<String>, 每次调用 next 都是按 in order 顺序
返回 BT 里面某 node 的 value,例子如下
root.data = “m”;
root.l.data=”g”;
root.r.data= “q”;
m
g q
a h p s
z
Iterates in this sequence: a, g, h, m, p, q, s, z
Solution:
recursion inorder tree travers:
public class Solution{ public ArrayList<String> getSeq(TreeNode root){ ArrayList<String> res = new ArrayList<String>(); getSeq2(res, root); return res; } private void getSeq2(ArrayList<String> list, TreeNode root){ if(root == null){ return; } getSeq2(list,root.left); list.add(root.val); getSeq2(list,root.right); }}
NO.2
检查一个字符串是否包含k位a进制数的所有表示形式。
保证原字符串的所有字串都是合法的k位a进制数。"00110, a=2, k=2" => true （包括了00，01，10，11）
Brute Force:
public class Solution{ public static void main(String[] args){ System.out.println(containNum("00110", 2, 2)); System.out.println(containNum("00110", 3, 2)); System.out.println(containNum("112020012210", 3, 2)); } public static boolean containNum(String str, int a, int k){ HashSet<String> table = generateSet(a,k); for(int i=0; i<str.length()-k+1; i++){ if(table.contains(str.substring(i,i+k))){ System.out.println(str.substring(i,i+k)); table.remove(str.substring(i,i+k)); } } if(table.isEmpty()){ return true; } return false; } private static HashSet<String> generateSet(int a, int k){ ArrayList<String> list = new ArrayList<String>(); for(int i=0; i<k; i++){ ArrayList<String> list2 = new ArrayList<String>(); if( i == 0){ for(int j=0 ;j < a; j++){ String tmp = ""+j; list2.add(tmp); } }else{ for(String tmp : list){ for(int j=0 ;j < a; j++){ String tmp2 = tmp+j; list2.add(tmp2); } } } list = list2; } HashSet<String> table = new HashSet<String>(); for(String tmp : list){ table.add(tmp); } return table; }}