EMC的笔试总结，最后没能去EMC，可惜了
1. 
除以59的余数是多少。
//答案是38，这个题目考费马小定理；不过直接硬算也可以。
第一次听到费马小定理: 如果一个数p是质数，且a与p互质，则a^(p-1)%p=1（a的p-1次方模p恒等于1）。
所以97^59%59=( (97^58%59)*(97%59) )%59= (1*38)%59 = 38.
//这题目太那个了。。。
2. int a=1000000000, b=2000000000; a=a+b;b=a-b;a=a-b; 最后a，b是多少？
正常交换。
3. 如何判别一个数是unsigned
我选了 a>=0 && -a>=0；但据说正确答案是 a>=0 && ~a>=0
4. 100层楼，两个鸡蛋。某层之上扔鸡蛋就会碎。问至少要测试多少次才能试出这个层数。
动态规划，答案是14。这个问题讨论很多了。
具体方法是先从14楼开始抛第一次；如果没碎，再从27楼抛第二次；如果还没碎，再从39楼抛第三次；如果还没碎，再从50 楼抛第四次；如此，每次间隔的楼层少一层。这样，任何一次抛棋子碎时，都能确保最多抛14次可以找出临界楼层。
5. 25匹马，每次比赛可选5匹马赛出次序（无法计时）。问至少要比赛多少次才能确定跑得最快，次快和第三快的三匹马。
7次。首先分为5组，每组进行一次比赛，然后每组的头一名共五匹马比赛一次。假设第一组快于第二组快于第三组依次。最后一次安排第一组的二三名和第二组的一二名和第三组的第一名。
6. 上台阶，每次可走一台阶和两台阶，问上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：在一个正整数序列中求和最大的非相邻子序列（序列任两元素在原序列里都不相邻）
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//不相邻整数和
inline int max(int a,int b){return a>b?a:b;}
int sum(int * a,int n)
{
int dp[n+1];
memset(dp,0,sizeof(dp)) ;
dp[1]=a[0];
for(int i = 1; i< n;++i)
{
dp[i+1]=max(dp[i],dp[i-1]+a[i]);
if(dp[i+1]==dp[i])a[i]=0;
}
return dp[n];
}
int main()
{
int a[]={3,2,4,1,3,5,2};
printf("%d\n",sum(a,7));
int i = 6;
while(i>=0){
if(a[i]==0){--i;continue;}
printf("%d\n",a[i]);
i-=2;
}
}
1. 火星上到处是硬币，随便拿起一个，如果是头朝下的就翻成字朝上的，如果是字朝上
的就抛出，落地后有各一半的机会头朝上或字朝上。再随便拿起包括刚才那个在内的
所有硬币中的一个，重复前述步骤。问，很多很多次后字朝上和头朝上的硬币比例？
类似的题目：地上有很多硬币,有很多机器人在处理硬币,如果是反面,就把硬币翻转;如
果是正面就随机抛一下,一直进行下去,问最后地上硬币正反面的比例如何？
solution:
设最后平衡状态，有x个反面，y个正面，然后进行上面的操作，得到x+1/2y个正面，
1/2y个反面。列个方程x:y = 1/2y : (x+1/2y),可以得到x:y = 1:2
//my solution:
假设t时刻有x个正面，y个反面，则t+1时刻有x/2+y正面，x/2反面。
则t+1时刻由正面变成反面的硬币数量为x/2，由反面变成正面的硬币数量为y。
由于最后达到平衡状态（即正反硬币数量不在变化）则两边相互转化的硬币数量应该相等（即正面硬币变成反面硬币的数量等于反面硬币变成正面硬币的数量），所以有x/2=y ，即x:y=2:1
4.经过最少多少次比较能找出1000个元素中second
smallest的一个
n + lgn - 2
//n-1 times comparison for finding the smallest element.
// the second smallest elements must be among the elements that are compared with smallest element and lose the match. there are at most lgn elements that are compared with smallest element so at most [lgn]-1 times comparisons are required to find the smallest
element in the lgn elements which is the second smallest element in the whole set.
10个口袋依次取 0 1 2 3 4 5 6 7 8 9 个金币，称一次看看比 9*10/2*10 缺多少就知道了
//不变量题目：不变量=（0+9） /2*10*10，0-9每个变量k的权重是k*10。真实值与不变量差值为k*10，即可求得k。
同类题目如：1-100中少了一个数，求该数。
//同样，1-100不变量为（1+100）/2*100，1-100每个元素k的权重是k，真实值与不变量的差值是k，即可求得少了的数。
6. 实验室里有1000个一模一样的瓶子，但是其中的一瓶有毒。可以用实验室的小白鼠来
测试哪一瓶是毒药。如果小白鼠喝掉毒药的话，会在一个星期的时候死去，其他瓶子里的
药水没有任何副作用。请问最少用多少只小白鼠可以在一个星期以内查出哪瓶是毒药
10
//1000个瓶子，用二进制编码，即0000000001~11111101000。然后给老鼠编号1-10，1号老鼠喝瓶子编号第一位是1的瓶子。2号老鼠喝瓶子编号第二位为1的瓶子，以此类推。假设3,4,5号老鼠死了，即第0000011100=28号瓶子有毒。因为只有28号瓶子被3,4,5号老鼠同时喝了。
思考：这个题目是个编号题目，如果1000个瓶子用10进制一一编号则需1000个老鼠一一对应 ，如果用二进制编号则需要10个老鼠多对对一。所以需要多个老鼠同时喝一瓶水才能找到那个瓶子。
7.碗里有n根面条，现在一次在碗中取任意两头（未必是同一根面条的）连在一起，直到
没有面条的“头”剩下为止，问平均可以在碗里形成多少个圈？
sum(1/(2i-1)) (i=1,2,...n)
概率问题：n个面条，2n个头，一次取2个头取到相同面条的概率是1/2n*1/(2n-1)*n*2 //第一次取个头概率1/2n,第二次取个头概率1/(2n-1)，有n个面条，并且面条的两头顺序可以交换，所以乘2。
则不在一条线的的概率是1-1/(2n-1)=(2n-2)/(2n-1)。
设f(n)表示n个面条产生的圈，则：
f(n)=1/(2n-1)*(f(n-1)+1)+(2n-2)/(2n-1)*f(n-1) //1/(2n-1)的概率可以在f(n-1)基础上增加一个圈，(2n-2)/(2n-1)概率不能在f(n-1)基础上增加一个圈。
所以f(n)-f(n-1)=1/(2n-1)。则f(n)=sum(1/(2i-1)) i=1,2,3,4..n
思考：典型的概率问题。取两个头有两种情况：
1. 两个头在一个面条上，则可以增加一个圈
2. 两个头不在一个面条上，不能增加圈
产生递归公式：f(n) = P(1)*(g( f(n-1) )) + P(2)*( h(f(n-1)) ) //1情况下圈数量+2情况下的圈数量。对取任意两头事件的一个全分割。
1. Four people are in a group
Alice says,”Exactly one of us is lying.”
Bob says, ”Exactly two of us are lying.”
Charles says, “Exactly three of us are lying.”
Dick says, “All four of us are lying.”
How many people in this group are lying?
A. 0
B. 1
C. 2
D. 3
E. 4
Answer; D
典型的排除法：一个个选项和题目说明相比较
如果选A，则那么四个人都说谎了，应该是4个说谎，不对
如果选B，那么B,C,D都说谎了，应该是3个说谎，不对
如果选C，那么A,C,D都说谎了，应该3个说谎，不对
如果选D，那么A,B,D都说谎，3个说谎，这个对的。
如果选E，则A,B,C说谎，应该3个说谎，不对
2. Allen and Brenda, both have a note stuck on their forehead, with a positive
integer number
written on it .Both Allen and Brenda can see each other’s number. They also k
now that the two
numbers have a difference of one. They are trying to figure out the number on
their own forehead.
Allen first says,”I don’t know my number.”
Brenda says,” I don’t know my number either”
Then Allen says “Now, I know my number”
Brenda now says, “Yeah, I know my number also!”
What is the number of Allen and Brenda?
A. 2,1
B. 1,2
C. 3,2
D. 2,3
E. 4,3
Answer: C
思考：同样用排除法。一个个尝试
A:2.1。 因为两个人都是正数，所以如果一方是1个话另一方马上就可以知道自己是2，因为不会是0。排除
B:1,2. 原因同A，排除
C:3,2。 A看到B是2，所以A可能是1或者3，但是A不知道。同样B看到A是3，所以知道自己是2或者4，同样不确定。
但是因为B说自己不知道自己的数字，所以A马上知道了自己一定不是1，因为如果A是1，那么B马上能知道自己的数字是2，但是B不知道，所以A就可以知道自己是3.
同样一旦A知道了自己是3，那么B马上知道了自己是2，因为只有是2才能使A确定自己是3.
D：2,3。顺序反了，因为是A先说自己知道了，但是A没法知道，都由B先知道，因为2在A这边
E: 4,3。两个人都没法知道。
3. Two kinds of chemical material are stored in six buckets(each bucket has o
nly one kind of
chemical). The volumes of these buckets are: 8L, 13L, 15L, 17L, 19L and 31L. I
t is also known
that the price of one chemical is twice that of the other. A man has purchased
five of the buckets,
and found that he spent the same amount money on each kind of chemical. Which
bucket was left
unsold?
A. 8L
B. 13L
C. 15L
D. 17L
E. 19L
Answer: E
排除法：一个个尝试。去点一个bucket，然后剩下的5个中的三个是另外二个的的两倍体积即可。（当然4个对一个也是可以的，但是这道题目不行）
只能凭耐心，不要出错。
1、两个人往圆桌上放硬币，最后谁没有地方放，谁就为输家。你先放，请问有致胜方法吗？
solution: 这道题目有致胜的方法。
致胜的策略就是你将第一颗硬币放在圆桌的中心，然后对方放一颗，你就一圆桌中心为对称点
的另一侧放一颗硬币。这样就可以保准自己永远有地方放。最后对方一定是先没有地方放的。
此时桌面上的硬币数量个数为奇数。
PS：此题有一个引申的题目，
一个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.以上全对
此题答案为B.
//第二道题目在编程之美上有
2、有两堆东西，一份有4个、一份有7个，两个人开始拿东西，一次可拿任意多个，但只能
从一份中拿。现规定：如果最后剩下1个，而且轮到谁拿谁就输了，现在你先拿，请问有致
胜方法吗？
solution:
first one: 0000
second one: 0000000
采取的策略也很简单，第一次取的时候从七个里面取三个，让两堆的数量相等，然后分情况讨论
1. 对方从另一堆取1，2个时从另外一堆取同样的个数。当你发现某一堆只剩下一个，就将另一
堆所有的都取走。
2. 如果对方一次从一堆中取3个，你就将另一堆的所有都取走
3.如果对方一次从一堆中取4个，你就从另外一堆取走3个
e = 2.71828183，e^0.5 = 1.6462077633154327947670181628178
pi = 3.14159265, pi^0.5 = 1.77245
优先级翻转（Priority Inversion），是指某同步资源被较低优先级的进程/线程所拥有，较高优先级的进程/线程竞争该同步资源未获得该资源，而使得较高优先级进程/线程反而推迟被调度执行的现象。
在设计多线程程序时候，避免优先级翻转的最简单方法，就是不要让不同优先级的线程去竞争同一个同步资源。
http://blog.csdn.net/thl789/article/details/617629
可以，对于高端内存建立永久映射或者临时映射都可以访问。
2. kernel中可以调用syscall吗？
这个还真没注意过，感觉完全取决于软中断指令int 80的语义。可以。
3. 在kernel中，一个线程获得了spinlock，那么这个线程可以被interrupt吗？
可以，spinlock 并没有关中断，貌似spinlock_irqsave 才关中断了。
class Test{
};
int main(){
const Test & t = Test(); //可以通过，临时对象是右值，只能赋给const的引用，因为临时对象没地址
Test & t = Test();
//通不过。临时对象不是左值，不能赋给非const引用。
}
引用不能指向临时对象的原因我觉得是临时对象被自动析构后引用就成了dangling reference了，会有异常。
引用可以指向无名对象，但必须是const的引用，因为无名对象是const的。
char a[]="abcd";
char * p = a;
p+2=a //错误
p[-1]=32; //可以通过编译并运行
p[4]=a[2]; //可以通过编译并运行
database transaction : atomic,
consistent,
isolated and
durable.
kernel cannot access to libc
file metadata has no filename
spinlock is lighter than mutex. no cpu consumption when one process waits for the mutex.
spinlock holder can be interrupted? //spinlock can be interrupted but interrupt spinlock might cause deadlock so we need disable local interrupt.
kernel can access to all memory? //still in search,no answer
kernel can call syscall?
int dup(int fd),将fd复制给新的fd，新的fd是最小的没有使用的fd编号。
int dup2(int fd1,int fd2):将fd1复制为fd2,如果fd2原先打开，则先关闭。
使用fcntl进行复制，F_DUPFD，
fcntl可以获得/设置文件标志位，文件锁等。
ioctl用来访问设备的。
sql中5/null的结果是null
interface derivation and implementation derivation:
interface derivation is a much better oo design. a group of rules to be followed by its implementers.
多选题1：
#define abc(s,m) (size_t)&(((s*)0)->m)
#define bcd(ptr,type,member) ({ \
const typeof(((type*)0)->member) * __mptr = (ptr); \
(type*)((char*)__mptr - abc(type,member));})
//abc是取结构体s里面成员m相对于结构体s头部的偏移
//bcd是取结构体type的头部
//这两个取自linux内核的list数据结构实现。
struct test{
int a;
char b; padding是放在b后面的，不是放在c后面的，要注意
long c;
};
int main()
{
struct test t;
t.a=-1;
t.c =31;
struct test * p ;
p = bcd(&(t.c),struct test,c); //其实bcd就是把t.c这个成员所在的结构体头部地址返回。
printf("%ld\n",p->c); //输出31。
return 0;
}
多选题2：
int main{
char buf[4];
int x = 345;
sprintf(buf,"%s","abcdef"); //buf只有4个字节，ef把后面的x冲掉了。
buf[4]=0;
buf[3]='k';
printf("%d,%s\n",x,buf); //输出 26112,abck
return 0;
}
写一个可增可减的hash函数：
//n:输入id
//m：hash表大小
//diff:哈希表大小变化值，增加或者减少diff个长度
int hash(int n,int m, int diff)
{
return (n%m - n/m*diff)%(diff+m) //（原来的对应格子号-变化的格子数）%变化后的hash表大小
}