关于"精读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 几个把我整惨的面试题
No comments:
Post a Comment