D****6
发帖数: 278 | 1 1. inorder traverse tree A and B, save sorted values in two arrays. (m+n)
2. merge two arrays into a bigger sorted array. (m+n)
3. use recursive binary search algorithm on the big sorted array, to
construct the new BST. (log(m+n))
so, total running time (m+n)
对吗? |
|
i**8
发帖数: 134 | 2 可能以前有人在版上发过了，贴上我的code抛砖引玉哈
BST, given a node in it, find its next inorder successor. (the min of bigger
nodes)
note: root is not known, but node has pointer to parent.
my code:
typedef struct node {
struct node* left;
struct node* right;
struct node* parent; |
|
c*****o
发帖数: 178 | 3 弱问一下，第N大元素不应该是从后数第N个吗？inorder访问的第N个是从头数N个阿。 |
|
H*M
发帖数: 1268 | 4 u can change the inorder "order", from right, itself, to the left |
|
z*******y
发帖数: 578 | 5 这个判定BST的有两个解法，一个就是inorder 一下看看是不是升序的排列
另一个方法是 判断 根节点的值是不是大于左子树的最大值并且小于右子树的最小值，
递归实现。 |
|
s****t
发帖数: 36 | 6 1. compare array and map.
2. compare queue and priority queue.
3. find the middle of the linklist.
4. InOrder traversal, recursive and nonrecursive (coding).
5. How to find a particular phone number among lots of file.
问题都很简单，phone number那个以为他想问用什么data structure，我就说用B
tree，然后找range。 原来他是问unix command，我说用grep，他说如果files很多
的话，grep不行，告诉我用xargs。 unix不是很懂，这个答得不好。HR发信过来说是
intern的position，但是后来那个面的人问我有什么question的时候，我问这个
intern是general hire还是进你们team啊。他说这是个fulltime的position啊，不
是intern啊。我intern和fulltime都投了， |
|
d*******8
发帖数: 785 | 7 继上周Amazon Onsite被一个三哥灭了
这次电面又被国人灭了。
具体过程是这样
前25分钟聊Research...
（真的没什么好聊，我都想早点结束留时间给后面的算法题，但是他一直要问：（ ）
接下来二叉树遍历编程题，
inorder的非递归。
几个Typo，然后被说某个判定条件多余了，又按他的意思改了下。
最后20分钟讲个算法题目。
给一个M个数字的从1到N的整数数组，找出一个K个大小的子集，这个子集
每个数pair的Distance，使得这个min distance 最大化。
题目解释了半天..就剩10分想了。。
先Sort 数组，取 头尾做最初两个元素，然后K-2中做DP，但是DP我方向想错了
用f(k-1) 到f (k)，虽然知道也不对，但是一下子卡住了。
这位国人大哥也不给我提示，到了最后结束了跟我讲 从左到右 扫描做DP，
挂了电话后我就想出来了
大概是
F（k, head, end) = Max ( for ((i in [head, end-k+1]),j in [i+k-1,end]) Min(
distanc(head,i),distance(j,end) |
|
s******t
发帖数: 2374 | 8 我想了好久还是不知道怎么用递归做。。。
笨死了。
上来求教一下，不想浪费时间了。
如果inorder，可以用static变量的话我似乎还能写一个出来，不过static变量应该是不被favorable的吧。。。
static int = k;
void search(Node cur){
if(cur == null || index < 0) return;
search(cur.left);
if(--index == 0) {System.out.println(cur.value); return;}
search(cur.right);
}
很土。。。。感觉是totally wrong.... |
|
m******9
发帖数: 968 | 9 直接把inorder改一改就可以了:
void find_ith(Node* root, int i, int& count)
{
if(root!=NULL)
{
find_ith(root->left, i, count);
count++;
if(count==i){
cout<key<
return;
}
find_ith(root->right,i,count);
}
}
int count = 0;
find_ith(root, 5, count) print 5-th min |
|
b******v
发帖数: 1493 | 10 我amazon一面时就遇到这样的情况
一道很简单的题，怎样判断两个BST是否相同
结果我给了判断inorder traversal和preorder traversal是否相同的解法，并coding
用掉了面试大部分的时间
其实只需要用递归判断当前节点，左子树，右子树是否相同就可以了
好在他们还是给了我二面的机会，希望我不会再次搞砸
flag |
|
s*****r
发帖数: 773 | 11 我也是，问我相同的一模一样的问题。。。。。。。
我当时在一个很大的停车场，想找个安静的地方都找不到，不停的有车开，吵死了。
他问我是否有时间，我以为随便问问，就说好，谁知道他继续问，越问越detail。。。。。
本来准备写面经的，没来得及写你就写了
没事，大家同挂。。。
不过他后来跟我补充了一个问题
如何通过preorder和inorder来构建一个树?
这个怎么答？ 怎么说才叫答好？ |
|
k**********i
发帖数: 177 | 12 你怎么读第二个bst的每一个节点是从小到大？inorder？，并且读的复杂度不是O（n）
？ 为啥？
该也是
O(1)，所以总的时间为O(n) |
|
r****o
发帖数: 1950 | 13 你是说两个都以non-recursive的inorder访问?
我有个疑问是，对于第二个BST的每一个节点，怎么找到第一个BST的一对L1和L2呢？
这里是不是要用到binary search?
该也是O(1)，所以总的时间为O(n) |
|
x***y
发帖数: 633 | 14 How can you inorder traverse the 2nd BST in O(1) space? At least a stack is
needed for non-recursive method.....In essence, what trick in your method
makes the space from O(n), in flattening and merging method, to O(1). thanks a lot
...
该也是O(1)，所以总的时间为O(n) |
|
b********h
发帖数: 119 | 15 bst的inorder traversal就是一个有序的list，但从一个有序list还原到bst不是唯一
的。最简单的可以遍历这个list，把每个元素加到bst的左边（原list按降序排列）或
右边（原list按升序排列）。但这样出来的bst的高度就是list的长度，所以是最差的
bst。好点的做法可以每次取list中间的元素作为root，然后递归的建左子树和右子树
。这两个的复杂度都是O（n）。 |
|
D****6
发帖数: 278 | 16 变成string, 就是很standard的binary tree serialize to preorder and inorder
strings, then re-create the tree from them
对了, 你怎么投的apple的??
谢谢 |
|
j**l
发帖数: 2911 | 17 Cong~, 俺去年7月第一轮的电面的第二题就问了serialize binary tree, 当时准备不
充分，挂了。我告诉他可以用Preorder + Inorder, 迅速反问我如何编写代码，我只好
说我知道这个结论可行，但是想不起来具体怎么操作了。然后给了一个只适合存储完全
二叉树的一维数组方法(参考堆的一维数组表示法), 结果人家又听不大懂这个方法，又
问复杂度，我鬼使神差的说是O(2^h), h是平均高度，其实应该直接说O(n),人家又以为
我说成了指数复杂度...
于是第二天就是客气的拒信，显然认为我不行。 |
|
K******g
发帖数: 1870 | 18 如果，把一个链表慢慢插入生成BST，然后在inorder transverse，不就是排序了吗，
这个好像是O（nlogn+n),请问这个叫什么排序呢。多谢 |
|
I**A
发帖数: 2345 | 19 哦，那这个逻辑应该是通的。。
我自己都不记得了，这个题目是以前的一个，好像里面要求了不要inorder traverse，
是这么回事儿麽？ |
|
l*********b
发帖数: 1541 | 20 这个太复杂啦。做个inorder, 只要测试每个值比前面大就行啦。 |
|
d****2
发帖数: 6250 | 21
node.right = buildTree(preorder, start1+1+(k-start2), inorder, k+1,
len-k-1); |
|
p**********s
发帖数: 115 | 22 一轮电话+5人onsite
华人mm电面,很nice,声音特好听.问了些c++和算法的基础题.一周之后onsite见到了组
里的4个人+project manager+team manager.吃中午饭也是一个华人带着吃,聊得很开心
onsite开始做一套题,限时1个半小时.
1 比较几个数, n!, n^n之类的数
2 longest common substring
3 rebuild a tree from inorder and level order(我总觉得这题构造出的树未必唯一)
4,5 都不记得了....
他们家特别喜欢智力题,几乎每个人都问.记得的题目有
1 reverse a link list within each k blocks(这道题空手写还挺恶心的)
2 有很多硬币,垒起来跟帝国大厦一样高,问能不能把这些硬币放到一个小房间里
3 10个人站一排,每人头顶一个帽子(只能是白或者黑),后面的人可以看到前面人的帽子
,但不知道自己的帽子颜色.有一个变态的女皇,从后往前依次问每个人他们觉得自己头
顶的帽子颜色.如果回答错误该人被枪毙.注意每个人只能回答白或者黑. |
|
p**********s
发帖数: 115 | 23 方法二用inorder，传递上一个访问值。如果当前值大于上个值就继续，否则return
false. |
|
K******g
发帖数: 1870 | 24 怎么传递上一个访问值？从上往下可以传递，如果inorder从leaf返回的时候，你怎么
把左边被访问的leaf传到上一层去？除非你additional storage存起来，就可以了 |
|
A*********3
发帖数: 70 | 25 1. 算时针和分针的夹角
2. brain teaser: ３个盒子，1个apple, 1个orange，１个orange和apple的混合
所有盒子的标签都是错的，每次从１个盒子里面拿１个水果，问拿几次才能判断每个盒
子里面是什么
3. 判断List有没有环，分析时间复杂度
4. inorder遍历binary search tree
5. why amazon |
|
|
|
g******d
发帖数: 511 | 28 好像是从本版抄的.
node * restore(int pre[], int in[], int N)
{
if (!N) return NULL;
int * it = std::lower_bound(in, in + N, *pre);
assert(it != in + N && !(*pre < *it));
int index = it - in;
node * root = new node(*pre);
root->left = restore(pre + 1, in, index);
root->right = restore(pre + index + 1, in + index + 1, N - index - 1);
return root;
} |
|
c*******w
发帖数: 63 | 29 仅仅靠Index(Parent)
子树的根啊?
比如:
int inorderSeq[]= {2,4,9,8,3,1,6,7,5};
int levorderSeq[]={1,2,5,3,6,4,7,8,9};
When you go to the first element of level order 1, it is the root, 1
separate the in order seq into two parts. The left part is its left subtree
[2,4,9,8,3], the right part is its right subtree[6,7,5]. The program goes to
the left subtree, we need find which one is the root of left subtree.
The root of left subtree is the one with the minimum level |
|
|
K******g
发帖数: 1870 | 31 这个解答好像有问题，试试level>3的tree，就不对了 |
|
p********7
发帖数: 549 | 32 给楼主补充几个题吧
BST转为双链表
双链表转为平衡BST
求leaf之间最大距离
由inorder和preorder的序列，重建BST |
|
p********7
发帖数: 549 | 33 需要inorder和preorder 两个序列才能重构
leaf 之间是任意的，可以说是任意节点之间的距离 |
|
l**********3
发帖数: 161 | 34 inorder遍历树，同时找longest increasing sequence? |
|
n******h
发帖数: 50 | 35 paul大有offer了啊。恭喜。
从数组重建的话，写个recursive的函数应该不复杂吧。 |
|
d**e
发帖数: 6098 | 36 最简单的应该是inorder，如果递增就是bst |
|
c***2
发帖数: 838 | 37 I can do it manually. But can't get an elegant program in C.
Does Anybody know a good solution?
Thanks, |
|
c***2
发帖数: 838 | 38 This one works, but looks ugly. |
|
c***2
发帖数: 838 | 39 Assume total nodes <= 16. |
|
h**********d
发帖数: 4313 | 40 再问下楼主那两个arg min 和max是什么？第一个数和最后一个？谢谢
楼上inorder那个方法应该是最优的
题。 |
|
e********s
发帖数: 248 | 41 来自主题: JobHunting版 - 谷歌 电面 Your code seems to work for inorder instead of preorder, am I right? |
|
j********x
发帖数: 2330 | 42 2个，第一个老美：
abstract class 和 interface 的区别 （java才有）
class和object的区别
从两个customer id list里找出同时出现过的id，这个之后有让我写代码；比
较简单没有考虑文件很大之类的问题
我首先提了一个基于排序的方法，然后要改进，那就hash table
第二个应该是老中：
先问了个research 的问题
然后要serialize binary tree（不是bst）；表示看到过这个题，说两种遍
历，preorder和inorder，然后重建；
表示开销太大（两次遍历，存储两次 ）；提出只进行一次preorder，但是需要
记录每个子树的size，大概是这样node_0,left_tree_size,
right_tree_size, node_1....
然后让叙述代码，比较不顺利 |
|
d******a
发帖数: 238 | 43 some of them might be easy to give out idea, but a little hard to write bug-
free code.
1 merge-sort without recursion
we should use loop to sovle it. we could use loop to get n/2 sorted
subarrays, then n/4 sorted arrays...I think we should be careful to consider
the boundary conditions.
2 Find whether one string is a subset of another string (not need to be
contiguous, but order should match).
use the idea of hash, > is a pair. e.g. "abcaeaf", "aaf"
a 0, 3, 5
b 1,
c 2,
e 4... 阅读全帖 |
|
s*********l
发帖数: 103 | 44
注意二叉树不同节点内容可能有重复，比如
inorder: [1,1,1,1,1,1,1]
preorder: [1,1,1,1,1,1,1] |
|
g*l
发帖数: 385 | 45 yeah, should be two separate questions. I'm asking both. |
|
g*l
发帖数: 385 | 46 I don't think it's right. |
|
c******w
发帖数: 102 | 47 这个算法是针对BST的。 如果是一般的binary tree， 需要通过回朔父节点。 |
|
g*l
发帖数: 385 | 48 This code is surprisingly simple but seems to work. Is this a classic
question? How did you derive it, hehe? |
|
l*****a
发帖数: 559 | 49 For each level, locating the first-element of preorder sequence in inorder
sequence takes O(n) time.
Worst case is there may be O(n) levels. |
|
y*********e
发帖数: 518 | 50 这个yield return只是一个syntax sugar, 只能用于来写iterator.
尤其是这个面试题,要记住状态,满麻烦的.若是只是想,我就写一个inorder traversal,
那就容易多啦!yield return就是让开发者只需要按照traversal的思路写,然后在访问
每一个节点的时候,yield return下便是了!
比如,这个很简单的例子.给定一个array,来写一个iterator:
int[] intArray;
.......
for (int i = 0; i < intArray.Length; i++)
yield return intArray[i];
编译器会自动把如上的代码转换成,创建一个iterator,然后每执行current()一次,就从
array里面提取一个对象,如下:
class __intArrayEnumerator // C#里面把iterator叫Enumerator
{
private int[] __object;
private int __state;
public int... 阅读全帖 |
|
