几个把我整惨的面试题

2012-10-17

关于"精读APUE"方面问挂的几个

fork和vfork的区别

vfork跟fork一样创建子进程,但是并不将父进程的地址空间完全复制到子进程中,因为子进程会立即调用exec或exit,子进借用的父进行的地址空间。另一个区别是:vfork保证子进程先运行,在它调用exec或exit之后父进程才可能被调度运行。

exit和_exit的区别

exit是标准c函数,会先执行一些清理,包括执行各终止处理程序,关闭标准I/O流等,然后才进入内核。_exit是一个系统调用,直接进入到内核

孤儿进程和僵尸进程

一个已终止,但其父进程尚未对其进行善后处理(获取终止子进程的有关信息,释放它仍占用的资源)的进程被称为僵尸进程

一个父进程已终止的进程叫做孤儿进程。当一个进程终止时它会向父进程发SIGCHLD信号,父进程可以忽略该信号,或者提供一个信号处理函数。系统默认动作是忽略这个信号。

多线程中的信号处理

信号处理是进程中所有线程共享的。当线程修改了某个信号相关的处理行为以后,所有线程都必须共享这个处理行为的改变。每个线程有自己的信号屏蔽字,单个线程可以阻止某些信号。

进程中的信号是递送到单个线程的。如果信号与硬件故障或计时器超时相关,该信号就被发送到引起该事件的线程中去,而其它的信号则被发送到任意一个线程。

算法方面

洗牌算法的概率证明

从后往前扫一遍,每个词有1/(n-i)的概率跟前面某个数发生交换。
最后一个留到原位置的概率是1/n,然后到前面某个位置的概率也是(1-1/n)/(n-1)=1/n的概率
第二个,它到最后一个位置的情况是,最后一个跟它换的。概率是1/n。然后它如果没跟第一个换,则它到后面每个格式的概率是相等的,是(1-1/n)/(n-1)
第i个,它到后面格子的情况是它跟后面某个发生了交换,到后面每个格子的概率是1/n。到原位置或前面的概率是(1-i/n)/i=1/n

兄弟单词

给一个单词,求它的兄弟单词,这个兄弟单词必须在词典中是存在的。这个设计某个特殊的hash,保证一个单词和它的兄弟单词都会被hash到同一个桶中。例如,将单词按字母从小到大重新排序后作为其key,比如bad的key为abd,good的key为dgoo。

支持min操作的栈,要求O(1)复杂度

维护二个栈,一个正常栈,另一个栈pop时同步pop,push时维护栈顶始终是最小的

从一个单词变为另一个单词之一

比如说acfed,abfd,每次可以插入,或修改,或删除一个单词,问最少多少步可以变为第二个单词

从一个单词变为另一个单词之二

两个长度一样长的单词,比如banana和pandor,每步可以变其中一个字符.有个词典,要求每步变化得到的中间状态词都是词典中的词,问最少经过多少次变换?

最大子数组和的动态规划的推导过程

b[i] = max{b[i-1]+a[i], a[i]}

二维的最大子数组和

把从i到j之间的行,叠加成一个数组,然后就可以跟一维最大子数组和一样的方式处理了

等找完工作稍微有点时间之后,我好好再读一遍APUE

面试题