百度map2015年实习生招聘（研发）笔试题浅析
百度地图2015年实习生招聘（研发）
==================
注：以下为本人参加百度地图2015年实习生笔试所回忆的题目，以及解题思路，不代表标准的答案，仅供参考学习。
一算法题（请写出代码，标明语言种类）
- Reverse a singly linked list（反转单向链表）
struct Node{
int value;
Node * next;
};
Node* ReverseNode(Node* link)
{
Node* result = link;
Node* frontNode = link; //第一个遍历指针
Node* rearNode = link->next; //指向第二个
while(rearNode)
{
result = rearNode;
rearNode = rearNode->next;
result->next = frontNode;
frontNode = result;
}
return result;
}详细可见：http://www.cnblogs.com/wyqx/p/3346293.html
- Evaluate the value of an arithmetic expression in Reverse Polish Notation.（逆波兰式，即后缀表达式）
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:
[“2”, “1”, “+”, “3”, ““] -> ((2 + 1) 3) -> 9
[“4”, “13”, “5”, “/”, “+”] -> (4 + (13 / 5)) -> 6
可参考http://blog.csdn.net/antineutrino/article/details/6763722
- 有a个1、b个2、c个3、d个4，判断这些数字能否构成若干个长度不小于3的等差数列并且没有数字剩余，请给出代码或代码思路（只写思路或者写伪代码得一半的分）。
例如：输入的abcd四个值为
[1,2,2,1]时，则能组成等差数列[1,2,3]和[2,3,4]，且没有数字剩余
[1,0,0,0]时，则只有数字1，不能组成等差数列
[4,0,0,0]时，则可组成一个等差数列[1,1,1,1]
分析：
等差队列的情况
① 1,1,1,….. 设有k1 个 1
② 2,2,2,…. 设有k2 个 2
③ 3,3,3,…. 设有k3 个3
④ 4,4,4,…. 设有k4个 3
⑤ 1,2,3 设有 k5 个这样的队列
⑥ 2,3,4 设有k6 个这样的队列
⑦ 1,2,3,4 设有 k7 个这样的队列
根据输入的abcd值，则有
K1 + k5 + k7 = a
K2 + k5 + k6 + k7 = b
K3 + k5 + k6 + k7 = c
K4 + k6 + k7 = d
要是所输入的值能全部构成等差数列，则要满足一下条件
a + b + c + d ≥3
k1,k2,k3,k4 ≥3 （①）
或者
a,b,c,d ≥3 （②）
解法：
当为条件（②）时，直接满足题目要求，最简单的队列方法，每个数字单独成为一队列。
当为条件（①）时，可以先把第⑦种队列的情况穷举完，再进行⑤和⑥，最后得到找到①~④中的值，如果大于等于3则，满足题目要求，否则不满足。
二、设计模式
Singleton 设计模式是什么？写一个线程安全的Singleton类，除Singleton外，请说出几种设计模式，并简要说明。
Singleton单例模式，是一种常用的软件设计模式。在它的核心结构中只包含一个被称为单例类的特殊类。通过单例模式可以保证系统中一个类只有一个实例而且该实例易于外界访问，从而方便对实例个数的控制并节约系统资源。如果希望在系统中某个类的对象只能存在一个，单例模式是最好的解决方案。
#ifndef _SINGLETON_H_
#define _SINGLETON_H_
#include "MultiThread.h"
class singleton
{
public:
~singleton()
{
}
static singleton* getInstance()
{
if(NULL == instance_)
{
MutexLockGuard lock(mutex_);//作用域为临界区
if(NULL == instance_)
{
instance_ = new singleton();
}
}
return instance_;
}
private:
singleton()
{
}
static singleton* instance_;
Mutex mutex_;
};
singleton* singleton::instance_ = NULL;
#endif //_SINGLETON_H_设计模式（Design pattern）是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。使用设计模式是为了可重用代码、让代码更容易被他人理解、保证代码可靠性。 毫无疑问，设计模式于己于他人于系统都是多赢的；设计模式使代码编制真正工程化；设计模式是软件工程的基石脉络，如同大厦的结构一样。
设计模式分为三种类型，共23种。
创建型模式：单例模式、抽象工厂模式、建造者模式、工厂模式、原型模式。
结构型模式：适配器模式、桥接模式、装饰模式、组合模式、外观模式、享元模式、代理模式。
行为型模式：模版方法模式、命令模式、迭代器模式、观察者模式、中介者模式、备忘录模式、解释器模式、状态模式、策略模式、职责链模式、访问者模式。
按字典序排列简介如下。
Abstract Factory（抽象工厂模式）：提供一个创建一系列相关或相互依赖对象的接口，而无需指定它们具体的类。
Adapter（适配器模式）：将一个类的接口转换成客户希望的另外一个接口。Adapter模式使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。
Bridge（桥接模式）：将抽象部分与它的实现部分分离，使它们都可以独立地变化。
Builder（建造者模式）：将一个复杂对象的构建与它的表示分离，使得同样的构建过程可以创建不同的表示。
Chain of Responsibility（职责链模式）：为解除请求的发送者和接收者之间耦合，而使多个对象都有机会处理这个请求。将这些对象连成一条链，并沿着这条链传递该请求，直到有一个对象处理它。
Command（命令模式）：将一个请求封装为一个对象，从而使你可用不同的请求对客户进行参数化；对请求排队或记录请求日志，以及支持可取消的操作。
Composite（组合模式）：将对象组合成树形结构以表示“部分-整体”的层次结构。它使得客户对单个对象和复合对象的使用具有一致性。
Decorator（装饰模式）：动态地给一个对象添加一些额外的职责。就扩展功能而言， 它比生成子类方式更为灵活。
Facade（外观模式）：为子系统中的一组接口提供一个一致的界面，Facade模式定义了一个高层接口，这个接口使得这一子系统更加容易使用。
Factory Method（工厂模式）：定义一个用于创建对象的接口，让子类决定将哪一个类实例化。Factory Method使一个类的实例化延迟到其子类。
Flyweight（享元模式）：运用共享技术有效地支持大量细粒度的对象。
Interpreter（解析器模式）：给定一个语言, 定义它的文法的一种表示，并定义一个解释器, 该解释器使用该表示来解释语言中的句子。
Iterator（迭代器模式）：提供一种方法顺序访问一个聚合对象中各个元素，而又不需暴露该对象的内部表示。
Mediator（中介模式）：用一个中介对象来封装一系列的对象交互。中介者使各对象不需要显式地相互引用，从而使其耦合松散，而且可以独立地改变它们之间的交互。
Memento（备忘录模式）：在不破坏封装性的前提下，捕获一个对象的内部状态，并在该对象之外保存这个状态。这样以后就可将该对象恢复到保存的状态。
Observer（观察者模式）：定义对象间的一种一对多的依赖关系,以便当一个对象的状态发生改变时,所有依赖于它的对象都得到通知并自动刷新。
Prototype（原型模式）：用原型实例指定创建对象的种类，并且通过拷贝这个原型来创建新的对象。
Proxy（代理模式）：为其他对象提供一个代理以控制对这个对象的访问。
Singleton（单例模式）：保证一个类仅有一个实例，并提供一个访问它的全局访问点。 单例模式是最简单的设计模式之一，但是对于Java的开发者来说，它却有很多缺陷。在九月的专栏中，David Geary探讨了单例模式以及在面对多线程（multi-threading）、类装载器（class loaders）和序列化（serialization）时如何处理这些缺陷。
State（状态模式）：允许一个对象在其内部状态改变时改变它的行为。对象看起来似乎修改了它所属的类。
Strategy（策略模式）：定义一系列的算法,把它们一个个封装起来, 并且使它们可相互替换。本模式使得算法的变化可独立于使用它的客户。
Template Method（模板方法模式）：定义一个操作中的算法的骨架，而将一些步骤延迟到子类中。Template Method使得子类可以不改变一个算法的结构即可重定义该算法的某些特定步骤。
Visitor（访问者模式）：表示一个作用于某对象结构中的各元素的操作。它使你可以在不改变各元素的类的前提下定义作用于这些元素的新操作。
三、主观题
如果让你来出一道技术面试题，你会出什么题？给出题目和解法，并说明考察的知识点。