【回馈牛客】后台实习面经

总算是有offer了.分享一下面试经历.

offer：快手

简历挂：freewheel，face++（没面试明确发了拒信），猿题库,小米，爱奇艺，去哪，搜狗

笔试挂：美团（当天晚上有事想起来笔试还有30min结束就没打），网易乐得（编程题AK还挂了...）

面试挂：百度，阿里，腾讯，头条，滴滴，京东

大致按照投递顺序：

京东

一轮电面

1. 自我介绍
2. 问项目Java做了什么项目？
3. springboot干什么用的？
4. springboot为了解决什么问题提出？
5. SSH这样的框架用过吗？
6. 算法相关你做过什么？(面试官不知道ACM，以为我做的机器学习算法)
7. 二叉树遍历，怎么遍历？
8. 快速排序是什么意思？魔尔排序说一下？(其实想问希尔排序...)
9. Java基础怎么样？HashMap干什么用的？HashSet呢？ArrayList？
10. 设计模式了解吗？
11. Java接口继承说一下？
12. MySQL用过吗？写个SQL语句：求平均分大于80分的学生姓名？表结构（姓名，科目，分数）。
注意：对于分组后的条件查询，用HAVING AVG(分数)>80 ,而不是where 语句。
13. 线程了解么？问了个sychronzied的题目。
14. 单链表求查询节点向前数第三个节点，怎么做？
15. 你算法应该没问题，那你Java写的多吗？
16. 了解过zookeper吗？分布式项目做过吗？

二轮现场面

没录音，记得不多。

先自我介绍，之后一直在问项目，问到：大量文章，关键字搜索怎么做？

倒排索引了解一下

MySQL源码读过吗？...

今日头条

头条号后台开发

没录音，记一下大概的算法题和设计题

一面

自我介绍

问一下ACM经历：

JVM了解吗？讲一下内存模型？

MySQL MVCC实现了解吗？锁机制？事物特性？

手写代码：

直方图最大矩阵面积

加密算法了解吗？

线程进程说一下

二面

手写代码:

二叉树转单链表右指针连接

二分查找有序翻转数组中某个值

三面

手写代码：

数组2个数异或最大值（没写出来...）

设计题：

1 - 设计微信朋友圈的数据结构，并分析优缺点

2 - 一亿对象一百个访问，怎么实现互斥？分析锁的粒度

讲一下TCP拥塞控制

面试官表示没感觉算法哪里强了（确实弱，全靠运气a题），设计题分析比较不行.

阿里

蚂蚁金服芝麻信用

一面

1.自我介绍

2.树层次遍历第一层从左往右，第二层从右向左怎么做？

剑指offer原题，当时没刷

3.一个数据流一直在动，等概率采样k次，问怎么做？

4.LRU策略，缓存淘汰策略，问怎么O(1) get 和set 操作?

双向链表+hashmap leetcode原题，当时不会

5.诊断数据库耗时，mybatis层面加拦截器，做个插件拦截SQL执行时间怎么做？

6.分布式系统爬取url，问怎么去重？

提示：分桶，转化为单机问题，一致性hash算法，解决分布式均分

单机内怎么高效去重？

布隆过滤器或者bitset

7.大量数据，文件每一行是一个string 问出现次数前100次的string？

答：每个string先hash，每次遇到string 将hash值加1，对hash的结果维护大小为100的堆

注意：
前k大用小顶堆；
前k小用大顶堆

8.除了ACM还有其他东西，你还关注了什么新技术？什么开源框架？什么源码？

问在ACM-队什么角色？

9.问你还有什么要问我？

问：对以后的学习方向还有什么建议？

面试官：多看看开源代码，开源框架。

听了好几遍自己的面试录音，感觉自己一面那么差还能有二面，很感谢阿里

二面

1- 自我介绍

2- 问未来打算，读研还是工作？

3- 能实习多久？什么时间点？

4- 你对Java了解多少？

5- 你讲一下对HashMap的理解？

6- HashMap不是线程安全的，那么线程安全的有哪些？

7- 你刚刚提到可重入锁，你有过哪些编码实践吗？

8- 你理解Lock和Synchronized有什么区别？

9- 其他解决锁和并发的方式？

10- Java的基础问题，泛型介绍一下？有什么价值？

11- Java 序列化介绍一下，为什么要序列化？应用场景？

12- 数据库里面的索引价值？有什么弊端？

13- 一般数据库的底层索引结构是什么样的？

14- 一般看什么技术书籍/blog？印象最深的点是什么？

15- 一个文件0到1e9的随机数字，缺少了100个数字，怎么快速找到这100个数字？

16 - 转正和保研offer怎么选？

17- 发个邮件做笔试给个字符串，按顺序从左向右找形如ABCBA的子串，找到后拼接继续找。

三面

1. 自我介绍
2. 问了一下成绩，以后打算？保研考研？怎么考虑的？
3. 什么时候开始研究Java？
4. 编程语言的选择？
5. 你做个什么项目呢？
6. 哪个项目收获大点？做了多久？
7. 服务器是阿里云的吗？用的哪的？
8. MySQL的悲观锁乐观锁怎么理解？
9. 你看过这些框架的源码吗？
10. 你做项目中遇到什么影响深刻的问题？
11. 通过什么途径解决？
12. 你和你的同学之间交流多么？
13. 你设计模式了解吗？
14. 你们学校有没有专门的做项目的俱乐部？
15. 打ACM，同一级的还有多少人？问了一下ACM详细经历。
16. 你自己对ACM比赛有什么总结？有什么可以加强的地方？
17. 还参加了什么公司面试？还投了什么公司？
18. 你对城市的希望还是在北京？大四还有时间实习吗？

我感觉像HR面，问了一下他说是技术面...
一周后已回绝
言多必失，自己太耿直了，芝麻信用没得北京岗还被捞简历，运气--。

2周后国际事业部一面

问了一下项目经历，然后表示北京没得hc，一个月后再次显示已回绝

腾讯

一轮现场面

录音听不清，简单记一下,想投个后台开发最好能遇到个Java的，结果被AI Lab 的捞了简历，运气真差..

1. 自我介绍
2. 手写链表翻转
3. 怎么实现多种数据结构的链表？模板
4. 怎么输出这个模板？继承的方法
5. 网络编程socket编程了解吗？
6. 进程线程讲一下？
7. 选了2个感兴趣的项目让我讲一下，一个PHP，一个深度学习的
8. 用过PHP的框架吗？
9. TCP/UDP说一下
10. 还有什么问我的？(想让换个部门，没敢说)

百度

一面主要怼设计模式和Java

二面问了一点数据库和对于工作岗位的看法

网易

唯一一个写了笔试总结的
Java开发岗

单选

吐槽一下第一题1 3 铺3 20 有多少种铺法？第一眼看到以为是dp 还是轮廓线dp，我说笔试这么难吗？单选轮廓线dp，我都没写过轮廓线dp，感觉之后的题不用写了。
看了下第二题继续做，回头看一下1 3 放 320 只能放3个横的或1个竖的，可以递推。如果是1010 的用13的铺，那我感觉可以直接关网页了。

编程题

A 求矩阵最大覆盖高度

一看到就想到很经典的求矩阵面积并，要线段树+扫描线，好久没写过这种东西了，准备粘板子(我裸敲不出来)，看了一下数据范围n才50，矩阵面积很大那么离散化一下暴力即可。

#include
using namespace std;
map mp;
int x1[60],yone[60],x2[60],ytwo[60];
int rec[405][405];
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>x1[i];
    for(int i=0;i<n;i++)
        cin>>yone[i];
    for(int i=0;i<n;i++)
    {
        cin>>x2[i];
        x2[i]--;
    }
    for(int i=0;i<n;i++)
    {
        cin>>ytwo[i];
        ytwo[i]--;
    }
    for(int i=0;i<n;i++)
    {
        mp[x1[i]]++;
        mp[x2[i]]++;
    }
    int cnt = 1;
    for(auto it = mp.begin();it!=mp.end();it++)
        it->second = cnt++;
    for(int i=0;i<n;i++)
    {
        x1[i] = mp[x1[i]];
        x2[i] = mp[x2[i]];
    }
    cnt = 1;
    mp.clear();
    for(int i=0;i<n;i++)
    {
        mp[yone[i]]++;
        mp[ytwo[i]]++;
    }
    for(auto it = mp.begin();it!=mp.end();it++)
        it->second = cnt++;
    for(int i=0;i<n;i++)
    {
        yone[i] = mp[yone[i]];
        ytwo[i] = mp[ytwo[i]];
    }
    int m = 400;
    for(int i=0;i<n;i++)
    {
        rec[x1[i]][yone[i]]++;
        rec[x1[i]][ytwo[i]+1]--;
        rec[x2[i]+1][yone[i]]--;
        rec[x2[i]+1][ytwo[i]+1]++;
    }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++)
            rec[i][j] = rec[i-1][j]+rec[i][j-1]+rec[i][j]-rec[i-1][j-1];
    int ans = 0;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++)
            ans = max(ans,rec[i][j]);
    cout<<ans<<endl;
    return 0;
}

离散化手段很多，sort，unique，或者用map

这里将点坐标转为方块坐标，所以右下角--

之后还可以使用点操作最后总体扫一遍来把N3操作减到N2操作

B 求(X=k 且1<=x,y<=n

一看数据范围1e5 NlogN的数论题。
按着暴力的思路写了一下感觉复杂度是N2的，交1发试试没T wa 80%，我复杂度估计错了？没T？找了半天bug，测试边界数据发现多算了k==0 x等于0 的情况

#include
using namespace std;

//B
int main()
{
    ios::sync_with_stdio(false);
    long long n,k;
    cin>>n>>k;
    long long ans=0;
    if(k==0)
        ans-=n;//删除x取0的情况
    for(long long y=k+1;y<=n;y++){
        for(long long cnt=0;cnt*y+k<=n;cnt++){
            if(cnt*y+y-1<=n)
                ans+=y-k;
            else ans+=n-(cnt*y+k)+1;
        }
    }
    cout<<ans<<endl;
    return 0;
}

这题复杂度似乎是NlogN的

C 安排工作薪资最高

看到的第一感觉是16年青岛的KD-Tree，完了又不会写，KD-Tree板子都还不会用，又看一遍题目发现只有1维要求，那就很简单了，sort一下,前缀直接搞。

#include
using namespace std;
int A[100005],D[100005],Pay[100005],Max[100005];
struct P{
    int d;
    int pay;
}job[100005];
bool cmp(P a,P b){
    if(a.d!=b.d)
        return a.d<b.d;
    else return a.pay<b.pay;
}
int main()
{
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>job[i].d>>job[i].pay;
    }
    sort(job,job+n,cmp);
    for(int i=0;i<n;i++)
    {
        D[i]=job[i].d;
        Pay[i]=job[i].pay;
        if(i)
        Max[i]=max(Max[i-1],Pay[i]);
        else Max[i]=Pay[i];
    }
    for(int i=0;i<m;i++)
    {
       cin>>A[i];
       int pos=upper_bound(D,D+n,A[i])-D;
       cout<<Max[pos-1]<<"\n";
    }

    return 0;
}

个人感觉这3题难度是递减的。

滴滴

现场一面

快手

视频2+1

有人看我再写一下滴滴和快手的...