面试题随笔-21/4/10

发表于 | 分类于 | 次

今日面经

链接：https://www.nowcoder.com/discuss/630480?source_id=profile_create_nctrack&channel=-1

HBase是根据rowkey查询，当数据量相当大的时候，是怎么读的很快的，缓存、索引、布隆过滤器、有序

如果快速查询（从磁盘读数据），hbase是根据rowkey查询的，只要能快速的定位rowkey, 就能实现快速的查询，主要是以下因素：
1、hbase是可划分成多个region，你可以简单的理解为关系型数据库的多个分区。
2、键是排好序了的
3、按列存储的

  1. 首先，能快速找到行所在的region(分区)，假设表有10亿条记录，占空间1TB, 分列成了500个region, 1个region占2个G. 最多读取2G的记录，就能找到对应记录；

  2. 其次，是按列存储的，其实是列族，假设分为3个列族，每个列族就是666M， 如果要查询的东西在其中1个列族上，1个列族包含1个或者多个 HStoreFile，假设一个HStoreFile是128M， 该列族包含5个HStoreFile在磁盘上. 剩下的在内存中。

  3. 再次，是排好序了的，你要的记录有可能在最前面，也有可能在最后面，假设在中间，我们只需遍历2.5个HStoreFile共300M

  4. 最后，每个HStoreFile(HFile的封装)，是以键值对（key-value）方式存储，只要遍历一个个数据块中的key的位置，并判断符合条 件可以了。 一般key是有限的长度，假设跟value是1:19（忽略HFile上其它块），最终只需要15M就可获取的对应的记录，按照磁盘的访问 100M/S，只需0.15秒。 加上块缓存机制（LRU原则），会取得更高的效率。

  5. hbase数据存储及访问

hbase的实际存储结构是HFile，它是位于hdfs系统中的，也就是在磁盘中。而加载到内存中的数据存储在MemStore中，当MemStore中的数据达到一定数量时，它会将数据存入HFile中。

​ HFIle是由一个个数据块与索引块组成，他们通常默认为64KB。hbase是通过块索引来访问这些数据块的。而索引是由每个数据块的第一行数据的rowkey组成的。当hbase打开一个HFile时，块索引信息会优先加载到内存当中。然后hbase会通过这些块索引来查询数据。

  1. 布隆过滤器在hbase中的应用

    当我们随机读get数据时，如果采用hbase的块索引机制，hbase会加载很多块文件。

​ 采用布隆过滤器后，它能够准确判断该HFile的所有数据块中是否含有我们查询的数据，从而大大减少不必要的块加载，增加吞吐，降低内存消耗，提高性能

​ 在读取数据时，hbase会首先在布隆过滤器中查询，根据布隆过滤器的结果，再在MemStore中查询，最后再在对应的HFile中查询。

zookeeper的作用

  1. 数据发布/订阅

数据发布/订阅（Publish/Subscribe）系统，即所谓的配置中心，顾明思义就是发布者将数据发布到zookeeper的一个或一系列的节点上，供订阅者进行数据订阅，进而达到动态获取数据的目的，实现配置信息的集中式管理和数据的动态更新。

  1. 负载均衡

每台服务端在启动时都会去zookeeper的servers节点下注册临时节点（注册临时节点是因为，当服务不可用时，这个临时节点会消失，客户端也就不会请求这个服务端），每台客户端在启动时都会去servers节点下取得所有可用的工作服务器列表，并通过一定的负载均衡算法计算得出应该将请求发到哪个服务器上

  1. 命名服务

命名服务是分布式系统中比较常见的一类场景。在分布式系统中，被命名的实体通常可以是集群中的机器，提供的服务地址或远程对象等-这些我们都可以统称他们为名字，其中较为常见的就是一些分布式服务框架（如RPC，RMI）中的服务地址列表，通过命名服务，客户端应用能够根据指定名字来获取资源的实体，服务地址和提供者的信息等。

  1. Master选举

Master选举是一个在分布式系统中非常常见的应用场景。在分布式系统中，Master往往用来协调系统中的其他系统单元，具有对分布式系统状态变更的决定权。例如，在一些读写分离的应用场景用，客户端的写请求往往是由Master来处理的，而在另一些场景中， Master则常常负负责处理一下复杂的逻辑，并将处理结果同步给集群中其他系统单元。

客户端集群往zookeeper上创建一个/master临时节点。在这个过程中，只有一个客户端能够成功创建这个节点，那么这个客户端就成了master。同时其他没有在zookeeper上成功创建节点的客户端，都会在节点/master上注册一个变更的watcher，用于监控当前的master机器是否存活，一旦发现当前的master挂了，那么其余的客户端将会重新进行master选举。

一个文件有上亿url，内存很小，找Top10

利用hash函数，划分成n个文件，再利用小根堆，求每个文件的to p10

每个店铺访问次数top3的访客信息，输出店铺名称，访客id，访问次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
select
	t2.user_id,
	t2.shop,
	t2.num
from
(
  select
    t1.user_id user_id,
    t1.shop shop,
    t1.num,
    rank() over(partition by t1.user_id order by num) con
  from 
  (
    select
      user_id,
      shop,
      count(*) num
    from second_visit
    group by user_id,shop
  ) t1
) t2
where con <= 3;

今日面经2

链接：https://www.nowcoder.com/discuss/636761?type=post&order=time&pos=&page=0&channel=-1&source_id=search_post_nctrack&subType=2

spark怎样连接MySQL

第一种方式

spark.read.jdbc(“jdbc:mysql://192.168.126.111:3306/spark”,”person”,properties)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def main(args: Array[String]): Unit = {
  val spark: SparkSession = SparkSession.builder().master("local").appName("createdataframefrommysql")
  .config("spark.sql.shuffle.partitions", 1).getOrCreate()
  /**
    * 读取mysql的第一中方式
    *
    */
  val properties = new Properties()
  properties.setProperty("user","root")
  properties.setProperty("password","123")
  val person: DataFrame = spark.read.jdbc("jdbc:mysql://192.168.126.111:3306/spark","person",properties)

  person.show()
  spark.read.jdbc("jdbc:mysql://192.168.126.111:3306/spark","(select person.id,person.name,person.age,score.score from person,score where person.id = score.id) T",properties).show()

第二种方式

spark.read.format(“jdbc”) + Map

1
2
3
4
5
6
7
8
9
10
11
12
val map: Map[String, String] = Map[String, String](
  elems = "url" -> "jdbc:mysql://192.168.126.111:3306/spark",
  "driver" -> "com.mysql.jdbc.Driver",
  "user" -> "root",
  "password" -> "123",
  "dbtable" -> "score"

)

val score: DataFrame = spark.read.format("jdbc").options(map).load

score.show()

第三种方式

DataFrameReader

1
2
3
4
5
6
7
8
9
10
val reader: DataFrameReader = spark.read.format("jdbc")
.option("url", "jdbc:mysql://192.168.126.111:3306/spark")
.option("driver", "com.mysql.jdbc.Driver")
.option("user", "root")
.option("password", "123")
.option("dbtable", "score")

val source2: DataFrame = reader.load()

source2.show()

第四种方式

Sparksql

1
2
3
4
5
6
7
8
9
10
11
//将以上两张表注册为临时表，进行关联查询
person.createOrReplaceTempView("person")
score2.createOrReplaceTempView("score")

val result = spark.sql("select person.id,person.name,person.age,score.score from person,score  where person.id=score.id ")

result.show()

//将查询出的结果保存到mysql表之中

result.write.mode(SaveMode.Append).jdbc("jdbc:mysql://192.168.126.111:3306/spark","result",properties)

HashMap和hashtable区别，concurrenthashmap底层

①hashMap实现了Map接口，实现了将唯一隐射到特定值上。允许一个null键和多个null值。非线程安全。

②hashTable：类似于HashMap，但不允许null键和null值，比HashMap慢，因为它是同步的。它是线程安全的类，它使用sysnchronized来锁住整张hash表来实现线程安全，每次锁住整张表让线程独占。

③ConcurrentHashMap：允许多个修改操作并发进行，关键在于使用了锁分离技术。使用多个锁控制对哈希表的不同部分进行的修改。它内部使用段（Segment）来表示这些不同的部分，每个段其实就是一个小的Hashtable，它们有自己的锁。多个修改操作发生在不同的时段上，它们就可以并发进行。

为什么java类加载要使用双亲委派模型

双亲委派模型的工作过程如下：
（1）当前类加载器从自己已经加载的类中查询是否此类已经加载，如果已经加载则直接返回原来已经加载的类。
（2）如果没有找到，就去委托父类加载器去加载（如代码c = parent.loadClass(name, false)所示）。父类加载器也会采用同样的策略，查看自己已经加载过的类中是否包含这个类，有就返回，没有就委托父类的父类去加载，一直到启动类加载器。因为如果父加载器为空了，就代表使用启动类加载器作为父加载器去加载。
（3）如果启动类加载器加载失败（例如在$JAVA_HOME/jre/lib里未查找到该class），则会抛出一个异常ClassNotFoundException，然后再调用当前加载器的findClass()方法进行加载。

双亲委派的原因：
（1）主要是为了安全性，避免用户自己编写的类动态替换 Java的一些核心类，比如 String。
（2）同时也避免了类的重复加载，因为 JVM中区分不同类，不仅仅是根据类名，相同的 class文件被不同的 ClassLoader加载就是不同的两个类。

数据库四大特性

原子性：事务内包含的所有操作要么全部成功，要么全部失败回滚；实现：日志，将所有的更新操作全部写入日志当中，若因为一些系统奔溃/断电等原因导致事务中的部分更新操作已经执行，部分操作未执行，则通过回溯日志，将操作回滚，使系统保证原子性以及一致性；

一致性：不管任何时间有少个并发的事务，系统也必须保持一致；

隔离性：多个并发的事务的操作，在同一时间只能有一个事务执行（及串行的执行）；

持久性：事务正确执行后，事务中对数据的操作不会回滚；

数据库最左匹配原则

写在前面：我在上大学的时候就听说过数据库的最左匹配原则，当时是通过各大博客论坛了解的，但是这些博客的局限性在于它们对最左匹配原则的描述就像一些数学定义一样，往往都是列出123点，满足这123点就能匹配上索引，否则就不能。但是我觉得编程不是死记硬背，这个所谓最左匹配原则肯定是有他背后的原理的。所以我尝试说明一下这个原理，这样以后用上优化索引的时候就不需要去记这些像数学定理一样的东西。了解原理比记住某些表面特点，我觉得是更聪明的方式。

  1. 简单说下什么是最左匹配原则
    顾名思义：最左优先，以最左边的为起点任何连续的索引都能匹配上。同时遇到范围查询(>、<、between、like)就会停止匹配。
    例如：b = 2 如果建立(a,b)顺序的索引，是匹配不到(a,b)索引的；但是如果查询条件是a = 1 and b = 2或者a=1(又或者是b = 2 and b = 1)就可以，因为优化器会自动调整a,b的顺序。再比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d)顺序的索引，d是用不到索引的，因为c字段是一个范围查询，它之后的字段会停止匹配。
  2. 最左匹配原则的原理
    最左匹配原则都是针对联合索引来说的，所以我们有必要了解一下联合索引的原理。了解了联合索引，那么为什么会有最左匹配原则这种说法也就理解了。

我们都知道索引的底层是一颗B+树，那么联合索引当然还是一颗B+树，只不过联合索引的健值数量不是一个，而是多个。构建一颗B+树只能根据一个值来构建，因此数据库依据联合索引最左的字段来构建B+树。
例子：假如创建一个（a,b)的联合索引，那么它的索引树是这样的

可以看到a的值是有顺序的，1，1，2，2，3，3，而b的值是没有顺序的1，2，1，4，1，2。所以b = 2这种查询条件没有办法利用索引，因为联合索引首先是按a排序的，b是无序的。

同时我们还可以发现在a值相等的情况下，b值又是按顺序排列的，但是这种顺序是相对的。所以最左匹配原则遇上范围查询就会停止，剩下的字段都无法使用索引。例如a = 1 and b = 2 a,b字段都可以使用索引，因为在a值确定的情况下b是相对有序的，而a>1and b=2，a字段可以匹配上索引，但b值不可以，因为a的值是一个范围，在这个范围中b是无序的。

链接:https://www.cnblogs.com/lanqi/p/10282279.html

Java里你自己怎么实现栈、队列、HashMap

（1）两个栈实现一个队列

（2）两个队列实现一个栈

GC算法有哪些？

1：标记—清除 Mark-Sweep
过程：标记可回收对象，进行清除
缺点：标记和清除效率低，清除后会产生内存碎片

2：复制算法
过程：将内存划分为相等的两块，将存活的对象复制到另一块内存，把已经使用的内存清理掉
缺点：使用的内存变为了原来的一半
进化：将一块内存按8:1的比例分为一块Eden区（80%）和两块Survivor区（10%）
每次使用Eden和一块Survivor，回收时，将存活的对象一次性复制到另一块Survivor上，如果另一块Survivor空间不足，则使用分配担保机制存入老年代

3：标记—整理 Mark—Compact
过程：所有存活的对象向一端移动，然后清除掉端边界以外的内存

4：分代收集算法
过程：将堆分为新生代和老年代，根据区域特点选用不同的收集算法，如果新生代朝生夕死，则采用复制算法，老年代采用标记清除，或标记整理

  • 对象怎样有新生代转到年老代

大对象直接进入老年代中。-XX:+PretenuerSizeThreshold 控制”大对象的“的大小。即当创建的对象大于这个临界值时，则该对象直接进入老年代。

长期存活的对象将进入老年代。虚拟机对每个对象定义了一个对象年龄（Age）计数器。当年龄增加到一定的临界值时，就会晋升到老年代中，该临界值由参数：-XX:MaxTenuringThreshold来设置。如果对象在Eden出生并在第一次发生Minor GC时仍然存活，并且能够被Survivor中所容纳的话，则该对象会被移动到Survivor中，并且设Age=1；以后每经历一次Minor GC，该对象还存活的话会被移动到另一个Survivor区中，并且Age=Age+1。

进程并发和线程并发

首先：

​ 并行是指两个或者多个事件在同一时刻发生；而并发是指两个或多个事件在同一时间间隔发生。

多进程其实是将所有进程按时间分为一个一个的时间片，每一个时刻只执行该运行的片，时间片过期后转而执行下一个进程。

线程并发，是一个进程中多个线程并发执行。

进程间有哪些通信方式？进程怎样共享内存？

共享内存是进程间通信中最简单的方式之一。共享内存允许两个或更多进程访问同一块内存，就如同 malloc() 函数向不同进程返回了指向同一个物理内存区域的指针。当一个进程改变了这块地址中的内容的时候，其它进程都会察觉到这个更改。

  • 共享内存的特点：
  1. 共享内存是进程间共享数据的一种最快的方法。一个进程向共享的内存区域写入了数据，共享这个内存区域的所有进程就可以立刻看到其中的内容。
  2. 使用共享内存要注意的是多个进程之间对一个给定存储区访问的互斥。若一个进程正在向共享内存区写数据，则在它做完这一步操作前，别的进程不应当去读、写这些数据。

僵尸进程是怎么出现的？

僵尸进程是当子进程比父进程先结束，而父进程又没有回收子进程，释放子进程占用的资源，此时子进程将成为一个僵尸进程

一个进程结束了，但是他的父进程没有等待(调用wait / waitpid)他， 那么他将变成一个僵尸进程。 但是如果该进程的父进程已经先结束了，那么该进程就不会变成僵尸进程， 因为每个进程结束的时候，系统都会扫描当前系统中所运行的所有进程， 看有没有哪个进程是刚刚结束的这个进程的子进程，如果是的话，就由Init 来接管他，成为他的父进程

TCP 和 UDP 的区别

  • TCP 是面向连接的，UDP 是面向无连接的
  • UDP程序结构较简单
  • TCP 是面向字节流的，UDP 是基于数据报的
  • TCP 保证数据正确性，UDP 可能丢包
  • TCP 保证数据顺序，UDP 不保证

udp的好处：

快。

比TCP稍安全 UDP没有TCP的握手、确认、窗口、重传、拥塞控制等机制，UDP是一个无状态的传输协议，所以它在传递数据时非常快。没有TCP的这些机制，UDP较TCP被攻击者利用的漏洞就要少一些。

HTTP常见状态码有哪些?

  • 2开头状态码；2xx (成功)表示成功处理了请求的状态代码；如：200 (成功) 服务器已成功处理了请求。
  • 3开头状态码；3xx (重定向) 表示要完成请求，需要进一步操作。 通常，这些状态代码用来重定向。如：304 (未修改) 自从上次请求后，请求的网页未修改过。 服务器返回此响应时，不会返回网页内容
  • 4开头状态码；4xx(请求错误) 这些状态代码表示请求可能出错，妨碍了服务器的处理；如：400 (错误请求) 服务器不理解请求的语法；403 (禁止) 服务器拒绝请求。404 (未找到) 服务器找不到请求的网页。
  • 5开头状态码；5xx(服务器错误)这些状态代码表示服务器在尝试处理请求时发生内部错误。 这些错误可能是服务器本身的错误，而不是请求出错；如：500 (服务器内部错误) 服务器遇到错误，无法完成请求

甲乙两人轮流拿100枚硬币，一次可拿1-5枚，拿到最后一枚的人获胜，如果甲先拿，怎样可以保证甲获胜？

甲先拿4个,以后的拿法为：乙拿x个,1≤x≤5,则甲拿6-x个
乙拿一次甲拿一次算一轮的话,每轮都会减少6个球.
所以最后一轮会剩下6个,无论乙拿几个甲都会拿到最后1个

还了解什么其他的数据库吗？

redis：

缓存穿透，缓存雪崩，缓存击穿

哨兵模式

数据类型

持久化（rdb,aof)

悲观锁

乐观锁

将一条线段任意分成三段,求这三条线段可以组成一个三角形的概率.

设线段长为a,任意分成三段的长度分别是x 、y 和z=a-(x+y) ,
x +y＜a
三段能构成三角形,则
x+y＞z,即 x+y>(a-x-y),x +y>a/2
y+z＞x,即 y+(a-x-y)>x,x＜a/2
z+x＞y,即 (a-x-y)+x>y,y＜a/2
所求概率等于x+y=a/2、x=a/2、y=a/2三条直线所包围图形的面积除以直线(x+y)=a与x轴、y轴所包围图形的面积.
故将一条线段任意分成三段,这三条线段可以组成一个三角形的概率是
（a/2a/21/2）÷（aa1/2）=a²/8÷a²/2=1/4