大数据开发工程师面试《一》Shopee虾皮技术面

一、项目问题

1 做了哪些项目
2 使用什么技术
3 哪个是你主导的项目，一共开发多少个接口，项目多长时间，数据库有多少个表

二、技术问题

1 用自己擅长的语言实现非递归单链表反转 现场手写
2 Hadoop和spark的主要区别
3 Hadoop中一个大文件进行排序，如何保证整体有序？sort只会保证单个节点的数据有序
4 Hive中有哪些udf
5 Hadoop中文件put get的过程详细描述
6 Java中有哪些GC算法
7 Java中的弱引用 强引用和软引用分别在哪些场景中使用

三、技术问题解析

1 用java实现非递归单链表反转

思路：

因为在对链表进行反转的时候，需要更新每一个node的”next”值，但是，在更新 next 的值前，我们需要保存 next 的值，否则我们无法继续。所以，我们需要两个指针分别指向前一个节点和后一个节点，每次做完当前节点”next”值更新后，把两个节点往下移，直到到达最后节点。

实现代码如下：

class Node {
    char value;
    Node next;
}

public Node reverse(Node current) {
    //initialization
    Node previousNode = null;
    Node nextNode = null;

    while (current != null) {
        //save the next node
        nextNode = current.next;
        //update the value of "next"
        current.next = previousNode;
        //shift the pointers
        previousNode = current;
        current = nextNode;
    }
    return previousNode;

}

public class Test{
　　public static void main(String[] args) {
　　　　Node head = new Node(0);
　　　　Node node1 = new Node(1);
　　　　Node node2 = new Node(2);
　　　　Node node3 = new Node(3);

　　　　head.setNext(node1);
　　　　node1.setNext(node2);
　　　　node2.setNext(node3);

　　　　// 打印反转前的链表
　　　　Node h = head;
　　　　while (null != h) {
　　　　　　System.out.print(h.getData() + " ");
　　　　　　h = h.getNext();
　　　　}
　　　　// 调用反转方法
　　　　// head = reverse1(head);
　　　　head = reverse(head);

　　　　System.out.println("\n**************************");
　　　　// 打印反转后的结果
　　　　while (null != head) {
　　　　　　System.out.print(head.getData() + " ");
　　　　　　head = head.getNext();
　　　　}
　　}}

2 Hadoop和spark的主要区别-这个问题基本都会问到

记住3点最重要的不同之处：

• spark消除了冗余的 HDFS 读写: Hadoop 每次 shuffle 操作后，必须写到磁盘，而 Spark 在 shuffle 后不一定落盘，可以 cache 到内存中，以便迭代时使用。如果操作复杂，很多的 shufle 操作，那么 Hadoop 的读写 IO 时间会大大增加，也是 Hive 更慢的主要原因了。
• spark消除了冗余的 MapReduce 阶段: Hadoop 的 shuffle 操作一定连着完整的 MapReduce 操作，冗余繁琐。而 Spark 基于 RDD 提供了丰富的算子操作，且 reduce 操作产生 shuffle 数据，可以缓存在内存中。
• JVM 的优化: Hadoop 每次 MapReduce 操作，启动一个 Task 便会启动一次 JVM，基于进程的操作。而 Spark 每次 MapReduce 操作是基于线程的，只在启动 Executor 是启动一次 JVM，内存的 Task 操作是在线程复用的。每次启动 JVM 的时间可能就需要几秒甚至十几秒，那么当 Task 多了，这个时间 Hadoop 不知道比 Spark 慢了多。

3 Hadoop中一个大文件进行排序，如何保证整体有序

在Spark中使用算子sortByKey()可以实现按关键字排序，那Hadoop中实现全排序呢？

我们知道Mapreduce框架在feed数据给reducer之前会对map output key排序，这种排序机制保证了每一个reducer局部有序，hadoop 默认的partitioner是HashPartitioner，它依赖于output key的hashcode，使得相同key会去相同reducer，但是不保证全局有序，如果想要获得全局排序结果（比如获取top N, bottom N），Hadoop提供TotalOrderPartitioner类用于实现全局排序的功能，并且解决了OOM和数据倾斜的问题。TotalOrderPartitioner 类提供了三个采样器，分别是：

• SplitSampler 分片采样器，从数据分片中采样数据，该采样器不适合已经排好序的数据
• RandomSampler随机采样器，按照设置好的采样率从一个数据集中采样
• IntervalSampler间隔采样机，以固定的间隔从分片中采样数据，对于已经排好序的数据效果非常好。

具体实现可以参考https://zhuanlan.zhihu.com/p/43851100

4 Hive中有哪些UDF

Hive中有3种UDF：

• UDF(User-Defined-Function)用户自定义函数，输入一个数据然后产生一个数据；
• UDAF(User-Defined Aggregation Function)用户自定义聚合函数，多个输入数据然后产生一个输出参数；
• UDTF(User-Defined Table-generating Function)用户自定义表生成函数，输入一行数据生成N行数据。

你写过哪些UDF？在哪种情况下会使用该UDF？–自己可以扩展这个问题

5 Hadoop中数据读写流程分析，即文件在put get过程中具体发生了什么

i) hadoop fs -put 操作为例:

• 当接收到 PUT 请求时，尝试在 NameNode 中 create 一个新的 INode 节点，这个节点是根据 create 中发送过去的 src 路径构建出的目标节点,如果发现节点已存在或是节点的 parent 存在且不为 INodeDirectory 则异常中断，否则则返回包含 INode 信息的 HdfsFileStatus 对象。
• 使用 HdfsFileStatus 构造一个实现了 OutputStream 接口的 DFSOutputStream 类，通过 nio 接口将需要传输的数据写入 DFSOutputStream。
• 在 DFSOutputStream 中写入的数据被以一定的 size（一般是 64 k）封装成一个 DFSPacket,压入 DataStreamer 的传输队列中。
• DataStreamer 是 Client 中负责数据传输的独立线程，当发现队列中有 DFSPacket 时，先通过 namenode.addBlock 从 NameNode 中获取可供传输的 DataNode 信息，然后同指定的 DataNode 进行数据传输。
• DataNode 中有一个专门的 DataXceiverServer 负责接收数据，当有数据到来时，就进行对应的 writeBlock 写入操作，同时如果发现还有下游的 DataNode 同样需要接收数据，就通过管道再次将发来的数据转发给下游 DataNode，实现数据的备份，避免通过 Client 一次进行数据发送。

整个操作步骤中的关键步骤有 NameNode::addBlock 以及 DataNode::writeBlock, 接下来会对这两步进行详细分析。

ii) hadoop fs -get操作：

GET 操作的流程，相对于 PUT 会比较简单，先通过参数中的来源路径从 NameNode 对应 INode 中获取对应的 Block 位置，然后基于返回的 LocatedBlocks 构造出一个 DFSInputStream 对象。在 DFSInputStream 的 read 方法中，根据 LocatedBlocks 找到拥有 Block 的 DataNode 地址，通过 readBlock 从 DataNode 获取字节流。

6 Java中有哪些GC算法

现代虚拟机中的垃圾搜集算法：

• 标记-清除
• 复制算法（适合新生代）
• 标记-压缩（适合老年代）
• 分代收集（新生代采用复制算法，老年代采用标记-压缩算法）

标记 -清除算法

“标记-清除”（Mark-Sweep）算法，如它的名字一样，算法分为”标记”和”清除”两个阶段：首先标记出所有需要回收的对象，在标记完成后统一回收掉所有被标记的对象。之所以说它是最基础的收集算法，是因为后续的收集算法都是基于这种思路并对其缺点进行改进而得到的。

它主要有两个缺点：一是效率问题，标记和移除过程的效率不高；二是空间问题，标记移除后会产生大量不连续的内存碎片，过多的空间碎片可能会导致程序在未来需要分配更大的对象时，找不到足够的连续内存，不得不提前触发另一次垃圾收集动作。

复制算法

“复制”（Copying）的收集算法，它将可用内存按容量划分为大小相等的两块，每次只使用其中的一块。当这一块的内存用完了，就将还存活着的对象复制到另外一块上面，然后再把已使用过的内存空间一次清理掉。

这样，每次都会回收一个块，在分配内存时不必考虑内存碎片等复杂情况。只要移动堆栈顶部的指针并按顺序分配内存，实现就简单而高效。然而，该算法的代价是将内存减少到原来的一半，并且对长寿命对象的连续复制导致效率低下。

标记-压缩算法

当对象存活率高时，复制收集算法会执行更多的复制操作，效率会降低。更关键的是，如果您不想浪费50%的空间，则需要额外的空间用于分配保证，以处理已使用内存中的所有对象都是100%活动的极端情况，因此该算法在过去通常不能直接使用。

根据老年代的特点，有人提出了另外一种”标记-整理”（Mark-Compact）算法，标记过程仍然与”标记-清除”算法一样，但后续步骤不是直接对可回收对象进行清理，而是让所有存活的对象都向一端移动，然后直接清理掉端边界以外的内存

分代收集算法

GC分代的基本假设：绝大部分对象的生命周期都非常短暂，存活时间短。

“分代收集”（Generational Collection）算法，把Java堆分为新生代和老年代，这样就可以根据各个年代的特点采用最适当的收集算法。在新生代中，每次垃圾收集时都发现有大批对象死去，只有少量存活，那就选用复制算法，只需要付出少量存活对象的复制成本就可以完成收集。而老年代中因为对象存活率高、没有额外空间对它进行分配担保，就必须使用”标记-清理”或”标记-整理”算法来进行回收。

7 Java中的弱引用、强引用、软引用和虚引用是什么，他们分别在哪些场景中使用

• 强引用（”Strong”Reference），我们平常典型编码 Object obj=newObject() 中的obj就是强引用。通过 关键字new创建的对象所关联的引用就是强引用。 强引用是使用最普遍的引用。如果一个对象具有强引用，那垃圾回收器绝不会回收它。当JVM 内存空间不足，JVM 宁愿抛出OutOfMemoryError运行时错误（OOM），使程序异常终止，也不会靠随意回收具有强引用的”存活”对象来解决内存不足的问题。只要还有强引用指向一个对象，就能表明对象还”活着”，垃圾收集器不会碰这种对象。 对于一个普通的对象，如果没有其他的引用关系，只要超出对象的生命周期范围或者显式地将相应（强）引用赋值为null，就是可以被垃圾收集的了，当然具体回收时机还是要看垃圾收集策略。
• 软引用（SoftReference），是一种相对强引用弱化一些的引用，可以让对象豁免一些垃圾收集， 只有当JVM 认为内存不足时，才会去试图回收软引用指向的对象。JVM 会确保在抛出OutOfMemoryError之前，清理软引用指向的对象。软引用通常用来实现内存敏感的缓存，如果还有空闲内存，就可以暂时保留缓存，当内存不足时清理掉，这样就保证了使用缓存的同时，不会耗尽内存。软引用可以和一个引用队（ReferenceQueue）联合使用，如果软引用所引用的对象被垃圾回收器回收，Java虚拟机就会把这个软引用加入到与之关联的引用队列中。后续，我们可以调用ReferenceQueue的poll()方法来检查是否有它所关心的对象被回收。如果队列为空，将返回一个null,否则该方法返回队列中前面的一个Reference对象。【应用场景】：软引用通常用来实现内存敏感的缓存。如果还有空闲内存，就可以暂时保留缓存，当内存不足时清理掉，这样就保证了使用缓存的同时，不会耗尽内存。
• 弱引用通过WeakReference类实现。弱引用的生命周期比软引用短。在垃圾回收器线程扫描它所管辖的内存区域的过程中， 一旦发现了具有弱引用的对象，不管当前内存空间足够与否，都会回收它的内存。由于垃圾回收器是一个优先级很低的线程，因此不一定会很快回收弱引用的对象。弱引用可以和一个引用队列（ReferenceQueue）联合使用，如果弱引用所引用的对象被垃圾回收，Java虚拟机就会把这个弱引用加入到与之关联的引用队列中。【应用场景】：弱应用同样可用于内存敏感的缓存。
• 虚引用，你不能通过它访问对象。幻象引用仅仅是提供了一种确保对象被finalize以后，做某些事情的机制。虚引用只是用来得知对象是否被GC。 如果一个对象仅持有虚引用，那么它就和没有任何引用一样，在任何时候都可能被垃圾回收器回收。虚引用必须和引用队列（ReferenceQueue）联合使用。当垃圾回收器准备回收一个对象时，如果发现它还有虚引用，就会在回收对象的内存之前，把这个虚引用加入到与之关联的引用队列中。【应用场景】：可用来跟踪对象被垃圾回收器回收的活动，当一个虚引用关联的对象被垃圾收集器回收之前会收到一条系统通知。

通过表格来说明一下，如下：

引用类型

被垃圾回收时间

用途

生存时间

强引用

从来不会

对象的一般状态

JVM停止运行时终止

软引用

在内存不足时

对象缓存

内存不足时终止

弱引用

在垃圾回收时

对象缓存

gc运行后终止

虚引用

任何时候

跟踪对象被垃圾回收器回收的活动

Unknown

=================================================================================

原创文章，转载请务必将下面这段话置于文章开头处（保留超链接）。
本文转发自程序媛说事儿 ，原文链接https://www.cnblogs.com/abc8023/p/10910741.html

=================================================================================

Original: https://www.cnblogs.com/abc8023/p/11041921.html
Author: 藤露
Title: 大数据开发工程师面试《一》Shopee虾皮技术面