Pass了mentor的面试
非常坎坷的过了mentor的面试。虽然题目非常的简单，但是讨论很长时间。唉。不应该把面试看的这么难。应该抓住最基本的东西去做。然后下午又和整个团队玩面试游戏
。出了很多面试题，就这样把一下午的时间都消磨干净了。因为整个team在做pilot所以大家都有空闲时间。因为又不能去玩其他的游戏，所以只是在cubic里做了
大量的面试题。最值得高兴的是，在今晚8点半到9点之间，玮出了道95年的计算机竞赛题决赛题，虽然大费周折，但是还是把它做出来了。
团队的Weekly English Meeting
今天Lynn做host，的的确确开心了一把。第一个游戏测试记忆，结果只有玮唱了首Happy
birthday。第二个游戏是模拟游戏。五个人，每个人拥有自己的角色。并分配了任务。只能靠字条通信，通信的模式是：A <->B,B<->C , B<->D,
B<->E；那个团队先解决了任务，哪个团队获胜。因为我们是第一次玩，并且不清楚各自的角色。我是A，发了多个任务消息给B（Shawn）但是他迟迟不回我。Ann
ie是D，老是发无效消息骚扰B。其实任务很简单，只是找到5个人都有的Symbol。但是Shawn一直不发消息给我。所以我也不清楚发什么给他。即便如此，他还是
猜中了任务。最后我问他，为什么不向我要任务，或者说你不清楚任务？他的回答让我当场晕倒，“忘了”。无语，Shawn很happy的回着Annie的无聊消息，把我
给忘了。Lynn最后解释这个游戏是干啥的：B is PM, C, D, E are Devs and Tests, A is
custom.PM竟然把客户忘记了。o,my God! 不过从这个小游戏中很清楚的知道，PM是至关重要的人物，不光要分配任务，而且要和客户打交道。并且在De
v和Test不知道干什么的时候，就应该让他们忙忙其他的，不要让他们老来烦自己。
做题练习--归并排序,穷举
最近比较闲，抽空练练爪子：
多路归并
void MergeLines( int * temp, int * A, int left, int right)
//
其中temp是临时存储空间，A是真正的存放数据空间，left是数组的最左下标，right是数组的最右下标。
  … {
// 先判断些特殊的边界条件
if (right - left < 1 )
return ;
if (right - left == 1 )
  … {
if (A[right] > A[left])
  … {
swap(A[right],A[left]);
 }
return ;
 }
int mid = (right - left) / 2 + left;
MergeLines( & temp[ 0 ], & A[ 0 ],left,mid);
MergeLines( & temp[mid + 1 ], & A[mid + 1 ], 0 ,right - mid -
1 );
// 真正的归并开始（这里可以看做已经做到最后一步）
int k = 0 ;
int i = 0 ,j = mid + 1 ;
while (i <= mid && j <= right)
  … {
if (A[i] > A[j])
  … {
temp[k ++ ] = A[i ++ ];
 }
else
  … {
temp[k ++ ] = A[j ++ ];
 }
 }
if (i > mid)
  … {
while (j <= right)
  … {
temp[k ++ ] = A[j ++ ];
 }
 }
else
  … {
while (i <= mid)
  … {
temp[k ++ ] = A[i ++ ];
 }
 }
// 重新将值赋回A数组
for (i = 0 ; i < k;i ++ )
  … {
A[i] = temp[i];
 }
 }
使用一个串中相同的字母再生成新串，打印所有的串。比如“abc”有“bac”“bca”…等等。
这段代码的想法是{a,b,c},拿到{a}，将{b,c}去递归。如果拿到{b},将{a,c}去递归。
void All( string pre, char * str, int len) //
pre是前缀，str是真正的串，len是串的长度（除去’/ 0’）
//
这里注意str必须是一个new出来的字符串数组，不能是字符串常量数组。
//
开始的调用可以这样写All(“”,str,strlen(str));
  … {
if ( * str == ’ / 0 ’ )
return ;
if (len == 1 )
  … {
cout << pre << str[ 0 ] << endl;
return ;
 }
for ( int i = 0 ; i < len; i ++ )
  … {
if (i == 0 )
All(pre + str[ 0 ], & str[ 1 ],len - 1 );
if (i != 0 )
  … {
swap(str[i],str[ 0 ]);
All(pre + str[ 0 ], & str[ 1 ],len - 1 );
swap(str[i],str[ 0 ]);
 }
 }
 }
上面的函数可以进一步改写:这里的List就是{‘a’,‘b’},currentIndex = 0;k = len -1,len = List的元素个数。
void All( char * List, int currentIndex, int k, int len)
  … {
if (currentIndex == k)
  … {
for ( int i = 0 ; i < len; i ++ )
  … {
cout << List[i];
 }
cout << endl;
 }
else
  … {
for ( int i = currentIndex; i <= k; i ++ )
  … {
swap(List[currentIndex],List[i]);
All(List, currentIndex + 1 , k,len);
swap(List[currentIndex],List[i]);
 }
 }
 }
现在有一张纸币，但是现在有一堆个数无限的硬币（1角，2角，5角），兑换硬币
void past( int i) // 这里的i是最初的钱的价值（兑换成角，1元就是10角…）不过这里还是使用了穷举…:<
  … {
int u = 0 ;
for ( int j = 0 ; j <= i; j += 5 )
for ( int x = 0 ; x <= i; x += 2 )
for ( int c = 0 ; c <= i;c += 1 )
  … {
if (j + x + c == i)
  … {
cout << " <5,2,1> " << endl;
cout << j / 5 << " , " << x / 2 << " , " << c << endl;
u ++ ;
 }
 }
 }
不过写的代码自我感觉变量命名和函数命名不规范。这的确是今后要大大改进的地方。而且效率还很低。
因为硬币的穷举算法效率很低，所以用背包法重写代码：
如果输入的dest是10角，那么这里的srcSet应该含有10/1个1角，10/2个2角，10/5个5角。currentIndex是srcSet的下标，sr
cLen是srcSet的大小，subSet是符合条件的数据,num是subSet的集合中现含的元素个数。
int match( int * srcSet, int currentIndex, int srcLen, int dest,
int * subSet, int num)
  … {
if (currentIndex == srcLen)
return - 1 ;
if(dest-srcSet[currentIndex] < 0)
return -1;
if (dest - srcSet[currentIndex] == 0 )
  … {
subSet[num ++ ] = srcSet[currentIndex];
cout << num << " number match the dest, they are: " << endl;
for ( int i = 0 ; i < num; i ++ )
  … {
cout << subSet[i] << " " ;
 }
cout << endl;
return num;
 }
subSet[num] = srcSet[currentIndex];
int number = match(srcSet,currentIndex + 1 ,srcLen,dest -
srcSet[currentIndex],subSet,num + 1 );
if (number <= 0 )
  … {
return match(srcSet,currentIndex + 1 ,srcLen,dest,subSet,num);
 }
else
  … {
return match(srcSet,currentIndex + 1 ,srcLen,dest,subSet,num);
 }
 }
但是该算法仍然有的缺陷是最后返回的一定是-1。所以只好在程序运行过程中打印出结果。这里要求数组srcSet是从小到大排列的。虽然算法的复杂度没有降低，但是运
行的时间可能会加快。但是在最差情况下，比上面的穷举效率还低。而且多使用了空间。感觉类似于迷宫问题。虽然可以用A*但是最差情况下，比穷举还低。
C# Network Stream
今天碰到一个问题。运行的时候Server和Client端可以正常通讯，但是调试的时候去在Stream.Read()那里卡死。看Client端的代码，发现有很
多的thread.Sleep()操作。于是把Thread.Sheep()中的参数值调大了些，向networkStream中写数据不像过去那么快，结果调试就p
ass了。百思不得其解，瑞军老大说：“StreamRead是不是同一个？”就这一句话解决了JAME（j2me
自动化测试框架）多个月来的稳定问题。原因在于用同一个NetworkStream New出多个StreamReader。一旦有一个StreamReader实例
调用的一次Read()函数。那么它将把当前缓存区中的内容全部都拿到自己的私有缓存区中。用微软的refactor工具看的源码 ：）
，那么另外的StreamReader实例就不可能再得到缓存区的内存。其结果就是在Read()处挂死。
做题沙龙
昨天和瑞军老大一起看编程珠玑。顺便讨论下问题。听到我和老大再讨论黑豆白豆的农民问题时，Annie过来凑热闹。我给她出了道老大给我出的手机T9输入法。没过多久
便认输了。然后老大给她出了道90%九十程序员会错的二分查找。Annie又写了一段时间。在这段时间内和瑞军，Cloud讨论Annie给我们出的另类二分法。结果
我们讨论了半天无果。最后问问Annie，才发现题目没有听清楚。所有人都当场晕倒。
后来大家又讨论google面试云云。給我的感觉是3点：位运算，函数规范，归类。
Server Stress Test
1.Go through. One user account goes through every operator, if it’s ok, then
do the stress test.
2.Concurrent. Many user-accounts go through every operator, if it’s ok, then
do the next step.
3.Random. Many accounts go through every operator randomly. This step may
break server cache.
4. Time stamp. Client should log the time for every operator in order to
analyse server performance.
5.Exception catch. Client log this in order to log why it’s failed.
6.Use process not use thread in some time. Web service will catch many client-
threads in one session, though the web service will assign one and only
session ID to each thread. The server will replace one another.
7.Last time. test time should last as long as possible.
8.Clearly know which operator will cost the most(cpu, memory, network) in
server. You can fouse on it.
9.Clearly know the envirnment and configuration of server.
10.Clearly know the server application depends which kind of application(os,
db)
各种缺陷的二分法算法
二分法是思想精髓就是如果左下标和右下标得到的中间下标所在的值等于所要查找的值，算法结束；如果中间的值小于目标值，则说明目标值可能在中间值和右下标所在的区间内
，就将中间下标当成左下标，继续搜索。如果中间值大于目标值，则把中间下标当成右下标，继续搜索。
这是近期在网上用google搜索“二分法算法”找到的二分法算法。结果发现各种各样的缺陷。
public int erfen()
//二分法查找
{
int iindex=0; //相当于指针的东西
int istart=0; //
int iend=iarray.length-1;
while(true)
{
icount++;
iindex = (istart+iend)/2;
if(iarray[iindex]<iseek)
{
istart = iindex;
}
else if(iarray[iindex]>iseek)
{
iend = iindex;
}
else
{
break;
}
}
return icount;
}
用一个测试用例就能证明的这个算法错误。
0 1 2 3 4 5查找5.结果你会发现死循环。
很多人认为只要起始值的左值和右值相加为n-1就可以了。其实不然，二分法是10年多的时间才找到了一种正确的算法。如果你开始的左值设为0并且右值设为n-1,程序
很大的程度上会错。除非你解决了最后的死循环问题。
下面的算法
left = - 1 ;
right = length;
while (left <= right)
  … {
mid = (left + right) / 2 ;
if (a[mid] > value)
  … {
// 中间值比目标值大
right = mid;
 }
else if (a[mid] < value )
  … {
// 中间值比目标值小
left = mid;
 }
else
  … {
// 找到，中间值等于目标值
return left;
 }
 }
return - 1 ;
可以解决上面的0 1 2 3 4 5 查找5找不到的问题。但是，却在查找不存在的数上出了问题。比如6
下面的代码解决了这个问题：
left = - 1 ;
right = length;
while (left + 1 != right) // 注意这句话！！！
  … … {
mid = (left + right) / 2 ;
if (a[mid] > value)
  … … {
// 中间值比目标值大
right = mid;
 }
else if (a[mid] < value )
  … … {
// 中间值比目标值小
left = mid;
 }
else
  … … {
// 找到，中间值等于目标值
return left;
 }
 }
return - 1 ;
但是上的这段真的解决了所有的问题？如果left + right 超过了整数范围？
改为下面的代码：
int BinarySearch( int value)
  … {
 
int left = -1 ;
int right = length ;
int mid;
while (left +1! = right)
  … {
mid = left + (right - left) / 2 ; // 注意这里的写法
if (values[mid] == value)
  … {
return mid;
 }
else if (values[mid] < value)
  … {
left = mid;
 }
else
  … {
right = mid;
 }
 }
return - 1 ;
 }
这里解决了越界问题。但是这段代码真的没有问题了吗？没有人能保证。除非能用数学证明。
另外还有一种写法：但是必须特判length==0的情况,否则一定会访问越界。
int bsearch(int* a, int l, int r,int k) { int mid = 0; if(l-r == 0) return -1;
while(l<=r){ mid = (l+r)/2; if(a[mid]<k) l = mid+1; else if(a[mid]>k) r=mid-1;
else return mid; } return -1; }
发布网站，解决SecurityException
今天发布网站一直不顺。应用中含有Webservices的调用，本地发布成功，但是异地发布却是失败的。后来排除WebService的Url不匹配问题。结果程序
还是报一下异常。
[SecurityException: Request for the permission of type ‘。。。’
解决方案是：在web.config文件中加入
异地发布时，如果没有单独的ErrorPage,就要添加
如果报有can not find type in
很有可能IIS上的网站设置选用的不是.net framework 2.0，这个在网站的属性里设置即可。
这里的异地发布是指，不再开发的机器上发布。
字符串匹配算法
基本思想是从源字符串的起始位置起每个字符匹配。如果中间出现失配，则回溯到某个位置再行匹配。
1.最简单的就是回溯到前一次失配串的第二个字符再行匹配，并将目标串的起始位置重置。
int Index( const char * src, const char * des, int start)
  … {
int lengthSrc = strlen(src);
int lengthDes = strlen(des);
int i = start,j = 0 ;
for (; i < lengthSrc && j < lengthDes; i ++ ,j ++ )
  … {
if (src[i] == des[j])
  … {
continue ; // 这个位置匹配成功
 }
else
  … {
// 这个位置失配，将i复位到前一次匹配串的起始位置的下一位,目标串重置
// 这里因为马上要进入下一个循环，并且i++,j++，所以i = start,j = -1.
// 标记起始位置的start也要加一。
i = start;
start += 1 ;
j =- 1 ;
 }
 }
if (j == lengthDes)
  … {
return start;
 }
else
  … {
return - 1 ;
 }
 }
2.使用KMP算法。KMP算法的思想只是将刚才算法优化了一下。在好的情况下，可以不用从上一个匹配串的start+1位置重新匹配。而是可以从某个可能的位置重新
匹配。
但是这样要先消耗一个n的时间来得到目标串的每一个位置失配后将从哪个位置开始重新匹配。当然这样好处还有源串的匹配位置不用改变。
int * Get_Next( const char * a)
  … {
int length = strlen(a);
int * next = new int [length];
next[ 0 ] = - 1 ;
// 该算法中约定第一个位置的重匹配要从目标串起始位置的下标减一开始。
// 当然这只是为了后面的匹配函数好些罢了。
for ( int i = 0 ,j = - 1 ; i < length;)
  … {
if (j == - 1 || a[j] == a[i])
  … {
j ++ ;
i ++ ;
if (a[i] != a[j])
  … {
next[i] = j;
 }
else
  … { //
如果目标串出现“aaaab”这样的情况，可以使得后面的’a’重用前面a的匹配位置。
// 类似于动态规划的思想。
next[i] = next[j];
 }
 }
else
  … {
j = next[j];
 }
 }
return next; // 这里并没有返回数组的个数…
 }
真正的功能函数：
int IndexKMP( const char * src, const char * des, int start)
  … {
int length1 = strlen(src);
int length2 = strlen(des);
int * next = Get_Next(des);
int i = start,j = 0 ;
while (i < length1 && j < length2)
  … {
if (j == - 1 || src[i] == des[j])
  … {
i ++ ;
j ++ ;
 }
else
  … {
j = next[j]; // 只不过这里有所改变。
 }
 }
if (j == length2)
  … {
return i - length2;
 }
else
  … {
return - 1 ;
 }
 }
解决了一下内存泄露的问题，同时找到一个数组越界的bug。在Get_Next()中next数组的下标有可能超过其长度。改进后的算法如下：
int * GetNext( const char * a, int * next)
  … {
int length = strlen(a);
next[ 0 ] = - 1 ;
for ( int i = 0 ,j = - 1 ; i < length;)
  … {
if (j == - 1 || a[j] == a[i])
  … {
j ++ ;
i ++ ;
if (a[i] != a[j])
  … {
next[i] = j;
 }
else
  … {
next[i] = next[j];
 }
 }
else
  … {
j = next[j];
 }
 }
本着谁生成谁释放的原则，在IndexKMP中生成next数组：注意这里的数组长度是length2+1,很奇怪的是，当初值为length2时，本该越界处是在G
etNext()中。但是那里并没有抛出异常。倒是在delete中抛出来Heap被破坏的异常。所以如果你写的程序抛出Heap Corruption
Exception，那么很有可能你的数组已经在前面越界。
int IndexKMP( const char * src, const char * des, int start)
  … {
int length1 = strlen(src);
int length2 = strlen(des);
int * next = new int [length2 + 1 ];
GetNext(des,next);
int i = start,j = 0 ;
while (i < length1 && j < length2)
  … {
if (j == - 1 || src[i] == des[j])
  … {
i ++ ;
j ++ ;
 }
else
  … {
j = next[j];
 }
 }
delete [] next;
if (j == length2)
  … {
return i - length2;
 }
else
  … {
return - 1 ;
 }
 }
继续优化代码：在开始处判断目标串和源串的长度
int IndexKMP( const char * src, const char * des, int start)
  … {
int length1 = strlen(src);
int length2 = strlen(des);
if (length2 > length1)
  … {
return - 1 ;
 }
int * next = new int [length2 + 1 ];
GetNext(des,next);
int i = start,j = 0 ;
while (i < length1 && j < length2)
  … {
if (j == - 1 || src[i] == des[j])
  … {
i ++ ;
j ++ ;
 }
else
  … {
j = next[j];
 }
 }
delete [] next;
if (j == length2)
  … {
return i - length2;
 }
else
  … {
return - 1 ;
 }
 }
Dos "For"
for /L %f in (1,1,5) do @echo %f
这意味着输出是 1 2 3 4 5, (1,2,5) 从1开始到5结束，2为步长。如果这个for要执行多条命令则用|分开
@echo %f | @echo %f. %f只是一个变量。如果在cmd窗口下写这样没有错误，但是如果要运行在bat脚本中，就要将这个%f写为 %%f
才正确。
不明白的命令使用 [command] /? 或者使用 help [command]