o**********e
发帖数: 18403 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: onetiemyshoe (onetiemyshoe), 信区: JobHunting
标 题: 烙印Tree Growing Algorithm: G家的观察
发信站: BBS 未名空间站 (Tue Oct 28 23:40:51 2014, 美东)
烙印占据狗狗的PM. 烙印有点
tree growing algorithm.
一个烙印帮着2个烙印进来，
即使同级3个烙印进了一个team。
会开始分工。 婆罗门会成为
”新星“就不会去跟人吵架了。
其他两可以干活的干活，打手的
打手。
然后很快婆罗门会往管理进军。
一旦得手，就开始吸收更多烙印，
外包给烙印，排挤别的民族和
竞争对手。
这种algorithm的结果就是到最TOP
的一般是高种姓婆罗门,被捧出来，
被团团保护出来的。
高种姓吃”肉”，一派高洁。
低种姓喝“汤”，干活当打手捧着老大。
老中老美就只好当“贱民”了，
随时被排挤走路。
狗狗的engineering 挂帅的文化
是这种algorithm的克星。 可是
现在engineer老大和其他engine... 阅读全帖 |
|
m********t
发帖数: 9426 | 2 看完觉得很搞笑，academic tree和family tree是很不同的
血缘和DNA是可以代代相传的
学术的精神和思想，huh，也许可以吧，那也得你的上面每一代祖师都没有偏差的继承
至于学术能力...我只能笑了
说自己的直接PhD Advisor和自己关系近还情有可原
列一个academic tree给自己脸上贴金，和逢人就说我的祖师爷，祖祖师爷，还有自己
的师兄如何如何
那是比较low的 |
|
J***y
发帖数: 133 | 3 I am tired of this greedy ass-hole. When the former tenant lived in his
partial house (The master bedroom is locked and the garage is full of the
landlord's stuff like trash furnitures from the dump sites, only about 800
SF usable), a tree/bush died for un-known reason. This greedy guy told me
that the tenant got his tree/bush dead. Frankly, I did not see how the
former tenant make the tree die.
Every time when you told him something was broken and needed to be fixed. He
always found some excuse... 阅读全帖 |
|
C**********n
发帖数: 100 | 4 问个很基本的问题。
假定某个binary search tree和max heap都是有输入一些数字序列所构成，
那么是不是binary search tree跟输入数字的顺序无关，只可能有一种binary search
tree,
但max heap(或min heap)则跟输入数字的顺序有关，同样的几个数字，输入顺序不同所
形成的max heap也不一样？ |
|
c*********t
发帖数: 2921 | 5 1. 如何用iterative 的方法实现postorder遍历binary tree？
recursive的方法太简单了。
好像inorder, preorder的iterative比较容易用stack就行了。可是postorder,我想不
出好的方法。谁能给个pseudo code?
2. 给定postorder 和 inorder遍历的结果，想个算法还原出binary tree.
3. 给定preorder 和 inorder遍历的结果，想个算法还原出binary tree.
我有三个包子，谁给回答对，就发包子给谁，一个包子一题。
给出pseudo code就行了。
谢谢！ |
|
i***0
发帖数: 8469 | 6 You are given a binary tree:
struct node
{
int n;
//
value of node
struct node *left;
//
left subtree
struct node *right;
//
right subtree
struct node *level;
//
level pointer (node “to the right”)
}
Initially, the level field is set to NULL.
1. Write a function that will link all the nodes at the same level in a
given tree.
void linkSameLevel(struct node *t);
2. Please explain what the running time and memory usage of your function
are for a tree of depth d
containing n nodes.
For instance, if |
|
t**g
发帖数: 1164 | 7 一个unbalanced binary tree
每个节点记录一个整数
对每个节点值
左边的child小于当前节点
右边的child大于当前节点
所以你插入1,2,3,4,5...n,会得到一个depth=n的树
可是插入6,4,8,3,5,7,9，就会得到一个well balanced tree
问题：
What is the average asymptotic depth of a simple unbalanced search tree of
integers? Use O(n) notation and provide proof |
|
r********t
发帖数: 395 | 8 http://careercup.com/question?id=405592
Q: Take a tree (binary or otherwise), write a method in any language that,
when given the root node, will print out the tree in level order. With a new
line after the end of every level.
Helper methods are ok, big O run time efficiency doesn't matter (though
obviously a quicker solution is better). Do not destroy original tree.
A:
1. queue.push(root)
2. queue.push(marker)
3. while queue not empty
node = queue.pop()
if(node == marker)
|
|
t*****j
发帖数: 1105 | 9 我感觉这题应该用数学归纳法。
首先可以确定的是n一定要是奇数，偶数个数的n不存在full binary trees.
B(1) = 1
B(3) = 1
given B(n)
B(n+2): 实际上就是在B(n)个数上加两个节点。可以确定的是这两个节点一定是在一起
的。因为B(n)的所有节点都是偶数个小孩。要保持平衡只能加在同一个节点上。
所以这就是计算B(n)颗树总共有多少叶节点。总共有（n+1）/2个节点。因为每次的递
增都是只增加一个叶节点。
所以 B(n+2)=B(n)×（n+1）/2
然后算通式。。。
A binary tree is full if all of its vertices have either zero or two
children.
Let B_n denote the number of full binary trees with n vertices. What is B_n? |
|
t*****j
发帖数: 1105 | 10 我这个算法可能不一定对，可能有些数算重复了。
我感觉这题应该用数学归纳法。
首先可以确定的是n一定要是奇数，偶数个数的n不存在full binary trees.
B(1) = 1
B(3) = 1
given B(n)
B(n+2): 实际上就是在B(n)个数上加两个节点。可以确定的是这两个节点一定是在一起
的。因为B(n)的所有节点都是偶数个小孩。要保持平衡只能加在同一个节点上。
所以这就是计算B(n)颗树总共有多少叶节点。总共有（n+1）/2个节点。因为每次的递
增都是只增加一个叶节点。
所以 B(n+2)=B(n)×（n+1）/2
然后算通式。。。
A binary tree is full if all of its vertices have either zero or two
children.
Let B_n denote the number of full binary trees with n vertices. What is B_n? |
|
c**********n
发帖数: 516 | 11 The structure of a binary tree is fixed given the total number of nodes in
the tree, say N , so now you can easily construct the tree. I do not know
what is troubling you. perhaps you can post your code here, and we can tell
you what you need. |
|
d****2
发帖数: 6250 | 12 find root from pre-order tree, use that to split left-tree, right-tree from
in-order list, recursively go down. |
|
y*****a
发帖数: 221 | 13 原题是这么说的
Suppose there is a binary tree having millions of nodes and by mistake one
node has two indegree........(i.e. There becomes a cycle/loop in that tree .
..u have to find that node which is having two indegree....
Constraint is no extra memory can be used and tree representation is in
Linked list format... |
|
r******e
发帖数: 80 | 14 Question:
Write an O(n)-time nonrecursive procedure that, given an n-node binary tree,
prints out the key of each node. Use no more than constant extra space
outside of the tree itself and do not modify the tree, even temporarily,
during the procedure. Assume each node has a left pointer to its left child
, a right pointer to its right child, and no parent pointer.
Is this possible? Any ideas? Thanks. |
|
d*******d
发帖数: 2050 | 15 2,先把所有的x坐标拿出来排个序,然后在y坐标上建interval tree,scanline从左往右,
每次touch rectangle left的时候,放入y1-y2到tree,同时看有没有重叠,touch到
rectangle右边的时候,拿掉.
tree. |
|
m**q
发帖数: 189 | 16 Preorder traversal result cannot uniquely identify the original tree
structure unless it is a BST, or you insert special node into the list
to represent NULL in the tree.
ihas1337code has a good example of how to make a double linked list
out of a binary tree, and is in-place. |
|
P**********c
发帖数: 3417 | 17 我不是问到底要返回什么，这个不重要，我是说网上大部分答案到那里就停止了。
这个对binary tree也是一样，一般都是碰到当前是p或者当前是q, 则认为当前就是LCA.
如果不assume两个node都在tree里的话，这个就不成立，很多算法可能都要有改动。
我主要是想问，如果大家面试的时候遇到这题，会assume两个节点在tree里么？ |
|
r******n
发帖数: 170 | 18 贴个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... 阅读全帖 |
|
b****g
发帖数: 625 | 19 triple/quad/any other trees can be represented in binary tree
But I am not sure this is the correct answer |
|
S********t
发帖数: 3431 | 20 看似是旧题，你仔细做就知道不是了。跟经典的重健二叉树的题有点类似，但要稍难些。
现在有个树的类，不让你直接知道树的结构，但是有一个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 写一个... 阅读全帖 |
|
i**********e
发帖数: 1145 | 21 不好意思，可能破坏你这道面试题了。
假设定义为 general tree 的 postorder traversal 是遍历完current node的所有
children再遍历currentnode。
那么主要的trick是要发现 general tree (GT) 的 preorder 跟 binary tree
representation (BTR) 的 preorder 是一样的。另外，GT 的 postorder 和 BTR 的
inorder 遍历也是一样的。
所以重建树就成为了 BTR 的 preorder 和 inorder.
所以这题主要就利用经典的 preorder 和 inorder 遍历重建二叉树，然后再把 BTR 转化成 GT，不知道说对了没有？
http://www.cs.rutgers.edu/~kaplan/503/handouts/btreconNgentrees |
|
l***i
发帖数: 1309 | 22 multiway merge is not hard, if you know AVL tree or treap, you could get
away with 2-3-4 tree or Red-black tree as they do similar things. |
|
d********w
发帖数: 363 | 23 complete tree定义
a binary tree in which every level, except possibly the last, is completely
filled, and all nodes are as far left as possible.
不能使用额外的空间，
insert(int data, TreeNode root)
例如complete tree
1
2 3
4
插入节点就是成为２的右儿子
1
2 3
4 5 |
|
j********e
发帖数: 1192 | 24 写了个使用O(1)memory, O(logN * logN) (N是tree的size)的程序。
类似于binary search的算法，测试代码也在下面，应该没有大bug。
先获得树的高度h，然后比较h和root->right子树的高度+1,如果相同，
说明树最后一个节点在root->right，否则最后一个节点在root->left的子树。
#include
#include
#include
#include
using namespace std;
class Node {
private:
Node *left;
Node *right;
int value;
public:
Node() {
left = right = NULL;
value = 0;
}
Node(int v) {
left = right = NULL;
value = v;
}
int Height(Node *node) {
int h... 阅读全帖
|
|
s**1
发帖数: 71 | 25 大家好
有道binary Tree 的题请教大家，generate all structurally distinct full binary
trees with n leaves， "full" means all internal (non-leaf) nodes have
exactly two children. For example, there are 5 distinct full binary trees
with 4 leaves each.
着重想问下 如何用DP解决呢？
多谢多谢！ |
|
h****n
发帖数: 1093 | 26 不需要vector吧,假设binary tree是complete binary tree
已通过online judge测试
/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
void connect(TreeLinkNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(root==NULL) return;
TreeLinkNode * cur = root;
TreeLinkNode ... 阅读全帖 |
|
h****n
发帖数: 1093 | 27 不需要vector吧,假设binary tree是complete binary tree
已通过online judge测试
/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
void connect(TreeLinkNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(root==NULL) return;
TreeLinkNode * cur = root;
TreeLinkNode ... 阅读全帖 |
|
m*******1
发帖数: 77 | 28 Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,
1
/ \
2 3
Return 6.
leetcode 上面的一道题，求大神们解释啊 |
|
c********t
发帖数: 5706 | 29 你这个是full binary tree吧
complete要求是尽量full,但最后一层可以不满，但必须都靠左
A complete binary tree is a binary tree in which every level, except
possibly the last, is completely filled, and all nodes are as far left as
possible
这是一道编程题。 |
|
f*********m
发帖数: 726 | 30 这里说的是概念上的Tree。
若把整个大问题放在root，可以用DP解决的问题会有很多重复的subtree。除了这些还
有别的区别吗，尤其是（概念上）构建tree的时候？
比如说，是按照从左到右（从小问题到大问题）构建好（即，把小问题放在tree的高层
,把最后的大问题放在叶子），还是从右到左构建好（即，把大问题放在高层）？有没
有比较好的通用策略？ |
|
i**********e
发帖数: 1145 | 31 这是问题给的 "Height-Balanced binary tree" 的定义：
“a height-balanced binary tree is defined as a binary tree in which the
DEPTH of the two subtrees of EVERY node never differ by more than 1.”
请重复读清楚问题至少三遍，然后再看看你画的图，你就明白了 :) |
|
r*****e
发帖数: 792 | 32 出题的人是不是假设tree的每个node都占用26个字母，假设不考虑大小写，也没有
其他符号的话。那compress这个tree就是用list表示每个node，这样算完成要求吗？
或者用ternary tree，不过这样相应的算法都都要变了，虽然可能是个space
efficient的表示方式。 |
|
r*****e
发帖数: 792 | 33 出题的人是不是假设tree的每个node都占用26个字母，假设不考虑大小写，也没有
其他符号的话。那compress这个tree就是用list表示每个node，这样算完成要求吗？
或者用ternary tree，不过这样相应的算法都都要变了，虽然可能是个space
efficient的表示方式。 |
|
|
u*l
发帖数: 1943 | 35 比如suffix tree, trie, B tree, RB tree. |
|
J****3
发帖数: 427 | 36 OJ's Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where '#
' signifies a path terminator where no node exists below.
Here's an example:
1
/
2 3
/
4
5
The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}". |
|
J****3
发帖数: 427 | 37 OJ's Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where '#
' signifies a path terminator where no node exists below.
Here's an example:
1
/
2 3
/
4
5
The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}". |
|
k*j
发帖数: 153 | 38 http://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/suffixtrees.pdf
PAGE 44
Determine the strings in a database {S1, S2, S3, ..., Sm} that contain
query string q:
Build generalized suffix tree for {S1, S2, S3, ..., Sm}
Follow the path for q in the suffix tree.
Suppose you end at node u: traverse the tree below u, and
output i if you find a string containing #i |
|
y*********0
发帖数: 406 | 39 /**
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,
1
/ \
2 3
Return 6.
**/
OJ上面的题目。
给的例子，为啥是结果6，而不是4？ 不是说path吗？ |
|
f********g
发帖数: 157 | 40 永远不要用suffix tree!
能用suffix tree的情况，都应该考虑用suffix array。suffix tree内存消耗太大，根
本不可能处理大数据。而suffix array的binary search，O(logN)的复杂度，即便再大
的N，实际当中都可以把logN看成常数。 |
|
z****e
发帖数: 54598 | 41 tree和hash应该是最常见的两种结构
总体而言，现在用hash比较多，因为hash可以提供amortized o(1)复杂度的search
while tree只能保证o(lgn)复杂度的search
但是如果需要频繁排序，比如经常性插入，删除，弹出一个最小最大值
这个时候才用tree，比如priorityqueue，其实就是堆排序
否则就用hash，包括分布式现在常见的consistent hashing |
|
f**********t
发帖数: 1001 | 42 最近在练习用Tree Iterator实现Tree的非递归遍历。想练习一下begin()/end()/++的
版本。code如下：
结果在operator !=那里出了问题：
Line 45: passing ‘const TreeIterator’ as ‘this’ argument of ‘TreeNode*
TreeIterator::getRoot()’ discards qualifiers [-fpermissive]
求教这个怎么fix? 多谢啦 =)
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class TreeIterator {
stack s;
TreeNode *root_;
public:
TreeN... 阅读全帖 |
|
n******7
发帖数: 99 | 43 看到网上一些例题都是预先确定size再build tree，之后进行update和query。如果数
据不断增加和删除，还能用segment tree来进行log（n）的range query吗？增加或删
除node要重新build tree吗？多谢 |
|
w***t
发帖数: 1474 | 44 n-ary tree不是binary tree。没有左右子树之分，只有第一个第二个子树这种。所以
你这两个树用n-ary tree表示是一样的 |
|
S*******C
发帖数: 822 | 45 the weight of a tree = sum of weight of all node in the tree. Weight of node
= value of node * level of the node in the tree。
这里的代码能计算weight
public int findWeight(TreeNode root) {
int res = 0;
if (root == null)
return res;
List curLevel = new ArrayList();
curLevel.add(root);
int level = 1;
while (!curLevel.isEmpty()) {
for (TreeNode p : curLevel)
res += p.val * level;
level... 阅读全帖 |
|
c********t
发帖数: 5706 | 46 哦，target是个区间啊
sort and merge. Then use binary search check. 其实time complexity 是一样的，
space complexity还更好 O(n)。我总觉得segment tree 没什么用。有没有哪道题需要
用segment tree?
A segment tree for a set I of n intervals uses O(n log n) storage and can be
built in O(n log n) time |
|
f****e
发帖数: 923 | 47 看到一个面经
半小時前剛面完，是個很有親和力的印度姐姐。
題目是 serialize and deserialize binary tree。(類似 LC 297)
與原題不同的地方在於：規定要把 tree 轉成 "linked list" ，再把 "linked list"
轉成 tree 鏉 |
|
a*****0
发帖数: 3319 | 48 后院两棵pine tree越长越高，有一棵离房子的两扇sliding door挺近的，有必要粉刷
外墙前先trim树吗？还是可以先粉刷外墙，再修剪pine trees或让它们去不断长高. 有点担心trim树会否刮到落地窗（去年新换的，$1800/扇）或弄脏外墙。
若需要修剪，也请推荐湾区好的tree service。多谢。 |
|
a*******7
发帖数: 131 | 49 this is evergreen tree, if the tree gets too close to the neighbor's house/
window, which might cause lots of shades and then moss on the roof, such
type of issues, do I have to be responsible for that?
also if we offer to trim the tree on their side(since cannot do on our side)
, and if they refuse, later if any damage occurs, is still our liability? |
|
s*********9
发帖数: 38 | 50 I planted a tree. Several days later, the electric company placed mark lines
over my house's grass. This line happened to pass the tree. Does that mean
I need to move the tree to another place?
Thanks |
|
