好吧，题目真心不难
两道要码的
1. Rotate r node to right: A->B->C->D->E->NULL, r = 2
D->E->A->B->C->Null
2. iterator has only bool hasNext () and T next() method, write a wrapper
for iterator, to support peek ()
I deleted my original post. It is wrong. :)
I think we need to know how iterator is defined, i.e what interface function
it has.. A lot of iterators you can just deference it to get current value,
i.e. peek.
public void printEveryLeaf(Tree root) {
Stack backTrackStack = new Stack ();
Set visited = new HashSet ();
backTrackStack.push(root);
while (!backTrackStack.empty()) {
Tree n = backTrackStack.peek();
if ((n.left != null) && (!visited.contains(n.left))) {
backTrackStack.push(n.left);
visited.add(n.left);
continue;
}
if ((n.right != null) && (!visi... 阅读全帖
写了个第一题的DFS的非递归解法， 请高手多指教
public static TreeNode findDeepestNode(TreeNode root){
if(root ==null) return root;
int maxDepth = 1;
TreeNode deepestNode = root;
// The previous node we just traversed
TreeNode preNode=null;
// The top item in the stack
TreeNode curNode;
Stack nodeStack = new Stack();
nodeStack.push(root);
// exit until the stack is empty
while(!nodeStack.isEmpty())... 阅读全帖
来一个不递归的：
boolean validate(int[] A) {
//int[] A = {4,3,2,1};
Stack s = new Stack();
int max = Integer.MAX_VALUE;
for(int i = A.length - 1; i >= 0; i--) {
int x = A[i];
if(x > max) {
return false;
}
while(!s.empty() && x < s.peek()) {
max = s.pop();
}
s.push(x);
}
return true;
}
public static class Bar{
int height, startIdx;
Bar(int h, int i){ height = h; startIdx = i; }
}
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) return 0;
int n = matrix.length, m = matrix[0].length;
int[][] aux = new int[n][m];
for (int i=0; i
aux[0][i] = matrix[0][i] - '0';
}
for (int i=1; i
... 阅读全帖
写了一个infix to postfix，实现起来简单, 不知道思路还真不好想，面试的时候我肯
定想不出来。逆波兰表达式(postfix)evaluation是常见题，我就不贴了.
public List toPostfix(String[] in) {
List pf = new ArrayList();
Stack stack = new Stack();
for ( String s : in ) {
int p = getPrecedence( s );
if ( p == 0 )
pf.add( s );
else if ( stack.empty() )
stack.push( s );
else {
while( !stack.isEmpty() && getPrecedence( stack.peek() ) >= p )
pf.add( ... 阅读全帖
写了一个infix to postfix，实现起来简单, 不知道思路还真不好想，面试的时候我肯
定想不出来。逆波兰表达式(postfix)evaluation是常见题，我就不贴了.
public List toPostfix(String[] in) {
List pf = new ArrayList();
Stack stack = new Stack();
for ( String s : in ) {
int p = getPrecedence( s );
if ( p == 0 )
pf.add( s );
else if ( stack.empty() )
stack.push( s );
else {
while( !stack.isEmpty() && getPrecedence( stack.peek() ) >= p )
pf.add( ... 阅读全帖
第三题的答案：
public class InfixToPostfix {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
String infix="4*((5+6)*7";
infix="3+(1*2)";
String postfix=toPostfix(infix);
System.out.println(postfix);
System.out.println(evaluate(postfix));
}
//evaluate a postfix equation
static int evaluate(String postfix)
{
Stack st=new Stack阅读全帖
结果：面试7家，5 onsite，3 offer。
面经：
Amazon：2轮电面，5轮onsite。2天后offer，最后decline，非常nice的manager（拿到
A offer时还在面其它公司，比较大度地祝我good luck），拒绝的时候感情上比较难受。
电面1，设计parking lot
2， intersection of sorted int array; design data structure for a phone
contact book
onsite 1: find biggest int in array,
find K biggest int in array(tradeoff between many methods),
implement using heap
2: print modification path from "head" to "tail", given isWord()
api and every time can modify 1 word in the strin... 阅读全帖
public int maxDepth(TreeNode root) {
if (root == null) return 0;
if (root.left == null && root.right == null)
return 1;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
public int maxDepth(TreeNode root) {
Stack stack = new Stack();
TreeNode x = root, prev = null;
int maxDepth = 0;
while (x != null || !stack.isEmpty()){
while (x != null){
stack.push(x);
x = x.left;
}
maxDe... 阅读全帖
if (prev==null || prev.left==current || prev.right==current) {
if (current.left!=null) stack.push(current.left);
else if (current.right!=null) stack.p... 阅读全帖
用heap, nlogk
// T(nlgk), S(k+lgk)
public static void heapWay1(int[] num, int k) {
PriorityQueue heap = new PriorityQueue(k);
int size = k;
for (int i=0; i
if (heap.size()
heap.offer(num[i]);
else { // reach the size==k
if (num[i]<=heap.peek()) // smaller than root
continue;
else { // remove root, insert new one
... 阅读全帖
每个时间段还有找最大的要求，应该会比O(nolgn)要稍大。
class Record {
int start;
int end;
int vol;
public Record(int s, int e, int vol) {
assert (s < e);
this.start = s;
this.end = e;
this.vol = vol;
}
}
class Point {
int time;
boolean isStart;
Record rec;
public Point(int time, boolean isStart, Record rec) {
this.time = time;
this.isStart = isStart;
this.rec = rec;
}
}
ArrayList loudestVol(Record[] varr) {
assert (v... 阅读全帖
class Record {
int start;
int end;
int vol;
public Record(int s, int e, int vol) {
assert (s < e);
this.start = s;
this.end = e;
this.vol = vol;
}
}
class Point {
int time;
boolean isStart;
Record rec;
public Point(int time, boolean isStart, Record rec) {
this.time = time;
this.isStart = isStart;
this.rec = rec;
}
}
ArrayList loudestVol(Record[] varr) {
assert (varr != null);
ArrayList阅读全帖
