z*s
发帖数: 209 | 1 这学期终于结束，今天回家。分享一下上个月的Google校园面试题。一共两个面试官，
每人问45分钟。
一、
1、1~1000的数中有一个重复的数，把这个数找出来。
2、找出Binary Search Tree树的Median number。
这两道题的要求都是提出尽量多的算法，并给出复杂度。
3、第2题我说了一个O(log n)的算法，他就让我比较几个时间复杂度：O(n)、O(n^2)、
O(log n)、O(n log n)，问哪个是最快的。是不是任何时候O(log n)都比O(n)的算法好
？他想要的答案大概是："Big O notation discards multiplicative constants on
the running time, and ignores efficiency for low input sizes, it does not
always reveal the fastest algorithm in practice or for practically-sized
data sets." http://en.wikipedia.org/wiki/Big_O_notation
4、写出我说的那个O(log n)的算法的代码。我当时我一个地方写错了，一个参数没有
加引用，但是他当时也没看出来，对我的答案还比较满意。
二、就问了一道题，直方图中找最大矩形。要求也是提出尽量多的算法，并分别给出复
杂度。我当时没有没说出来O(n)的算法，但还是过了。
感觉这一次的问题都不难，很常见，也很基础。 |
D***h
发帖数: 183 | 2 第二题怎么可能O(lgn)? 数完节点数目就O(n)了.
【在 z*s 的大作中提到】
: 这学期终于结束，今天回家。分享一下上个月的Google校园面试题。一共两个面试官，
: 每人问45分钟。
: 一、
: 1、1~1000的数中有一个重复的数，把这个数找出来。
: 2、找出Binary Search Tree树的Median number。
: 这两道题的要求都是提出尽量多的算法，并给出复杂度。
: 3、第2题我说了一个O(log n)的算法，他就让我比较几个时间复杂度：O(n)、O(n^2)、
: O(log n)、O(n log n)，问哪个是最快的。是不是任何时候O(log n)都比O(n)的算法好
: ？他想要的答案大概是："Big O notation discards multiplicative constants on
: the running time, and ignores efficiency for low input sizes, it does not
|
m********e
发帖数: 33 | 3 赞。知道树的大小吗？
【在 z*s 的大作中提到】
: 这学期终于结束，今天回家。分享一下上个月的Google校园面试题。一共两个面试官，
: 每人问45分钟。
: 一、
: 1、1~1000的数中有一个重复的数，把这个数找出来。
: 2、找出Binary Search Tree树的Median number。
: 这两道题的要求都是提出尽量多的算法，并给出复杂度。
: 3、第2题我说了一个O(log n)的算法，他就让我比较几个时间复杂度：O(n)、O(n^2)、
: O(log n)、O(n log n)，问哪个是最快的。是不是任何时候O(log n)都比O(n)的算法好
: ？他想要的答案大概是："Big O notation discards multiplicative constants on
: the running time, and ignores efficiency for low input sizes, it does not
|
d****j
发帖数: 293 | 4 同问，难不成每个节点包含了子树节点的个数？
强烈要求lz继续解释一下。
【在 D***h 的大作中提到】
: 第二题怎么可能O(lgn)? 数完节点数目就O(n)了.
|
z*s
发帖数: 209 | 5 对，可以给节点添加其他信息。
【在 d****j 的大作中提到】
: 同问，难不成每个节点包含了子树节点的个数？
: 强烈要求lz继续解释一下。
|
z*s
发帖数: 209 | 6 忘了说了，可以给节点添加其他信息。
其实这种题他告诉你的条件很少，怎么解、怎么加附加条件都取决于你，只要合理就行
，我觉得。
【在 D***h 的大作中提到】
: 第二题怎么可能O(lgn)? 数完节点数目就O(n)了.
|
m******0
发帖数: 73 | 7 二、就问了一道题，直方图中找最大矩形。要求也是提出尽量多的算法，并分别给出复
杂度。我当时没有没说出来O(n)的算法，但还是过了。
O(n) 的解法是什么 |
n****t
发帖数: 241 | 8 第二题怎么做？
这学期终于结束，今天回家。分享一下上个月的Google校园面试题。一共两个面试官，
每人问45分钟。
一、
1、1~1000的数中有一个重复的数，把这个数找出来。
2、找出Binary Search Tree树的Median number。
这两道题的要求都是提出尽量多的算法，并给出复杂度。
3、第2题我说了一个O(log n)的算法，他就让我比较几个时间复杂度：O(n)、O(n^2)、
O(log n)、O(n log n)，问哪个是最快的。是不是任何时候O(log n)都比O(n)的算法好
？他想要的答案大概是："Big O notation discards multiplicative constants on
the running time, and ignores efficiency for low input sizes, it does not
always reveal the fastest algorithm in practice or for practically-sized
data sets." http://en.wikipedia.org/wiki/Big_O_notation
4、写出我说的那个O(log n)的算法的代码。我当时我一个地方写错了，一个参数没有
加引用，但是他当时也没看出来，对我的答案还比较满意。
二、就问了一道题，直方图中找最大矩形。要求也是提出尽量多的算法，并分别给出复
杂度。我当时没有没说出来O(n)的算法，但还是过了。
感觉这一次的问题都不难，很常见，也很基础。
【在 z*s 的大作中提到】
: 这学期终于结束，今天回家。分享一下上个月的Google校园面试题。一共两个面试官，
: 每人问45分钟。
: 一、
: 1、1~1000的数中有一个重复的数，把这个数找出来。
: 2、找出Binary Search Tree树的Median number。
: 这两道题的要求都是提出尽量多的算法，并给出复杂度。
: 3、第2题我说了一个O(log n)的算法，他就让我比较几个时间复杂度：O(n)、O(n^2)、
: O(log n)、O(n log n)，问哪个是最快的。是不是任何时候O(log n)都比O(n)的算法好
: ？他想要的答案大概是："Big O notation discards multiplicative constants on
: the running time, and ignores efficiency for low input sizes, it does not
|
h***n
发帖数: 276 | 9 for question 2, if you assume each node has one more field to store the numb
er of children it has, you can do it in O(logn)
hint: try to think of the definition of median
【在 n****t 的大作中提到】
: 第二题怎么做？
:
: 这学期终于结束，今天回家。分享一下上个月的Google校园面试题。一共两个面试官，
: 每人问45分钟。
: 一、
: 1、1~1000的数中有一个重复的数，把这个数找出来。
: 2、找出Binary Search Tree树的Median number。
: 这两道题的要求都是提出尽量多的算法，并给出复杂度。
: 3、第2题我说了一个O(log n)的算法，他就让我比较几个时间复杂度：O(n)、O(n^2)、
: O(log n)、O(n log n)，问哪个是最快的。是不是任何时候O(log n)都比O(n)的算法好
|
n****t
发帖数: 241 | 10 求每个节点的子节点数本身就需要一个全递归吧。。。
还是你假设子节点数已经存在父节点了，不需要这步的求解过程？
for question 2, if you assume each node has one more field to store the numb
er of children it has, you can do it in O(logn)
hint: try to think of the definition of median
【在 h***n 的大作中提到】
: for question 2, if you assume each node has one more field to store the numb
: er of children it has, you can do it in O(logn)
: hint: try to think of the definition of median
|
|
|
n****t
发帖数: 241 | 11 我看到貌似正确的一个解法，加了很多限制条件。。。
面试题之二叉搜索树的中位数 收藏
这个问题不算是很常见的问题，基本上在中文的论坛社区没有看到过，遇见这个是因为
偶尔在http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi 上面注册了账号而看到的，题目如下：
Given a BST (Binary search Tree) how will you find median in that?
Constraints:
* No extra memory.
* Function should be reentrant (No static, global variables allowed.)
* Median for even no of nodes will be the average of 2 middle elements and
for odd no of terms will be middle element only.
* Algorithm should be efficient in terms of complexity.
中文不需要赘述了，就是二叉搜索树如何高效地找到中位数，不希望申请内存，不要
static/global的变量来实现。
第一反应就是中序遍历就是排序了，但是如果要计数的话，我们需要一个额外的变量，
这样恐怕需要或是静态或者全局变量了，故不可以用。但是我们其他很多次都碰到了那
样类似的问题，如何把一个二叉树原地转化成双向链表，那时候还有点觉得题目没意思
，没啥用处。但是在这里，作用得以体现。假如有形如
10
/ \
6 14
/ \ / \
4 8 12 16
的二叉树转化成了4=6=8=10=12=14=16这样一个双链表，那后面的问题就变成了如何在4
=6=8=10=12=14=16里面找到中间节点了，这对于我们习惯了2个快慢指针追赶的小朋友
来说不算问题了。
下面就是写的一个实现：
view plaincopy to clipboardprint?
#include
typedef struct bstNode
{
int data;
bstNode* pLeft;
bstNode* pRight;
bstNode()
{
data = 0;
pLeft = NULL;
pRight = NULL;
}
}bstNode;
void bst2dll (bstNode* pNode, bstNode*& pTail )
{
// in-order traverse
if (pNode == NULL) return ;
if (pNode->pLeft) bst2dll(pNode->pLeft,pTail);
bstNode* pCurrent = pNode;
pCurrent->pLeft = pTail;
if (pTail)
pTail->pRight = pCurrent;
pTail = pCurrent;
if(pNode->pRight) bst2dll(pNode->pRight, pTail);
}
// parameter is the original root
// return the new double linked list head
int medianInBST ( bstNode* pRoot )
{
bstNode* pTail = NULL;
bst2dll(pRoot,pTail);
// dummy handling here
if (pTail == NULL) return -1;
bstNode* pFast = pTail;
bstNode* pSlow = pTail;
while (pFast&&pSlow)
{
if (pFast->pLeft==NULL)
return pSlow->data;
else if (pFast->pLeft != NULL && pFast->pLeft->pLeft == NULL)
return (pSlow->data + pSlow->pLeft->data)>>1;
else
{
pFast = pFast->pLeft;
pFast = pFast->pLeft;
pSlow = pSlow->pLeft;
}
}
}
// test case
/*
10
/ \
6 14
/ \ / \
4 8 12 16
*/
bstNode* buildupTree()
{
// level 1
bstNode* pRoot = new bstNode;
pRoot->data = 10;
//level2
bstNode* pNewL = new bstNode;
pNewL->data = 6;
bstNode* pNewR = new bstNode;
pNewR->data = 14;
//level3
bstNode* pNewLL = new bstNode;
pNewLL->data = 4;
bstNode* pNewLR = new bstNode;
pNewLR->data = 8;
bstNode* pNewRL = new bstNode;
pNewRL->data = 12;
bstNode* pNewRR = new bstNode;
pNewRR->data = 16;
pRoot->pLeft = pNewL;
pRoot->pRight = pNewR;
pNewL->pLeft = pNewLL;
pNewL->pRight = pNewLR;
pNewR->pLeft = pNewRL;
pNewR->pRight = pNewRR;
return pRoot;
}
void main()
{
bstNode* pRoot = buildupTree();
std::cout<
system("pause");
}
说实话这样的题目还是比较喜欢的，考到了很多的概念和想法，
a.中序遍历
b.BST转化成DLL
c.寻找链表的中间节点
如果任何一个问题割裂开了问， 都是比较容易解决的。困难就在于如何用已知的办法
组合地解决未知的问题，发人深思，余是以记之。
for question 2, if you assume each node has one more field to store the numb
er of children it has, you can do it in O(logn)
hint: try to think of the definition of median
【在 h***n 的大作中提到】
: for question 2, if you assume each node has one more field to store the numb
: er of children it has, you can do it in O(logn)
: hint: try to think of the definition of median
|
d*********i
发帖数: 628 | 12 是不是直接找到最左面和最右面的叶节点，然后相加除2？
复杂度就是树的高度。。。 |
h***n
发帖数: 276 | 13 我是假设每个节点知道他所有孩子的数目的信息，你可以把这步看成预处理，不把复杂
度计算在内，就像binary search之前已经assume array is sorted，这样才能达到楼主
说的O(logn），否则是O(n）
另外，知道父节点信息的话，并不能使得复杂度降为O(n）
numb
【在 n****t 的大作中提到】
: 求每个节点的子节点数本身就需要一个全递归吧。。。
: 还是你假设子节点数已经存在父节点了，不需要这步的求解过程？
:
: for question 2, if you assume each node has one more field to store the numb
: er of children it has, you can do it in O(logn)
: hint: try to think of the definition of median
|
h***n
发帖数: 276 | 14 nice solution，但是缺点就是波坏了原来的数据结构
【在 n****t 的大作中提到】
: 我看到貌似正确的一个解法，加了很多限制条件。。。
: 面试题之二叉搜索树的中位数 收藏
: 这个问题不算是很常见的问题，基本上在中文的论坛社区没有看到过，遇见这个是因为
: 偶尔在http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi 上面注册了账号而看到的，题目如下：
: Given a BST (Binary search Tree) how will you find median in that?
: Constraints:
: * No extra memory.
: * Function should be reentrant (No static, global variables allowed.)
: * Median for even no of nodes will be the average of 2 middle elements and
: for odd no of terms will be middle element only.
|
h***n
发帖数: 276 | 15 不是，看看median number得定义先
【在 d*********i 的大作中提到】
: 是不是直接找到最左面和最右面的叶节点，然后相加除2？
: 复杂度就是树的高度。。。
|
b**y
发帖数: 32 | 16 但这个市O(n)不是楼主说的O(logn)...
【在 n****t 的大作中提到】
: 我看到貌似正确的一个解法，加了很多限制条件。。。
: 面试题之二叉搜索树的中位数 收藏
: 这个问题不算是很常见的问题，基本上在中文的论坛社区没有看到过，遇见这个是因为
: 偶尔在http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi 上面注册了账号而看到的，题目如下：
: Given a BST (Binary search Tree) how will you find median in that?
: Constraints:
: * No extra memory.
: * Function should be reentrant (No static, global variables allowed.)
: * Median for even no of nodes will be the average of 2 middle elements and
: for odd no of terms will be middle element only.
|
c*****l
发帖数: 30 | 17 这个思路不错; 跟之前看到过的In-order Binary Tree Traversal without recursion
or
stack有异曲同工之妙, 都是in place修改BST的结构
不过转化成DLL就没法转回来了吧?
而看到的，题目如下：
【在 n****t 的大作中提到】
: 我看到貌似正确的一个解法，加了很多限制条件。。。
: 面试题之二叉搜索树的中位数 收藏
: 这个问题不算是很常见的问题，基本上在中文的论坛社区没有看到过，遇见这个是因为
: 偶尔在http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi 上面注册了账号而看到的，题目如下：
: Given a BST (Binary search Tree) how will you find median in that?
: Constraints:
: * No extra memory.
: * Function should be reentrant (No static, global variables allowed.)
: * Median for even no of nodes will be the average of 2 middle elements and
: for odd no of terms will be middle element only.
|
g*********s
发帖数: 1782 | 18 Sorry, even if u know the count of descent for each node, how can u achieve
O(lgN) with that info?
In the worst, case the bst is a sorted singly linked list. How can you get
the median of the SLL in O(lgN)?
Unless it's a balanced bst. But the condition is missing from your original description, which is misleading.
【在 z*s 的大作中提到】
: 对，可以给节点添加其他信息。
|
j*****u
发帖数: 1133 | 19 if there's a count of subtree nodes on each node, every time you either go t
o left child or right - dropping half nodes, thus O(lgN) assume the bst is b
alanced
achieve
【在 g*********s 的大作中提到】
: Sorry, even if u know the count of descent for each node, how can u achieve
: O(lgN) with that info?
: In the worst, case the bst is a sorted singly linked list. How can you get
: the median of the SLL in O(lgN)?
: Unless it's a balanced bst. But the condition is missing from your original description, which is misleading.
|
n****t
发帖数: 241 | 20 楼主说的那个，也需要预处理（一样的复杂度）。。。
【在 b**y 的大作中提到】
: 但这个市O(n)不是楼主说的O(logn)...
|
|
|
n****t
发帖数: 241 | 21 所以我一直没有想明白怎么样是lgn...
Sorry, even if u know the count of descent for each node, how can u achieve
O(lgN) with that info?
In the worst, case the bst is a sorted singly linked list. How can you get
the median of the SLL in O(lgN)?
Unless it's a balanced bst. But the condition is missing from your original
description, which is misleading.
【在 g*********s 的大作中提到】
: Sorry, even if u know the count of descent for each node, how can u achieve
: O(lgN) with that info?
: In the worst, case the bst is a sorted singly linked list. How can you get
: the median of the SLL in O(lgN)?
: Unless it's a balanced bst. But the condition is missing from your original description, which is misleading.
|
z*s
发帖数: 209 | 22 各位，不好意思。昨天回国了，没上mitbbs。
更正一下：二叉树那道题我说如果再查找中数之前就知道以每个节点为根的子树中节点
的个数的话，假设节点总数n是奇数，m=(n+1)/2，根的左子树的节点数是k，右子树(n-
k-1)。这样的话，就把找中数转换成找第m小的数：
if (m == k+1) return root;
else if (m <= k) find_m(root->lchild, m);
else find_m(root->rchild, m-k-1);
当然，我跟他说都是基于节点个数是奇数，而且没有重复的数的假设。这道题只是让我
说出算法的思路，没让写代码。我说的方法他认可了，所以之后我也没有细想。
我当时说这个方法的复杂度是O(log n)。大家看看这种方法对吗？如果对的话，复杂度应该是多少？
后面那道写代码的题我说错了！他让我写的是 创建我所说的bst that each node
contains the number of descendants in the subtree rooted at this node，就是
一个创建二叉排序数的过程，很简单。
第一次发贴连题都没说清楚，抱歉！ |
b**y
发帖数: 32 | 23 直方图中的最大矩阵指的是什么？有什么好的solution码？ |
z*s
发帖数: 209 | |
g*********s
发帖数: 1782 | 25 the idea is right but the complexity is O(h). so it requires a balanced
bst to get O(lgN).
n-
度应该是多
少？
【在 z*s 的大作中提到】
: 各位，不好意思。昨天回国了，没上mitbbs。
: 更正一下：二叉树那道题我说如果再查找中数之前就知道以每个节点为根的子树中节点
: 的个数的话，假设节点总数n是奇数，m=(n+1)/2，根的左子树的节点数是k，右子树(n-
: k-1)。这样的话，就把找中数转换成找第m小的数：
: if (m == k+1) return root;
: else if (m <= k) find_m(root->lchild, m);
: else find_m(root->rchild, m-k-1);
: 当然，我跟他说都是基于节点个数是奇数，而且没有重复的数的假设。这道题只是让我
: 说出算法的思路，没让写代码。我说的方法他认可了，所以之后我也没有细想。
: 我当时说这个方法的复杂度是O(log n)。大家看看这种方法对吗？如果对的话，复杂度应该是多少？
|
g*********s
发帖数: 1782 | 26 后面那道写代码的题我说错了！他让我写的是 创建我所说的bst that each node
contains the number of descendants in the subtree rooted at this node，就
是一个创建二叉排序数的过程，很简单。
what is "创建二叉排序数"? u mean creating a bst given an array, or given
the bst, calculate each node's sub-tree size? the former is not that
straightforward while the latter is easy.
n-
度应该是多
少？
【在 z*s 的大作中提到】
: 各位，不好意思。昨天回国了，没上mitbbs。
: 更正一下：二叉树那道题我说如果再查找中数之前就知道以每个节点为根的子树中节点
: 的个数的话，假设节点总数n是奇数，m=(n+1)/2，根的左子树的节点数是k，右子树(n-
: k-1)。这样的话，就把找中数转换成找第m小的数：
: if (m == k+1) return root;
: else if (m <= k) find_m(root->lchild, m);
: else find_m(root->rchild, m-k-1);
: 当然，我跟他说都是基于节点个数是奇数，而且没有重复的数的假设。这道题只是让我
: 说出算法的思路，没让写代码。我说的方法他认可了，所以之后我也没有细想。
: 我当时说这个方法的复杂度是O(log n)。大家看看这种方法对吗？如果对的话，复杂度应该是多少？
|
z*s
发帖数: 209 | 27 I mean the former one. given a bunch of numbers and create such a bst (
unbalanced).
My method is to use a regular recursive bst node insertion http://en.wikipedia.org/wiki/Binary_search_tree#Insertion, set numOfDescendents of the newly added node to 1 and increment numOfDescendents of the nodes along the insertion path by 1.
【在 g*********s 的大作中提到】
: 后面那道写代码的题我说错了！他让我写的是 创建我所说的bst that each node
: contains the number of descendants in the subtree rooted at this node，就
: 是一个创建二叉排序数的过程，很简单。
: what is "创建二叉排序数"? u mean creating a bst given an array, or given
: the bst, calculate each node's sub-tree size? the former is not that
: straightforward while the latter is easy.
:
: n-
: 度应该是多
: 少？
|
d*******g
发帖数: 121 | |
g*********s
发帖数: 1782 | 29 with unbalanced bst, you can't query the median in O(lgN). so the bst you
created doesn't meet the requirement of (2).
for creation of a balanced bst, there's extra work to do. that's why i say
it's not straightforward.
http://en.wikipedia.org/wiki/Binary_search_tree#Insertion, set
numOfDescendents of the newly added node to 1 and increment
numOfDescendents of the nodes along the insertion path by 1.
【在 z*s 的大作中提到】
: I mean the former one. given a bunch of numbers and create such a bst (
: unbalanced).
: My method is to use a regular recursive bst node insertion http://en.wikipedia.org/wiki/Binary_search_tree#Insertion, set numOfDescendents of the newly added node to 1 and increment numOfDescendents of the nodes along the insertion path by 1.
|
g*********s
发帖数: 1782 | 30 这个题没意思，属于钻牛角尖。闲的无聊时可以用来练练脑子，实际价值真不大。
而且后面有人也提到了，致命弱点是destructive。
而看到的，题目如下：
【在 n****t 的大作中提到】
: 我看到貌似正确的一个解法，加了很多限制条件。。。
: 面试题之二叉搜索树的中位数 收藏
: 这个问题不算是很常见的问题，基本上在中文的论坛社区没有看到过，遇见这个是因为
: 偶尔在http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi 上面注册了账号而看到的，题目如下：
: Given a BST (Binary search Tree) how will you find median in that?
: Constraints:
: * No extra memory.
: * Function should be reentrant (No static, global variables allowed.)
: * Median for even no of nodes will be the average of 2 middle elements and
: for odd no of terms will be middle element only.
|
|
|
z*s
发帖数: 209 | 31 明白了，多谢！
【在 g*********s 的大作中提到】
: with unbalanced bst, you can't query the median in O(lgN). so the bst you
: created doesn't meet the requirement of (2).
: for creation of a balanced bst, there's extra work to do. that's why i say
: it's not straightforward.
:
: http://en.wikipedia.org/wiki/Binary_search_tree#Insertion, set
: numOfDescendents of the newly added node to 1 and increment
: numOfDescendents of the nodes along the insertion path by 1.
|
