豌豆荚北京现场面

wandoujia-beijing-3rd.md

豌豆荚的北京现场面

高效地、线程安全地实现C++单例

首先我目前只会加锁机制版本的，不知道是不是面试官特意强调的高效版

	//Singleton.h
	class Singleton
	{
		public:
			static Singleton* GetInstance();
		private:
			Singleton() {}
			static Singleton *singleton;
	};
	//Singleton.cpp
	Singleton* Singleton::singleton = NULL;
	Singleton* Singleton::GetInstance()
	{
		if(singleton == NULL)
		{
			lock();
			if(singleton == NULL)
			{
				singleton = new Singleton();
			}
		}
		return singleton;
	}

如果是C#，则线程安全且高效地做法如下：

	public sealed class Singleton
	{
		Singleton()
		{
		}
		public static Singleton Instance
		{
			get
			{
				return Nested.instance;
			}
		}
		class Nested
		{
			static Nested()
			{
			}
			internal static readonly Singleton instance=new Singleton();
		}
	}

给定一个数组，乱序，求解Max(aj>ai),j>i

对于数组A={A1，A2，A3，….,An}，构造数组B，使得对于任意的Bi（i=1,2,3，…，n-1）满足如下条件：

Bi=An-i-1-An-i

即：

B1=An-An-1;

B2=An-1-An-2;

....

Bn-1=A2-A1;

对于任意的Aj-Ai（j>i）有如下公式成立：

Aj-Ai=Aj-Aj-1+Aj-1-Aj-2+…+Ai+2-Ai+1+Ai+1-Ai=Bk+Bk+1+…+Bp

其中k=n-j+1，p=n-i+1；

所以问题就转换为求数组B的连续子向量的最大和问题了

	int max_sum_of_subarray(int *array,int len)
	{
	       int i=0,maxendinghere=0,maxsofar=0;
	       for(i=0;i<len;++i)
	       {
	              maxendinghere=(maxendinghere+array[i])>0?maxendinghere+array[i]:0;
	              maxsofar=(maxendinghere>maxsofar)?maxendinghere:maxsofar;
	       }
	       return maxsofar;
	}

	int find_max_diff(int *array,int len)
	{
	       int *diff_array=new int[len-1];
	       int i=0,j=0;
	       for(i=len-1,j=0;i>0;i--,j++)
	       {
	              diff_array[j]=array[i]-array[i-1];
	       }
	       int ret=max_sum_of_subarray(diff_array,len-1);
	       delete []diff_array;
	       return ret;
	}

树的遍历问题

给定一棵树，如下

			6
		/		\
		3		7
	/		\		\
	2		4		8

输出 2-3-4-3-6-7-8-7-6，即中序遍历跟节点输出两次

思路

递归的输出序列，只要在输出右孩子的之后再次输出这个root就好了

如果给定一个遍历序列，重建二叉树的话，利用find找到和当前节点一样的POS，那么当前节点和POS之间的就是当前节点的右子树，左边是左子树，然后不断递归这个过程知道遇到单一的节点为止！