#

给出两个单词（start和end）与一个字典，找出从start到end的最短转换序列

腾讯视频搜索部门 — 一面（两个小时）

远程写代码

二分查找和二叉树两个结点的最低公共子结点

介绍项目

大端模式和小端模式

0x12345678
地址：0x00 0x01 0x02 0x03
大端：0x78 0x56 0x34 0x12
小端：0x12 0x34 0x56 0x78
大端就是数据的高位保存在内存的低位，即倒序
小端就是数据的低位保存在内存的低位，即正序

Read More

#

树中两个节点的最低公共祖先

思路一：二叉搜索树

树是二叉树，而且是二叉搜索树的情况，因为二叉搜索树都是排序过的，位于左子树的节点都比父节点小，而位于右子树上面的节点都比父节点大。

• 如果当前节点的值比两个结点 的值都大，那么最低的共同的父节点一定是在当前节点的左子树中，于是下一步遍历当前节点的左子节点。
• 如果当前节点的值比两个结点的值都小，那么最低的共同的父节点一定是在当前节点的右子树中，于是下一步遍历当前节点的右子节点。
• 这样从上到下，找到的第一个在两个输入结点的值之间的节点，就是最低的公共祖先。

Read More

树中两个节点的最低公共祖先

思路一：二叉搜索树

树是二叉树，而且是二叉搜索树的情况，因为二叉搜索树都是排序过的，位于左子树的节点都比父节点小，而位于右子树上面的节点都比父节点大。

• 如果当前节点的值比两个结点 的值都大，那么最低的共同的父节点一定是在当前节点的左子树中，于是下一步遍历当前节点的左子节点。
• 如果当前节点的值比两个结点的值都小，那么最低的共同的父节点一定是在当前节点的右子树中，于是下一步遍历当前节点的右子节点。
• 这样从上到下，找到的第一个在两个输入结点的值之间的节点，就是最低的公共祖先。

Read More

51面经

一面面经

介绍项目

针对项目问问题

倒排索引

MapReduce过程

Shuffle 做了什么

Combine 做了什么

Combiner 所做的事情：
每一个map都可能会产生大量的本地输出，Combiner的作用就是对map端的输出先做一次合并，以减少在map和reduce节点之间的数据传输量；
Combiner 的意义：
在MapReduce中，当map生成的数据过大时，带宽就成了瓶颈，当在发送给 Reduce 时对数据进行一次本地合并，减少数据传输量以提高网络IO性能；
Combiner 的时机：
Combiner 最基本的是实现本地key的聚合，有本地 Reduce 之称
，实际上是现实就继承来 Reducer ，本质上就是一个 Reducer。

Read More

ThreadLocal详解

携程一面

相邻五分钟面了携程两次，估计应该是两个部门的
一个面的稀烂，一个面的挺好。。。逗

第一个

上来先介绍项目

对一个全局缓存如何确保并发访问安全

实现生产者消费者模型

生产/消费者问题是个非常典型的多线程问题，涉及到的对象包括“生产者”、“消费者”、“仓库”和“产品”。他们之间的关系如下：

1. 生产者仅仅在仓储未满时候生产，仓满则停止生产。
2. 消费者仅仅在仓储有产品时候才能消费，仓空则等待。
3. 当消费者发现仓库没产品可消费时候会通知生产者生产。
4. 生产者在生产出可消费产品时候，应该通知等待的消费者去消费。

解决生产者/消费者问题的方法可分为两类：（1）采用某种机制保护生产者和消费者之间的同步；（2）在生产者和消费者之间建立一个管道。

生产者消费者保证同步的方法：

• 采用synchronized锁以及wait()/notify()方法实现
• 采用Lock锁以及await()/signal()方法实现
• BlockingQueue阻塞队列方法
• Semaphore方法实现同步

管道的方法：

• PipedInputStream / PipedOutputStream

Read More