s*******t
发帖数: 248 | 1 直接面的第2轮，两道题，
1. printBSTOnHeight(Node *root, int height)
print the height level nodes， code on paper.
按层打印BST的变种，我给的方案是，用一个Queue，输入每个node然后每一层用一个
SingalNode来分开，然后检测，打印。版上讨论过，方法应该类似。
这个想法显然不是面试官脑子里的想法，揪住我问了半天，最后通过一个simulation，
终于让他知道这个是可行的。
2. Stock price. given a company name, print the last 20 prices based on time
.
我给出的方案是 map >
streamingData, 每进来一个，queue里剔除头上的一个。
我个人觉得都答对了， 大家帮我看看有什么问题？
我自己觉得如果有问题，可能是第一个写得慢了点儿，另外他可能有比我这个更好的方
法，我能想到的是用一个count来记录每层的数，然后打印。但我想，至少我的方法可
行呀，复杂度也没提高。
被拒后，十分沮丧！上学期面过一次internship，想试试，因为没怎么准备，挂在了一
个比较简单的题上了。这次认真准备了，但又没过！我觉得面试最郁闷的就是这种情况
了，自己感觉良好，但没有过，还不知道原因。（题外话，面试官两次都是同一位国人
大哥）。
Anyway, 发发牢骚，接着看书了. |
v***v
发帖数: 5504 | 2 printBSTOnHeight(Node *root, int height)
{
check_print_node_level(root, 0, height);
}
void check_print_node_level(Node * root, int currentLevel, int heightDesired)
{
if (!root) return;
if (currentLevel == heightDesired)
{ /* print node information*/
}
else if (currentLevel < heightDesired)
{
check_print_node_level (root->left, currentLevel + 1,
heightDesired);
check_print_node_level (root->right, currentLevel + 1,
heightDesired);
}
} |
j*****g
发帖数: 223 | 3 面试这东西，没什么规律可言，你不知道在他们那边的状况. 有可能他们已经有了人选
，只不过想再试试to confirm their choice; 有可能between they asking you to do
an onsite and actually doing the onsite, a NTE freeze has come down,很多时
候hiring manager也不是什么都知道的，所以他们只好走过场，再把你给锯了; 有可能
不是因为coding, 而是表达能力，lack of passion (at least seemingly lack of
passion), etc., etc..
所以看开点，告诉自己，statistically, you'll succeed eventually.
time
【在 s*******t 的大作中提到】
: 直接面的第2轮，两道题，
: 1. printBSTOnHeight(Node *root, int height)
: print the height level nodes， code on paper.
: 按层打印BST的变种，我给的方案是，用一个Queue，输入每个node然后每一层用一个
: SingalNode来分开，然后检测，打印。版上讨论过，方法应该类似。
: 这个想法显然不是面试官脑子里的想法，揪住我问了半天，最后通过一个simulation，
: 终于让他知道这个是可行的。
: 2. Stock price. given a company name, print the last 20 prices based on time
: .
: 我给出的方案是 map >
|
s*******t
发帖数: 248 | 4 Thanks for your encouragement!
do
时
【在 j*****g 的大作中提到】
: 面试这东西，没什么规律可言，你不知道在他们那边的状况. 有可能他们已经有了人选
: ，只不过想再试试to confirm their choice; 有可能between they asking you to do
: an onsite and actually doing the onsite, a NTE freeze has come down,很多时
: 候hiring manager也不是什么都知道的，所以他们只好走过场，再把你给锯了; 有可能
: 不是因为coding, 而是表达能力，lack of passion (at least seemingly lack of
: passion), etc., etc..
: 所以看开点，告诉自己，statistically, you'll succeed eventually.
:
: time
|
e****a
发帖数: 449 | 5 是 FSD职位吗 您老一看就像科班出身 不是他们的 style 呵呵 |
s*******t
发帖数: 248 | 6 这个是比我的写得要好些！
heightDesired)
【在 v***v 的大作中提到】
: printBSTOnHeight(Node *root, int height)
: {
: check_print_node_level(root, 0, height);
: }
: void check_print_node_level(Node * root, int currentLevel, int heightDesired)
: {
: if (!root) return;
: if (currentLevel == heightDesired)
: { /* print node information*/
: }
|
i**********e
发帖数: 1145 | 7 Nice.
This solution is doing Depth-First Traversal (DFS). BFS is fine, but you
need to enqueue all nodes before that level printing a certain level. Here
is a similar solution, but eliminate the currentLevel variable. (we just
start from a level, and decrement the level by one everytime we go into the
next level. When it reaches 1, we have reached the desired level.)
void printLevel(BinaryTree *p, int level) {
if (!p) return;
if (level == 1) {
cout << p->data << " ";
} else {
printLevel(p->left, level-1);
printLevel(p->right, level-1);
}
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
heightDesired)
【在 v***v 的大作中提到】
: printBSTOnHeight(Node *root, int height)
: {
: check_print_node_level(root, 0, height);
: }
: void check_print_node_level(Node * root, int currentLevel, int heightDesired)
: {
: if (!root) return;
: if (currentLevel == heightDesired)
: { /* print node information*/
: }
|
s*******t
发帖数: 248 | 8 Then I think the interviewer must have the similar thought.
He may expect me to do it in recursive way, but what I gave him is not a
recursive one.
the
【在 i**********e 的大作中提到】
: Nice.
: This solution is doing Depth-First Traversal (DFS). BFS is fine, but you
: need to enqueue all nodes before that level printing a certain level. Here
: is a similar solution, but eliminate the currentLevel variable. (we just
: start from a level, and decrement the level by one everytime we go into the
: next level. When it reaches 1, we have reached the desired level.)
: void printLevel(BinaryTree *p, int level) {
: if (!p) return;
: if (level == 1) {
: cout << p->data << " ";
|
t*****j
发帖数: 1105 | 9 这个是可行的，但是如果要打印出一棵树的所有层次来，不是要call很多次吗？对每一
个height都要call一次？那得recursive很多次啊。
第一层 recursive 0次 第二层recursive 1次， 第n层recursive n次..
哪里有queue的好啊，那个才只是一次遍历下所有节点。
heightDesired)
【在 v***v 的大作中提到】
: printBSTOnHeight(Node *root, int height)
: {
: check_print_node_level(root, 0, height);
: }
: void check_print_node_level(Node * root, int currentLevel, int heightDesired)
: {
: if (!root) return;
: if (currentLevel == heightDesired)
: { /* print node information*/
: }
|
s*******t
发帖数: 248 | 10 题目本身要求打印某一层，所以应该不存在你说的问题。
【在 t*****j 的大作中提到】
: 这个是可行的，但是如果要打印出一棵树的所有层次来，不是要call很多次吗？对每一
: 个height都要call一次？那得recursive很多次啊。
: 第一层 recursive 0次 第二层recursive 1次， 第n层recursive n次..
: 哪里有queue的好啊，那个才只是一次遍历下所有节点。
:
: heightDesired)
|
|
|
d**e
发帖数: 6098 | 11 呵呵，我也没看清楚，如果是只打印一层，那是比较好，不需要queue而且也是O(n)的
时间
【在 s*******t 的大作中提到】
: 题目本身要求打印某一层，所以应该不存在你说的问题。
|
y***y
发帖数: 224 | 12 我on-site的时候也遇到这个题...不过是打印某层之后所有的节点. 这样是不是用
queue比较好了啊?
当时也是废了好大劲才让两个面试官明白... |
i**********e
发帖数: 1145 | 13 You are right that printing the tree level by level using the DFS method
will have the same node traversed multiple times.
The complexity, however, is the same order as the BFS method = O(N).
Assuming the binary tree is a balanced tree, it would have height of lg N.
Printing the last level will traverse a total of N nodes. Printing the level
above it will traverse a total of N/2 nodes, and so on... Until it reaches
the top level, which traverse only 1 node.
Therefore,
T(N) = N + N/2 + N/2^2 + ... 1 (A total of lg N terms here)
= N (2 - 1/N)
= 2*N
= O(N)
Finally, we can conclude that both methods are in the same order of
complexity, even thought the BFS method might be slightly more efficient (
Don't forget BFS uses extra queue to store the nodes though).
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 t*****j 的大作中提到】
: 这个是可行的，但是如果要打印出一棵树的所有层次来，不是要call很多次吗？对每一
: 个height都要call一次？那得recursive很多次啊。
: 第一层 recursive 0次 第二层recursive 1次， 第n层recursive n次..
: 哪里有queue的好啊，那个才只是一次遍历下所有节点。
:
: heightDesired)
|
l*****a
发帖数: 14598 | 14 Please add
if(level<=0) return;
Here
the
【在 i**********e 的大作中提到】
: Nice.
: This solution is doing Depth-First Traversal (DFS). BFS is fine, but you
: need to enqueue all nodes before that level printing a certain level. Here
: is a similar solution, but eliminate the currentLevel variable. (we just
: start from a level, and decrement the level by one everytime we go into the
: next level. When it reaches 1, we have reached the desired level.)
: void printLevel(BinaryTree *p, int level) {
: if (!p) return;
: if (level == 1) {
: cout << p->data << " ";
|
x*********s
发帖数: 2604 | |
l*****a
发帖数: 14598 | 16 如果我是那个 interviewer，
我会觉得你在生搬硬套一个你见国的题目，而没有变通
Sorry
【在 s*******t 的大作中提到】
: Then I think the interviewer must have the similar thought.
: He may expect me to do it in recursive way, but what I gave him is not a
: recursive one.
:
: the
|
s*********g
发帖数: 153 | 17 楼主发挥的很不错了，虽败尤荣，Bloomberg可能比较严吧。
对于第一个问题：首先
ihasleetcode 指出了查找某个level的答案，用DST做时间复杂度o(n),BST做2*O（n）
，多了n个pop_front in queue的操作。
即时打印所有level，两个时间复杂度是一样的。
第二个问题，我认为楼主的思想很正确，但是可以用更好方法：
multimap my_multimap
每次插入操作前，用 my_multimap.count（string）看看满不满20个，如果满的话
my_multimap.erase(my_mulltimap.find(string)),移出最早的第一个数据，再插入新
数据，这样就永远保持最新的20个数据了。所以说，楼主思想正确，但是忘记用最好的
STL structure了
time
【在 s*******t 的大作中提到】
: 直接面的第2轮，两道题，
: 1. printBSTOnHeight(Node *root, int height)
: print the height level nodes， code on paper.
: 按层打印BST的变种，我给的方案是，用一个Queue，输入每个node然后每一层用一个
: SingalNode来分开，然后检测，打印。版上讨论过，方法应该类似。
: 这个想法显然不是面试官脑子里的想法，揪住我问了半天，最后通过一个simulation，
: 终于让他知道这个是可行的。
: 2. Stock price. given a company name, print the last 20 prices based on time
: .
: 我给出的方案是 map >
|
a********1
发帖数: 750 | 18 我和同学的经历是bloomberg就是不喜欢cs的人，转找外行
time
【在 s*******t 的大作中提到】
: 直接面的第2轮，两道题，
: 1. printBSTOnHeight(Node *root, int height)
: print the height level nodes， code on paper.
: 按层打印BST的变种，我给的方案是，用一个Queue，输入每个node然后每一层用一个
: SingalNode来分开，然后检测，打印。版上讨论过，方法应该类似。
: 这个想法显然不是面试官脑子里的想法，揪住我问了半天，最后通过一个simulation，
: 终于让他知道这个是可行的。
: 2. Stock price. given a company name, print the last 20 prices based on time
: .
: 我给出的方案是 map >
|
h*******n
发帖数: 614 | 19 。。。技术好牛。想起我师兄的一句话，面试的时候看的不仅仅是你题答对了没有，在
你回答的过程中，任何一个细节都透露出你的思考模式，你的行为习惯，还有你的性格
。也许lz思考的方法他们不喜欢？
其实还有一个可能，面试官自己也许就不具备通过面试的能力，可能当场写相同代码写
得并不如你？
一来他们可能自卑了，没来由不喜欢你，就fail你，二来，也有可能他们误以为你上来
就写这么好，是因为事先背过题，在生搬硬套？
anyway，move on，楼主技术这么强，肯定会有更好的offer等着你啦。 |
c********u
发帖数: 1608 | 20 这么难呀，看来俺还是不去了，随便投了份简历，下周要来学校interview。不是cs出
身，第二轮这么难，本来想去赚点第一轮面试经验的，要是也这么难还是算了，嘿嘿。 |
