f****s
发帖数: 74 | 1 leetcode上给出的思想很好。就是keep一个pre和一个cur，
如果cur是pre的孩子，说明我们正从上到下，如果反过来，说明我们从下往上，就该打
印节点了。
顺便练一个，
void postorder(Node* r)
{
if(!r) return;
stack s;
Node* pre=0;
Node* cur=r;
s.push(r);
while(!s.empty()){
cur=s.top();
if(pre==0||cur==pre->left||cur==pre->right){
if(cur->left) s.push(cur->left);
else if(cur->right) s.push(cur->right);
else{
cout<val;
s.pop();
}
}else{
if(pre=cu... 阅读全帖 |
|
f*********m
发帖数: 726 | 2 请问下面几个题是怎么答的？
面试官2：
（1）一个urn里有red，blue，green三种小球，分别的个数都已知。给一个uniform
random number generator产生[0，1]之间的数，要求写一个function随机选取小球，
选取的概率跟球的分布一致
面试官5：
（2）硬币问题：给一个unfair coin，Head和Tail的概率未知。现在已知扔了N次得到K
次Head，分别用MLE和MAP估计第N+1次出现Head的概率。
（3）先是定义：如果一个binary tree的一个subtree里所有node的key都一样，则这个
subtree叫identical tree（一个identical tree的子树理论上也是identical tree，
但计算时只算最大的那个）。 现在给任意一个binary tree，求它所包含的identical
tree的数量，比如[1，1,1]算1个，[1,2,2]算2个，[1,1,2]也算2个。
第三题能不能用Inorder，postorder, preorder 把树分别走一遍，发现不同的key就把
identical... 阅读全帖 |
|
s******r
发帖数: 65 | 3 今天真衰，只做了两道。
12. Construct binary tree from inorder and preorder/postorder traversal (
recursion, traversal properties)
13. The Painter's partition problem (dp) 吭哧吭哧。。。
征刷友啊，嘿嘿，刚开始leetcode。。。 |
|
b*****t
发帖数: 296 | 4 俺面的是广告组的Sr. SDE
1）白男老头，上来让实现一个generic stack，刚开始，俺有点不在状态，忘记
generic怎么用了，就用arraylist写了一个处理整数的，有bug，老爷子看了看我，没
说啥，问二叉查找树的查找时间复杂度，又问用过shell和pattern matching么。
2）国女，先问简历，data locality如何实现的，俺自己解释了。用图说明过程，后来
就问，你做的都是hadoop的体系结构，对写application有用么？俺说，不懂得体系结
构，可能没法写出高效的程序，后来让俺写一个给定整数数组，找出最长的连续和最大
的序列。俺给了个n平方的算法，然后让俺优化，这个确实忘记了，以前好像做过，提
示说用tree，构建过程中被打断，说为了给你下一个面试官留够时间，这个题pass吧。
3）年轻阿三，上来问简历，然后让写给定正常顺序，编程逆波兰式：a+b -> ab+,其实
就是个postOrder 的DFS，之后是terasort，说的他很爽；然后是给定字符串找出第一
个非重复的字符；之后是给两个数，找到在一个BST中的共同最深的祖先。俺给了个... 阅读全帖 |
|
s*********t
发帖数: 52 | 5 inorder一遍，再postorder一遍，然后再恢复，行不 |
|
h*****n
发帖数: 15 | 6 序列化不是好解 因为对于不balance的树 空间复杂是2^n次，链表的话
个人觉得inorder+postorder 才是比较好的解 O（2n）还是线性解 |
|
p*****3
发帖数: 488 | 7 我觉得inorder+postorder的解法很差，一个是多用空间，一个是如果节点值一样的情
况树的形状有歧义。
leetcode的解法(用#标注空指针的那个)也不好，如果#可以是value的一部分呢 |
|
h*****n
发帖数: 15 | 8 序列化 不是应该2^n 么？ 如果 是一个极不平衡的树 ，每个节点只有右儿子
如果一般树的话，postorder 和 inorder 确实有问题，
以前看过这道题目，这里有个链接，这个算法太复杂，感觉面试估计写不出。
http://codegolf.stackexchange.com/questions/339/binary-tree-enc
我的想法是encode成一个数组
[num of node in cur level][node content][if node have children]...
5
/
3 2
/
2 1
/
9 9
[if node have children] 有4个状态 0 是没有child， 1是left only，2是2个，3是
right only
举个例子，
[1, 5, 2, //第一层，2 是表示 5这个node 有两个children， 1是这一层只有1个node
2， 3， 0， 2， 2， //第二层
2， 2， 2， 1， 0, //第三层
2, 9, 0, ... 阅读全帖 |
|
N*D
发帖数: 3641 | 9 非递归Postorder Tree Traversal |
|
w******j
发帖数: 185 | 10 这个是常见题来的......
要准备啊...
顺便再看看preoder/postorder |
|
a*******e
发帖数: 455 | 11 Inorder, preorder 写出来不难， postorder 麻烦一点 |
|
J****3
发帖数: 427 | 12 试着写写， 楼主看看， 大家一起总结：
1. Clone Graph-> BFS+HashMap
2. Gas Station->DP
3. Candy->Two Pointers
4. Single Number-> Xor, HashMap, or Sum or Product way to find
5. Single Number II -> Xor, HashMap
6. Copy List with Random Pointers -> Two Pointers, HashMap with two times
traverse(like clone graph)
7. List Cycle, List Cycle II, Reorder List-> Two Pointers
8. Binary Tree Preorder, Postorder recursive -> Using stack to mock
recursive way, or implement like morris way.
9. LRU Cache-> HashMap + list
10. Inse... 阅读全帖 |
|
C**5
发帖数: 202 | 13 使用Stack的网上有，要最简单的 Recursive solution |
|
v**m
发帖数: 706 | 14 recursive solution is easier. |
|
b*********s
发帖数: 115 | 15 public class Solution {
public ArrayList postorderTraversal(TreeNode root) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
ArrayList res = new ArrayList();
visit(res, root);
return res;
}
private void visit(ArrayList res, TreeNode root) {
if (root == null) return;
visit(res, root.left);
visit(res, root.r... 阅读全帖 |
|
|
h**o
发帖数: 548 | 17 象这种题目的iterative解法一般有什么套路那?
好像三种树(pre, in, postorder)的iterative traversal法都套不上啊? |
|
a********9
发帖数: 129 | 18 L:
问答题
Write-through cache vs write-back cache
what's memory mapped file
算法题，都是老题
1) 给一个nested的int array， 返回sum of int weight by its depth
2) 写一个支持removeRandom的hashtable
3) 一串字符串，返回有多少个substring符合某些pattern，这些pattern都是10char的
长度，所以逐个比较就可以了
4) tree lowest ancestor( tree node have parent pointer)
RF:
基本全是老印，一个比一个吊炸天
1) 给一个数字，可以删除k个digit，返回最小的结果
example num=42139,k=1 == > 2139
answers: 首先从左到右，如果左边的digit比右边的大，就删除左边的digit，如果删
除不够k个digit则把最后的几位删掉，不大好实现，最好把输入变成array再做，或者
java的string
2) 写一个数据结构支持,put,get... 阅读全帖 |
|
j****y
发帖数: 684 | 19 serialize BST preorder就够了，数字之间是空格。
deserialize, 用preorder, 类似find maximal BST in BT, 用min, max value check,
O（n).
inorder, postorder单独都不行. 若用2个比如pre,in,的话，不知道人家愿不愿意. |
|
f*******w
发帖数: 1243 | 20 树就是图的一种啊，为什么不能BFS, DFS
你说说一个树和一个有向图在表现形式上有什么区别？
BFS就是level order
DFS的话可以是inorder, preorder, postorder |
|
p********n
发帖数: 165 | 21 DFS的话可以是inorder, preorder, postorder????
求解释DFS怎么in order 和post order。。。。。。 |
|
l*****a
发帖数: 14598 | 22 1. Print all paths of a binary tree
How to do it iteratively? 用一个stack实现preorder来做？
==>postOrder可做
2. Given an array of integers, find any 3 numbers in array such that they
sum to zero. eg:
[1, 2, -3, 4, 0]
1) 1 , 2, -3
2) 0, 0, 0
这个是不是三重循环？还有更快的吗？
==>sort O(nlogn), then n^2
3. 一个数组,一个target,求所有的pairs, array[i] - array[j] = k.
hash table? 要是k=0, 所有数都相等呢？怎么看都是n^2了
==> u should know 2 sum
4. 一个字符串,一个字符数组,求所有的子字符串,子字符串不能包括字符数组里面的所
有元素.
abbc, [a,b,c] -> a, b, c, ab, abb, bbc, bb, bc
有什么好思路？
==>懒得想... 阅读全帖 |
|
s*******e
发帖数: 142 | 23 morris postorder tree traversal。话说真有人被考过这题吗？ |
|
a***e
发帖数: 413 | 24 其他两种preorder和inorder都很快写出来了，这种写到这步还是不对。明早上再做算
了，不然又睡不好。
vector postorderTraversal(TreeNode *root) {
vector ret;
if (root==NULL)
return ret;
stack st;
st.push(root);
TreeNode *r = root->left;
TreeNode *lastVisitedNode=root;
while(1)
{
while(r)
{
st.push(r);
r=r->left;
}
if (st.empty())
break;
TreeN... 阅读全帖 |
|
j*****8
发帖数: 3635 | 25 是刻意不用一个set来记录是否visited了吗？ 不然的话没那么复杂阿
boolean flag = false;
if(rightChild != null && notVisited) push to stack, flag = true;
if(leftChild != null && notVisited) push to stack. if(!flag) flag = true;
if(!flag) stack pop |
|
l*****a
发帖数: 14598 | 26 while(1) {
if( cur.left!=null){ push(cur);cur=cur.left; }
else if( cur.right!=null){ push(cur);cur=cur.right; }
else { }
} |
|
a***e
发帖数: 413 | 27 多谢回复，看了网上讨论的idea，改了改preorder traversal写的一个
vector postorderTraversal(TreeNode *root) {
stack st;
vector ret;
if (root==NULL)
return ret;
st.push(root);
ret.push_back(root->val);
TreeNode *r = root->right;
while(1)
{
while (r!=NULL)
{
st.push(r);
ret.push_back(r->val);
r=r->right;
}
if (st.empty())
... 阅读全帖 |
|
a***e
发帖数: 413 | 28 要简化还要花些功夫，大家写的看着好简洁。。。。。。。。。。 |
|
l*****a
发帖数: 14598 | 29 这个主意不错
一点comment就是不用那个output stack了
直接往result里面好了。vector.insert(vector.begin(),**)
不过不要说insert效率低哦 |
|
|
|
h*******e
发帖数: 1377 | 32 是，我承认对于二叉树迭代可以有简化的形式比如bfs， 可是标准递归转迭代是不是给
每个分支赋值然后stack 存这个counter 和 递归参数， 然后要么counter + 1 进入下
一个 , 要么回溯这种做法么。 |
|
h*******e
发帖数: 1377 | 33 上个我的～～我这个是照沙特版< 算法设计技巧与分析> 的思路改的,可以推广到各种
递归转非递归。。
class Solution {
public:
void postHelper(TreeNode * root)
{
if(root == NULL) return;
stack > stack;
stack.push(make_pair(root, 0));
while(true)
{
while(stack.top().first != NULL)
// pre order get data place
stack.push(make_pair(stack.top().first->left, 0));
int preLev;
do
{
preLev = stac... 阅读全帖 |
|
a***e
发帖数: 413 | 34 请问哪里有沙特版< 算法设计技巧与分析>？多谢！ |
|
y***n
发帖数: 1594 | 35 沙特版的上来了，走火入魔了吧。。
明年不会有阿富汗版的吧？ |
|
|
h*******e
发帖数: 1377 | 37 这是我校第一届acm 校队队长的女朋友在我大一时候给我推荐的，中文版本浅显易懂～
～～她算法在我校本科４０００个学计算机的算法校赛里面拿了第一。 |
|
a***e
发帖数: 413 | 38 最近几天的少得可怜的准备时间都在看这个。60多行程序改个地方就通不过了。区别仅
在于
while(1)
{
r.push_back(p->val);
if(p==from)
break;
p = p->right;
}
不能改成
while(p!=from)
{
r.push_back(p->val);
p = p->right;
}
哎，可能还是因为这个算法不是自己想出来的，总是糊涂。
偶尔说起来，别人说那种属于比较偏的题了，如果问道肯定是存心要fail某人。
就是好奇有没有人真被问到。
能通过OJ的，
void reverse(TreeNode *from, TreeNode *to)
{
if (from==to)
return;
TreeNode *... 阅读全帖 |
|
l*****a
发帖数: 14598 | 39 面什么厂啊,需要专门准备这个?
会个一般解法的就可以了吧 |
|
A*****i
发帖数: 3587 | 40 两年前有一个朋友被yelp问到，这是我唯一一次听说有人被问到这个算法的。
那也是第一次听说有这么个玩意儿存在 |
|
|
|
b******g
发帖数: 3616 | 43 Morris本来就挺复杂了.Morris Poster Order还是三种顺序访问里最难的一个.这个面
试考的话实在太变态了.面试官自己能半小时内写出来就很不错了... |
|
h*********d
发帖数: 1054 | 44 it does not hurt to study if you have time. |
|
M*******a
发帖数: 1633 | 45 我老想了一下好像morris traverse只能pre/in order，不能post order把，当然不排
除你自己想个post order的traverse但是估计也更morris差很远了吧。 |
|
A*****i
发帖数: 3587 | 46 别用static直接传引用用postOrderTraversal(TreeNode * root, vector &list)
然后把list在另一个wrapper里面声明同时在这个wrapper里面调用postOrder这个 |
|
|
i*****h
发帖数: 1534 | 48 我被问过的：
write a method to replace all spaces in a string with ‘@10’
binary search tree postorder traversal (recursion not allowed)
同学被问过的：
Given a circular linked list, implement an algorithm which returns node at
beginning of the loop.
Write a method to generate the nth Fibonacci number |
|
t*****3
发帖数: 112 | 49 两个题的followup本质都是要求用postorder的stack解法 |
|
|
