forked from HuskyBin/Need-To-Do
-
Notifications
You must be signed in to change notification settings - Fork 3
/
mitbbs的大部分题目(必看)
3656 lines (2017 loc) · 105 KB
/
mitbbs的大部分题目(必看)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
不敢保证全部涵盖,大部分的都在。
我自己找了一遍,大家一起用着都方便。
不过只是含有题目的帖子 我才包含进来了,只分享经验没贴题目的 我都没有包含
进来。
大家复习着方便。
1. 一个sorted interger Array[1...N], 已知范围 1...N+1. 已知一个数字missing。
找该数字。
把原题改为unsorted,找missing数字。 performance。
2. 复制linked list。 已知每个节点有两个pointer,一个指向后一个节点,另一个指向
其他任意一节点。 O(n)时间内,无附加内存,复制该linked list。(存储不连续)
3. 一个party N个人,如果一个人不认识任何其他人,又被任何其他人认识,此人为
celebrity。用O(n)时间找到此celebrity。
4. 给中序后续,构建树。
其他的每轮都问了简历。
感觉答的都不错,没什么难度。不知道为啥就被拒了。总之感觉很奇怪,不过也无所谓
了。
希望对大家有帮助。
Pasted from <http://www.mitbbs.com/article_t/JobHunting/31342084.html
>
贡献一道cs面试题,虽然我的面试机会极少。 :D
设计一个函数,返回一组数字的组合,combination,
不同的是,你每调用它一次,它就返回下一个组合,而不是一次全返回。
注:你不能一次算完,把他们存起来,而必须临时算!
Pasted from <http://www.mitbbs.com/article_t/JobHunting/31347263.html
>
IT company, 全都是brain teaser, 有点老。
1. 50个黑球50个百球,2个罐,要求你放这100个球在这2个罐,使得别人随机从2个
罐中任意拿一个球是黑球的几率达到最大。
2. heard on the street 上的男人出轨题,简单逻辑推理。
3. 这个没答上来,后来给了提示做出来了,但是回头想想还是不对。上来请教一下
。
2个人商量好策略,然后一个从52张牌里面随机抽5张,看牌,考虑。。。然后排在
桌上,摊开前4张,第5张面朝下,由第二个人判断第5张牌。 问这个策略。
Pasted from <http://www.mitbbs.com/article_t/JobHunting/31347264.html
>
这周一面的,一共5个人,碰到的题目不太难:
1. 写atoi函数,
测nodepad
2. 古老的三角形问题:输入3边,看是什么三角形。
一个mobile device可以从服务器上传和下载图像,怎么测试这个系统?
3. lunch meeting之后回办公室打开电脑,说他们现在开发的某产品有问题,每次要
loading很久,差不多10秒的样子。问怎么测试并找出这个bug? 这个把我难住了,胡乱
讲了一通,然后说太困难了;于是他换了个题目,画了一个plotter软件的界面,问怎
么测。
coding的题目是Path Walk,给一条路径,写一个函数来走通它。其实这个题目我没
搞明白什么意思,先沟通了很久,最后开始写(还是不太明白。汗...),写完了觉得
不正确,正想再改改,被打住了,说给个test case一起来看看程序怎么执行。每句代
码跑了一通,却发现code写正确了:-)
4. 一开始是个IQ题,把一堆数字填到格子里,满足一些条件,比如1和2不能相邻。
测一个记事薄软件。有scheduler和notifier两部分,可以从scheduler输入时间和
内容,然后notifier到预定时间会给出提醒。
coding题目很容易,找到单链表倒数第N个节点。
5. 最后是hiring manager,问了一些behavior问题,然后打开一个网站,问怎么测试。
Pasted from <http://www.mitbbs.com/article_t/JobHunting/31348374.html
>
在onsite面试中实际遇到的。
1.template中用typename和用class有什么区别?
2.unix下执行shell脚本和执行可执行文件有什么区别?哪个更快,为什么?脚本语言
程序(如javascript)和可执行文件程序有什么区别?shell和这两者却别呢?
3.如何对const data member做assignment?
class A{
const int a;
public:
A():a(0){};
A(int m_a):a(m_a){};
};
int main(){
A a(1);
A b;
b = a; //how to implement assignment for this?
}
4.如果把base class对象赋给derived class对象,会怎么样?compiler报错还是执行错
误?
class A{
public:
int a;
};
class B:public A{
public:
int b;
};
int main(){
A a;
B b;
b = a; //what happend?
cout << b.b << endl;
B* b2;
b2 = &a; //how about this?
cout << b->b << endl;
}
Pasted from <http://www.mitbbs.com/article_t/JobHunting/31348607.html
>
两波两小时,第一波老白+老印,小兵
1. 介绍Recent Project
2. 两个C的程序问题
先是char*指针问题
char *dosth()
{
char s[256];
char * p = r;
p = "some new string":
}
然后问了一堆变量的值,比如 s, *s, *(s+2), &p, etc.
另外一个switch程序找错,没有加break之类,还有就是return local variable地址的
问题
3. 手写fab(n)函数,不是算,而是输出,递归或者循环都可,不过递归不高效大家应
该知道
4. 逻辑问题:八个水罐称重
5. 一堆关于OO概念的问题,多态,继承,封装,接口和抽象类的区别,复写和重载(
包括C++具体怎么实现的)
6. 反馈问题
第二波一个项目经理
一来就是比较高难度的,给你一个字节数组(注意取值范围),数组长度可能非常长,
如何找到第一个只出现了一次的数字。开始没什么思路,和他讨论了一会,边问还边问
复杂度和数据结构的问题,后来发现应该进行数出现次数,这样复杂度就是2n,结果
出来了要求手写出代码。
然后就是一个智力问题,三个囚犯黑帽白帽,之前没见过,所以用了不少时间才想出来
,大家可以搜搜,有现成的。 最后反问问题后结束。
虽然每个问题都答出来了,不过最后还是功亏一篑。不是很清楚什么原因,哪位同学能
够指点一下?现在继续回归闺中状态中。不过感觉彭博问题的重复概率很大,希望对后
来的同学能够有所帮助:)
Pasted from <http://www.mitbbs.com/article_t/JobHunting/31350186.html
>
1, C vs C++
2, struct in C v.s. in C++ v.s. class in C++
3, virtual function, pure virtual function, abstract class
what is the advantages of using virtual function
4, new v.s. malloc()
5, memory for a process (code, static data, stack, heap)
6, how to know the stack is growing in the direction of address increasing
or decreasing
7, virtual memory
Pasted from <http://www.mitbbs.com/article/JobHunting/31354737_3.html
>
nsite 只见了2个人,估计over了,总结一下教训。
题目不难,主要一共3道题,都算比较基础的题。
1.reverse words in a sentence,使用如下函数。
char* reverseWord(const char* str)
2.an interger array containing millions of elements with min 0 and max 1000,
how to sort it?
3.covert interger number to date string, for example, 20090130 -> "01/30/
2009"
说说教训:
第一道被输入const给搞死了。先是没有注意const,直接按照常规非const做,没有写完
就被叫停了;然后是被平时强调的malloc后必须及时delete规则搞死,坚持认为在函数
里malloc一块内存然后在函数外delete是不好的习惯;最后当面试者提出如果定义一块
内存
,如char tmp[2048],然后使用会怎么样?自己提到可以在函数外strcpy函数返回结果
,却忘了
arr大小实际是无法指定的,所以这种方法是不可接受的。总之,很多的trick在里
面没有注意到。
第二道使用couting sort应该就可以。面试者要求描述算法,不需写代码。
第三道自己的做法是先取得30,然后01,然后2009然后组合成一个string。问题是这样
的话,月和日的01前的0可能会丢失,使得最后结果可能不对。后来想正确的做法应该
是先把整形转成string,然后使用substr并组合。另外,面试者问有stl有什么可以替换
itoa,自己答不出来。后来查了下,应该是可以使用stringstream来实现,如下:
stringstream ss;
ss << intVal;
ss.str()就是我们要的结果。
Pasted from <http://www.mitbbs.com/article/JobHunting/31356298_3.html
>
现在版上的文章好像已经以H1申请为主了,不知道多少人还对面经感兴趣。不过想想还
是写一下好,要不自己过几天可能就忘光了,呵呵。
申请工作:Software Developer,Mobile Application组
问题问的很多很杂,基本上不难。不过后来想想,也没有全都答对。大概包括:
* 为什么对Amazon感兴趣。
* 自己最近的Project。
* 说出自己会的编程语言并打分(1-5)。
* 有没有开发Mobile application的经验。
* 几个常见Data structure的Lookup操作的时间复杂度。
* HTTP post和get的区别。
* Design Pattern: Singleton, Factory, Lazy initialization。
* Multi-threaded programming, deadlock之类。
* 对Unix环境是否熟悉,几个常见命令,ls, ps之类。
* Reflection的概念,Java reflection,C++里面是不是有reflection。
* 如何实现Garbage Collection。Reference counting的缺点(cycle),如何解决,JVM
有没有解决。
* C++里面virtual destructor的用途,于一般virtual function的区别。
* 写一个函数实现两个整数相除,不用"/"和"%",返回商和余数。写完读给他听。
* 算法设计:一个Galaxy,每个星星用一个三围座标表示,找出离地球最近的1000个。
(后来发现这也是老题了)
Pasted from <http://www.mitbbs.com/article/JobHunting/31368921_3.html
>
have read many posts here although not really helpful this time, here is
something about bloomberg's phone interview question
1. How to implement garbage collector ( what data structure)
2. How to implement c++ smart pointer
3. Pro and Con of multi process and multi-thread
4. How many stack/heap does a multi-thread program with 10 threads have?
there are some other questions I don't remember.
☆─────────────────────────────────────☆
yellpine (fresh CS master looking for referral) 于 (Wed Mar 4 16:42:52
2009) 提到:
4. How many stack/heap does a multi-thread program with 10 threads have?
who can help me with this?
10 stacks? 1 heap?
Pasted from <http://www.mitbbs.com/article/JobHunting/31373641_3.html
>
估计没有多少人感兴趣,
不过还是说一说.
面的是ELASTIC COMPUTING CLOUD组的SE,我是做网络的,对他们的这个cloud service有
些兴趣,以为会问算法和系统的问题,结果问了一个OOD的问题,
说一个大楼,10层,4个电梯,怎么设计类来实现这样一个系统?
题目career cup上有,不过没想到他会问这个,ECC又不是做应用的.刚好是我的弱项,一
直做research,对算法和语言还算了解,对应用系统和设计那是一片空白.面的是一塌糊
涂. 有要面amazon的参考一下.
Pasted from <http://www.mitbbs.com/article_t/JobHunting/31376671.html
>
S Master
Windows Live Experience 组:
我一直催HR,今天给我打电话说拒了。 汗了--自我感觉还挺好的。
拒了 也把经验给大家分享一下,在版上受益这么多,回报一下大家。
一共见了5个人, 两个SDET, 两个SDET lead, 最后一个director。题目都很简单
1.美国人。上来随便聊聊,然后出了个coding 题目 一个数组,找出第一个重复的数
我给了三种方法,最后用hash写的,然后问test case之类的
2.印度人
上来问我会什么C#还是C++,我说C#会的多一些。然后他上来问了四五个简单的 语法
问题。正好我还都会,心理还窃喜着呢。coding 也很简单,给一个01字符串,转化成
整数。写完后 test case。 第二个题目是两个函数互相调用,无限循环了,然我找出
毛病,问怎么解决。
然后午饭跟这个印度人吃,随便聊聊。 就过了
3.欧洲人,不知道哪国。
女的, 人很好,跟她聊的最开心。coding 题目是个没见过的,double bytes
string实现delete键功能。这个比较难解释,她开始也跟我解释了很长时间。 就是删
除字符的时候如何确定是删一个字节还是删两个字节的问题。我给出算法,然后她有提
示有哪些特殊情况要考虑,也做出来了。然后她就问我给一个一般的application 如何
测试,又随便说了一通,结束了
4.美国人 senior test lead
coding 很简单,给一个句子,把里边所有的单词自身reverse
然后给我看他们的产品,问我怎么测试。聊的也挺好
5.欧洲人 director
面到这个人的时候,我都快累趴下了,都不想面了,实在是累。心理还想着,offer拿
不拿得着无所谓,别把老子给累死了。(看来真得努力锻炼身体,不然面试都挺不住)
题目也很简单,找1--100的素数。我就给了最简单的方法,然后我说要 check一些边界
情况,他说不用了。然后让我做到他的椅子上,打开excel,问我怎么测设置字体这个
feature。说完了问我有什么问题没有
面完后觉得还不错,因为去之前心态还不错,现在就业情况不好
也怕,没打算毕业。
后来回到学校我就一直催HR赶紧给我结果,今天就给催出来了 呵呵
我说打算postpone到年底毕业,他说到时候可以直接再联系他(有个屁用啊 呵呵)
在学校继续呆着吧,呵呵,把身体锻炼好,面试也是一个体力活。
写出来 希望对大家能有点帮助。
Pasted from <http://www.mitbbs.com/article/JobHunting/31383513_3.html
>
iantianz (tiantianz) 于 (Thu Mar 12 15:23:30 2009) 提到:
刚刚电面了一家中型软件公司的summer intern,问了一个算法题:
给你一本dictionary,任意给你七个letters,让你找出包含这七个字母的、最长的单
词。
条件:可以pre-processing,这样每次给你不同的letters时,可以very effcient
我当时想了好久也没给出完整答案。。。
naive 的解法当然就是每次scan dictionary,每次 O(n)。。。
pre-peocessing那就是建index,但index怎么建?怎么操作?
Pasted from <http://www.mitbbs.com/article/JobHunting/31387661_3.html
>
MichaelChen (Michael) 于 (Thu Mar 12 17:05:44 2009) 提到:
上学期ON CAMPUS的INTERVIEW,PENDING了几个月给了ON SITE
两周前去的,面的FULL TIME SDE。
见了5个人
1.REVERSE LINKLIST.
2.给了N个数,值域[1,N-1],如何找出第一个重复的数
3.算POLYNOMIAL,比如5x^4+6x^3-7x^2-8=?
4.给一个URL,如何把空格这种字符转换成%20这种
5.给一个LINKLIST,VALUE的指针指向其他NODE,复制他
今天RECRUITER发邮件通知给OFFER了,漫长的两周。。。希望收回OFFER这种事不要发
生。。
准备基本就是看MITBBS精华区,programming interview exposed和careercup,希望大
家都好运,ms应该还是在招人。
Pasted from <http://www.mitbbs.com/article/JobHunting/31387663_3.html
>
攒rp,最近遇到的面试题。。。
C++:effective c++上的东西若干;exception相关;继承和子父类指针若干. 十五分
钟左右。
算法/编程:1. 大文件随机sample,one pass. 2. sodoku solver. 3. logn解x^y,
4. DP题 5. 1Billion query里选出时间最近5分钟内最frequent的1000个,one pass
(我以前在amazon见到过这题)。6.两个排序数组找共同中值。递归和非递归解法。7.
斐波那契数列。100层楼梯下楼,可以一步也可以两步,多少种下法?递归和非递归。
8 贝叶斯后验概率。9。多少人在一起,生日可能出现重复概率大于0.5?(算法导论原
题,我只记得个答案,直接说了。。。)10. 一个数组,找最大值比较次数?同时找最
大值和最小值比较次数?找最大值和次最大值比较次数?(他问我是否知道这题,我说
是作业题。后来和师兄聊说是这他常拿来用的面试题。)
系统设计和经验:1 设计一个库,提供timer的功能。deltalist/hash,或类似linux
kernal的 timer 设计。效率要比较高。2. 一个类似chord的DHT设计。3. 你有一个奇
怪的程序,有时有bug,有时没有,说出尽可能多的可能原因。4. printf来debug有何
不妥。5. process和thread。process之间的IPC有那些种?process间是否也可以share
memory.何时选thread或process。
Pasted from <http://www.mitbbs.com/article/JobHunting/31393101_3.html
>
职位是 junior financial engineer, 公司是一hedge fund,其实面完就感觉不太好,
一共见了6个人,有两个人问得技术问题答得不太好,也怪自己事先准备面试下的功夫
不太到家,准备得重点没有把握好。以下是一些能想起来的问题:
1。C++ 中的virtual destructor是啥? 为啥要用?
2。quick sort, merge sort的复杂度。
3。 Structure 和class的区别是什么? (我晕,这个我居然给答反了)
4。关于C++ 处理异常的方法 。 (基本上一头雾水)
5。Monte Carlo method in american style option pricing。 (我说的用least
square regression method,blah......)
6. Int_0^T W(t) dW(t) ( 一看见这个,贼激动阿,熟悉的ito' s formula)
7. Stonivich intergral 是啥? 为什么用Ito's 不用 stonivich? (不知道拼得对不
对)
8. 一个国家所有的人如果生了一个男孩以后就停止生育,生了女孩以后就继续生,直
到生出男孩才停止生育,问多年以后男孩多还是女孩多? (要联系上stopping time的
概念)。
9。什么是AR model? 啥时候用AR model?
10. American option 的up bound? (我说是stock price,被直接鄙视了,说更精确的
,只好答没有研究过,当时一头雾水)。
以上的是我能记得的一些问题,还有一些关于数据结构的问题我就彻底歇菜了,从来没
有这方面的背景,也就不记得他的问题了。
还有就是,关于自己的简历上面的Project 工作经历,一定要熟练再熟练,有些人问得
那叫一个细啊,而且基本上我所有的Project都被人问到了。这次面试的前4个人主要问
计算机和金融方面的技术问题,第5个HR,问些personality的问题,最后是hiring
manager,因为之前电话面试过我,就没有问问题,简单聊聊。整个面试花了5个小时,
雷死了,脑子到后面都已经不转了。虽然结果让人遗憾,不过就当是学习了,贴点信息
和大家共享下,希望自己能早日找到工作,也希望还在努力找工作的XDJM们再加把劲,
大家一起加油。
Pasted from <http://www.mitbbs.com/article/JobHunting/31406731_3.html
>
CS方向,希望对大家准备面试有帮助
1. 用stack class来实现queue,具体用几个stack不限。完了以后问怎么实现thread
safety,然后是怎么测试。
2. 实现strstr(str1, str2),如果str2是str1的子串,返回true,否则返回false。实
现完了以后问如何测试。
3. 给定一个integer array with both positive and negative numbers,return a
contiguous subarray with the largest sum. 我本来想用dynamic programming实现
,但面试官希望按照他的一个更heuristic的思路来解,最后勉强搞定。
4. 给定一个排好序的linked list,删除其中所有的重复元素。比如给定1->2->3->3->
4->4->5,返回1->2->5。给定1->1->1->2->3,返回2->3。看起来简单,一边写一边发
现许多细节需要小心应对,好在最后搞定。
5. 给你三个烤箱,每个烤箱可以同时烤两片面包,需要的时间分别是3分钟,4分钟和3
分钟。但第三个烤箱有一个slot出了点问题,每次只能烤面包的一面。所以这个烤箱三
分钟后只能算烤好一片半面包,你需要把那半片翻个面,在同一个slot里再烤一次才算
一片完整的。现在给你这三个烤箱,问烤好21片面包最少需要多少时间?如果是2100片
呢?如果是任意给定的N片,要求O(1)时间内给出最少需要的时间。
6. 给你三根棍子,每根都需要一个小时才烧完,但每根燃烧的速度都不一样,也不均
匀。问只有这三根棍子和火柴,如何精确的得到1小时45分钟的计时?
7. 在一个party上,每个人可能认识别人,也可能不认识。现在其中有一个人是名人,
定义就是所有的人都认识他,但他不认识其余的任何人。现在要求你去找出这个名人来
。但你只可以通过一个方法,就是问A是不是认识B,回答是表示A认识B,不是表示A不
认识B。你可以任意去问这样的问题,问最少需要多少次能找出这个名人?思路有了之
后要求写代码实现,可以调用knows(A, B),代表上面的那个问题。实现完了以后问如
何测试
8. 测试copy这个命令。然后自己问了一些clarifying questions,搞清了实际上是
copy src dest。src可以是文件,也可以是目录。dest可以存在,也可以不存在。
Pasted from <http://www.mitbbs.com/article/JobHunting/31410833_3.html
>
OO设计题,怎么做一个十字路口的traffic light.
2. 怎么不用recursion 做二叉树in order 遍历。
Pasted from <http://www.mitbbs.com/article/JobHunting/31421129_3.html
>
1. Write a function that returns a node in a tree given two parameters:
pointer to the root node and the in order traversal number of the node we
want to return. The only information stored in the tree is the number of
children for each node.
2. Input a message and a text, find if the message can be composed by the
text.
If the text is in a magazine (two pages/a paper), how to design an algorithm
?
Pasted from <http://www.mitbbs.com/article/JobHunting/31422009_3.html
>
1
When casting an object of a polymorphic class from a base calss type, which
one of the following casts
performs the task only if the cast is valid?
a. static_cast
b. (void*)
c. dynamic_cast
d. const_cast
e. reinterpret_cast
2. class A
{
public: void f();
protected: A() {}
A(const A&) {}
};
why are the default and copy constructors declared as protected?
a. to ensure that instance of A can not be created via new by a more derived
class
b. to ensure that instance of A can only be created by subclasses of A
c. to ensure that isntance of A can not be copied
d. to ensure that A cannot be used as a base class.
e. to ensure that A cannot be instantiated on the stack
3. template<class T1; class T2; class T3>
int Product(T1 a, T2 b, T3 c)
{
return a*b*c;
}
what is wrong with the sample code above?
a. templates must be class definitions
b. the template parameters should be separated by commas.
c. the template definition is missing a pair of braces.
d. template parameters must be pointer types.
e. the * operator has not been defined for T1, T2, and T3.
4. class FOO
{
char * buf;
public:
Foo (const char *b = "default")
{
if (b)
{ buf = new char[std::strlen(b) + 1];
std::strcpy(buf, b);
}
else
buf=0;
}
~Foo() { delete[] buf; }
};
Foo func (Foo f)
{
return f;
}
when the function fun is called, the program may crash or exhibit unexpected
behavior, what is the reason ofr this problem?
a. the destructor may attempt to delete the string literal "default"
b. the destructor needs to check that the value of buf is not 0.
c. the class does not allocate a long enough buffer.
d. the function needs to return Foo& instead of Foo.
e the class needs to specify a copy constructor and assignment operator.
Pasted from <http://www.mitbbs.com/article/JobHunting/31426509_3.html
>
1.请书写一个程序,将整型变量 x 中数字左右翻转后存到另外一个整型变量 y中,例
如 x = 12345 时,y为 54321,x = ‐123 时,y为‐321。其中 x 的个位不为 0。
void reverse (int x, int* y);
(1) 请实现该函数,以上函数原型是用 C语言写的,你可以用你熟悉的语言;
(2) 请写出一段代码验证该函数在各种情况下的正确性。
2.对集合{1, 2, 3, …, n}中的数进行全排列,可以得到 n!个不同的排列方式。现在
我们用字母序把它们列出来,并一一标上序号,如当 n=3 时:
0.123
1.132
2.213
3.231
4.312
5.321
现在,请书写一个函数 void print (int n, int k), (函数原型是用 C语言写的,
你可以用你熟悉的语言)在已知 n和序号 k 的情况下,输出对应的排列,并简要阐述
思路。
3.一维数轴上有 n 条线段,它们的端点都是已知的。请设计一个算法,计算出这些线
段的并集在数轴上所覆盖的长度,并分析时间复杂度。例如,线段 A 的坐标为[4, 8]
,线段 B 的坐标为[1, 5.1], 那么它们共同覆盖的长度为 7。 请尽量找出最优化的
算法, 解释算法即可,不必写代码。
Pasted from <http://www.mitbbs.com/article/JobHunting/31428195_3.html
>
Given a sorted integer array and a number, find all the pairs that sum up to
the number.
这个很简单,但现在多了一个条件
What if the array is sorted by absolute value, for example {1, -2, 4, -9},
find the answer in O(N).
这样有什么好的思路么?
Pasted from <http://www.mitbbs.com/article/JobHunting/31430593_3.html
>
How do you find sequences of consecutive integers in a list that add to a
particular number.
Array里面正负数都有.
这个能在O(n)时间内解决吗?
Pasted from <http://www.mitbbs.com/article/JobHunting/31431861_3.html
>
A m*n matrix of integer, all rows and columns are sorted in ascending order.
Find the most efficient way to print out all numbers in ascending order.
Pasted from <http://www.mitbbs.com/article/JobHunting/31434325_3.html
>
一次面世Google,问到hash table是怎么实现的。我说了一个取尾数(round)的方法
,他说这个方法很navie,工业界一般用其他的方法,比方说STL的map。
我想了半天没有想出来,到这里问问。hash table具体怎么实现的啊?
Pasted from <http://www.mitbbs.com/article/JobHunting/31434401_3.html
>
49 辆赛车. Assume for each one, it travels the track in the same amount of t
ime every time. Also assume no two finish the track in the same amount of ti
me. Suppose you have 7 tracks, but no timer. Design races to find the 25-th
fastest with minimal number of races.
Pasted from <http://www.mitbbs.com/article/JobHunting/31434523_3.html
>
ime span: 38:39
interviewers: 2 -- 1 indian, 1 american
How do you know the bloomberg?
What position do you expect?
What language do you want to answer with? (I choose C.)
What kind of questions do you meet for the online assessment?
what is static in C? how is it implemented by the compiler?
write the definition of a function that returns both the max and min.
why do you use the condition variable?
how to implement a lock?
Under what condition must you use linked list instead of array?
what data structure can you use to store elements dynamically and access
them efficiently?
The complexity of finding any element in a linked list in the worst case.
multi-thread library programming: did you write your multi-thread library
with p-thread? is there any problem you have with you library?
did you do your projects on linux? If you want to find a string in a file,
what command should you use?
do you know vector in C++?
a question about real-time programming (I forgot)
what is buffer overflow?
一些问题是针对我的简历里面提到的内容,所以,简历里面的内容要尽量的吃透。
Pasted from <http://www.mitbbs.com/article/JobHunting/31434685_3.html
>
Given two classes:
class B
{
public:
B(args_1);
B(args_2);
// and many constructors with different arg lists
};
class D : public B
{
public:
D(args_1) : B(args_1) {}
D(args_2) : B(args_2) {}
// and many constructors with different signatures similarly implemented
// some additional stuff specific to D
};
Assume that the arg list for B's constructors are quite long and may be
revised pretty often in the future, in which case D's constructors have
to be recoded correspondingly. Duplicating the update by copy-and-paste
will certainly work here. Can you propose a better way so that the
update can be done in one place without copy-and-paste duplication?
Pasted from <http://www.mitbbs.com/article/JobHunting/31434891_3.html
>
Given a large string (haystack), find a substring (needle) on it.
感觉这道题不就是scan一遍吗?
有什么time and space complexity上面的trick吗?
Pasted from <http://www.mitbbs.com/article/JobHunting/31435419_3.html
>
准备了很久,看了很久算法的书。。 结果被问了一个怎么 optimize memcpy()..傻
眼了。。碰到了女老印,倒霉~~~~
Pasted from <http://www.mitbbs.com/article/JobHunting/31435587_3.html
>
规问题后,问了个code的问题:
给一个substr,如何判断它在不在给定的str里面。
substr有两个新的符号可能在里面:
(1)* : 0-n个任意字符
(2)? : 1个任意字符
太紧张了,所以面试者简化了题目,说去掉“?”,然后让code和测试:基本框架出来
了,但是好多特殊情况没有处理到,比如substr以“?”起头。
后来又问如果加入“*”有没有思路,刚说了两句就out of time了。
唉,失败了,不知道有没有下文。
Pasted from <http://www.mitbbs.com/article/JobHunting/31436721_3.html
>
给定 X[1..n] and Y[1..m] 两个 arrays,已经sort好了.
如何找到X <Union> Y的median?我说用merge sort,要O(m+n/2)时间。面试官明显不
满意。
这个已经 lineal了?难道还有更快的?
Pasted from <http://www.mitbbs.com/article/JobHunting/31437417_3.html
>
given a 32 bit number N and 2 numbers(A & B) that determine 2 different bit
pos
itions of N how do you make all the bits between A and B equal to another
given
integer k.
given (A,B is in the range [0 to 31] and
k<=2^(B-A+1) ( so that k fits between B-A+1 bits). Give an O(1) solution for
th
is
e.g if N=9 ( 1001) ,A=0 ,B=2,K=5(101 then the result should be 1101 (1.e 13)
这个题是什么意思啊?
Pasted from <http://www.mitbbs.com/article/JobHunting/31437907_3.html
>
在做careercup上面的题目, 有两个问题没有看懂, 希望有人指点下
1 一个BST, 给定一个值, 打印出所有的path,使path上所有节点的值等于给定值;
2 一个tree, 如何高效的找出最长的path?
☆─────────────────────────────────────☆
mitbbs59 (59) 于 (Fri Jul 3 15:35:37 2009, 美东) 提到:
这都是amazon的题目吧
1.sum of all nodes in a path = givenValue
2.http://www.careercup.com/question?id=87897
Pasted from <http://www.mitbbs.com/article/JobHunting/31441709_3.html