技术岗面试题小结（二）

Unisky大约 6 分钟

技术岗面试题小结（二）

研发岗的面试问题可能不会局限于某个编程语言或者某个技术栈，有时候也会去问一些比较杂项的东西，所以这里单开一个系列来汇总这些杂项题目。可能会包括一些智力题和应用题

1.CAS算法的缺点

ABA问题，数据经过多次修改回到了初始值，此时使用CAS算法无法判断是否被修改解决方案是引入版本号数据，案例有Java的AtomicStampedReference类

高竞争开销，反复重试的情况下CPU开销大，解决方案是引入退出机制，设置重试次数上限，或避免使用乐观锁

功能受限，CAS只能保证单值的操作原子性

2.包装类Integer，如果值都是100，用==判断，它们是否是相等的？

相等，虽然Integer对象比较的是地址，但值位于-128到127之间时会直接使用常量池中对应的缓存对象，因此两个值为100的Integer对象实则引用的是同一个缓存对象

3.CPU核心数量与线程池数量的关系

CPU密集型应用（算法等）：线程池大小设置为N+1左右

IO密集型应用（IO,网络等）：线程池大小设置为2N+1左右

4.一根绳子随机切3段，能够构成三角形的概率是多大

概率为1/4，需要列举不等式组来通过图像解答，如下：记三段绳子长为x,y,1-x-y,约束条件为：

$0<x,y<0.5$
$x+y>1-x-y$
$x+1-x-y>y$
$y+1-x-y>x$

画出图像可以发现取值范围占定义域的四分之一

5.KMP算法

KMP是高效的字符串匹配算法，避免了传统字符串匹配的繁杂回溯操作记原字符串为str，其索引为 $i$ ，需匹配字符串为模式字符串pat，其索引为 $j$

要求即为寻找txt中是否包含pat

同时提出一个最大匹配长度的概念，这个指的是子串前缀与后缀相同部分的最大长度

使用next[]数组来储存模式字符串每一个子串（均从头开始）的最大匹配长度，next[i]意味着匹配失败时 $j$ 需要回退到的位置，而 $i$ 无需回溯。next的算法如下：

next[0]=0;
for(int i=1;i<pat.length();i++){
  if(pat.chatAt(i)==pat.charAt(next[i-1])){
    next[i]=next[i-1]+1;
  }else{
    next[i]=0;
  }
}

然后是正式匹配操作， $i$ 和 $j$ 均从 $0$ 开始进行匹配。若匹配成功，即str[i]==pat[j]， $i$ 和 $j$ 均+1 若匹配失败， $i$ 保持不变， $j$ 回退到next[j-1]的位置，继续匹配str[i]和pat[next[j-1]]

算法如下：

int i=0,j=0;
while(i<str.length()){
  if(str.charAt[i]==pat.charAt[j]){
    i++;
    j++;
  }else{
    j=next[j-1];
  }
  if(j==pat.length())return true;
}
return false;

6.SQL语句优化

不使用 * 而使用具体字段，节省资源

//优化前
SELECT * FROM user;
//优化后
SELECT id, name FROM user;

对排重要求不高的情况合并查询结果用union all 代替union

//优化前
(SELECT * FROM user WHERE id=1)
UNION
(SELECT * FROM user WHERE id=2);
//优化后
(SELECT * FROM user WHERE id=1)
UNION ALL
(SELECT * FROM user WHERE id=2);