朗基努斯

2019-08-22 18:18 已编辑天津大学 Java

关注

2019春招实习面试总结

自己做的几个小项目

以下需要总结整理细节部分

1. 车道线检测

2. 视频解压缩编码、传输等

3. 一个用python做的路径寻址application

关于三维模型搜索引擎项目相关度排序算法是怎么做的:

以文字搜模型:

基于Lucene文本搜索引擎，查找最匹配的；

以图片搜模型:

计算图片特征，对图片特征计算HashCode, 搜索的时候匹配HashCode;

以模型搜模型：

计算模型的特征得到n维特征矩阵，对特征矩阵计算HashCode, 搜索的时候匹配HashCode;

去重和检测url有效性是怎么做的：

对外网数据去重:

一开始直接使用条件逐个字段比较判断是否重复；

后来对关键字段连接建立联合哈希值保存，用这个哈希值去重；

后来想到其实外网的url是唯一的，直接对url建立哈希值来去重；后来设想直接用url哈希之后作为主键保存，建立聚集索引；但是数据量上去了之后速度明显下降；

现在可以使用的解决方法:

对URL 使用布隆过滤器

有效性检测比较简单:

使用java.net 下的类来实现，主要用到了 URL和HttpURLConnection :

刚开始使用openStream()方法，这样使用倒是可以，但是速度慢；

最后使用了getResponseCode（）方法，可以得到请求的响应状态，该方法返回一个 int 分别是 200 and 404 如无法从响应中识别任何代码则返回 -1, 如果对该url发起的5次请求都没有应答则认为链接失效;

你的项目用了哪些技术？

Lucene, Solr

MySQL,

Redis,

Java多线程

遇到过什么问题？你是怎么解决的？

去重的过程经历了多次迭代:

刚开始直接对记录逐个字段比较判断是否重复 ——>然后对关键字段建立HashCode作为标识，对比该Hash字段——>再是对外网URL建立HashCode对比;

有什么可以改进的地方？

可以对URL使用布隆过滤器做去重；（位图+多个哈希函数）

使用缓存数据库来提高并发访问；(缓存穿透（查询一个数据库一定不存在的数据），缓存击穿（一个key非常热点，在不停的扛着大并发，大并发集中对这一个点进行访问，当这个key在失效的瞬间，持续的大并发就穿破缓存），缓存雪崩（缓存集中过期失效）)

使用Elesticsearch来替代Solr（Elasticsearch是分布式的, 不需要其他组件，分发是实时的;solr需要结合依赖其他分布式组件来实现分布式）;

2019年3月19日腾讯后台开发一面问题待解决（QQ浏览器搜索部门）

1. 你们搜索引擎的QPS有多少？

2000到10000左右

2. 关于文字搜索的部分， Lucene是怎么设置索引/关键字/相似性度量的？

4. 你做的去重、检查有效性的工具在运行的时候监控过性能吗？哪种资源占用比较多？

5. 你们的搜索引擎支持图片搜索，是怎么做的？用了什么算法（提取图片特征用了什么算法）？

CNN-底层是VGG16，之前用的是pHOG(分层梯度方向直方图(Pyramid Histogram of Oriented Gradients,PHOG) 是一种描述空间形状的特征向量)

6. 不管是图片的特征还是三维模型的特征，你们提取了之后保存在数据库里面，然后新来了一张图片，你也计算了它的特征，那么如何度量这个特征与你数据库中已有图片的特征的相似度呢？

答：直接使用欧式距离计算。反问: 你们的数据量大概有三百万，你要是这么做的话，挨个计算距离效率也太低了吧？

正确答案：

提取特征之后，用Lire计算特征的局部敏感HashCode（局部敏感哈希的特征是3个字符一组，成为一个单词），然后HashCode采用String类型存储。如果有了一个新的检索项过来，先用同样的算法计算其特征以及局部敏感HashCode, 将其转为字符串。然后采取字符串匹配的方式寻找已经存储的HashCode中的匹配项。字符串匹配程度越高的说明相似性越大，这个交给Lire来做。采用倒排索引的方式来加快检索。数据库里的每个局部敏感HashCode都看作一个个的文档，统计所有文档里面的单词，并建立单词对应的文档索引(倒排索引)。对于被检索的HashCode, 也是分成一个个单词，去找哪些文档里面包含这些单词，按包含单词的多少返回检索结果。

细节：图片提取的特征有4096个维度，每个维度是一个浮点数，对于每个维度，在不做降维处理之前，每个维度会对应产生3个字符长度的局部敏感HashCode, 所以一个特征生成的局部敏感HashCode长度为4096*3。但是HashCode作为检索项，如果太长了会影响检索速度，因此作了降维处理，去除一些冗余的维度后，计算出来的HashCode总长在176个字符左右。

模型的方法类似。

7. 你们这个项目还有哪些可以改进的地方（主键设置不合理，怎么设置）？

设置数据库主键，除了用自增的序列以外，还可以用UUID（UUID 是通用唯一识别码（Universally Unique Identifier））

第一期的方案是Solr + MySQL，缺点主要是每次更新需要重新导入MySQL数据，不得不停机更新；

改用ElasticSearch, 可以不适用数据库，直接插入JSON格式数据建立索引。只在持久化的时候使用MySQL.

8. 知道网络编程吗？了解网络IO模型吗？讲一讲IO多路复用

9. redis了解吗？你提到了redis的缓存替换策略， allkeys lru 替换策略中的 LRU(Least Recently Used)算法的原理是什么？不知道？那如果让你设计，应该怎么设计？

LRU(Least recent Used)算法原理

10. 如果让你设计一个数据库，实现增删该查这些功能，有什么注意事项？

11. 讲一讲多线程编程？

面试结果：秒灰

数据库的知识问了很多

针对项目问了很多

一定一定一定要了解项目的所有细节！

2019年3月23日字节跳动后台开发一面问题

HashMap的底层原理，以及如何优化HashMap的查找效率？（HashMap怎么提高解决Hash冲突的效率？）

MySQL数据库的索引，为什么用B+树不用B树？

数据库的隔离级别，以及MySQL的默认隔离级别？

Redis常用的数据结构有哪些？（作死把redis往上写，结果连这个都说不全，面试之前需要认真检查简历上所写的一切，保证你能回答上跟简历上所写的任何一个点的中等难度左右的问题）

IO网络模型有哪些？说一说多路复用IO？

线程和进程有哪些区别？

TCP/UDP 的区别

三次挥手、四次握手

JAVA有哪些锁？

悲观锁和乐观锁的区别？

实现乐观锁的CAS方法，具体是怎么做的？这么做有什么问题？

来做一个题:

给你k个有序数组，请排成一个有序数组

先答归并，问时间复杂度。

提示可以用堆，再问时间复杂度，现场编程。

你有什么问题问我吗？

怎么提高我这弱鸡的代码能力？

多练习，多写，多总结；

怎么读源码，你们工作上经常读源码吗？

看你的目的，是为了解决工作上的需求就读某一个点； Debug源码；

面试题：1,进程和线程的区别？什么时候用进程？什么时候用线程？为什么你的项目中用的是线程？为什么不用进程？如果只有进程，对你这个项目有没有影响？

2019年4月21日百度JAVA开发一面问题

1. String, StringBuider, StringBuffer的区别， StringBuider和StringBuffer为什么是可变的，他们哪个是线程安全的；

2. CurrentHashMap介绍一下；ArrayList的线程安全版本是什么了解过吗?

3. Sychronized关键字加在类、方法和代码块上的区别是什么？

4. JUC java并发包；

5. MySQL有哪些引擎，介绍一下他们的区别；介绍一下B+树；

6. 介绍一下redis，以及为什么要用redis;

7. 你的论文是哪个期刊？

8. 代码题考的是二叉树的镜像。

9. Object类有哪些方法：

hashcode, equals, getClass, toString,wait, notify, notifyAll, finalize, clone方法

2019年4月24日腾讯正式批一面（腾讯地图）

问了一下项目，排序算法怎么做的?
python的效率为什么低？

多线程

python的多线程了解吗？（答不太了解，但了解JAVA多线程，讲了一些JAVA多线程）
线程之间怎么通信(操作系统级别的线程怎么通信)？
怎么用一个进程开另一个进程(说了fork)?

数据库

MySQL的默认隔离级别?数据库有哪些级别?
怎么修改默认隔离级别?
redis有哪些数据结构?redis持久化有哪些方法?redis线程怎么做的（大概是这个意思）?

计网

HTTP header包含哪些内容？
其中的connection字段的作用是什么？
TCP三次握手、四次挥手过程、为什么是三次不是两次，为什么等2MSL时间?
HTTP是哪一层的协议，TCP的拥塞控制机制是怎么实现的?

搜索框架

lucene方面了解的多吗?
elesticsearch问了一下，有哪些API?

代码托管

git 两个人的分支有冲突怎么合并，pull和fetch方法有什么区别?

代码加试：

2019年4月24日腾讯正式批二面（腾讯地图）

详细的问了项目，三维模型检索这块；整个的流程是怎么做的，去重是怎么做的，检索的效果怎么样;

论文, 论文整体是怎么做的，论文的算法（特征融合后的方法）放到三维模型检索系统里面去的效果又怎么样的提升；

你不是科班的，你觉得你做coding的优势和劣势有哪些？

劣势是没有学过计算机的很多专业课，但劣势可以转为优势：现在有目的的去学，能理解更深；

你目前拿了哪些OFFER？

你能实习多久？

2019年4月25日快手一面

问题问的比较常规，现在记不太清了，有印象的是讲了redis的两种数据持久化的方式: RDB快照和AOF；问了JAVA线程池的核心参数， threadlocal 变量; 问了数据库出现并发修改怎么办；

然后考了两道编程题：

1、用数组实现固定容量的队列，实现put函数和take函数

这一题在面试官的提醒下，用count记录队列长度的方法下，写出了如下代码:

 1 public class duilie {
 2 
 3     int volume = 5;
 4     int i = 4;
 5     int j = 4;
 6     int[] Q = new int[volume];
 7     int count = 0;
 8 
 9     public void put(int a) {
10         if (count == volume) {
11             System.out.println("The Queue is Full!");
12         } else {
13             count++;
14             if (i == 0) {
15                 Q[i] = a;
16                 i = volume - 1;
17             } else {
18                 Q[i--] = a;
19             }
20         }
21 
22     }
23 
24     public int take() {
25         int res;
26         if (count == 0) {
27             System.out.println("Empty Queue!");
28             res = -100;
29         } else {
30             count--;
31             res = Q[j];
32             if (j == 0) {
33                 j = volume - 1;
34             } else {
35                 j--;
36             }
37         }
38         return res;
39     }
40 
41     public static void main(String[] args) {
42         duilie q = new duilie();
43         //System.out.println(q.take());//空
44         q.put(2);
45         System.out.println(q.take());//3
46         q.put(3);
47         System.out.println(q.take());//3
48         q.put(1);
49         q.put(2);
50         q.put(3);
51         q.put(4);
52         q.put(5);
53         System.out.println(q.take());
54         System.out.println(q.take());
55         System.out.println(q.take());
56         System.out.println(q.take());
57         System.out.println(q.take());
58 
59     }
60 
61 }

View Code

两个功能测试正常

2、寻找矩阵的最长上升路径长度:

1 2 3 4 5 6

1 1 1 1 1 3

3 4 1 2 3 4

最长上升路径长度为6

解法是枚举每个起点做深搜，但是递归出口老写不对，截至面试结束调试的结果仍然不正确。下面的代码有问题

 1 public class Main {
 2     static int max = Integer.MIN_VALUE;
 3     static int[][] arr;
 4     static int m;
 5     static int n;
 6     static int[] dx = {-1, 0, 1, 0};
 7     static int[] dy = {0, 1, 0, -1};
 8 
 9     public static int search(int[][] _arr) {
10         arr = _arr;
11         m = arr.length;
12         n = arr[0].length;
13         for(int i = 0; i<m; i++){
14             for(int j = 0; j<n; j++){
15                 int tmp = dfs(0,i,j);
16                 max = max>tmp?max:tmp;
17             }
18         }
19         return max;
20     }
21 
22     public static int dfs(int cur, int i, int j){
23         //缺少递归出口
24         if(!check(i,j)) return cur;
25         int res = cur;
26         for(int k = 0; k<4;k++){
27             int x = i+dx[k];
28             int y = j+dy[k];
29             if(x<0||x>=m||y<0||y>m||arr[x][y]<arr[i][j])
30                 continue;
31             else{
32                 res = dfs(++cur, x, y);
33             }
34         }
35         return res;
36     }
37 
38     public static boolean check(int i, int j){
39         boolean flag = true;
40         for(int k = 0; k<4; k++){
41             int x = i+dx[k];
42             int y = j+dy[k];
43             flag = flag && (x<0||x>=m||y<0||y>m||arr[x][y]<arr[i][j]);
44         }
45         return flag;
46     }
47 
48     public static void main(String[] args){
49         int[][] arr = {{1, 2, 3, 4, 5},{1, 1, 1, 1, 2},{1, 3, 2, 1, 4}};
50         System.out.println(search(arr));
51     }
52 }