几个把我整惨的面试题

几个把我整惨的面试题

关于"精读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

Read full article from 几个把我整惨的面试题