秋招记录-知乎
知乎连续面了三面，第三面挂了，不过还是学习到了不少的东西。
一面：
1、介绍项目
2、一个数组，所有数组都出现了两次，只有一个数出现了一次，返回这个数
这个题很简单，两个相同的数的异或是0，因此所有数求异或，剩下的数即为我们要求的数。
class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for(int i=0;i<nums.length;i++)
res ^= nums[I];
return res;
}
}
3、一个数组，一个数出现了超过一半次数，返回这个数
这里用到的就是两两消除的思路。
class Solution {
public int majorityElement(int[] nums) {
if(nums==null || nums.length==0)
return -1;
int res = nums[0];
int count = 1;
for(int i=1;i<nums.length;i++){
if(res == nums[I])
count++;
else{
if(count==0){
count ++;
res = nums[I];
}
else
count--;
}
}
return res;
}
}
4、将除法的结果用字符串返回，如果能够除尽，则返回相除的结果，如果不能除尽，则无限循环部分用[]标记。
这里我采用了队列和Map的做法，使用map记录每个除数出现的位置，如果出现了相同的除数，则表明出现了无限循环部分。如果除数变成了0，则说明除尽了。
import java.util.*;
public class DivideTwoInteger {
public static void divide(int p1,int p2){
Queue<Integer> queue = new LinkedList<Integer>();
int intPart = p1 / p2;
int reminder = p1 % p2;
if(reminder == 0){
System.out.println("" + intPart);
return;
}
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
map.put(reminder,0);
int index = 0;
while(true){
queue.offer(reminder * 10 / p2);
reminder = reminder * 10 % p2;
if(map.containsKey(reminder) || reminder==0)
break;
else
map.put(reminder,++index);
}
StringBuilder stb = new StringBuilder();
stb.append(intPart + "");
stb.append(".");
if(reminder == 0){
while(!queue.isEmpty())
stb.append(queue.poll() + "");
System.out.println(stb.toString());
}
else{
int pos = map.get(reminder);
index = 0;
while(index < pos)
stb.append(queue.poll() + "");
stb.append("[");
while(!queue.isEmpty())
stb.append(queue.poll() + "");
stb.append("]");
System.out.println(stb.toString());
}
}
public static void main(String[] args){
divide(1,3);
divide(100,3);
divide(6,3);
divide(10,4);
}
}
5、介绍下DeepFM
二面：
1、介绍项目
2、word2vec的原理简单介绍下
有关word2vec的原理，大家可以看https://blog.csdn.net/itplus/article/details/37969519
3、DeepFM介绍下
4、FM推导
5、数组排序，假设数组排序后的位次和排序前的位次绝对值差值小于K，有什么比快排好的算法？
堆排序，建堆的过程是KlogK。我开始说用堆排序，先将数组的前K+1个元素建堆，然后每次出去一个进来一个，完成排序。面试官问我，这样做是有序的么。我一开始说不一定，但仔细想想，一定是有序的。我们来分析一下。
因为排序前和排序后，同一个数字的索引之差小于等于K。假设K=3，也就是说，索引为2的数，在排序后，最大位置不超过5。再假设我们当前找到的是排序后索引为2的数，且后面有一个数比这个要小。由于这个数不在堆中，因此这个数的排序前索引一定大于5，这与假设相矛盾。因此用堆排序一定能保证数组有序。
6、树中两个节点的第一个的公共祖先。
这个题Leetcode上有原题：https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/
代码贴出来：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null || root == p || root== q)
return root;
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if(left!=null && right!=null) return root;
return left !=null?left:right!=null?right:null;
}
}
三面：
1、介绍下项目
2、word2vec里面的层次索引
3、boosting和bagging的区别？
1）样本选择上：
Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的.
Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化.而权值是根据上一轮的分类结果进行调整.
2）样例权重：
Bagging：使用均匀取样，每个样例的权重相等
Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大.
3）预测函数：
Bagging：所有预测函数的权重相等.
Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重.
4）并行计算：
Bagging：各个预测函数可以并行生成
Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果.
4、bagging为什么能减小方差？
参考博客：https://blog.csdn.net/shenxiaoming77/article/details/53894973
可能不懂的地方看下面的公式就知道了：
5、交叉熵损失函数，0-1分类的交叉熵损失函数的。什么是凸函数？0-1分类如果用平方损失为什么用交叉熵而不是平方损失？
这里我们只回答最后一个问题，也就是说逻辑回归为什么不用平方损失？有两点原因：
1）平方损失函数非凸函数。为什么非凸？凸函数二阶导数大于等于0，证明一下即可。
2）但是会在h(wx)接近0和1的地方梯度很小，不容易学习。
6、python里的gc和多线程。
在Python中，为了解决内存泄露问题，采用了对象引用计数，并基于引用计数实现自动垃圾回收。
