template <typename Comparable>
Comparable maxprod( const vector<Comparable>&v)
{
    int i;
    Comparable maxProduct = 1;
    Comparable minProduct = 1;
    Comparable maxCurrent = 1;
    Comparable minCurrent = 1;
    //Comparable t;

    for( i=0; i< v.size() ;i++)
    {
        maxCurrent *= v[i];
        minCurrent *= v[i];
        if(maxCurrent > maxProduct) 
            maxProduct = maxCurrent;
        if(minCurrent > maxProduct)
            maxProduct = minCurrent;
        if(maxCurrent < minProduct)
            minProduct = maxCurrent;
        if(minCurrent < minProduct)
            minProduct = minCurrent;
        if(minCurrent > maxCurrent)
            swap(maxCurrent,minCurrent);
        if(maxCurrent<1)
            maxCurrent = 1;
        //if(minCurrent>1)
        //    minCurrent =1;
    }
    return maxProduct; 
}

/*
 给定一个整数数组，有正有负数，0，正数组成,数组下标从1算起
 求最大连续子序列乘积，并输出这个序列，如果最大子序列乘积为负数，那么就输出-1
 用Max[i]表示以a[i]结尾乘积最大的连续子序列
 用Min[i]表示以a[i]结尾乘积最小的连续子序列  因为有复数，所以保存这个是必须的
*/
void longest_multiple(int *a,int n){
 int *Min=new int[n+1]();
 int *Max=new int[n+1]();
 int *p=new int[n+1]();
 //初始化
 for(int i=0;i<=n;i++){
  p[i]=-1;
 }
 Min[1]=a[1];
 Max[1]=a[1];
 int max_val=Max[1];
 for(int i=2;i<=n;i++){
  Max[i]=max(Max[i-1]*a[i],Min[i-1]*a[i],a[i]);
  Min[i]=min(Max[i-1]*a[i],Min[i-1]*a[i],a[i]);
  if(max_val<Max[i])
   max_val=Max[i];
 }
 if(max_val<0)
  printf("%d",-1);
 else
  printf("%d",max_val);
//内存释放
 delete [] Max;
 delete [] Min;
}

定一个长度为N的整数数组，只允许用乘法，不能用除法，计算任意（N-1）个数的组合中乘积最大的一组，并写出算法的时间复杂度。
我们可以把所有可能的（N-1）个数的组合找出来，分别计算它们的乘积，并比较大小。由于总共有N个（N-1）个数的组合，总的时间复杂度为O（N2），显然这不是最好的解法。
OK，以下解答来自编程之美
解法1

解法2
此外，还可以通过分析，进一步减少解答问题的计算量。假设N个整数的乘积为P，针对P的正负性进行如下分析（其中，AN-1表示N-1个数的组合，PN-1表示N-1个数的组合的乘积）。
1.P为0

那么，数组中至少包含有一个0。假设除去一个0之外，其他N-1个数的乘积为Q，根据Q的正负性进行讨论：

Q为0
说明数组中至少有两个0，那么N-1个数的乘积只能为0，返回0；
Q为正数
返回Q，因为如果以0替换此时A_N-1中的任一个数，所得到的P_N-1为0，必然小于Q；
Q为负数
如果以0替换此时A_N-1中的任一个数，所得到的P_N-1为0，大于Q，乘积最大值为0。

2.P为负数

根据“负负得正”的乘法性质，自然想到从N个整数中去掉一个负数，使得P_N-1为一个正数。而要使这个正数最大，这个被去掉的负数的绝对值必须是数组中最小的。我们只需要扫描一遍数组，把绝对值最小的负数给去掉就可以了。

3.P为正数

类似地，如果数组中存在正数值，那么应该去掉最小的正数值，否则去掉绝对值最大的负数值。

上面的解法采用了直接求N个整数的乘积P，进而判断P的正负性的办法，但是直接求乘积在编译环境下往往会有溢出的危险（这也就是本题要求不使用除法的潜在用意），事实上可做一个小的转变，不需要直接求乘积，而是求出数组中正数（+）、负数（-）和0的个数，从而判断P的正负性，其余部分与以上面的解法相同。
在时间复杂度方面，由于只需要遍历数组一次，在遍历数组的同时就可得到数组中正数（+）、负数（-）和0的个数，以及数组中绝对值最小的正数和负数，时间复杂度为O（N）。 9月15日，中兴面试 ：
小端系统

union{
        int i;
        unsigned char ch[2];
}Student;


int main()
{
        Student  student;
        student.i=0x1420;
        printf("%d  %d",student.ch[0],student.ch[1]);
	return 0;
}

输出结果为？（答案：32 20） 一道有趣的Facebook面试题：
给一个二叉树，每个节点都是正或负整数，如何找到一个子树，它所有节点的和最大？
点评：
@某猛将兄:后序遍历，每一个节点保存左右子树的和加上自己的值。额外一个空间存放最大值。
@陈利人：同学们，如果你面试的是软件工程师的职位，一般面试官会要求你在短时间内写出一个比较整洁的，最好是高效的，没有什么bug的程序。所以，光有算法不够，还得多实践。
写完后序遍历，面试官可能接着与你讨论，a). 如果要求找出只含正数的最大子树，程序该如何修改来实现？b). 假设我们将子树定义为它和它的部分后代，那该如何解决？c). 对于b，加上正数的限制，方案又该如何？总之，一道看似简单的面试题，可能能变换成各种花样。
比如，面试管可能还会再提两个要求：第一，不能用全局变量；第一，有个参数控制是否要只含正数的子树。其它的，随意，当然，编程风格也很重要。 谷歌面试题：
有几百亿的整数，分布的存储到几百台通过网络连接的计算机上，你能否开发出一个算法和系统，找出这几百亿数据的中值？就是在一组排序好的数据中居于中间的数。显然，一台机器是装不下所有的数据。也尽量少用网络带宽。 小米，南京站笔试（原第 20 题）：
一个数组里，数都是两两出现的，但是有三个数是唯一出现的，找出这三个数。
点评：
3个数唯一出现，各不相同。由于x与a、b、c都各不相同，因此x^a、x^b、x^c都不等于0。具体答案请参看这两篇文章：1、http://blog.csdn.net/w397090770/article/details/8032898， 2、 http://zhedahht.blog.163.com/blog/static/25411174201283084246412/ 。 9月19日，IGT面试：你走到一个分叉路口，有两条路，每个路口有一个人，一个说假话，一个说真话，你只能问其中一个人仅一个问题，如何问才能得到正确答案？点评：答案是，问其中一个人：另一个人会说你的路口是通往正确的道路么？ 9月19日， 创新工厂笔试题：
给定一整型数组，若数组中某个下标值大的元素值小于某个下标值比它小的元素值，称这是一个反序。
即：数组a[]; 对于i < j 且 a[i] > a[j],则称这是一个反序。
给定一个数组，要求写一个函数，计算出这个数组里所有反序的个数。
点评：
归并排序，至于有的人说是否有O（N）的时间复杂度，我认为答案是否定的，正如老梦所说，下限就是nlgn，n个元素的数组的排列共有的排列是nlgn，n！（ 算法导论里面也用递归树证明了：O(n*logn)是最优的解法，具体可以看下这个链接：）。然后，我再给一个链接，这里有那天笔试的两道题目： http://blog.csdn.net/luno1/article/details/8001892 。 9月20日，创新工厂南京站笔试：
已知字符串里的字符是互不相同的，现在任意组合，比如ab，则输出aa，ab，ba，bb，编程按照字典序输出所有的组合。
点评：非简单的全排列问题（ 跟全排列的形式不同,abc 全排列的话，只有６个不同的输出：http://blog.csdn.net/v_july_v/article/details/6879101）。本题可用递归 的思想，设置一个变量表示已输出的个数，然后当个数达到字符串长度时，就输出。

//假设str已经有序，from 一直很安静
void perm(char *str, int size, int resPos)
{
    if(resPos == size)
	print(result);
    else
    {
	for(int i = 0; i < size; ++i)
        {
	  result[resPos] = str[i];
	  perm(str, size, resPos + 1);
	}
    }
}

9月21日，小米，电子科大&西安交通大学笔试题：

void fun()
{
	unsigned int a = 2013;
	int b = -2;
	int c = 0;
	while (a + b > 0)
	{
		a = a + b;
		c++;
	}
	printf("%d", c);
}

问：最后程序输出是多少？ 点评： 此题有陷阱，答题需谨慎！

点评：
针对上述第3题朋友圈的问题，读者@互联网的飞虫提供的解法及代码如下（有任何问题，欢迎指正，多谢）：

#include <STDIO.H>
#include <WINDOWS.H>


int Friends(int n, int m , int* r[]);

int main(int argc,char** argv)
{ 
  int r[5][2] = {{1,2},{4,3},{6,5},{7,8},{7,9}};
 
  printf("有%d个朋友圈。n",Friends(0,5,(int**)r));
  return 0;
}

int Friends(int n, int m, int* r[]) // 注意这里的参数很奇葩  
{
 
  int *p = (int*)malloc(sizeof(int)*m*3);

  memset(p,0,sizeof(int)*m*3);
  int i = 0;

  int iCount = 0;

  int j = 0;

  int * q = (int*)r; // 这里很巧妙  将二维指针 强转为一维指针

  for (i=0;i<m;++i)
  {
    for (j=0;j<2;++j)
    {
      p[i*3+j]=q[i*2+j];   // 注意这里二维数组向一维数组的转换
    }

    p[i*3+j] = 0;
  }

  bool bFlag = false;

  for (i=0;i<m;++i)
  {
    bFlag = false;
    if (p[i*3+2]==1)
    {
       bFlag = true;
    }
    p[i*3+2] = 1;
    for (j=0;j<m;++j)
    {
      if (i==j)
      {
        continue;
      } 
     

      if (p[i*3]==p[j*3] ||
        p[i*3] == p[j*3+1] ||
        p[i*3+1] == p[j*3+0] ||
        p[i*3+1] == p[j*3+1])
      {
        if (p[j*3+2]==1)
        {
          bFlag = true;
        }
        p[j*3+2] = 1;
      }
    }

    if (!bFlag)
    {
      ++iCount;
    }
  }

  free(p); 
  
  return iCount;
}

9月21日晚，海豚浏览器笔试题：
1、有两个序列A和B,A=(a1,a2,...,ak),B=(b1,b2,...,bk),A和B都按升序排列，对于1<=i,j<=k，求k个最小的（ai+bj），要求算法尽量高效。
2、输入：
L:“shit”“fuck”“you”
S:“shitmeshitfuckyou”
输出：S中包含的L一个单词，要求这个单词只出现一次，如果有多个出现一次的，输出第一个这样的单词
怎么做？ 9月22日上午，百度西安站全套笔试题如下：
点评 ：上述的系统设计题简单来讲，是建立起按键号码数字到人名(手机号)的映射关系，具体讲，步骤解法如下图所示：

3.算法与程序设计
第一题：
某个公司举行一场羽毛球赛，有1001个人参加，现在为了评比出“最厉害的那个人”，进行淘汰赛，请问至少需要进行多少次比赛。
第二题
有100个灯泡，第一轮把所有灯泡都开启，第二轮把奇数位的灯泡灭掉，第三轮每隔两个灯泡，灭一个，开一个，依此类推。求100轮后还亮的灯泡。
点评： 完全平方数，本人去58面试时，也遇到过与此类似的题。
第三题
有20个数组，每个数组里面有500个数组，降序排列，每个数字是32位的unit,求出这10000个数字中最大的500个。
点评：http://www.51nod.com/question/index.html#!questionId=647。
4.系统设计题
类似做一个手机键盘，上面有1到9个数字，每个数字都代表几个字母（比如1代表abc三个字母，z代表wxyz等等），现在要求设计当输入某几个数字的组合时，查找出通讯录中的人名及电话号码。
其它的还有三道简答题，比如线程的死锁，内存的管理等等。最后，附一讨论帖子： http://topic.csdn.net/u/20120923/18/7fd148b2-c000-4326-93a6-cb3bb8675702.html 。 9月22日，微软笔试：
T(n)=1(n<=1),T(n) = 25*T(n/5) + n^2，求算法的时间复杂度。更多题目请参见： http://blog.csdn.net/wonderwander6642/article/details/8008209 。 9月23日，腾讯校招部分笔试题( 特别提醒:下述试卷上的答案只是一考生的解答,非代表正确答案.如下面第11题答案选D,第12题答案选C,至于解释可看这里:http://coolshell.cn/articles/7965.html )：

点评： 根号九说，不过最后两道大的附加题，全是秒杀99%海量数据处理面试题里的： http://blog.csdn.net/v_july_v/article/details/7382693 ，太感谢July了。 9月23日，搜狗校招武汉站笔试题：
一、已知计算机有以下原子操作
1、 赋值操作：b = a;
2、 ++a和a+1;
3、for( ){ ***}有限循环；
4、操作数只能为0或者正整数；
5、定义函数
实现加减乘操作
二、对一个链表进行排序，效率越高越好，LinkedList<Integer>.

附：9月15日，搜弧校招笔试题：http://blog.csdn.net/hackbuteer1/article/details/8015964。 搜狗校招笔试题：
100个任务，100个工人每人可做一项任务，每个任务每个人做的的费用为t[100][100],求一个分配任务的方案使得总费用最少。
点评 ：匈牙利算法，可以看看这篇文章： http://www.byvoid.com/blog/hungary/ ，及这个链接： http://www.51nod.com/question/index.html#!questionId=641 。 9月24日，Google南京等站全套笔试题如下：

点评：
谷歌的笔试从易到难，基础到复杂，涵盖操作系统 网络 数据结构 语言 数学思维 编程能力 算法能力，基本上能把一个人的能力全面考察出来。
至于上述2.1寻找3个数的中位数,请看读者sos-phoenix给出的思路及代码：

2.1 // 采用两两比较的思路（目前没想到更好的）  
    if (a <= b) {  
        if (b <= c)  
            return b;  
        else {  
            if (a <=c)  
                return c;  
            else  
                return a;  
            }  
    }  
    else {  
        if (a <= c)  
            return a;  
        else {  
            if (b <= c)  
                return c;  
            else  
                return b;  
            }  
    }  

最坏情况下的比较次数：3 （次）
平均情况下的比较次数：(2×2 + 4*3)/6 = 8/3 （次）
此外这题，微博上的左耳朵耗子后来也给出了一个链接: http://stackoverflow.com/questions/1582356/fastest-way-of-finding-the-middle-value-of-a-triple，最后是微博上的梁斌penny的解答：http://weibo.com/1497035431/yFusm7obQ。其余更多参考答案请看本文评论下第93楼 。 读者来信，提供的几个hulu面试题：
9月19号,hulu电面：
问题1 两个骰子，两个人轮流投，直到点数和大于6就停止，最终投的那个人获胜。问先投那个人获胜概率？
问题2 平面上n个圆，任意两个都相交，是否有一条直线和所有的圆都有交点。
9月22号,上午hulu面试
问题1 100个人，每人头上戴一顶帽子，写有0..99的一个数，数可能重复，每个人都只能看到除自己以外其他人的帽子。每个人需要说出自己的帽子的数，一个人说对就算赢。 点评： 参考答案请看这个链接： http://www.51nod.com/question/index.html#!questionId=642 。
问题2 n台机器，每台有负载，以和负载成正比的概率，随机选择一台机器。「原题是希望设计O(1)的算法（预处理O(n)不可少，要算出每台机器的比例），因为非O(1)的话，就trivial了：可以产生随机数例如[0,1)然后，根据负载比例，2分或者直接循环检查落入哪个区间，决定机器。 面试官想问，有没更好的办法，避免那种查找。即能否多次（常数次）调用随机函数，拟合出一个概率分布」
问题3 行列都递增的矩阵，求中位数。 点评： http://www.51nod.com/question/index.html#!questionId=643，http://blog.csdn.net/v_july_v/article/details/7085669（杨氏矩阵查找问题） 。 西安百度软件研发工程师：
一面(2012.9.24)：
问的比较广，涉及操作系统、网络、数据结构。比较难的就2道题。
(1)10亿个int型整数，如何找出重复出现的数字；
(2)有2G的一个文本文档，文件每行存储的是一个句子，每个单词是用空格隔开的。问：输入一个句子，如何找到和它最相似的前10个句子。（提示：可用倒排文档）。
二面(2012.9.25)：
(1)一个处理器最多能处理m个任务。现在有n个任务需要完成，每个任务都有自己完成所需的时间。此外每个任务之间有依赖性，比如任务Ａ开始执行的前提是任务Ｂ必须完成。设计一个调度算法，使得这n这任务的完成时间最小；
(2)有一个排序二叉树，数据类型是int型，如何找出中间大的元素；
(3)一个N个元素的整形数组，如何找出前K个最大的元素。
(4)给定一个凸四边形，如何判断一个点在这个平面上。
点评：本题的讨论及参考答案请见这：http://www.51nod.com/question/index.html#!questionId=669。
运维部(2012.9.27)：
(1)堆和栈的区别；
(2)问如何数出自己头上的头发。 9月25日，人人网笔试题：

点评：参考答案请见，http://www.51nod.com/question/index.html#!questionId=671。 9月25日晚，创新工场校园招聘北邮站笔试：
9月25日，小米大连站笔试题：
1一共有100万，抽中的2万，每月增加4万，问20个月能抽中的概率为：？
2 for(int i=0;i<strlen(s);i++){n+=I;}时间复杂度O（n）
3 手机wifi（A）….wifi ap….局域网（B）…..路由器…ADSL（C）…..互联网…..服务器
断掉上述ABC哪些点TCP链接会立刻断掉？
4 12345入栈，出栈结果 21543 31245 43215 12534 可能的为？(第一个和第三个)
5 x^n+a1x^n-1+…+an-1x+an,最少要做—乘法？题目中a1，a2，an为常数。 9月26日，百度一二面：
1、给定一数组，输出满足2a=b（a，b代表数组中的数）的数对，要求时间复杂度尽量低。
2、搜索引擎多线程中每个线程占用多少内存？如果搜索引擎存储网页内存占用太大怎么解决？
3、有很多url，例如*.baidu.com，*.sina.com ......
现在给你一个sports.sina.com 快速匹配出是*.sina.com。点评：老题，此前blog内曾整理过。
4、找出字符串的编辑距离，即把一个字符串s1最少经过多少步操作变成编程字符串s2，操作有三种，添加一个字符，删除一个字符，修改一个字符（只要听过编辑距离，知道往动态规划上想，很快就可以找到解法）。

点评：请看链接： http://blog.csdn.net/Lost_Painting/article/details/6457334。
5、编程实现memcopy，注意考虑目标内存空间和源空间重叠的时候。
6、实现简单的一个查找二叉树的深度的函数。
9月26日晚，优酷土豆笔试题一道：
优酷是一家视频网站，每天有上亿的视频被观看，现在公司要请研发人员找出最热门的视频。
该问题的输入可以简化为一个字符串文件，每一行都表示一个视频id，然后要找出出现次数最多的前100个视频id，将其输出，同时输出该视频的出现次数。
1.假设每天的视频播放次数为3亿次，被观看的视频数量为一百万个，每个视频ID的长度为20字节，限定使用的内存为1G。请简述做法，再写代码。
2.假设每个月的视频播放次数为100亿次，被观看的视频数量为1亿，每个视频ID的长度为20字节，一台机器被限定使用的内存为1G。
点评： 有关海量数据处理的题目，请到此文中找方法(无论题目形式怎么变，基本方法不变，当然，最最常用的方法是：分而治之/Hash映射 + Hash统计 + 堆/快速/归并排序)： http://blog.csdn.net/v_july_v/article/details/7382693 。注：上题第二问文件太大，则可如模1000，把整个大文件映射为1000个小文件再处理 .... 9月26日，baidu面试题：
1.进程和线程的区别
2.一个有序数组（从小到大排列），数组中的数据有正有负，求这个数组中的最小绝对值
3.链表倒数第n个元素
4.有一个函数fun能返回0和1两个值，返回0和1的概率都是1/2，问怎么利用这个函数得到另一个函数fun2，使fun2也只能返回0和1，且返回0的概率为1/4,返回1的概率为3/4。（如果返回0的概率为0.3而返回1的概率为0.7呢）
5.有8个球，其中有7个球的质量相同，另一个与其他球的质量不同（且不知道是比其他球重还是轻），请问在最坏的情况下，最少需要多少次就能找出这个不同质量的球
6.数据库索引
7.有一个数组a，设有一个值n。在数组中找到两个元素a[i]和a[j]，使得a[i]+a[j]等于n，求出所有满足以上条件的i和j。
8.1万个元素的数组，90%的元素都是1到100的数，10%的元素是101--10000的数，如何高效排序。 小米的web开发笔试题：
一场星际争霸比赛，共8个人，每个人的实力用分数表示，要分成两队，如何保证实力最平均？ 给定一个浮点数的序列，F1,F2,……，Fn（1<=n<=1000）,定义P(s,e)为子序列Fi(s<=i<=e)的积，求P的最大值。 9月27日，趋势科技面试题：
马路口，30分钟内看到汽车的概率是95%，那么在10分钟内看不到汽车的概率是？ 9月27日晚，IGT笔试题：
给定一个字符串里面只有"R" "G" "B" 三个字符，请排序，最终结果的顺序是R在前 G中 B在后。
要求：空间复杂度是O(1)，且只能遍历一次字符串。
点评： 本质是荷兰国旗问题，类似快排中partition过程，具体思路路分析及代码可以参考此文第8节： http://blog.csdn.net/v_july_v/article/details/6211155 。 9月27日，人人两面：
一面
1 实现atoi
2 单链表变形 如 1 2 3 4 5 变为 1 3 5 4 2 如1 2 3 4 变为 1 3 4 2
(就是拆分链表 把偶数为反过来接在奇数位后面）
二面
1 二叉树查找不严格小于一个值的最大值（返回节点）。
2 有序数组里二分