z****u
发帖数: 41 | 1 楼主啊，他的代码这里的 "curHead -> next" 貌似使用了指向sibling的指针，不是没
有指向sibling的指针么？
我怎么觉得这一题就是iterative inorder 的题目呢，只是不是binary tree而已。pop
一次，n++,till n==100或者stack.empty(). chenglg的代码本质就是用了吧while(n++
<100) 改成了 f(n) = sth + f(--n)而已。 |
|
b********t
发帖数: 2 | 2 第一轮：
印度小哥，先讲project。
实现一个二叉树的类，包含parent节点。
给一个二叉树的任意节点，返回inorder遍历的下一个节点。
刚开始写了返回右子树最左边的节点，后来经提醒补充了没有子树要从parent里找的情
况。中间穿插问了一些java和数据结构的小问题，不难。
第二轮：
白人，kindle组搞测试的，先是自我介绍。
然后写题：给一个string，返回出现频率最高的字符。
先给他讨论思路，问他这些char在不在ASCII范围内，他说good question，不一定。
然后用hashmap写了出来，中间让我解释了一下hash得概念，还有一些小问题记不清了
都不难。
中间遍历hashmap的时候卡了一下，忘了那个KV pair怎么写了，经提醒写出来了，后来
又发现不用遍历hashmap，直接遍历string就可以，然后改正。
最后问了一些测试的问题， 比如刚才是我写的如果输入String为空，就返回null，但
是我的方法返回类型是char，不能用null，后来告诉我可以返回‘\0’(这个我之前还
真不知道。。。)
后来又问我改如何测试，给了几个test case... 阅读全帖 |
|
f******h
发帖数: 45 | 3 也找工作了一段时间了，从版上学了很多，上周G家面完了，求个bless。
之前的一些都挂了，还在继续找其他的。等定下来之后一定发面经回报本版。
谢谢大家啦！！
1. http://www.mitbbs.com/article_t/JobHunting/32005597.html
1) Implement a simple calculator (+,-,*,/);
2) Implement "+1" for a large integer;
3) How to match Ads to users;
4) How to extract useful information from a forum webpage (list all
kinds of useful signal you can think of)
5) How to detect the duplicate HTML pages (large scale);
6) Find all the paths between two places on Google map;
7)... 阅读全帖 |
|
s********f
发帖数: 510 | 4 第一题不是要求inplace么， 为什么给了递归解法呢。
第三题没太看明白你说的Inorder Traverse。是不是面的人觉得解法不够清晰？ |
|
k***s
发帖数: 6 | 5 感觉应该是O(n)。以当前节点为inorder node的字符串长为left + 1 + right, 其中
left和right都可以只算一次然后用map存起来。
伪代码如下，感觉写得有点恶...
Character c;
Map map;
private int count(Node node, int rank) {
if (rank <= 0) {
return 0;
} else if (node == null) {
return 0;
} else if (map.containsKey(node)) {
return map.get(node);
}
int count = 1;
int leftCount = count(node.left, rank);
if (leftCount == -1) {
return -1;
} else if ((count += leftCount) == rank) {
c = node.ch;
return -1;
... 阅读全帖 |
|
G*****n
发帖数: 19 | 6 请问DAG的in order traversal 什么是停止条件？比如树的inorder 遇到叶结点(左右
child都是null)就可以返回当前recursion
那图的呢？ |
|
b*****u
发帖数: 648 | 7 具体原理记得不太清楚了，但是直观上应该和节点的结构有关。
比如每个节点只有指向孩子节点的指针，root 已知，就不太好Inorder
关于dfs vs. bfs 马上能想到的一个例子是华容道， 给定一个开始pattern和一个结束
pattern，求路径，比较靠谱的办法是从两端开始同时进行bfs，在中间相遇。 |
|
f*******w
发帖数: 1243 | 8 树就是图的一种啊，为什么不能BFS, DFS
你说说一个树和一个有向图在表现形式上有什么区别？
BFS就是level order
DFS的话可以是inorder, preorder, postorder |
|
p********n
发帖数: 165 | 9 DFS的话可以是inorder, preorder, postorder????
求解释DFS怎么in order 和post order。。。。。。 |
|
x******i
发帖数: 374 | 10 constant space 也是可以的。
因为inorder traversal 中，只有一对（相邻的）或者两对（不相邻的）前后数字顺序
乱了。
所以不需要记录所有的节点，只要一个变量记住前一个访问过的（prev) ，跟current
比较, 如果顺序不对，就记录，全部访问后，最多2对（4个数），或者一对，交换第一
个和最后一个就好了。 |
|
r*****0
发帖数: 38 | 11 inorder traversal 需要 logn的栈空间。
current |
|
r*******2
发帖数: 104 | 12 一周之内面了微软两个组，刚刚收到结果双双悲剧，一个组的HR说It's a tough call
，另一个组的HR说very close，不知道是不是套话，总之很沮丧……来版上求问一下大
家问题可能出在哪，并且附上大概的面试过程和coding题目。
第一组：
第1轮：是一个SDE II，看名字像是中东人。coding题目是给定2棵树，判定是否其中一
棵是另一棵的subtree，同时用了DFS和BFS，写完code讨论了几个testcases和复杂度就
结束了。
第2轮：一个白哥Senior Lead，问的题目是一个maze（用2D matrix表示，有的坐标上
有障碍），给定起点和终点，找出从起点到终点的path，还是用的常规的DFS解法，搜
索过程排除有障碍的和访问过的坐标。
第3轮：一个小黑Lead II带去一起lunch，午饭之后问了大概半小时设计题，设计当软
件窗口（比如Word窗口）大小变化的时候每个子图标栏的大小如何变化，大概定义了一
下各个class，挑了其中一个function写了code。
第4轮：一个三哥Principle Lead，先问了一个ASCII和Kanji字... 阅读全帖 |
|
r*******2
发帖数: 104 | 13
好的，我把我的解题过程也说一下。Leetcode原题就不用说了。
第一组：
第1轮：判断subtree。假设两棵树T1和T2，先用DFS在T1里找到和T2的root一样的结点
，然后从找到的结点开始和T2进行比较，我用了BFS，就是用queue，一边一个queue，
同时push/pop进行比较，如果碰到不一样的就return false。做完了想起来其实就是
Leetcode上的Same Tree，直接还用DFS递归比queue省事。
第2轮：找出maze中的path。开一个matrix标记maze的每一个点是否访问过，然后DFS搜
索，从起点开始，查找它的上下左右邻居，如果没有访问过也没有obstacle，就作为一
个选择进行下一步搜索，一直递归下去直到找到终点为止。
第3轮：设计题。
第4轮：ASCII和Kanji字符的题以前面过，当时没做出来，答案就是回来网上搜的（参
考这个网址http://discuss.joelonsoftware.com/default.asp?interview.11.334807.4）。Spiral Matrix是Leetcode原题就不说了。
第... 阅读全帖 |
|
l**********7
发帖数: 55 | 14 来自主题: JobHunting版 - 请教一道题 牛！
Follow your idea. Here are my two cents.
void sortbst(int *A, int n)
{
int k, h;
//compute height
for (h=1;;h++) {
if (1<
}
//start the last left node with two leaves
//do inorder traverse the array
k=1<<(h-2)-1;
while(1)
{
printf(" %d ",A[2*k+1]);
printf(" %d ",A[k]);
printf(" %d ",A[2*k+2]);
if(2*k+2>=n-1) break;
printf(" %d ", A[k/2]);
k=k+1;
}
printf("n");
}
// a should be from a com... 阅读全帖 |
|
R******9
发帖数: 267 | 15 确实是，遍历叶子不需要 inorder
) { |
|
|
a***e
发帖数: 413 | 17 其他两种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... 阅读全帖 |
|
c********6
发帖数: 33 | 18 应该是 inorder必须知道，pre 和 post知道一个就可以
level order 如果不是完全二叉树的话不行，
举个例子，
假如最后一排有4个位置 但是只有两个叶子节点，
level order的话 没法判断两个叶子节点的具体位置 |
|
c**g
发帖数: 45 | 19 void inorderTraversalByIteration(TreeNode* root, vector& ret)
{
if(root == 0)
return;
stack s;
s.push(root);
while(s.size() > 0)
{
if(s.top()->left != 0)
{
s.push(s.top()->left);
}else
{
TreeNode* cur = s.top();
s.pop();
ret.push_back(cur->val);
if(cur->right != 0)
... 阅读全帖 |
|
n*****5
发帖数: 984 | 20 假设 root 有个左节点 。你就会 入站 root， left ，弹出 left。 入站left 循环 |
|
m*********a
发帖数: 3299 | 21 这个code 是错的，真如楼上所说，会进入死循环。
你在else 后加while (!s.empty())
然后说if (s->right!=NULL) ，push stack 后，break; |
|
r******l
发帖数: 10760 | 22 这种问题自己单步执行一下不就知道了？难道只会写代码，不会debug？ |
|
s*******7
发帖数: 23 | 23 我觉得O(n) 可以做
1. 把无序的array给heapify
2. 建立binary tree， 建的方法是 Ai 的左边 是 A（2i＋1）， 右边子节点是 A（
2i ＋ 2）
3. 把这个树， inorder打印就行了
泡这个版多年， 作点贡献 ：） |
|
j**********3
发帖数: 3211 | 24 来自主题: JobHunting版 - 面试题请教 只给inorder traverse，能确定binary tree么？ |
|
j**********3
发帖数: 3211 | 25 来自主题: JobHunting版 - 面试题请教 只给inorder traverse，能确定binary tree么？ |
|
l****o
发帖数: 135 | 26 某上市电商公司，电话面试，是个中国人面的。
上来就用中文打招呼，那个亲切啊！花半个小时问了一堆简历上的东西，然后说做个题
写个inorder traversal吧，我说recursive还是iterative。他说就写个recursive吧，
我说recursive是不是太简单了？他说那就都写吧。于是刷刷刷就写好了，给他解释了
一下recursive的代码。他说好，再做一道给定硬币面值，求给定值如6的找钱组合数。
也是常见题，给了个例子确定了一下需求，然后刷刷刷写完，他没怎么看懂，于是在
collaedit上编译通过一个测试case。
然后，第二天就来了据信说根据你phone interview的结果，我们决定找更适合的
candidate。尼玛，不带这么耍人的。实在不很理解面试官的心里。。。 |
|
a********r
发帖数: 217 | 27 假设BST每个key都是 >=0 的整数，而且不重复，有没有时间复杂度是O(lgn)的算法来
search kth smallest key. inorder traversal似乎不能满足要求。 |
|
a********r
发帖数: 217 | 28 但是树已经是建好的,重建的话至少要O (n)
时间。所以说能不能优化, 整数inorder search的时间是关键。 |
|
x******0
发帖数: 1025 | 29 这个就是inorder对么？
但是括号怎么弄呢 |
|
a***e
发帖数: 413 | 30 多谢大牛，我觉得它们都是O（N^2），但看2说自己是O（N）又不确定了。
下面这种解法应该怎么分析复杂度呢？我觉得是O（N）但还是不确定。
class Solution {
public:
TreeNode *buildTree(vector &pre, vector &in) {
int i=0,j=0;
TreeNode *root=new TreeNode(0x80000000);
TreeNode *pp=NULL,*ptr=root;
stack sn;sn.push(root);
while (j
if (sn.top()->val==in[j]) {
pp=sn.top();
sn.pop();
j++;
} else if (pp) {
ptr... 阅读全帖 |
|
b******g
发帖数: 3616 | 31 这个应该是O(N)了，除了第一个元素外，其他每个元素进出栈一次，而且i,j各扫描pre
,in一次。
这个算法很牛啊，虽然follow了个简单的例子觉得算法应该是对的，但还没有完全理解
是什么原理。请高手解释！ |
|
M*****M
发帖数: 20 | 32 第三题
内部数据结构用BST，不用array?以便void store(int input)时lgN？
boolean test(int val)内部先inorder BST,然后two sum？ |
|
M*****M
发帖数: 20 | 33 第三题
内部数据结构用BST，不用array?以便void store(int input)时lgN？
boolean test(int val)内部先inorder BST,然后two sum？ |
|
C*******n
发帖数: 193 | 34 /**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector inorderTraversal(TreeNode *root) {
vector ret;
if(root) {
stack stack;
stack.push(root);
TreeNode* top = stack.top();
while(!stack.empty() || top!=NULL){
... 阅读全帖 |
|
d********o
发帖数: 15 | 35 好像每回都跳掉了top->right 的node没有入栈 |
|
y******0
发帖数: 93 | 36 top = top->right;之后top可能为null，然后你上面又继续top->left |
|
f********h
发帖数: 155 | 37 // 不是牛；这样简单
class Solution {
public:
vector inorderTraversal(TreeNode *root) {
vector ret;
stack stack;
TreeNode * top = root;
while (!stack.empty() || top != null) {
if (top != null) {
stack.push(top);
top = top->left;
} else {
top = stack.top();
stack.pop();
ret.push_back(top->val);
top = top->right;
}
... 阅读全帖 |
|
H******7
发帖数: 1728 | 38 good one
★ 发自iPhone App: ChineseWeb 8.7 |
|
b******g
发帖数: 3616 | 39 基本就是楼上几位说的两个问题
1.top->right始终没有进stack。当第二层的while loop结束后，top访问到了一个没有
left child的节点，输出该节点后访问到了他的right child（top=top->right)，假设
这个节点为X，然后因为stack非空再次回到内层的while loop开始把这个x的left
child依次压入，但x始终没有入栈。
2.如果top->right为NULL，因为stack非空，仍旧会回到内层while loop，此时你直接
访问了NULL->left: while(top->left!=NULL) |
|
g********r
发帖数: 89 | 40 nice. O(log(n)) 就可以找到greaterNode
递归如何做呢？
非递归还可以用Moris inorder traverse，也是O(1) space, 但是time就是O(n)了，况
且代码复杂很多，杀鸡用牛刀的感觉。 |
|
C********e
发帖数: 492 | 41 也算吧，
比如inorder遍历tree，不论是用stack还是递归，其实都是logN的space复杂度
真正的O（1）space解法，需要靠morris算法来 |
|
M******9
发帖数: 10 | 42 基本都面完了，前一段刚注册了一个帐号，上来发文，大概说下自己的经历，抛个砖头
，希望对大家有用，也祝愿大家都能找到满意的工作。有NDA就不说onsite具体题目了
，感觉也没什么必要说，会大概说说面到的知识点，可能比较乱，大家将就着看。
基本情况：fresh cs phd, 找的都是SE的工作，为啥不找教职或者research lab这里就
不讨论了. FLGT(2 offers, 1家withdraw, 1家简历被刷), startups UPASD(2 offers,
2家电面挂，1家没申请)
pros：背景还不错，都是top school, GPA高。。(fresh貌似公司还是会稍微看看这个)
cons: 没有intern经验是硬伤，PhD期间，上完课后代码写得不多
package还没开始谈，initial offer都差不多200k+的样子，大公司hr明确表示等我都
面完了可以谈, startup都是late stage, 股票都是十万分之5-10, 感觉不好谈。LD目
前在一家大公司，说其实先去大公司几年也不错，比较稳定，貌似股票refresh也可能
不错，work/life... 阅读全帖 |
|
M******9
发帖数: 10 | 43 基本都面完了，前一段刚注册了一个帐号，上来发文，大概说下自己的经历，抛个砖头
，希望对大家有用，也祝愿大家都能找到满意的工作。有NDA就不说onsite具体题目了
，感觉也没什么必要说，会大概说说面到的知识点，可能比较乱，大家将就着看。
基本情况：fresh cs phd, 找的都是SE的工作，为啥不找教职或者research lab这里就
不讨论了. FLGT(2 offers, 1家withdraw, 1家简历被刷), startups UPASD(2 offers,
2家电面挂，1家没申请)
pros：背景还不错，都是top school, GPA高。。(fresh貌似公司还是会稍微看看这个)
cons: 没有intern经验是硬伤，PhD期间，上完课后代码写得不多
package还没开始谈，initial offer都差不多200k+的样子，大公司hr明确表示等我都
面完了可以谈, startup感觉不好谈。LD目前在一家大公司，说其实先去大公司几年也
不错，比较稳定，貌似股票refresh也可能不错，work/life balance比较好。我自己是
想去startup, 但... 阅读全帖 |
|
w**********4
发帖数: 157 | 44 也写一下最近面的bloomberg 的面经。
总共两次phone interview 每次两个题目。
第一次phone interview
第一题 max stack ： 这个是 leetcode 上 min stack 的原题，只是 getMin
改成getMax
第二题 输入 一个String s 在 s 后添加最少的 String s' 得到 新的
String T 是一个 palindromic。
第二次phone interview
第一题 input array of number {1,2,3,4,5,6} return number of array {2
*3*4*5*6, 1*3*4*5*6,1*2*4*5*6,1*2*3*5*6,1*2*3*4*6,1*2*3*4*5 }, 要求 不允许用
除法。
my soluction :
publicList getResult(int[] num) {
List res = new ArrayLis... 阅读全帖 |
|
h******o
发帖数: 30 | 45 请问successor那个题考的是inorder的successor吗？ |
|
S*******C
发帖数: 822 | 46 public List inorderTraversal(TreeNode root) {
List res = new ArrayList();
if (root == null)
return res;
Stack stack = new Stack();
TreeNode p = root;
while (!stack.isEmpty() || p != null) {
// if it is not null, push to stack
//and go down the tree to left
if (p != null) {
stack.add(p);//stack.push(p);
p = p.left;
} els... 阅读全帖 |
|
|
d********o
发帖数: 12 | 48 这种方法确实是O(h)
如果用Morris Traversal，空间复杂度O(1) |
|
S*******C
发帖数: 822 | 49 连Morris Traversal都会写的人至少刷了500道题吧 |
|
s*********3
发帖数: 25 | 50 如果N是树的深度， 那么就是O(N).
如果N是节点的个数， 那么就看树是不是balance，如果是balance，那么就是O(logN). |
|
