2008年10月EMC笔试

zhiqiang10月 25, 2008 IT技术

今天下午去EMC笔试了。笔试题目分四部分：求职意向3题，专业基础知识和智力题25道，编程题3道，英语作文。全英文题目和作答。虽然前面关于操作系统，网络协议，C++的题目我大多都不会，但就后面那些数学和智力题而言，我觉得它们的题目出得非常好。考试时居然没签保密协定，所以我可以在这里随意透露题目 ${#emotions_dlg.titter.gif}$

下面有些内容由留言区网友提供，不一一指出。

$97^{59}$ 除以59的余数是多少。

答案是38，这个题目考费马小定理；不过直接硬算也可以。

int a=1000000000, b=2000000000; a=a+b;b=a-b;a=a-b; 最后a，b是多少？

正常交换。

如何判别一个数是unsigned

我选了 a>=0 && -a>=0；但据说正确答案是 a>=0 && ~a>=0 ${#emotions_dlg.sad.gif}$

100层楼，两个鸡蛋。某层之上扔鸡蛋就会碎。问至少要测试多少次才能试出这个层数。

动态规划，答案是14。这个问题讨论很多了。

具体方法是先从14楼开始抛第一次；如果没碎，再从27楼抛第二次；如果还没碎，再从39楼抛第三次；如果还没碎，再从50 楼抛第四次；如此，每次间隔的楼层少一层。这样，任何一次抛棋子碎时，都能确保最多抛14次可以找出临界楼层。

25匹马，每次比赛可选5匹马赛出次序（无法计时）。问至少要比赛多少次才能确定跑得最快，次快和第三快的三匹马。

7次。首先分为5组，每组进行一次比赛，然后每组的头一名共五匹马比赛一次。假设第一组快于第二组快于第三组依次。最后一次安排第一组的二三名和第二组的一二名和第三组的第一名。

上台阶，每次可走一台阶和两台阶，问上10个台阶有多少种走法

斐波那契数列。答案89

A、B、C三个瓶子，A瓶子是空的，B瓶子里有1个白球1个黑球，C瓶子里有1000个白球和1280个黑球。现在蒙着眼睛从C瓶子里取两个球放到A瓶子里。分两个阶段从三个瓶子中摸球（每次摸球后放回再摸下一次），摸到白球赢55000美元，摸到黑球什么也得不到也不损失什么。问为了使两次的收益最大，应该采取什么策略？

算了一下答案应该是两次都在B里面拿。

我又挂了一个题。

大题1：插入一个节点到一个有序链表。

大题2：循环的有序数组（比如1，2，3，4，5，-3，-2，-1这种数列）里查找一个数

大题3：在一个正整数序列中求和最大的非相邻子序列（序列任两元素在原序列里都不相邻）

还有好多题，忘了，想起来了再加。

做完了才发现判卷时先看小题，小题过了才判大题。大题也太简单。估计挂了 ${#emotions_dlg.crying.gif}$

查看更多关于EMC, 笔试, 面试题的内容。

你可能感兴趣的

At 2008.10.26 01:45, woodsword said:

下午也去考了，智力题做得太悲惨了...惨不忍睹...肯定挂了
如何判别一个数是unsigned
我选了 a>=0 && ~a>=0

[Reply]
- At 2008.10.26 09:08, zhiqiang said:
  
  ~a是啥意思来着？
  
  [Reply]
  - At 2008.10.26 09:54, karpar said:
    
    按位求反吧，你这种水平应该直接参加面试的，哪里还要笔试的？
    
    [Reply]
At 2008.10.26 07:47, Mr.Hdq said:

全是专家，偶可与IT联系少得紧！

[Reply]
At 2008.10.26 09:37, pkughost said:

100层楼，两个鸡蛋。某层之上扔鸡蛋就会碎。问至少要测试多少次才能试出这个层数。——动态规划。
这题不是O(n^{1/k})么...似乎不是dp啊..

[Reply]
At 2008.10.26 09:48, 夜弓 said:

我也去了，a>=0 && ~a>=0应该是对的
使用-号，即使是signed的话，也-a还是为0
但是~按位求补应该是0xffffffff，这应该是最小的负数

[Reply]
- At 2008.10.26 10:01, zhiqiang said:
  
  To 夜弓：
  unsigned的变量有什么特征？根本不懂这些东西，唉，平时编程太少了，写点程序也是最简单的那种，这种细节化的东西从来没用过。
  
  To pkughost：
  O(n^{1/k})是k个鸡蛋的渐近解，准确解还是需要动态规划去做。比如说两个鸡蛋时次数应该是14，没错吧
  
  [Reply]
  - At 2008.10.26 10:33, karpar said:
    
    http://bbs.chinaunix.net/viewthread.php?tid=636613
    i think this should help.
    
    [Reply]
  - At 2008.10.26 12:47, 夜弓 said:
    
    To zhiqiang:
    unsigned一般来说是从0×00000000到0×00000000分别表示0,1,2,...
    而signed一般来说是0xffffffff到0×80000000分别表示-1,-2,-3,...
    从0×00000000到0×7fffffff表示0,1,2,...
    而第一个bit，就是符号位。
    负数比整数多一个，因为正数那部分花了一个位置表示0。
    
    [Reply]
  - At 2008.12.03 17:17, lonegunman said:
    
    -a应该是让编译器转成signed数字了,因为没有显式标明unsigned,我的一个小猜想.
    
    [Reply]
At 2008.10.26 12:27, Teddy said:

100层楼，两个鸡蛋。某层之上扔鸡蛋就会碎。问至少要测试多少次才能试出这个层数。——动态规划。

--------

RRDW，是不是我没看懂题目？莫非用二分法不行么？50扔一个，碎了往下，25层。。或者不碎75层，log2（100）,差不多7次把。如果是dp，规划式子是什么？

[Reply]
- At 2008.10.26 12:50, 夜弓 said:
  
  显然不是二分嘛，有无限个鸡蛋当然可以二分
  但是鸡蛋是会碎的
  这道题我见过，但是没仔细看，以致于考试的时候很郁闷，直接跳过，4分飘走
  
  [Reply]
  - At 2008.10.26 13:29, Teddy said:
    
    呵呵，是搞错了，是有这么个题目。
    鸡蛋碎了就没了。
    不知道2分一个鸡蛋结合另一个鸡蛋的普通方式试探不知可行否！
    Google不到这个问题，也不知道原始的问题是怎么描述的-_-~。
    有没有达人把这个问题的完整解答给小弟show一下。
    
    [Reply]
    - At 2008.10.26 15:09, 夜弓 said:
      
      还是不能用二分，即使拿一个鸡蛋来做，二分代价也太大了
      二分中的机会几乎是相等的，也就是说，一上来就有50%的几率告诉你
      鸡蛋坏了，五十个，慢慢找吧
      http://fafeng.blogbus.com/logs/14168877.html
      
      [Reply]
At 2008.10.26 12:38, Teddy said:

两个鸡蛋，也就每次分成三股，应该更少啊。

[Reply]
At 2008.10.26 12:48, 严酷的魔王 said:

这个是考多久的啊?

[Reply]
- At 2008.10.26 15:15, zhiqiang said:
  
  考三个小时，时间还是挺紧的。有些题目如果没见过的话一个题目估计就要十分钟，比如那个仍鸡蛋的。
  
  [Reply]
  - At 2008.10.26 15:29, 严酷的魔王 said:
    
    扔鸡蛋的那个我记得准备NOIP的时候专门写过动规程序～
    
    [Reply]
At 2008.10.26 12:54, 夜弓 said:

费马那道能够直接算？
用(a*b) mod c = ((a mod c) * (b mod c)) mod c来算？
我这样算了两步，给出结论这个方案不行
想了1分钟，终于从大脑里挖掘出初中学竞赛的时候埋藏的费马小定理

[Reply]
At 2008.10.26 13:09, 夜弓 said:

费马那道题记错了
貌似是
[tex]97^{59} \mod 59 = 38[/tex]

[Reply]
At 2008.10.26 13:47, stone said:

你应该申请research scientist，然后跳过所有C++题目:)

[Reply]
- At 2008.10.26 15:19, zhiqiang said:
  
  这样可行吗？我倒是想这么做
  
  那些操作系统和网络的我也不会做，非科班出身的，不会啊。
  
  [Reply]
At 2008.10.26 17:14, sammychen said:

偶也去考了，做得晕乎乎，但愿能有面试机会-_-

[Reply]
At 2008.10.26 18:51, pkughost said:

扔鸡蛋那个题的思想确实是dp，恩，一开始没想清楚。

[Reply]
At 2008.10.26 21:19, 发给 said:

拜托就算有保密协定你透露也无妨吧

[Reply]
- At 2008.10.26 23:22, zhiqiang said:
  
  有保密協議的話，不能隨便透露吧，被看到就鐵定掛了。
  
  [Reply]
At 2008.10.27 01:12, cuckoo said:

哎，我看一遍都是陈题，这些人也太懒惰了，不动动脑筋换些新题目。

[Reply]
At 2008.10.27 09:30, ray said:

有一题求概率的：A、B、C三个瓶子，A瓶子是空的，B瓶子里有1个白球1个黑球，C瓶子里有1000个白球和1280个黑球。现在蒙着眼睛从C瓶子里取两个球放到A瓶子里。分两个阶段从三个瓶子中摸球，摸到白球赢55000美元，摸到黑球什么也得不到也不损失什么。问为了使两次的收益最大，应该采取什么策略？

[Reply]
- At 2008.10.27 09:56, zhiqiang said:
  
  这个题目我把题目搞错了，没看到还有一个B瓶子。最后选了先摸A，然后depends。
  
  后来才知道有三个瓶子，郁闷啊。那个分两个阶段是啥意思？可以选从A，B，C里面摸球么，摸了第一次是否放回呢？
  
  [Reply]
  - At 2008.10.27 10:15, GClover said:
    
    摸了第一次是放回的，A里面的球不知颜色，B里面一黑一白，所以确实应该先摸A，然后depends，如果第一次从A里面摸出了白球，说明A里至少有一个白球，不会比B里面的白球少，因此第二次应该继续在A里面摸（可能是两个白球），但是如果第一次摸出的是黑球，那有可能A里卖弄是两个黑球，因此第二次应该从B里面摸
    
    [Reply]
    - At 2008.10.27 20:48, stone said:
      
      跟题目数据有关的，要算一下概率。
      原题中A中两个球来自25:32的白黑球总体。
      先摸A，摸到白球的概率小于1／2，但是有可能提高第二次中的概率。
      我算出来这种策略还不如直接模两次B。
      
      [Reply]
      - At 2008.10.27 23:01, zhiqiang said:
        
        那个球的个数比例是25:32么？我算了一下，先摸A的确还不如直接摸两次B呢。
        
        郁闷，又错一个，已经没几个对的了。
        
        [Reply]
        
        At 2008.10.27 23:31, stone said:
        
        1000:1280=25:32
        我当时也选错了
At 2008.10.27 10:05, 小和尚 said:

100层楼，两个鸡蛋。某层之上扔鸡蛋就会碎。问至少要测试多少次才能试出这个层数。——动态规划。和google的面试题一样。只不过不是鸡蛋，10吧，记得

[Reply]
At 2008.10.27 13:28, szuxjq said:

有一幢100层高的大厦，给你两个完全相同的玻璃围棋子。假设从某一层开始，丢下玻璃棋子就会摔碎。那么怎么利用手中的两颗棋子，用一种什么样的最优策略，知道这个临界的层高呢？答：先从14楼开始抛第一次；如果没碎，再从27楼抛第二次；如果还没碎，再从39楼抛第三次；如果还没碎，再从50 楼抛第四次；如此，每次间隔的楼层少一层。这样，任何一次抛棋子碎时，都能确保最多抛14次可以找出临界楼层。
===========================================================================================================
有36匹马，六个跑道？没有记时器等设备，用最少的比赛次数算出跑的最快的前三名马？其实用排除法就可以把过程看的很清楚了，前面的步骤一样，6组分别比之后6个第一名比，这时候，假设排名为：A1、 B1、 C1、 D1、 E1、F1，此时可以断定A1为最快的马，然后排除法，看那些不可能是前三：
1、D，E，F组全部排除；
2、A组后三名全部排除（前面至少已经有A1,A2,A3）；
3、B组后四名全部排除（前面至少已经有A1,B1，B2）;
4、C组其实后五名都可以排除（前面至少已经有A1,B1，C1）；

剩下的就只有：A2、A3、B1、B2、C1，跑一次ok了

[Reply]
At 2008.10.28 13:09, Patrick LIANG said:

int a=1000000000, b=2000000000; a=a+b;b=a-b;a=a-b
这道会溢出嗎? 我考虑是a=a+b这句会 > 2^31 -1 这时a会变为负数.....不知这样考虑对不对呢

[Reply]
- At 2008.10.28 13:51, zhiqiang said:
  
  用VC6编译显示最终结果不会溢出，正常交换了a, b的值。但对于中间是否溢出，我不知道。
  
  [Reply]
  - At 2008.10.28 14:38, Patrick+LIANG said:
    
    呀....是正常交換...我当时还以为中間运算时a的溢出会引起错误...
    选了个奇怪的选项,我又错一道了....
    
    [Reply]
  - At 2008.10.28 18:56, stone said:
    
    中间结果会溢出，但是在补码表示下，溢出得到的是[-2^31, 2^31-1]范围内的模2^32的结果。
    所以计算结果在摸2^32次方下是对的。
    
    [Reply]
At 2008.10.28 17:05, David said:

看不懂，我是新时代文盲

[Reply]
At 2008.10.31 22:18, DavidW said:

请教大题3有什么好的解法

[Reply]
- At 2008.11.01 09:51, zhiqiang said:
  
  找最长链，中间的那个或者两个点即为所求。
  
  [Reply]
  - At 2008.11.03 11:57, kira said:
    
    第三题应该是一个动态规划吧
    max[0] = num[0]
    max[1] = max(num[0], num[1])
    max[i] = max(max[i-2] + num[i], max[i - 1])
    
    [Reply]
    - At 2008.11.03 14:05, zhiqiang said:
      
      对的，我说的那个是baidu的第三大题。EMC这次笔试的大题目都很简单。
      
      [Reply]