数据结构&算法设计

1. 括号匹配问题

Given a string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
Example
The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

2. 输入一个升序数组，然后在数组中快速寻找两个数字，其和等于一个给定的值。
   解题思路：用两个指针一个指向数组前面，一个指向数组的后面，遍历一遍就可以了。

考核要点: 时间复杂度为O(n)

3. 有10亿个杂乱无章的数，怎样最快地求出其中前1000大的数
   解题思路1：建一个1000个数的堆，复杂度为N*(log1000)=10N

考核要点：堆排序，空间复杂度

4. 一个文件中有40亿个整数，每个整数为四个字节，内存为1GB，写出一个算法：求出这个文件里的整数 里不包含的一个整数

解题思路：开辟40亿个bit位的空间，大约占用内存为：40*100000000/8 = 0.5GB,起始时所有位置为0，今次读取40亿个整数，将其映射到某个具体的bit上(位运算)，bit位的值就置为1，遍历结束后，扫描一次所有的bit，发现bit位值为0时，该bit位对应的整数就是没有出现过的。
考察要点：位操作

5. 给定一个存放整数的数组，重新排列数组使得数组左边为奇数，右边为偶数。要求：空间复杂度O(1)，时 间复杂度为O（n）

6. 找出数组中唯一的重复元素，1-1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其 它均只出现一次．每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空间，能否设计一个算法实现？
   解题思路：所有数组元素相加，减去1，2，3…1000，结果就是重复的数

7. 对一千万条数据排序，你认为最好的方式是什么，数据没有重复，且都不超过最大值。
   方案：申请长度为一千万位的位向量bit[10000000]，所有位设置为0，顺序读取待排序文件，每读入一个数i，便将bit[i]置为1。当所有数据读入完成，便对bit做从头到尾的遍历，如果bit[i]=1，则输出i到文件，当遍历完成，文件则已排好序。

Java基础题目

1. java中多线程机制，实现多线程的两种方式（继承Thread类和实现Runnable接口）的区别和联系。

2. java线程阻塞调用wait函数和sleep区别和联系，还有函数yield，notify等的作用。

wait是Object的方法，sleep是Thread类的方法；
wait让出CPU资源的同时会放弃锁，sleep让出CPU资源的同时不会释放锁；
wait需要notify或者notifyall来唤醒，sleep在沉睡指定时间后，会自动进入就绪状态；

3. ArrayList,LinkedList和Vector的区别和实现原理。
   ArrayList是基于数组的可变长数组，因为这个特性，所以它更适合实现get和set；LinkedList是基于双向链表的，所以比较适合实现插入和删除等操作；但以上两个都是非线程安全的，Vector的实现和ArrayList差不多，改进的地方是使用synchronized实现了线程安全。

4. HashMap的实现原理，线程是否安全，并发会有什么问题

   • HashMap底层实现

数组+链表+红黑树通常，只使用Entry数组存放键值对，key的hashcode()值决定它的存放位置，equals()方法决定最终的值。如果hash算法设计的足够好，是不会发生碰撞冲突的，但实际中肯定不存在这么完美的事情。当key的hashcode()相同，equals()方法返回不同时，会在相同的位置上形成一个链表，当链表长度大于8的时候，会转化成红黑树，链表的查找的时间复杂度为O(n)，而红黑树为O(lgn)，会提高查询的性能。当Entry数组不足以容纳更多的元素的时候，以负载因子为0.75，数组长度为20来说，当数组元素数到达15的时候，会自动触发一次resize操作，会把旧的数据映射到新的哈希表，数组扩容到原来的2倍。

• 不使用**HashTable**的原因

它使用synchronized来保证线程安全，会锁住整个哈希表。在线程竞争激烈的情况下效率非常低下，当一个线程访问HashTable的同步方法时，其它线程访问HashTable的同步方法只能进入阻塞或轮询状态。

• concurrentHashMap

核心：采用segment分段锁来保护不同段的数据，是线程安全且高效的。
当多线程访问容器里不同段的数据时，线程间就不会存在锁竞争，从而可以有效提高并发访问效率。

4. 一致性哈希原理

要点：a. 环形存储空间 b.新增节点或者移除节点时，只会有一小部分数据重新迁移。

数据库

1. 这个题目是实际项目研发过程中遇到的一个场景，精减提炼后如下：

   问题：有A表和B表，都只有一列(列名为word), 如何输出A表中B表没有出现过的单词，即实现A-B的逻辑
   答案：select A.word from A left outer join B on A.word=B.word where B.word is null;
   考察点：对外连接的理解，sql的熟悉程度

其它Java相关的面试题目，可以参照Java面试题

大数据

hadoop的shuffle过程

Map端的shuffle
Reduce端的shuffle

HDFS 读流程：

1.client链接namenode，查看元数据，找到数据的存储位置。
2.client通过hdfs的api并发读取数据。
3.关闭连接。

HDFS写流程

1.client链接namenode存数据
2.namenode记录一条数据位置信息（元数据），告诉client存哪。
3.client用hdfs的api将数据块（默认是64M）存储到datanode上。
4.datanode将数据水平备份。并且备份完将反馈client。
5.client通知namenode存储块完毕。
6.namenode将元数据同步到内存中。
7.另一块循环上面的过程。

Hbase rowkey设计原则

1. 长度

2. 散列

3. 唯一

storm 如果碰上了复杂逻辑,需要算很长的时间,你怎么去优化

拆分复杂的业务到多个bolt中，这样可以利用bolt的tree将速度提升，提高并行度

给定 a、b 两个文件，各存放 50 亿个 url，每个 url 各占 64 字节，内存限制是 4G，让你找出 a、b 文件共同的 url？

相同的hash函数将两个文件分别 拆分成1000个小文件，在序号相同的小文件中查找共同url

如何减少Hadoop Map端到Reduce端的数据传输量

使用combiner

hdfs本身是不支持文件随机插入数据。那么hbase中随机写入记录，在hdfs中是怎么实现的呢?

其实HBase/LevelDB等系统，背后都应用了Log-structured merge tree。HBase的写操作有两个步骤：1) 写入HLog(防止宕机丢失数据), 2) 写入对应的Memstore(内存)。当Memstore写满时，其中的数据被flush到HDFS，形成一个新的数据文件(HFile)。简单的讲，HBase的update/delete操作并不影响先前写入的字段，update只是对同一个key增加了一条记录，而delete只是将某个key标记为删除。由于HBase的数据文件是按key/column/timestamp有序的，所以读取时只要按照某种策略，可能只需要读取少数的数据文件(HFile)就能读取到对应key的最新状态。而系统提供了major comaction操作，该操作用于将对应列族的所有HFile合并为一个HFile，并删除TTL过期的数据，多余的版本，以及删除的数据。总之，LSM在某种程度上将随机写转化为顺序写，这也是HBase写性能及其优秀的原因。

数据分析：

1、某场景全量数据在表A中存放，字段名如下：
ID，Label，descrip1，descrip2，descrip3，descrip4
全表的行数约2000亿左右
其中ID为全表的ID，
Label字段将全表数据分为多个类别，约50w个左右，每个类别下的数据量不等，介于30w条到200w条之间，且数据在表中无顺序。
因建模需要对该场景全量数据完成采样，采样密度约37%左右，请用sql实现。
不可以用采样函数

2、尽可能多的罗列数据归一化的方式，并简述使用范围。

3、单位立方体对应的顶点分别是ABCDA1B1C1D1，一个小虫初始位置为A点，目的地为C1点，只能沿着棱爬行，在顶点选择相邻的棱爬行的概率相同，求她爬行到目的地时，爬行路程的期望是多少？
4、某公司内注册账户时使用了大量（数以亿计）的email，现在想识别机器注册的email，请设计一个评估email为机器生成email的模型，简述思路和过程。
5、实际工作中怎么发现overfitting？怎么避免overfitting？
6、 建模时候，入到缺失值是如何处理的

7、已知表a记录了交易，字段如下：user-ID，goods-title，price，trade-ID，create-time等字段
求：有多笔交易记录的消费者中，各自相邻两次交易的最大时间间隔