这个内存如何 - 未名空间MITBBS历史存档

s*t2013-01-23 08:01

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, 发发牢骚，接着看书了.

H*72013-01-23 08:01

2 楼

1950年11月25日清晨，天还未亮，志愿军机关人员就按照防空规定，除值班人员外
，统统都进了防空洞。值班人员在听到空袭警报后再进防空洞。
11时，3架美军B-29轰炸机飞了过来。正在忙着处理电报的毛岸英，被警卫人员硬
拉进了防空洞。
敌机空袭之后飞走了，毛岸英和作战参谋高瑞欣又从防空洞里跑回作战室处理电报
，晚上将发起第二次战役，还有许多工作要做。
不料，飞远了的敌机又突然调过头来，向志愿军总部所驻地的小山村俯冲，倾泻汽
油弹。顿时，志愿军总部一片火光！
后来，人们从被烧焦的尸体的腰间，发现了斯大林所赠的德制手枪和手腕上戴的那
只苏联产的手表，确认了这是毛岸英的遗体。

p*a2013-01-23 08:01

3 楼

我现在谈的这个对象不管是朋友还是家人都非常不满意，工资工资没我高，家
里情况没有我们家好，用难听的话来说以后要真的结婚了又是一个吃软饭的男人。
所以他们都劝我跟我对象分手，但是我就是不想分手，毕竟我们都在一起这么
长时间了，更何况他还是我的初恋。如果真的要是分手了我肯定会哭死的。但是他现在
这种状态也不行啊，如果以后还是像现在这样整天无所事事，不求进取的话我肯定也不
会跟他再一起的。所以我现在就逼着让他好好工作，这样才能以后赚更多的钱。
可是他真的就像扶不起的阿斗一样，整天就知道好吃懒做，不管是在生活中还
是在工作中都是特别的懒。从来没有说主动的完成一件事情，必须要你在后面催着，要
不然你这活肯定不知道要干到猴年马月去了。
哎，本来我还想扶他一把的，我还想让大家对他刮目想看的，但是现在他自己
都放弃自己了，我能有什么办法。实在不行就只有分手了，虽然肯定会很伤心，但是总
比以后伤心的好吧。

m*c2013-01-23 08:01

4 楼

感觉很便宜啊。有人用过么？质量兼容性如何？
http://www.newegg.com/Product/Product.aspx?SID=233iFmWREeKe_aLS

v*v2013-01-23 08:01

5 楼

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);
}
}

f*82013-01-23 08:01

6 楼

本来嘛，生了火才能炒饭啊

a*w2013-01-23 08:01

7 楼

我觉得不如这个
http://www.ebay.com/itm/370680762681?ssPageName=STRK:MESINDXX:I

【在 m**c 的大作中提到】

: 感觉很便宜啊。有人用过么？质量兼容性如何？
: http://www.newegg.com/Product/Product.aspx?SID=233iFmWREeKe_aLS

j*g2013-01-23 08:01

8 楼

面试这东西，没什么规律可言，你不知道在他们那边的状况. 有可能他们已经有了人选
，只不过想再试试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 >

c*o2013-01-23 08:01

9 楼

。。。

【在 H******7 的大作中提到】

: 1950年11月25日清晨，天还未亮，志愿军机关人员就按照防空规定，除值班人员外
: ，统统都进了防空洞。值班人员在听到空袭警报后再进防空洞。
: 11时，3架美军B-29轰炸机飞了过来。正在忙着处理电报的毛岸英，被警卫人员硬
: 拉进了防空洞。
: 敌机空袭之后飞走了，毛岸英和作战参谋高瑞欣又从防空洞里跑回作战室处理电报
: ，晚上将发起第二次战役，还有许多工作要做。
: 不料，飞远了的敌机又突然调过头来，向志愿军总部所驻地的小山村俯冲，倾泻汽
: 油弹。顿时，志愿军总部一片火光！
: 后来，人们从被烧焦的尸体的腰间，发现了斯大林所赠的德制手枪和手腕上戴的那
: 只苏联产的手表，确认了这是毛岸英的遗体。

s*t2013-01-23 08:01

10 楼

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

m*y2013-01-23 08:01

11 楼

一直都是处理电报
蛋炒饭都是你们这帮伢们想象出来知道运点大米上去多不容易吗？哪里有剩饭给你蛋
炒饭？连VOA都知道说是挂面

e*a2013-01-23 08:01

12 楼

是 FSD职位吗您老一看就像科班出身不是他们的 style 呵呵

s*t2013-01-23 08:01

13 楼

这个是比我的写得要好些！

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*e2013-01-23 08:01

14 楼

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*t2013-01-23 08:01

15 楼

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*j2013-01-23 08:01

16 楼

这个是可行的，但是如果要打印出一棵树的所有层次来，不是要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*t2013-01-23 08:01

17 楼

题目本身要求打印某一层，所以应该不存在你说的问题。

【在 t*****j 的大作中提到】

: 这个是可行的，但是如果要打印出一棵树的所有层次来，不是要call很多次吗？对每一
: 个height都要call一次？那得recursive很多次啊。
: 第一层 recursive 0次第二层recursive 1次，第n层recursive n次..
: 哪里有queue的好啊，那个才只是一次遍历下所有节点。
:
: heightDesired)

d*e2013-01-23 08:01

18 楼

呵呵，我也没看清楚，如果是只打印一层，那是比较好，不需要queue而且也是O(n)的
时间

【在 s*******t 的大作中提到】

: 题目本身要求打印某一层，所以应该不存在你说的问题。

y*y2013-01-23 08:01

19 楼

我on-site的时候也遇到这个题...不过是打印某层之后所有的节点. 这样是不是用
queue比较好了啊?
当时也是废了好大劲才让两个面试官明白...

i*e2013-01-23 08:01

20 楼

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*a2013-01-23 08:01

21 楼

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*s2013-01-23 08:01

22 楼

pat pat, move on

l*a2013-01-23 08:01

23 楼

如果我是那个 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*g2013-01-23 08:01

24 楼

楼主发挥的很不错了，虽败尤荣，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*12013-01-23 08:01

25 楼

我和同学的经历是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*n2013-01-23 08:01

26 楼

。。。技术好牛。想起我师兄的一句话，面试的时候看的不仅仅是你题答对了没有，在
你回答的过程中，任何一个细节都透露出你的思考模式，你的行为习惯，还有你的性格
。也许lz思考的方法他们不喜欢？
其实还有一个可能，面试官自己也许就不具备通过面试的能力，可能当场写相同代码写
得并不如你？
一来他们可能自卑了，没来由不喜欢你，就fail你，二来，也有可能他们误以为你上来
就写这么好，是因为事先背过题，在生搬硬套？
anyway，move on，楼主技术这么强，肯定会有更好的offer等着你啦。

c*u2013-01-23 08:01

27 楼

这么难呀，看来俺还是不去了，随便投了份简历，下周要来学校interview。不是cs出
身，第二轮这么难，本来想去赚点第一轮面试经验的，要是也这么难还是算了，嘿嘿。