按照之前写c/c++、java的习惯，这里肯定是等于-3。但是python下返回的结果竟然是1！

为什么会有不同的表现呢？先从取余操作本身说起：

关于取余(modulo operation)

取余的定义

由于不同的架构有不同的数字表示法和运算法，因此他们对于取余的定义也有可能略有不同。

一般来说，公认的取余操作（被除数a、除数n、商q以及余数r，n % a = r）需要满足以下三条：

然而这个定义是非常宽泛的。以 -3 % 4为例：

-3既可以表示为：-3 = 4 * -1 + 1

也可以表示为：-3 = 4 * 0 + (-3)

这两种表示法分别对应了两种实现方法：Truncated Division及 Floored Division。两种实现方法的求商方式不同，导致其最终结果也不同。

Truncated Division

在Truncated Division下，求商时，采用的是q = trunc(a/n) ，即将算数除法结果的小数部分移除，余下的整数部分作为商。

（也有一种更形象的说法，除法取整时，是朝着靠近0的方向取整）

以-3 % 4为例：

q = trunc(-3/4) = trunc(-0.75) = 0

因此，余数r = a - nq = -3 - (0 * 4) = -3

此实现有如下特点：

1. 余数的符号与被除数相同

2. 这种实现在某些地方被称之为取模

Floored Division

在Floored Division下，求商时，采用的是q = ⌊a/n⌋，即将算数除法结果进行向下取整作为商。

以-3 % 4为例：

q = ⌊-3/4⌋ = ⌊-0.75⌋ = -1

因此，余数r = a - nq = -3 - (-1 * 4) = 1

此实现有如下特点：

1. 余数的符号与除数相同

2. 这种实现在某些地方被称之为求余

关于语言标准

由上可知，存在着多种实现方式，那么具体地，c和python是如何选取的呢？

C语言标准中关于取余运算的说明

C89中，并未做严格规定：

When integers are divided and the division is inexact, if both operands are positive the result of the/ operator is the largest integer less than the algebraic quotient and the result of the % operator is positive. If either operand is negative, whether the result of the / operator is the largest integer less than the algebraic quotient or the smallest integer greater than the algebraic quotient is implementation-defined, as is the sign of the result of the % operator. If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a.

而C99，明确指定了需要使用Truncated Version：

When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded.⁸⁸⁾ If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a.

_{88) This is often called "truncation toward zero".}

Python标准中关于取余运算的说明

Python 2：从说明中关于余数符号的部分，可以推断出其指定了Floored Version

The % (modulo) operator yields the remainder from the division of the first argument by the second. The numeric arguments are first converted to a common type. A zero right argument raises the ZeroDivisionError exception. The arguments may be floating point numbers, e.g., 3.14%0.7 equals 0.34 (since 3.14 equals 4*0.7 + 0.34.) The modulo operator always yields a result with the same sign as its second operand (or zero); the absolute value of the result is strictly smaller than the absolute value of the second operand [2].

The integer division and modulo operators are connected by the following identity: x == (x/y)*y + (x%y). Integer division and modulo are also connected with the built-in function divmod(): divmod(x, y) == (x/y,x%y). These identities don’t hold for floating point numbers; there similar identities hold approximately where x/y is replaced by floor(x/y) or floor(x/y) - 1 [3].

Python 3：和2一样，可推断出指定Floored Version

The % (modulo) operator yields the remainder from the division of the first argument by the second. The numeric arguments are first converted to a common type. A zero right argument raises the ZeroDivisionError exception. The arguments may be floating point numbers, e.g., 3.14%0.7 equals 0.34 (since 3.14 equals 4*0.7 + 0.34.) The modulo operator always yields a result with the same sign as its second operand (or zero); the absolute value of the result is strictly smaller than the absolute value of the second operand [1].

The floor division and modulo operators are connected by the following identity: x == (x//y)*y + (x%y). Floor division and modulo are also connected with the built-in function divmod(): divmod(x, y) == (x//y, x%y). [2].

结论

一些推断及其他

最后，来小小地猜测一下，为什么c语言和python会选取不同的实现方案。

对于c：

在X86架构下，对于整数的除法和取余操作，都是通过同一个指令进行的（有符号除法使用idiv，而无符号为div），商和余数会同时作为结果返回在寄存器AX和DX中。

这个特性被c的库函数divmod所利用，导致编译器有可能会将除法及取余操作都优化为使用一个指令完成。

这样一来，通过如下三条：

1. c的除法正好为trunc除（即Truncated Version中取商的方式）

2. 通常程序里除法出现的频率都远远高过取余的频率，取余可能会被优化为一个指令

3. c语言设计风格为性能和简洁优先，而c++又要与c兼容

因此c语言采用了Truncated Version。

而这也为一个常用的判断埋下了坑：

如果你想判断一个数是否是奇数，

会埋下大坑（对负数存在bug）

而需要写成

对于python：

不会像c那样将性能放到第一位，会比c有更多的语法糖，更贴近常用思维，因此使用Floored Version会更加适合。

参考文献

https://en.wikipedia.org/wiki/Modulo_operation#Remainder_calculation_for_the_modulo_operation

https://docs.python.org/2/reference/expressions.html#arithmetic-conversions

http://stackoverflow.com/questions/3609572/does-either-ansi-c-or-iso-c-specify-what-5-10-should-be

http://stackoverflow.com/questions/11630321/why-does-c-output-negative-numbers-when-using-modulo

主要以招聘情况、各公司简单面经、找工作经验总结为主，点一下后面的标题就可以展开看详细

校招里我参加的所有公司招聘情况，按时间排序：

华为、阿里、百度、腾讯、去哪儿网简单面经：

找工作经验总结：

最后就结果而言，真是出乎意料。我认为，我绝对是这批面试者里最最最幸运的，人家以实力说话，我以运气通关。。。
下面开始流水账：

9月20日：
到达成都

因为穷，没有跟其他同学一样买动车而是买了个k开头的
在川大找了个50/天的房子和另一个同学合租

9月21日：
上午笔百度，下午笔腾讯，晚上笔锐捷

感觉百度腾讯的笔试题没有去年难了。另外锐捷竟然直到我离开成都也没有给过我信，我笔试答得有那么差嘛

9月22日：
经历了昨天狂笔的劳累以后好好休息了一上午，傍晚去了川师笔阿里。

笔试地点是在就业中心的教室里。强烈投诉川师的教室环境，蚊子实在太多了，竟然隔着衣服就开咬，各人战况惨烈
打了快两个小时的蚊子，心里还惦记着百度来着，于是hr要求手机关机的时候只是偷偷调了震动；果然在一边打蚊子一边检查的时候手机响了，于是果断交了卷打回去，总算是没漏掉百度一面通知

9月23日：
上午百度一面，晚上网易笔试。

百度一面就聊了20分钟左右，前面几个linux相关的答得不好，后面算法倒还勉强接的上。因为很短就结束了，感觉比较意外，还告诉面试官我以为会问更多的算法来着，面试官回了句你算法基础还挺扎实的
晚上网易笔试比较搞笑，4点多的时候才收到通知说晚上要去电子科大清水河校区笔试，感觉当即坐车估计都不一定能赶过去了。。。
于是众人纷纷跑到川大来霸笔，凭借短信方得以进场。还配合同学做了下假，把网易给我的短信改了下转发给他，结果他也霸笔成功
感觉网易的卷子是自己做的最好的，全在考C++细节、小技巧以及算法手写代码，写的挺爽的

9月24日：
上午面阿里、下午1点半面百度二面，4点面腾讯一面，晚上回来还笔了个优酷土豆

这是忙到死的一天，没想到一天一共面了五场晚上还笔了俩小时。
上午面阿里，稀里糊涂地一口气面完了HR。进去注意到阿里每个面试官前面还放了牌子写着自己的花名。
一面问了20分钟左右，主要在讨论各种算法，除了一般的算法外还包括我的论文算法，分词算法，推荐系统等。难道要我去搞dm？
面完以后让我等一下，去面二面（后来才知道二面面试官竟然是大boss，10P的，左耳朵耗子也才9P）
二面倒是主要是我在说，把对天猫的秒杀、抢红包等活动的策略及技术变化讲了下自己的看法，中间又问了些别的，最后大boss给了道智力题就让我再等等，在旁边找了个HR和我随便聊聊天竟然就结束了。。。

百度二面悲剧了，面试官是个非常亲和的人，问问题都和我一起商量着来。奈何人家手头活多，急需一个帮他写系统底层（准确说是kernel之上driver之下）的人，然后我就悲剧了
想试试面其他组，最后也没成功。感觉有些不甘心，都说百度最爱问算法，我却没被问多少

腾讯一面的面试官超有架子，问问题很快，问完几个问题就把我打发过去写算法了。他叫我20分钟写思路，10分钟写实现，被我搞定了。拿过去后他看了下说，你的二面将会非常艰难，硬着头皮上吧。我愣了下才反应过来他是告诉我一面结束了，出来后我才发现这貌似是我成都之行里用时最短的一次面试。

晚上笔优酷土豆，可能是我的职位填错了，笔完以后再无动静。。。

9月25日：
上午笔试去哪儿网，下午面了腾讯二面。

去哪儿网的笔试和网易的一面时间冲突了。我纠结了一阵后还是先跑到酒店去看了下网易HR的样子，顺便想看看自己的笔试成绩。HR说看不到分数，不过她是按成绩排的，我看到我是第三，也算心满意足了。看看时间差不多，想想网易这职位全国就招10个人，就放弃了面试，回去笔去哪儿网了。
其实说网易搞笑还是有另外一个原因，当初看到网易招人实在太少，我选了个招人多点的职位，没注意他考的是Java。等到笔试的时候，发现可以随便要卷子，于是我就要了C++的。做完C++笔试题以后，竟然收到了网易的Java面试通知。网易太奇妙了。
另外我很后悔报了网易互联网部门的。等回了重庆，觉得没有去面试游戏公司是一大遗憾。当初被网易游戏的招聘学校吓住了，其实我只是想要个聊天机会而已。

腾讯二面是下午四点，还想着面完腾讯以后去霸面下百度的，结果我前面的两个人每个人都面了一个半小时，我等了足足3个小时，6点多才面上腾讯。
更奇葩的是我只被问了不到20分钟就出来了，和前面俩人的时间差距也太大了。。。
就是问了些linux、socket相关的问题，几道算法，最后还有道智力题，两个人在桌子上摆硬币的那个，我没想出来。不过最后临走前面试官问了我个问题：“如果腾讯阿里都给你offer你选哪个”，本来看时间这么短，以为完全没戏的，听到这个感觉似乎又有了那么一点希望

9月26日：
阿里圆桌会议、腾讯三面。

晚上1点才接到阿里的电话通知，上午又跑回新良大酒店。说是圆桌会议，结果一个圆的桌子都没有看到。签了就业意向书，还一人发了一本《淘宝技术这十年》。今年阿里扩招，全国招1000人，成都这边要了70个，其中成电的就接近50个。

下午跑到腾讯总部去面hr了。因为今天要开华（tu）商（hao）大会的缘故，全市各机关单位放假，又各种封路，坐了挺久的公交才过去。和hr就北京和深圳的就业地点问题聊了好一段时间。不知道是不是上午签阿里太高兴了，下午腾讯面试一点都兴奋不起来，弄得hr还以为我一直很纠结北京来着

9月27日：
中午去找了几个在成都的本科同学聚了下，吃了正宗的川菜，傍晚去面了去哪儿网。

去哪儿网竟然下午5点才开始面试，之前hr还打了两个电话来提醒面试时间。
去哪儿网其实有很多独特的地方，一是今年不知为啥狂发offer，群里有同学大呼offer来的太容易，钱也不少，问是不是骗子公司
二是竟然完全不批笔试卷子，不知道他怎么筛选的，难道是看写的多少？
三是一些比较独特的言论，比如宣讲会时问他们笔试要不要带简历，人家直接回答说“你们应届生的简历都没啥值得看的”；我面完以后还听到一群人在商量怎么对付霸面的，“看看项目，看看照片就筛了呗（众人笑）”“还是出笔试题给他们做吧，一道就行”“这酒店太小了，没场地啊”“xx搞定了下面宾馆的那个场，没问题”
感觉是气氛非常融洽的一帮人，另外去哪儿网的2014应届生FAQ写的也很有生活气息

一面就拿着我笔试卷子问来问去，让我手写了快排，还问了算法、linux、多线程、tcp/ip，不知不觉竟然问了我40分钟，是我被面最久的一次了；
二面不问技术细节，就让我讲讲学习经历，印象最深的从书中学到的知识点，自己的优势什么的；
三面的时候我已经饿死了 OTL。。。 我表示因为实在太饿所以没法当场签，对面说可以两周后等我吃饱了签电子档的（误

9月28日：
去了天府软件园招聘会，回重庆

看到这个天府软件园招聘会还是有挺多公司的，特别是不少游戏公司，金山亚丁，完美，2k，gameloft等等。就是人实在是太多了……

人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人
人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人
人人人人人人人人人人人人人人人人人人我人人人人人人人人人人人人人人人人人人人人人
人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人
人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人

基本上都是排了很久的队后发现只是简单聊下，收收简历，好坑。不过这里简历可以免费复印打印。和几个做游戏的稍微聊了下就回重庆了

最后总结下，除了那个去哪儿网的一面之外，其他面试基本都没有超过半小时，没有遭遇压力面试，也没有被面试官拽住狂问，我觉得只能归结于踩了一堆又一堆的狗屎运。。。。
最大的体会是面试既有实力成分，也有运气成分。面试官的风格、偏好，有的时候会在应聘过程中取到决定性的作用；但一定要有一个拿得出手，令人印象深刻的方面做支撑，若是面试官通过前面几个问题可以认可你的简历而不是质疑，后面的事情就越来越简单了。
还是要特别感谢自己的大师兄川江神犇，他提醒我补算法，刷oj，确实受益匪浅。

盘算着从halifax回来以后去北京再面几家游戏公司，真的是很想借着应届生的身份去好好聊一下，说不定还能见到doublecai，littlewater，gltracy，advance等仰慕已久的大牛

介于是篇流水账，我在文中也没怎么提及面试被问到的详细内容（貌似这个还被很多同学问到了）
不写详细问题的主要原因有俩，一个是没有遇到很难的题，应该也没有遇到新题，都是些之前见到过的或者是已有问题的类似变种，平时去v_july_v之类的博客积累下，看看《编程之美》《编程珠玑》《剑指offer》等书肯定可以应付得了，所以印象不深刻，记录的价值也不高；另一个是因为实在是记不太清楚了OTL 特别是哪一面问了哪个算法题什么的，记忆已经完全乱作一团了……所以就不再记录。对于有些比较值得深入的题目，后面会另开文章单写

一路追到Cocos2dxRenderer.java里一览究竟：

原来是帧数控制部分被官方注释掉了，他们给的原因是“不精确，在某些设备上还会拖慢速度”

当然除了动这个java文件，其实也有其他的解决方案，比如说干脆用一个while死循环完完全全地轮询过去，但是这种情况下的耗电和cpu占用都令人难以接受；
也可以直接在游戏逻辑部分用c++写自己的帧数控制，但是却丧失了可移植性（至少linux/win32下的精确帧数控制写法是不同的）
所以不能这么轻易就放弃，还是要在这里好好动手改一下。

首先要提出批评，貌似cocos2dx在这个android帧数控制上一直都有问题。
首先注意看Thread.sleep((Cocos2dxRenderer.sAnimationInterval - interval) / Cocos2dxRenderer.NANOSECONDSPERMICROSECOND); 这句话，在早期版本里他sleep的时间是目前的2倍（官方注释都被保留了下来作为证据= =），至于为啥要乘以2他也语焉不详了。
后来也有使用者发现了这个问题，于是去掉了乘以2，确实有所改良。（见此）

不过现在的这个Cocos2dxRenderer.java里单纯去掉注释，还是不行，因为他interval（或是上一帧时间基准）的计算位置还是错的OTL……
给他挪好位置，在没什么负载的情况下，终于可以稳定在指定帧数上了。但是在有负载的情况下，却出现了拖慢的问题：
若是不启用帧数控制，则原本可同屏900子弹跑到35-40fps，若是启用帧数控制，连25帧都稳定不到了。
损耗出在哪里呢？我将计时换成了System.nanoTime()，已确定该函数损耗不高，但依旧不行。
问题出在sleep上。在java里，sleep本来就不是一个能够得到精确保证的计时函数，实际运行的时候，经过测试，精度至少是比15ms还要差的

所以我的解决方案是，先使用sleep进行等待在当前精度下比较保险的较短时间；对于剩余的部分，再采用while+轮询等待来补足。
比如说，预计精度是15ms，当前帧要等待35ms，则sleep(20ms)，在sleep醒来之后，可以预计此时时间已经过了20-35ms，但不会超过35ms，于是剩下的部分就用while等过去。
这样既能提高精度，又能够避免一直用循环等待而带来的高耗电和cpu占用。代码见下：

变量lastRenderingTime在onSurfaceCreated函数里初始化一下即可。
最后效果确实是提高了，至少可以稳定在28-30帧之间，勉强算是可以接受啦

第一题：密码合法性校验（点击展开）

第一题自己的代码

第二题：把数组排成最小的数

第二题自己的代码

第三题：以最节省的方式完成全程

第三题自己的代码

第一题：磁盘数据恢复（点此展开）

第一题自己的AC代码

第二题：容量转换

自己的代码wa了，找不到wa在哪，求各位指点……
最大数字应该是2的60次方，double也应该存的下才对，难道要大数乘法 OTL

第二题自己的代码

第三题：判断给定的数字是否满足给定的条件

只能粗略地把&&合并，最后是TLE
估计要用线段树

第三题自己的代码

2面是技术总监来面，但是感觉非常和蔼，整个过程都在微笑。一面的时候，我问面试官二面会不会还是你们项目组的，对面说不一定，于是二面的时候上来自我介绍我还是说了“自己首选c/c++，但是做java也可以”的情况。没想到2面的还是搞java的 OTL……

2面问的问题还是两部分，项目和技术细节
项目里，问了我怎么调试bug，遇到最困难的事情是什么，怎么解决的
技术细节方面，先后问了mysql调优（这个我不会！），forward和redirect的区别（还是不会！），gc机制（这个一面其实就问过了，我补习的，回答的还好），多线程（只是问了下有没有用过，我说没在java下用过，他就没问了OTL 其实我觉得我还是可以讲一讲的），滑动窗口（我大概写了过程，对面问我，是大三学的吧？看来忘得差不多了）
后来又问了一些网站安全方面的问题，先问了SQL注入是什么，怎么防，我答了下，顺口说觉得这个还比较好防，然后对面就开始问“你觉得什么比较难防”
我就把去年比较热的hash碰撞漏洞说了下，说到一半想起来这个一点都不难防，补丁早就有了= =！他也没说什么，还问了下XSS
不过真是一道算法相关的都没问……我还特地问了下，你觉得工作里会用到算法么？
对面曰：主要是做业务逻辑，所以一般是用的不多，不过到了要用到的时候，要是你不会，那可不行
后面就是交流了一下那边的工作内容，实习期的工作，长度，预期要做的事情，做实习生时导师的情况之类的，总共大概面了差不多40分钟

其实2面之前还是觉得非常紧张的，到场了以后和同学交流，同学说问的问题都很bt，比如说让你最快速度写出尽可能多的linux命令，还有算法题之类的
算法题凭记忆好像有单链表查环，上台阶的方法总数，海量数据库里找一个数是否存在，还有就是楼层扔鸡蛋的问题。感觉这些算法题都很好对付啊！可惜没人问我 TAT……

我觉得，我还是更适合做c/c++开发，不过linux确实是我的短板。

第二天HR面，我晚上一直没收到短信，还在想，是不是推到后天了？上午翻同学微博，才得知他们是今天HR面，然后赶快检查自己邮箱，原来自己也是下午HR面！
好险，差一点就错过了。不过时间也不多了，没怎么准备就去了

面我的hr其实之前见过，一面的时候她负责签到，算是hr里年龄比较大的，应该是主管之类的职位。一面二面我都是主动自我介绍，HR面倒是她先让我自我介绍了。
内容就是聊天，比如说家庭情况，爱好，职业规划，为什么选腾讯，学习的方法，是什么支持你学习这么多，缺点，优点之类的。有几个问题感觉准备的不够好，有几个问题觉得回答的不够好，但也是聊了半个小时多。
聊天的过程中看到她有自己的卷子，就问了下笔试成绩，得知只有60多，还是挺惊险的。顺便问了下，面HR的一共有多少人，对面说有几十个，我心一凉。对面接着说，这次的名额非常非常有限，所以如果挂了的话你可以考虑等9月份校招的时候再来面，那个时候岗位多。我心凉透了……我问她，这次也算是走到HR面，要是最后被鄙视了，那数据库会不会有啥记录之类的，她说，你把这个经历给面试官说一下，他会做参考的（也就是说人才库之类的就只是个安慰了……）

HR面完出来，进电梯正好碰到其他hr，她们看到我皱皱的衣服，凌乱的头发，唏嘘的胡渣，惊讶地对我说，面的这么惨啊。（……）
我顺便问了一下，下午大概要面多少人？她们说下午要面30个左右。加上上午面的，我估计重庆这边应该有5,60个来面HR的，最后留下的人也就十来个吧。以前还以为HR不刷人的，如今算了下，HR刷人比例一点都不比一面二面少……
参加笔试的应该在1000人出头，算上后面霸面的，估计每轮都是5个里选1个的程度了

根据群里其他同学的分享，产品只有2个名额，运维4个，后台这边来了三个组，有一个组只招1个或2个。感觉希望如此渺茫，就不报期待了，暂且忘掉面试，还是回到日常生活里吧

=================================================
5.6更新

同届有三四个同学拿到offer了吧，我被刷了。收获了挫折感，然后又是惯常地跑到个人记事本里去给自己打鸡血写计划去了啊哈哈，其实都没啥用。
其实开始的时候不报期望的，觉得能面上就不错了。而现在的感觉，却仿佛是当初壮志豪言一定要拿下最后却未能兑现。师兄和周围同学们总是说我没问题，人言可畏啊
至于被刷的原因，肯定是实力不足妥妥没跑了。除此之外再给自己找几个开脱借口：
1.面试时心不够沉静，对面面试官一笑，我这边就放松了。
2.准备的东西牛头不对马嘴。做了半年多oj，看了编程珠玑编程之美inside c++，却没想到面试官只看java和业务逻辑。对于自己最擅长的东西，不仅没有被问到，更连谈论的必要都没有。那个时候就应该果断提出去面其他面试官的。
3.重视程度不够。

顺便，阿里巴巴的暑期实习生简历都没过，网易微软根本不给我们这些小学校机会，百度的还遥遥无期，这个暑假估计是没得实习了。

到了晚上6点，都准备明天去霸面了，终于还是收到通知了。

通知是下午2点，实际上1点半就被叫进去了。
在宾馆的标准间里面的，面试官看着非常年轻，感觉和我差不多年纪吧，一点都不摆架子，很和善。
进门递了简历以后，还没等面试官就位我开始自我介绍，为的是抢占先机。
先是提到自己本科的毕设，引起了对面的兴趣，然后balabala
说完毕设，说本科的几个java网站项目，面试官终于来精神了，首先是问了使用的架构，分工，负载情况
然后问我，看你最擅长的是c/c++，那你java怎么样？
呃，两年没用java了，只能如实托出
然后面试官就java问了几个基础问题，比如说：
GC的工作原则和垃圾回收机制是什么？我只答了最基础的引用计数OTL…… 回来的路上想到，GC的任务是保证内存可用，回收内存只是一方面，另一方面还有内存碎片等问题，所以多机制是必然的
java里会不会内存泄露？我一开始回答说不会，因为java走的全都是引用，逃不掉引用计数。后来又补了下，GC认为一个变量要呆的时间比程序员认为的要长，那就算内存泄露，这种情况是可能出现的
JVM内部调用类库的方式是什么？我也完全空白，只好说不会。但是我说我可以做个推测，于是就把c/c++里面静态链接、动态链接大概说了一下
还问我有没有做过多线程？我就中兴比赛的那个程序说了一下，不过很快意识到应该是问java下的，就凭印象回答了runnable接口和thread类

回答之后，我询问了一下，面试官是不是主要就是做java的，对面回答说是wapqq门户网站模块的后台
感觉java的问题都答得很糟糕，但是面试官还是很和善的样子，说我们轻松一下，来聊聊怎么做个俄罗斯方块小游戏吧
然后我就把我常用的游戏结构给写上去了，主循环，渲染模块，逻辑模块，帧控制，在纸上做了大体表示
不过感觉回答的太快了，所以思路显得很乱。因为前面的结构早就有数了，我一上来就开始说怎么设计里面对象的类和属性了，不太好
并且忽略了对面擅长java的事情，应该把模块关系、类的构造和继承关系都清晰地写出来才对。

对面还特地问了一下，为什么要帧控制

问完游戏，他开始继续低头看我简历，我就抓紧机会，问了一下他们公司这边的情况。这次来重庆面试后台的有三个组，除去他们这个java组之外，另外两个组是c/c++为主，但都是类似服务器半开发半维护的样子。他们java组都是用的自己的框架，很少用开源的东西。面试官还问我，对他们做的后台方向有没有兴趣，我说，我以前也做过类似的工作，我觉得能来做这个的话是非常宝贵的机会，我想去
（其实心里也在想，本科以后就放弃做java网站后台了，还真没想过要重新做这个……不过我也没得挑，能过一面就算成功了）

至此面试就结束了，大概30分钟的样子，其他同学貌似都有被问40分钟。临走的时候对面说觉得还行，大概2,3天后会有结果。不过我回来想想，java的几个问题真是回答的乱七八糟，进二面估计很玄了。只能算是自己运气好，没有碰上爱给压力的面试官

另外今年的笔试题里有10道选择题、5道填空和加分题的第一题都与去年的题目一模一样 OTL……
没看去年的题亏死了

挑两道印象比较深的题记录下：
（都是去年的题，网上都有公开，应该不算是私自公布试卷了吧）

两人猜数字，范围为[1,100]， 甲写一个数字，让乙猜。
如果乙猜的偏小，甲会说偏小，但是如果某一次甲猜的偏大，乙之后都只会说对或不对。
问： 乙最少可以在多少次内保证猜对？在这种策略下，第一个猜的数字是什么？

看到这道题，首先可以推导出这两问的答案一定是同一数字。若第一次猜X且偏大，则之后需猜X-1次方能保证猜中，即最少需猜X次。
于是递推一下，设最少猜X次才能保证猜对，则第一次必定猜X
第二次要猜多少呢？第二次猜的时候，要保证在猜偏大的情况下，后面再猜X-2次就能保证猜中，所以第二次要猜X+X-1
同理，第三次若猜偏大，后面要再猜X-3次，所以第三次猜的数为X+X-1+X-2……直至猜了N次之后，猜的数>=100
这就是一个初项为X，公差为-1，项数为N的等差数列求和，即约束方程$X*N-\frac{N*(N-1)}{2}=100$下求X的最小值
$X=\frac{100}{N} + \frac{N}{2} - \frac12$，$N=\sqrt{200}$时有极值，X约为14
答案就是14 14

两个数组a[N]，b[N]，其中A[N]的各个元素值已知
现给b[i]赋值，b[i] = a[0]*a[1]*a[2]...*a[N-1]/a[i]；
要求：
1.不准用除法运算
2.除了循环计数值，a[N],b[N]外，不准再用其他任何变量（包括局部变量，全局变量等）
3.满足时间复杂度O（n），空间复杂度O（1）

在编程之美上出现过类似的
这个题不准用其他变量，那只能在a和b上下手了
我的思路是，对于b[i]来说，可以拆成a[0]*a[1]*...*a[i-1]和a[i+1]*a[i+2]*...*a[N-1]两部分，这两部分用O(n)分别求出来，最后再乘起来就行了
代码见下：

我这种写法的缺点是改变了输入数组a，这个不太好。把好写法贴一份：

题目是这样的：

=======================================================================

编程题（共1题，100分。请上机编写程序，按题目要求提交文件。测试用例不对考生公开，凡不满足提交要求导致不能运行或用例不通过，不予评分。）

1. 俄罗斯方块之棋盘覆盖

俄罗斯方块是一款风靡全球的益智类游戏。由俄罗斯人阿列克谢·帕基特诺夫发明，故得此名。俄罗斯方块的基本规则是移动、旋转和摆放游戏自动输出的各种方块，使之排列成完整的一行或多行并且消除得分。由于上手简单、老少皆宜，从而家喻户晓，风靡世界。

本试题是在俄罗斯方块几种常见的方块基础上，在指定大小和障碍的棋盘上，用标准的方块形状，完成对棋盘的覆盖。用于覆盖棋盘的方块可以是下文所给出方块的全集，也可以是其中的任意一个子集，且使用的方块数量不限，形状变化不限。

棋盘大小：

棋盘大小为21行21列的正方形。按照从上到下，从左到右，从1开始，依次进行编号，直到最右下方的格子标识为441。

可选方块：

可选方块为标准的俄罗斯方块形状，包括其标准的旋转变化。基本形状如图所示：

各形状的变化如图所示（字母为方块编号）：

 障碍说明：

棋盘上仅有一处障碍无法放置方块，障碍可处于棋盘任意位置。障碍为基本形状a及其所有的旋转变化，如图所示：

输入输出要求：

输入文件名为testin.txt，格式如下所示，各数字用空格隔开，各数字表示棋盘格子编号。

2 3 22 23

该输入表示障碍位于棋盘的左上角。

输出文件名为testout.txt，要求先输出棋盘覆盖结果，再输出未覆盖的格子个数。输出棋盘用21行21列数字/字母表示，其中0表示未覆盖的格子，1表示障碍，字母表示对应方块编号（字母对应关系见“可选方块”一节）。最后输出未覆盖格子个数。这里以6行10列棋盘举例示意输出格式（注意：实际输出应该是21行21列，对应方块形状用对应的字母表示）：

要求：

1、  用所提供的方块尽可能覆盖棋盘并输出结果；

2、  在（1）的基础上，棋盘上的空格越少越好。

交付件要求：

C/C++：需要提交可执行文件和压缩打包的源代码工程

JAVA：需要提交压缩打包的整个编码工程目录

==============================================================
点此直接跳到最后的构造法及代码

一看题目，第一感觉是搜索空间有点大，第二感觉是说不定旋转对称性可以利用，不管了先给他搜上再说

慢吞吞地写完后，一运行，╮(╯_╰)╭ ………………加了记忆也没用

然后开始使用无脑流乱改，眼瞅着那个长条挺好用，给我把大片的空白全填了去！

填到只剩6行（考虑到unsigned long 是128位，6 * 21 =126正好小于128就留了6行），还是特别龟速

然后稍微注意了一下，用我的土算法，实际搜索范围在7x7的时候就很慢了，再往上肯定无理

所以要么换搜索算法，要么就把搜索范围进一步缩小。

之前产生用长条填的想法，是基于以前看的俄罗斯方块视频。那位神玩家基本可以在任何情况下都使用长条一次性消去三四行，所以我觉得这道题可以整行整行地填充以缩小搜索范围，而不至于太过影响最终结果。看来光是按行填还不够

算法方面暂时想不出什么办法了，我需要一个好的启发式搜索剪枝算法！但是想不出……先吃饭嗯。这黄瓜好辣

吃完饭，想想觉得有个不怎么靠谱的结果总比一万年也跑不出个结果要强，于是把原来的算法改成不可靠算法，遍历的次序随机化，也只按照一定概率进行回溯。这下结果总算是有了，还可以跑个几百次取最佳值，最佳结果一般在9到20之间浮动。我在想，一共21行，这样的话就是每行不超过一个空，这电脑已经能玩的比我还好了。但是毕竟是比赛口牙，时间也还有，就再努努力试试

于是视线重回搜索范围，在长条填充的想法上进一步深入，填到只剩一个很小的方形如何？毕竟之前测试发现小范围搜索下遗留的空位也都很少

先看地图大小，21x21，长条填充的话是4+4+4+4+4+1（竖着），所以要想填充完整，这个方形的尺寸只能是4的倍数或4的倍数+1

考虑到之前的7x7最大值，我选择5x5的方形尺寸。21-5=16，这样只要保证这个方形两边的余下的长度都能被4整除，就可以用长条完美覆盖了

而障碍物的尺寸是2x3，长度为2的那条边肯定能被起始位置为4的倍数、尺寸为5的方形装入。而长度为3的那条边讨论起来就有点麻烦了

稍微画了下图，发现用障碍物的左上角位置对4取模，余数为0、1、2都没问题，3的话就只有增加方形尺寸。于是在这种情况下，把方形尺寸加到8，依旧可以较为完整地用长条铺满，只不过需要补一个长条，损失一个无法填补的位置。5x8也小于7x7，性能也可以接受。

之后做了下实验，5x5的小方形里会留1个空，5x8的小方形里不会留空，但是5x8时外面填充会有一个空，这样两处加起来也正好是1个空，比之前的随机算法效果好多了

不过依旧是不完美算法OTL ，不知道该怎么证明子空间的最优性。再说满眼都是 f 这算什么嘛！也完全不能保证找到最优解。最优解我是无论如何也想不出的，只能再多查找资料、多积累了。

后记：

和罗同学讨论、阅读了宝贵的博客留言后，思路也稍微明晰一点了。首先21x21，最优解为遗留1个空，这个我就完全没有察觉到……太沉浸在性能测试上了，性能测试时使用的棋盘大小又不是21x21的

晚上回来重新debug，发现自己的算法还是勉强可以完成只遗留1个空的（通过枚举小方形，但依旧不知道怎么证明），但是比赛时提交的代码里有错误，横向的情况被我写反了（左右颠倒了OTL 都没有认真核对障碍的形状就交上去了），这样一来一半的测试用例肯定都通不过了

我的实力也就仅此而已了，愿这次的失败能让我沉淀得更深

============================================================================

这两天也和网友进行了讨论，还是构造法最高啊……

构造法说起来也很简单，首先利用对称性和可旋转性，将输入缩减为一种（这里都缩减为），之后对输入的位置进行考虑：
若位于左上角，则可以通过如下的方式填充：

剩余的空格就是左上的第一个格子，剩下的21x16区域用长条可以完美填充
（右下角也是完全一样）
若不位于左上角或右下角，则可通过加入两个L，变成或的4x3的障碍。将障碍体积变为4x3后，剩下的区域再用长条填充，可以保证填充至只剩1个格子（简单画画图就能发现了，不证明了）。
被别人一点拨，感觉真的是醍醐灌顶，如此简易的分析方法自己便就是做不到口牙……！
照着这个思路，自己也大致写了下代码：