EMC面试题

Question

先说我还没完全解决的题目：
(1)关于操作系统中cache的管理。规则是先舍弃使用次数最多的cache块。共有大约1000块cache。要求设计一个数据结构来支持以下操作，以使每种操作都能达到o(1)的时间复杂度。（n表示正在使用的cache块，N表示cache的数量）
1.n<N时，需要使用一个cache。
2.访问cache，包括访问后的调整。
3.n=N时，需要使用一个cache。
 
(2)这个是笔试时的题目，我没搞定。
比较S1和S2的大小：
S1 = 1 - 1/3 + 1/5 - 1/7 + 1/9 - ......
S2 = 根号（10/16）
 
 
下面是在提示下做出来的题目：
(1)一个N*N的对称矩阵，每行每列都是数字1~N的一种全排列。例如：
1  2      1  2  3
2  1      2  3  1
          3  1  2
注意，3*3矩阵的一条对角线也是1、2、3的一个全排列，而2*2的矩阵则不是。请问，什么样的N，能使N*N的矩阵在满足题目条件的情况下必然有一条对角线是1~N的一个全排列。
A.3的幂
B.奇数
C.除了2以外的质数
D.N=3
E.以上全对
 
提示：做一个小游戏，两人轮流在一个圆桌上放硬币，不准重叠。谁没法再放下一个硬币时算输。请问第一个人如何做才能确保胜利？最后桌上的硬币数量是奇是偶？

Answer 1

s1=1 - 1/3 + 1/5 - 1/7 + 1/9 - ......
  =2/3+ 1/5 - 1/7 + 1/9 - .....
  =42/60- 1/7 + 1/9 - .....
  <42/60s2=(根号10)/4
  >3/4
  >45/60故，s2>s1第一个硬币放在圆心，后面就是放在对方硬币的对称位置,最后硬币数目为奇数

Answer 2

再发一遍...
S1趋向于π/4(学过算法的都知道吧)，sqrt（10）>π  S2>S1

Answer 3

to  eulerbert(自由思想)：
2/3+ 1/5 = 13/15 = 52/60   不是42/60。
我计算过前面几项，正好在根号（10/16）的周围，故无法简单判断。to  seu_cose(大三马上结束，找实习单位中)：
如何计算出S1的极限的？不好意思忘了这个极限的计算，要不我就不会做不出来了。

Answer 4

不好意思
好像是我搞错了
先前我也想过关于无穷级数的问题，但是觉得跟算法关系不大，而且也比较麻烦后来我翻了以前的书看，找到了这个级数，结果pi/4这个问题涉及到导数和无穷级数的知识1、(arctan x)的导数=1/(1+x2)  (arctan x是tan x(也记tg x)的反函数；x2是x的2次方，下同)
                   =1-x2+x4-x6....2、将上式两边同时积分，得
    arctan x=x-x3/3+x5/5-x7/7...显然，x=1时，有以下等式：
    arctan 1=1 - 1/3 + 1/5 - 1/7 + 1/9 - ......=s1=pi/4
剩下的问题就是比较pi(圆周率)和根号10的大小
不知道还有否更好的方法，再看看

Answer 5

啥是EMC？
咋这么难捏第1题不懂，这么底层的东西
第2题，高中或大学时我肯定会做,现在

Answer 6

快毕业了，跟班级去黄山旅游了3天，现在才来回帖，望关注的人们谅解。to eulerbert(自由思想) 
谢谢指点。你的方法应该是正解了。
我好久没碰高数了。这种常用级数已经没印象了。而且是利用的级数的一个特殊值，确实有点难想到。不过当初学高数的时候应该对pi/4的这个式子很熟悉才对。唉，数学还是要常复习才行啊。大家对其他的题目有什么想法没？第一题我现在差不多能做出来了。最后一题我面试时在面试官的提示下做出来的。（提示也写在题目下面的）