s********k
发帖数: 6180 | 1 每个节点只有left，right和value，不能加mark是否被访问过。用stack实现的？谢谢 |
|
|
|
g*****x
发帖数: 799 | 4 如果是binary的话inorder+preorder或inorder+postorder
n-nary存(node, parent) pair貌似可以，不知道有什么更好的方法 |
|
l*******x
发帖数: 11 | 5 我觉得这道题的本质是考 打印左边： preorder, 打印叶子，inorder，打印右面，
postorder |
|
y**********7
发帖数: 17 | 6 终于拿到offer，从上个月16号on-site完到今天，一共等了1个多月。今天接到
recruiter的电话后兴奋地在办公室里蹦了好几下，我旁边的哥们都震惊了。哈哈。
先报下背景，fresh cs master, 无牛实习，在学校一直跟着一个还不错的项目。
google给了我10.5w base+15% bonus+150 stock，不知道是个什么水平，但我已经很满
足了，准备从了。
第一个电面：
1. 比较hashtable和BST，神马时候用hashtable,神马时候用BST。各自的优势与缺点。
2. 那人在doc里粘了个BST的图，然后让我分别写下preorder, postorder和inorder。
然后问我已知这三个order的结果，能不能construct原本的bst。
3. 填这样一个函数 String reorder(String s, String order), 也就是要把s根据
order的顺序重新排序，然后返回。比如reorder("banana","na")应该返回"nnaab"。
order里没有出现的字母放在最后面就行了。
第二个电面：
1. 聊了... 阅读全帖 |
|
y*******g
发帖数: 6599 | 7 preorder postorder什么recursive就可以了吗？
重构要code么？感觉时间不是很够啊 |
|
x*********0
发帖数: 49 | 8 原帖：
先报下背景，fresh cs master, 无牛实习，在学校一直跟着一个还不错的项目。
google给了我10.5w base+15% bonus+150 stock，不知道是个什么水平，但我已经很满
足了，准备从了。
第一个电面：
1. 比较hashtable和BST，神马时候用hashtable,神马时候用BST。各自的优势与缺点。
2. 那人在doc里粘了个BST的图，然后让我分别写下preorder, postorder和inorder。
然后问我已知这三个order的结果，能不能construct原本的bst。
3. 填这样一个函数 String reorder(String s, String order), 也就是要把s根据
order的顺序重新排序，然后返回。比如reorder("banana","na")应该返回"nnaab"。
order里没有出现的字母放在最后面就行了。
第二个电面：
1. 聊了一下我现在做的项目
2. 比较array和linked list的。
3. 两个linked list，如何找到intersect的那个node。
4. 给一个i... 阅读全帖 |
|
l*****a
发帖数: 559 | 9 wiki上那个postorder的是要用flag记录是否访问过，
不用flag的非递归的还是有点麻烦的。 |
|
|
r******n
发帖数: 170 | 11 感觉可以模仿postorder的iterative 方法写，也应该得加个visited flag
如下：
void mirror(Node* root)
{
if (root == NULL)
return;
mirror(root->left);
mirror(root->right);
Node* tmp =root->left;
root->left=root->right;
root->right=tmp;
}
void mirror_iter(Node* root)
{
if (root == NULL)
return;
stack nodeStack;
nodeStack.push(root);
while (!nodeStack.empty())
{
Node* curr=nodeStack.top();
if (curr->left != NULL && curr-... 阅读全帖 |
|
s*****y
发帖数: 897 | 12 Construct Binary Tree From Inorder and Preorder/Postorder Traversal
const int MAX = 256;
// a fast lookup for inorder's element -> index
// binary tree's element must be in the range of [0, MAX-1]
int mapIndex[MAX];
void mapToIndices(int inorder[], int n) {
for (int i = 0; i < n; i++) {
assert(0 <= inorder[i] && inorder[i] <= MAX-1);
mapIndex[inorder[i]] = i;
}
}
// precondition: mapToIndices must be called before entry
Node *buildInorderPreorder(int in[], int pre[], int n, int offse... 阅读全帖 |
|
g*****i
发帖数: 2162 | 13 我觉得inorder,preorder, postorder的iterative都可以吧,但是我们不是比较结果,而
是过程. 入栈的时候两个数要都有node入,如果有exception说明结构不同.出栈的时候
值要一样. |
|
m**q
发帖数: 189 | 14 只看pop的两个值是不够的，比如getback上面举得例子。
两个树pop pre-order traversal pop的顺序都是1，2，3
guangyi说的看过程大概是可以的，或者就干脆最直接的
preorder + inorder 或者 postorder + inorder |
|
y******n
发帖数: 47 | 15
既然是BST, 那么只用preorder或者postorder序列就可以判断出来了吧, 不需要两个序
列. 一般的binary tree需要两个序列 |
|
|
|
v*****k
发帖数: 7798 | 18 不可能啊。任何operator都一定有两个子树。否则算式怎么成立呢？
PreOrder: * + 1 2 3
PostOrder: 1 2 + 3 *
* push stack 0
+ push stack 1, null push stack 0
1 push stack 1
2 push stack 1
stack 1 has 3 elements, back to stack 0, 3 push stack 0
然后先打印stack 1 再打印stack 0 |
|
d*******h
发帖数: 642 | 19 按照这个写法，出来的postorder 是 2 1 + 3 * |
|
r******n
发帖数: 170 | 20 贴个tree的版本，不过空string对应空tree的时候，似乎空指针处理的有些ugly，求更
简洁版本。
struct BNode
{
char c;
BNode* left;
BNode* right;
BNode():c(0){}; //avoid uninitialized value for c
BNode(char _c):c(_c),left(NULL),right(NULL){};
};
void pre2bst(string pre, size_t& start, size_t len, BNode* &p)
{
if(start
{
p=new BNode(pre[start]);
size_t curr=start;
start++;
if(pre[curr]=='+'||pre[curr]=='-'||pre[curr]=='*'||pre[curr]=='/')
{
pre2bst(pre,s... 阅读全帖 |
|
S**I
发帖数: 15689 | 21 ☆─────────────────────────────────────☆
hehe123 (hehe) 于 (Wed May 4 22:12:56 2011, 美东) 提到:
面经：
1. 两个sorted的数组merge
2. Binary Tree的Serialization和Deserialization, 随便用什么方法实现
3. 设计一DVD出租系统，database table, 类和接口等
4. Large file, multiple lines, how to get any line in equal probablity, 文件
太大内存无法装入
5. 用pre-order in-order sequence重构binary tree.
6. 大量behavior问题。每个人几乎问了15分钟这样的问题，然后只30分钟做题。
Offer：
Base： $116K
Stock: 320
Sign on: $32K
比现在的好不了太多，不过A家忙多了。请问怎么能多要点？
☆─────────────────────────────────... 阅读全帖 |
|
g**u
发帖数: 504 | 22 【 以下文字转载自 Computation 讨论区 】
发信人: gubu (法相), 信区: Computation
标 题: 问一个C++的binary search tree类实现问题
发信站: BBS 未名空间站 (Mon Jan 30 16:55:19 2012, 美东)
我想让search返回一个指向node的指针，下面代码编译有错误，不知道错在哪里？
错误提示是
error: expected constructor, destructor, or type conversion before ‘*’
token
search函数的实现如下：
template
BinarySearchTree::tree_node* BinarySearchTree::search(tree_node* p, T
d)
{
if(p==NULL||d==p->data)
return p;
else if(d>p->data)
return search(p->right,d);
else
... 阅读全帖 |
|
g**u
发帖数: 504 | 23 【 以下文字转载自 Computation 讨论区 】
发信人: gubu (法相), 信区: Computation
标 题: 问一个C++的binary search tree类实现问题
发信站: BBS 未名空间站 (Mon Jan 30 16:55:19 2012, 美东)
我想让search返回一个指向node的指针，下面代码编译有错误，不知道错在哪里？
错误提示是
error: expected constructor, destructor, or type conversion before ‘*’
token
search函数的实现如下：
template
BinarySearchTree::tree_node* BinarySearchTree::search(tree_node* p, T
d)
{
if(p==NULL||d==p->data)
return p;
else if(d>p->data)
return search(p->right,d);
else
... 阅读全帖 |
|
S**I
发帖数: 15689 | 24 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
S**I
发帖数: 15689 | 25 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
S********t
发帖数: 3431 | 26 看似是旧题，你仔细做就知道不是了。跟经典的重健二叉树的题有点类似，但要稍难些。
现在有个树的类，不让你直接知道树的结构，但是有一个visitor可以访问前
序和后序的节点，现在你要写一个你自己的visitor目的是重建树，给你一场面试的时
间你能写吗？
struct Node { ... };
class Tree {
public:
void Walk(TreeVisitor *visitor);
...
};
class TreeVisitor {
public:
virtual ~TreeVisitor();
virtual void PreOrder(const char *node_name, const char *node_value, bool is_leaf) ＝ 0;
virtual void PostOrder(const char *node_name, const char *node_value, bool is_leaf) ＝ 0;
};
现在你要做的是：
1 定义一个你自己的tree data structure (class MyTree)
2 写一个... 阅读全帖 |
|
S********t
发帖数: 3431 | 27 好吧，那我说清楚些
有个general tree，内部结构就是:
class Tree {
public:
void Walk(Visitor *v) {
// in preorder sequence
v->PreVisit(...);
...
// in postorder sequence
v->PostVisit(...);
...
}
private:
ValueType node_value;
vector children_;
}
class Visitor {
public:
virtual void PreVisit(const ValueType &node_value, bool is_leaf) = 0;
virtual void PostVisit(const ValueType &node_value, bool is_leaf) = 0;
}
Let's say you define your own tree data structure:
struct MyTree ... 阅读全帖 |
|
l*********8
发帖数: 4642 | 28 void PostOrder(Node * root)
{
for (Node * p=root, prev=root; p; } {
if (prev != p->left && prev != p->right && p->left) {
prev = p; p = p->left;
} else if (prev != p->right && p->right) {
prev = p; p = p->right;
} else {
Print(p->data);
prev = p; p = p->father;
}
}
} |
|
d******a
发帖数: 238 | 29 举2个例子
-1 返回0
-1 0 -1 0 返回0
第二题我用的也是postorder的方式写的，不知道有没有其他好的idea. |
|
s********0
发帖数: 34 | 30 那举个特例：二叉树
1 1
/ \
2 2
preorder: 1->2
postorder: 2->1
单单你给的条件ms不能保证unique啊， 我丢什么东西了么？
leaf |
|
j********2
发帖数: 82 | 31 do{
// traverse up the tree using post-order sequence
treePtr = treePtr.parent;
postPtr = next(postPtr); //what is the value of postPtr here? How can
this make us go back to the root?
} while(postPtr is not leaf);
Also, is it true that (preorder, postorder) can uniquely determine a general
tree?
Many thanks!
using
usin
ca
point
curren
r
initial |
|
m*****5
发帖数: 66 | 32 本人菜鸟一枚，不在牛A和牛C中间。
请各位大神轻拍！
听说本版祝福很灵，借人气求海量祝福。
成功后买包子送给大家，谢谢大伙啊！！！
周二onsite 至今都没有消息
fresh MS当成PhD面了（听说MS3轮，PhD4轮，我就多了一轮design）
郁闷紧张中
puzzle：
balance(平衡天平)，就是postorder traversal的应用，我用cache加速。
测试用例就三个，个人怀疑那code碰到大数据量就timeout了。
各位大神点评还可以怎么加速吧。
店面一次，两道题目：
1。isBST。
2。reverse words in sentence。
面试官非常nice，可能题目也不难，主要考察会不会编程。
最后稍微多聊了一些work相关的东东，超时几分钟。
题目不难，onsite详细面经如下(只给出了题目范围，具体题目由于NDA就不敢透露了):
0。午饭+参观。
1。组合coding+递归coding。
2。两数据结构coding。
3。behavior+小coding。
4。product design（考官最后说学术上已经解决，实现是个challe... 阅读全帖 |
|
g****y
发帖数: 240 | 33 left tree的post_index不对。
, |
|
|
j******2
发帖数: 362 | 35 没用啊。
不知道可不可以不用recursion |
|
|
i**********e
发帖数: 1145 | 37 你不能过large case是因为使用内存超过限制了。
为什么？
因为你传送 vector 可是 pass by value 阿。。
这个每一层递归都得拷贝，内存使用很大啊。
改成 pass by reference:
vector & 或者 const vector & 就行了。。。
, |
|
j******2
发帖数: 362 | 38 啊，权威回答！
终于明白为什么全部leetcode都用pass by reference了。。。一直的一个puzzle。
谢谢：）
看来以后递归里的参数能用pass by reference要尽量用pass by reference。 |
|
p*******8
发帖数: 344 | 39 其中有个input是inorder=[1,2], preorder=[2,1],eclipse里面跑了没错误，结果也是
正确的，为什么leetcode judge 就说runtime error? 有什么限制吗？inorder/
postorder也有这个问题，做过的大侠说说看？ |
|
c******t
发帖数: 391 | 40 debug了一下，貌似是那个Arrays.BinarySearch的问题，比如BinarySearch([2,1],1)
的结果是-1，因为不是有序的。 换成下面的搜索就可以了：
for(inorderRootPos = 0; inorder[inorderRootPos]!=rootVal; inorderRootPos++);
//empty loop body
my 2 cents :) |
|
t****n
发帖数: 19 | 41 多谢多谢
自己傻了，怎么会去用BinarySearch..状态不好时真不该去写代码..
); |
|
K*********n
发帖数: 2852 | 42 嗯，inorder也可以，postorder就不好写了，非递归的 |
|
c*****a
发帖数: 808 | 43 preorder的iterative跟postorder可以很接近啊，差别就是2条stack...多一两行code |
|
h****n
发帖数: 1093 | 44 一个的stack只会写改动TreeNode的结构体的post traversal版本呵呵
假设允许改动treenode，加个bool标志位visited，初始都初始化为false
够简洁吧。。
void PostOrder(TreeNode * root)
{
TreeNode* cur;
if(root)
{
stack st;
st.push(root);
while(!st.empty())
{
cur = st.top();
st.pop();
if(cur->visited)
cout<val<
else
{
cur->visited = true;
st.push(cur);
if(cur->right) st.push(cur->r... 阅读全帖 |
|
c********t
发帖数: 5706 | 45 上次有人发了 postorder只用一个stack的iteration解法。 inorder有谁有解法？
我用了一个stack还用了一个size n 的hashmap，好像不太漂亮。 |
|
o***d
发帖数: 313 | 46 还是不是很确定到底他要你怎么做.
综合上面的各位,那么solution:
1) PostOrder traverse
2) At each record of csv file, save children's line number first, then, use
another special token (say, :) to start string, which means the record saved
will look like this:
-1,-1:"first left"
-1,-1:"first right"
1,2: "root"
this is how it should work? |
|
c**y
发帖数: 172 | 47 brutal force复杂度是比较高，但是如果有duplicate的话，只能用brutal force吧。
我只是不理解为什么CC150和我贴的论坛上说只用InOrder和PreOrder就可以了。上面那
个反例说明只用InOrder和PreOrder不够的。另外一个问题是InOrder,PreOrder和
PostOrder是不是就可以了呢（对于没有duplicate的元素）？ |
|
e****e
发帖数: 418 | 48 我觉得你的反例已经说明只用InOrder和PreOrder是不行的。我也给出一个反例说明即
使有PostOrder还是不行。
T1:
1
/
2
T2:
1 |
|
c**y
发帖数: 172 | 49 I come up with some questions when considering the following problem. A
related discussion is found here
http://stackoverflow.com/questions/1017821/find-whether-a-tree- but I didn't find the answer to my particular questions.
Problem: given two binary trees T1 (large) and T2 (small), how do we check
whether or not T2 is a subtree of T1? Brutal force solution is out of scope
of this post. Another solution is as follows. A general idea is to serialize
T1 and T2 into two arrays A(T1) and A(T2) firs... 阅读全帖 |
|
p*****2
发帖数: 21240 | 50
你这个理解其实有些误区。因为吧，Code Lee上的一题可能是几题。
不如inorder transversal其实包含了很多题
1. dfs
2. iterative (我知道有三种解法）
3. morris
这样就是算5道题了，然后preorder+postorder就是10几道道题了。 |
|
