2018.08求职面经

“顺，不妄喜；逆，不惶馁；胸有惊雷而面如平湖者，可拜上将军！”——《史记》

• 背景介绍：7.11裸辞，休息调整 + 回家，7.28返程，8.1-8.7面试，8.8确定offer，8.13入职美团。
• 期望工作：数据类岗位（爬虫/数据分析/风控产品开发）。
• 技能栈：nwpu本硕；数据分析与挖掘、机器学习（1年）；爬虫（2年）；数据产品开发（1年）；Java；Python。
• 技能短板：缺乏对Hadoop、Spark等大数据工具的深入了解，缺乏对框架源码的深入了解。
• 心得：前东家对跳槽有很大的影响因素，薪酬、leader、团队、公司及行业都很重要。

关于自我介绍、具体项目经历、岗位期望、离职原因和职业规划这样的问题，每次面试都会问，项目经历面试官会问到你答不出来为止，所以简历上写的一定要熟知，切勿浮夸。

百度金融/度小满（8.1 2h），基础架构部，Python开发

• hr技术预备面试
  • 画出其中一个爬虫业务的架构图。
  • 【白纸coding】topk问题。找出乱序数组中第k大的数。

    • 快排，O(N·logN)；设置长度为k的子序列迭代找出前k大的数，O(K·N)；最大最小堆，O(N·logK)；快排指针，O(N)。

      public static void topkByPartition(int arr[], int low, int high, int k) {
          // 快排指针
          int l = low;
          int r = high;
          int p = getPartition(arr, l, r);
          while (p != k) {
              if (p < k) {
                  l = p + 1;
              } else {
                  r = p;
              }
              p = getPartition(arr, l, r);
          }
      }

  • 【白纸coding】一个01字符串，求出现0、1次数相等的最长子串。
    • ref：http://blog.sina.cn/dpool/blog/s/blog_3f297c5c0101aupu.html，O(N)。
  • Cache三级缓存。
• 一面（挂）
  • 【白纸coding】一个人从地点A开车到地点B，如何快速从地图上找出沿途1km范围内的加油站。
    
    • ref：https://www.cnblogs.com/aiweixiao/p/6188081.html，GeoHash算法。
  • 【白纸coding】100亿个int型32位的数，给定一台2GB内存的电脑，去重输出。
    • 基于位运算的bitmap算法，O(N)，核心条件：32位和2GB内存。
• 一面面试官建议：加强基础。

瓜子二手车（8.2三轮 2h，8.7总监面 0.5h），大交易增长平台，大数据开发/爬虫

• 一面（爬虫组）
  • 验证码，前端混淆，JS渲染，反爬策略，IP代理池，控频限流，增量抓取，脏数据等问题。
• 二面（交叉面试）
  • jvm内存模型JMM，jvm调优。
  • gc算法，年轻代、年老点和持久代。
  • 数据库一级、二级索引。
  • 【白纸coding】调度算法。给定一堆job的执行顺序【a → b;e → f;b → e;k → b;k → a;t → a】，那么一个合理的执行序列可以是ktabef或者tkabef，请编写代码实现。
    • 建立graph后dfs，注意搜索时出现环的情况。
  • Python中range和xrange的区别。
  • 【白纸coding】二分查找。
• 三面（Growth组组长）
  • HashMap的底层实现原理。如何让HashMap实现线程安全。如果HashMap的链表很长，如何优化查找（jdk 1.8后新增红黑树）。
  • HashMap和HashTable的区别。
  • 线程和进程。
  • Java多线程如何保证线程同步（volatile、synchronized、Lock）。分布式的情况下又如何保证（分布式锁）。
  • Spring MVC和Spring Boot的区别，具体到coding上有什么差异。
  • MySQL数据库采用什么索引结构，为什么选用这种索引结构（B+树）。
  • Redis数据类型（String，List，Hash，Set，Sorted Set）及实现原理，Sort Set中的跳跃表是如何实现的。Redis如何做集群。Redis击穿/雪崩问题。
• 总监面（大交易增长平台技术总监）
  • 【白纸coding】dfs生成目录树。给定GetName()、IsDir()、GetChildren()函数，分别代表获取目录名称、判断是否为文件夹、获取所有子文件夹，实现打印一个目录树的算法。
    • 深度优先搜索。
  • 【白纸coding】实现一个Java单例。
  • 【白纸coding】找出先严格递增后严格递减数组的最大值。
    • 二分查找变型。
• hr面
  • 通知薪资。
• 二面面试官建议：加强基础。总监建议：加强写代码基本功、代码质量、系统架构设计、数据敏感度。

洋钱罐（8.3 4h），风控部，数据工程师

• 风控总监预面
  • 技能栈询问，项目经历询问，离职原因询问。
• 一面
  • 【白纸coding】子串查找。找出s1 = "aab"的某种排列是否存在于s2 = "ccdsjsj_baa_ddcld"中。
    • 用HashMap，O(N1·N2)。
• 二面
  • 【白纸coding】平面点相遇问题。给定一个二维平面和一条直线，方程为y = k·x + b，初始状态给定N个位于直线上的点，告诉你这些点的初始坐标(x_i, y_i)，匀速运动速度(vx_i, vy_i)，求t秒后这些点的相遇总次数。
    • 降维，O(N)。p个点同时相遇算C(p, 2)次。两点i, j相遇，必须满足：

      1   y_i = k·x_i + b；    
      
      2   y_j = k·x_j + b；    
      
      3   x_i + vx_i·t = x_j + vx_j·t；
      
      4   y_i + vy_i·t = y_j + vy_j·t；

      联合四式方程组推出：

      1   （vx_i - vx_j）·t = -（x_i - x_j）
      2   （vy_i - vy_j）·t = -（y_i - y_j） = -k·（x_i - x_j）

      假设x_i ≠ x_j（意味着上两式左边也不会为0），式2除以式1，整理得：

      vy_j - k·vx_j = vy_i - k·vx_i

      即两个点相遇所满足的条件。设变量f_i = vy_i - k·vx_i，则问题简化为：

      数组f[i] = vy_i - k·vx_i在满足x_i ≠ x_j的条件下，计算元素重复情况。

      将[f[i], x_i]同时作为HashMap的key，则相遇总次数 = ΣC(HashMap.get([f[i], x_i]), 2)。

• 三面（风控总监）
  • 【白纸coding】找出乱序数组的中位数，并在白纸上推出算法时间复杂度。
    • 快排指针，O(N)。
• 报备CTO，没有然后了。

美团（8.6 4h），美团平台及酒店旅行事业群，地图-数据抓取开发

• 一面
  • 验证码，前端混淆，JS渲染，反爬策略，IP代理池，控频限流，增量抓取，脏数据等问题。
  • 多线程。Java ThreadPool有几种线程池，介绍项目中用过的。
  • 线程方法中，yield()、sleep()、wait()方法的区别？调用结束后线程分别进入什么状态。
    • 讲wait()时不要遗漏notify()、notifyAll()。
  • 【白纸coding】如何创建一个线程池，需要哪些变量，并说出各变量的含义。
  • 【白纸coding】字符串逆序。"Welcome to here" → "here to Welcome"。
    • 先整体逆序，再单词逆序，优化内存开销到最小，不到O(N²)。
• 二面（交叉面试）
  • NIO。
  • Java CAS。
  • 回调函数。
  • Spring框架的IoC和AOP原理，常用注解。
  • 数据库ORM。
  • Hibernate和MyBatis的区别。
  • 多线程并发。多个线程同时访问数据库某一行，如何加速。
  • MySQL行锁。
  • 数据库ACID解释，Spring事物原理。
• 三面（项目组长）
  • 如何解决爬虫中的脏数据问题。
  • 职业规划和技能广度面试。
• hr面试
  • offer倾向。怎么选。为什么这么选择。对比所有offer后希望得到的薪资。比较单刀直入，就是希望你选择美团。
• 三面面试官建议：加强热情、钻研和学习能力，缺乏大数据知识。

Java岗位准备

• 常见数据结构：基本类型，堆，栈，队列，树（B树，B+树，二叉树，二叉排序树，四叉树，平衡树，完全树，红黑树，avl树），图，单链表，双向链表。
• 常见算法（注重考察时间复杂度）：topK[1][2]，寻找数组的中位数，寻找数组的最大和子序列，8种排序（最好/最坏/平均复杂度，稳定性），外排序，dsf，bsf，动态规划，0-1背包，分治，贪心，回溯，递归，分支限界，倒排索引，链表逆序，链表快排，链表判断有环（是否存在，寻找入口，计算环长度），双链表判断相交，括号匹配，翻转句子中的单词，输出a[i] = i的索引下标，二分查找（包括变型：寻找先严格递增后严格递减数组最大值），不借助临时变量实现a+b，位运算实现a、b交换，二叉树（3种递归遍历和非递归遍历，层次遍历，重建，叶子/所有/第k层节点个数，高度，最近公共祖先，给定节点判断是否存在，是否平衡或完全，最远节点距离，镜像，不借助临时节点转换为有序双向链表），二叉树合并，删除/找出int数值排序二叉树第N大的元素，设计公平的红包分配算法，寻找01字符串中出现0、1次数相等的最长子串，各种字符串查找算法，bitmap（包括变型：基于位运算），找出1~N中缺失的某个数（位运算），找出在一个数组中出现次数超过一半的数，两个栈模拟队列，超大数运算（加减乘除）。
• 数据挖掘、机器学习：K-NN，K-means，simhash，线性回归，假设检验，em，bayes，lr，svm，lda，决策树，gbdt，rf，PageRank，boosting，bp/cnn/rnn/dnn，deep learning，强化学习（包括Q-Learning以及时间差学习），正则化，Gans，pca，Apriori，层次分析法，Markov，聚类分类，欠/过拟合问题。
• Java及架构：final，引用，多线程（volatile、synchronized、Lock，线程池，线程同步，线程通信，线程安全），各种锁，反射，序列化，Spring/Spring MVC/Spring Boot框架（事物，注解，IoC，AOP），RPC，消息队列，Kafka，设计模式，内存溢出的情况，jvm调优，jvm模型JMM（包括程序计数器），GC，Concurrent类，Collection类，HashMap/HashTable，CAS，String、StringBuilder和StringBuffer的区别，类的加载机制，Spring bean加载过程，cglib和jdk动态代理区别，单例，Hibernate和Mybatis的区别，负载均衡设计，java新旧版本对比，netty，设计秒杀系统。
• OS和网络：TCP三次握手和四次挥手，线程和进程，http和https，post和get，shell命令。
• （MySQL）数据库：索引类型，索引实现，分库分表，事物，ORM，行锁。
• （redis）缓存：数据类型，击穿，雪崩，并发，集群。
• 爬虫：验证码，前端混淆，JS渲染，反爬策略，IP代理池，控频限流，增量抓取，脏数据。
• sql：left join，right join，全连接，where/having/group等基本操作。
• 大数据工程：Hadoop，Hive，ZooKeeper，HBase，MR，Spark，Dubbo那一套。

ref：

网站

• Java方向如何准备BAT技术面试答案(汇总版)
• 如何准备校招技术面试
• 今年实习、校招面试（百度金融、凤巢，头条，小米，华为。。）
• JVM架构和GC垃圾回收机制(JVM面试不用愁)
• 二叉树的经典面试题总结，二叉树的层序遍历算法实现，Java实现二叉树的前序、中序、后序、层序遍历（非递归方法）
• 为什么MySQL数据库索引选择使用B+树？
• Java并发编程：线程池的使用
• java.util.concurrent 并发包诸类概览
• 深入理解Java之线程池
• 并发编程 – Concurrent 用户指南
• JVM原理讲解和调优
• redcreen的专栏：JVM系列1~5
• 江南白衣 | 关键系统的JVM参数推荐(2018仲夏版)
• 详细解读CAS实现原理
• ConcurrentHashMap 的 size 方法原理分析
• 事务四大特征：原子性，一致性，隔离性和持久性(ACID)
• 百度等公司面试总结
• MySQL分库分表总结
• 瓜子二手车直卖网面试经历
• 找实习之——瓜子二手车面试经历（后台开发工程师）
• **二手车事业部面试题 - CSDN博客
• 记瓜子二手车的一次面试
• 2018秋招心酸路---持续更新【面挂家】
• 瓜子二手车直卖网Offer，捎带面经，问问大伙这公司怎么样
• 瓜子二手车后台研发实习生面经
• 2019瓜子网后台开发笔试题目
• 瓜子二手车网面经（已通过）

书籍

• 《剑指offer》
• 《编程珠玑(第二版)》
• 其他常见Java基础书籍。

查找资料：

• 看准网
• 牛客网
• V2EX
• 知乎