# Resume 本小节主要总结一些**技术简历**相关的优质资源。具体的还可以参考前一节中 Facebook 提供的简历撰写指南，除了这些简短的资源外还强烈推荐下 Gayle 写的 *The Google Resume*，极其详细！干货超多！ ### Resume Template 推荐使用 Markdown 或者 Latex 撰写简历，可以使用 sharelatex 在线写简历，从 [CV or Resume](https://www.sharelatex.com/templates/cv-or-resume) 模板中挑，modernCV 的那些模板要写在一页里比较困难，这个 [Professional CV](https://www.sharelatex.com/templates/cv-or-resume/professional-cv) 相对紧凑一些，[LaTeX Templates » Curricula Vitae/Résumés](http://www.latextemplates.com/cat/curricula-vitae) 上还有更多更好的选择。另外推荐下自己写的一个还算简洁优雅的简历模板——[billryan/resume](https://github.com/billryan/resume), 同时支持中英文和 FontAwesome 字体，欢迎试用~ 中文的样式大概长成下面这个样子。  ### Reference - *The Google Resume* - 书名虽为简历，但本书可不只是教你写简历那么简单，除了教你如何写优秀简历外还总结了技术面试以及找工作过程中的方方面面。甚至连职业规划都有涉及！**力荐！** - [如何写好技术简历 —— 实例、模板及工具 | @Get社区](http://get.jobdeer.com/744.get) - 挺不错的技术简历实战。 - [精益技术简历之道——改善技术简历的47条原则 - Lucida](http://zh.lucida.me/blog/lean-technical-resume/) - 『Effective 简历』系列。 - [如何把简历写进一页 - V2EX](https://www.v2ex.com/t/175250) - 众人支招助萌妹纸优化简历。 - *Cracking the coding interview* 『写好简历』一节。

# Interview 本小节主要总结一些面试相关的优质资源。 ### Facebook workshop - Crush Your Coding Interview Facebook 每年的5月份左右会在中国大陆的清北复交浙等高校做技术讲座，基本模式是两到三个工程师进行现场分享，Frank 会着重介绍一些面试流程和简历撰写的细节，信息量非常大！其他几个工程师则是介绍自己在 Facebook 所做的产品和企业文化，全程约两个半小时，后面是 Q & A 环节，对提问者有各种小礼物送出。我会说我拿到了F的官方T恤了吗 :) 质地还不错，布料摸起来比较舒服，logo 也不太明显。强烈推荐在这五所高校附近的 CSer 们前去围观！本校的就更不要错过了啦~ 咳咳，进入正题，以下为自己对当晚 Facebook 工程师经验分享的一些总结，部分参考自浙大一位童鞋的总结[Facebook 交流](#)。 大致的 slides 如下，没有在网上找到公开的，以下是自己根据照片总结的。 ### Resume #### What to include on your resume 1. University, degree, expected graduation date - Highly recommended including GPA with scale/ranking 1. Projects - Industry experience (internships, competition, full-time) - Interesting projects - Links where applicable (github, apps, websites) 学校/学位/毕业时间(方便 HR 知道你何时毕业筛选简历)，GPA 最好能附上权重，不同的学校 GPA 总分不一样。 #### Writing a great resume 1. Focus on what you did 1. Focus on Impact(metrics and numbers are a plus) 1. Be specific and concise (1 page if at all possible) 1. Pro tip: alawys start with an active verb - example: built, optimized, improved, doubled, etc 1. Don't include - Age, photo, ID number 提供客观数据，具体且简短，多使用动词如『优化』、『提高』等，不要在简历中包含年龄，照片，ID 号，有些东西与法律相关。 ### Coding interview #### Goals of a coding interview Protip: Think out loud! 1. How you think and tackle technical problems 1. How you consider engineering trade offs (speed vs. time) 1. How you communicate in English about codes 1. Limits of what you know - Don't feel bad if you don't get all answers right #### What is covered? Use your comfortable coding language (C++ Java would be better) 之前听 Google 的工程师说是尽量使用 C++ 和 Java 实现。 1. Data structures and algorithms - implement, not memorize - discuss complexity (space and time trade-offs) - Common library functions are fair game 1. Specific questions about concepts are rare - Unless you claim to be an export or need the concept #### During the interview 1. Clarify your understanding - ask questions until you fully understand problem space and constraints - validate or state any assumptions - draw pictures to help you better understand problems 1. Focus on getting a working solution first - handle corner cases 1. Iterate 1. 举一两个例子，有可能的话还可以在白板上画出来帮助理解。问题的限制不是那么明确，确定和面试官理解的是同一个问题。 1. 尝试获得一个能工作的 code 1. 进行迭代，寻找更好的方法。记住测试自己的代码，选择简单但是典型的测试案例。 不要立即写代码，先明确思路，再写代码。Done is better than perfect 能否修改原数组，空间限制，时间限制。 大体方案要和面试官讨论。一定要和面试官多交流，思考过程和方法。 be yourself, 坦白地说出自己不懂的地方，没什么不好的，把知道的地方说清楚。 最近做的/最喜欢的/最具挑战性的项目是什么，不只是要把项目背景说出来，还要说出为什么喜欢，有哪些挑战，推理过程。 #### 项目讨论的框架 1. context: 简要描述项目背景，为什么要做，意义和影响何在。让面试官快速了解。 1. action: 你在这个项目中做了什么，贡献是什么。 1. result: 项目的结果，失败的项目也可以讲，在这个项目中学到了什么，得到了什么样的成长。 简历中提到的技术一定要熟悉。站在面试官的角度问自己会问自己什么问题。 面试之后，可以问面试官问题，着重问自己关心的问题。 ### behavior question 1. motivation：动机从何而来，整个过程中做了什么。 1. passion: 激情，哪种产品让你特别兴奋，为什么。 1. team pair: 团队合作? 这里忘了 1. disagreement: 怎么处理不同意见和冲突。 回答要具体，跟自己有关系，而不是泛泛而谈。 #### 总结 1. Think out loud, 不用担心自己的英语，把主要意思表达清楚就好了. 1. 面试中多问问题，充分理解题意。 1. 不要写 shit code, 提供典型案例测试自己的代码 1. 多练习，可以找几个小伙伴进行模拟面试，交换角色，在白板上多写代码。 1. 电话面试找一个安静的地方，把双手解放出来，便于写代码。 ### Reference 本小节部分摘自九章微信的分享。 - [www.geeksforgeeks.org](http://www.geeksforgeeks.org/) - 非常著名的漏题网站之一。上面会时不时的有各种公司的面试真题漏出。有一些题也会有解法分析。 - [Programming Interview Questions | CareerCup](http://www.careercup.com/) - CC150作者搞的网站，也是著名的漏题网站之一。大家会在上面讨论各个公司的面试题。 - [Glassdoor – Get Hired. Love Your Job.](http://www.glassdoor.com/index.htm) - 一个给公司打分的网站，类似yelp的公司版。会有一些人在上面讨论面试题，适合你在面某个公司的时候专门去看一下。 - [面经网 | 汇集热气腾腾的求职咨询](http://www.themianjing.com/) - 面经网。应该是个人经营的一个积累面经的网站。面经来源主要是一亩三分地，mitbbs之类的地方。 - [一亩三分地论坛-美国加拿大留学申请|工作就业|英语考试|学习生活信噪比最高的网站](http://www.1point3acres.com/bbs/) - 人气非常高的论坛。 - [待字闺中(JobHunting)版 | 未名空间(mitbbs.com)](http://www.mitbbs.com/bbsdoc/JobHunting.html) jobhunting版，美华人找工作必上。 - [程序员面试：电话面试问答Top 50 - 博客 - 伯乐在线](http://blog.jobbole.com/84618/) - 其实不仅仅只是 Top 50，扩展连接还给出了其他参考。 - [想加入硅谷顶级科技公司，你该知道这些](http://mp.weixin.qq.com/s?__biz=MzA4ODM1MTMzMQ==&mid=205185140&idx=2&sn=7682772b799b0542de2f1a5cd13ad292&scene=1#rd) - 数据工程师董飞的求职分享，涵盖硅谷公司的招聘流程，简历的书写，面试中的考察内容，选拔标准等。Evernote [备份链接](https://www.evernote.com/shard/s165/sh/4ef5916a-2db5-4d2e-b71b-68da38a92d41/cb6705242283b700) - [求职在美国，面试攻略我知道 on Vimeo](https://vimeo.com/113182965) - Coursera 数据工程师董飞的视频分享。 - Facebook 交流 > . [Facebook学长交流分享 - biaobiaoqi - 博客园](http://www.cnblogs.com/biaobiaoqi/p/3753750.html) > - Facebook 工程师的经验分享，Frank 对面试和简历部分的分享极其详细，信息量很大。 [ ↩](# "Jump back to footnote [Facebook 交流] in the text.")

# Appendix I Interview and Resume 本章主要总结一些技术面试和撰写简历方面的注意事项。

# Problem A. Farthest Point（圆周上最远整点） ### Source - [hihoCoder](http://hihocoder.com/contest/mstest2015sept2/problem/1) ### Problem 时间限制:5000ms 单点时限:1000ms 内存限制:256MB ### 描述 Given a circle on a two-dimentional plane. Output the **integral** point in or on the boundary of the circle which hasthe largest distance from the center. ### 输入 One line with three floats which are all accurate to three decimal places,indicating the coordinates of the center x, y and the radius r. For 80% of the data: |x|,|y|<=1000, 1<=r<=1000 For 100% of the data: |x|,|y|<=100000, 1<=r<=100000 ### 输出 One line with two integers separated by one space, indicating the answer. If there are multiple answers, print the one with the largest x-coordinate. If there are still multiple answers, print the one with the largesty-coordinate. #### 样例输入 ~~~ 1.000 1.000 5.000 ~~~ #### 样例输出 ~~~ 6 1 ~~~ ### 题解1 - 圆周枚举 其实自己最开始做这道题时用的就是枚举，但是似乎忘记加圆心坐标了，一直 WA... 题目要求是返回最大的 x, 所以我们首先根据半径范围将 x 的整数解范围求出来。然后求出可能的 y, 由于题中给出的解有3位小数，如果要精确求解的话，可以将圆方程两边同乘1000，然后判断是否为整数。 ### Java ~~~ import java.io.*; import java.util.*; import java.util.Queue; class Point { long x; long y; Point(long x, long y) { this.x = x; this.y = y; } } public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); double xd = in.nextDouble(), yd = in.nextDouble(), rd = in.nextDouble(); Point result = solve(xd, yd, rd); System.out.println(result.x + " " + result.y); } private static Point solve(double x0, double y0, double r) { // convert double to long(accurate) long xl0 = (long)(x0 * 1000), yl0 = (long)(y0 * 1000), rl0 = (long)(r * 1000); Point res = new Point(Long.MIN_VALUE, Long.MIN_VALUE); int lower_x = (int)Math.ceil(x0 - r), upper_x = (int)Math.floor(x0 + r); for (int i = upper_x; i >= lower_x; i--) { // circle above long y1l = yl0 + (long)(Math.sqrt(rl0*rl0 - (i*1000 - xl0)*(i*1000 - xl0)) + 0.5); if ((i*1000 - xl0)*(i*1000 - xl0) + (y1l - yl0)*(y1l - yl0) == rl0*rl0) { // ensure y1 is integer if (y1l % 1000 == 0) { res.x = i; res.y = y1l / 1000; return res; } } // circle below y1l = yl0 - (long)(Math.sqrt(rl0*rl0 - (i*1000 - xl0)*(i*1000 - xl0)) + 0.5); if ((i*1000 - xl0)*(i*1000 - xl0) + (y1l - yl0)*(y1l - yl0) == rl0*rl0) { // ensure y1 is integer if (y1l % 1000 == 0) { res.x = i; res.y = y1l / 1000; return res; } } } return res; } } ~~~ ### 源码分析 自右向左枚举，先枚举圆的上半部分，再枚举圆的下半部分。注意1000的转换。 ### 复杂度分析 最坏情况下 O(R)O(R)O(R). ### 题解2 - 整数分解 看似容易实则比较难的一道题，现场通过率非常低。我们仔细审下题，求圆周上的整点，有多个整点时输出最大的 x 和最大的 y. 容易想到的方案是枚举所有可能的 x 和 y, 然后代入等式测试是否相等，这个过不了大的 x 和 y. 如果用开方的方法必然有误差，我用这种方法不知道贡献了多少 WA, 泪流满面... 作为在线测试，**更为合理的方案应为先暴力搜索拿到百分之八十的分数。** 从 Microsoft 和 Google APAC 在线测试的风格来看是偏向于程序设计竞赛的，那么题目的考点自然就在竞赛范围之内，这道题看似是浮点型的数据，~~实际上考的却是整数中数论的基础。~~**注意题中的 accurate to three decimal places, 那么也就意味着我们对给定的数据同乘 10310^3103 后一定是整数！！**！这个关键的信息我在测试过程中也没注意到，直到第二天早上醒来后突然就想到了！兴奋地六点多就爬起来了。 首先肯定是要写出圆方程的，设圆心坐标为 (x0,y0)(x_0, y_0)(x0,y0), 半径为 rrr, 那么我们有：(x−x0)2+(y−y0)2=r2(x - x_0)^2 + (y - y_0)^2 = r^2(x−x0)2+(y−y0)2=r2 设 m=103(x−x0)m = 10^3(x - x_0)m=103(x−x0), n=103(y−y0)n = 10^3(y - y_0)n=103(y−y0), R=103rR = 10^3rR=103r, 那么我们有新的圆方程：m2+n2=R2m^2 + n^2 = R^2m2+n2=R2其中 `m, n, R` 均为整数。接下来我们看看给出的数据范围，x, y, r 均是 10610^6106 以内，那么圆方程两边同乘 10610^6106 （括号内的数即乘上 10310^3103）后数据在 101810^{18}1018 以内。我们来估算下整数的范围，210≈1032^{10} \approx 10^3210≈103, Java 中 int 型为4个字节，最大为 231−1≈2⋅1092^{31} - 1 \approx 2 \cdot 10^9231−1≈2⋅109, long 型为8个字节，最大为 263−1≈23⋅10182^{63} - 1 \approx 2^3 \cdot 10^{18}263−1≈23⋅1018, 估算下来应该选用 long 保存 m, n, R. 接下来就是数论部分的推导了，先来一个简单的推导，勾股数部分的推导不直观。首先从已知部分出发，已知的只有勾股数方程和 m, n 均是整数，那么接下来肯定是要利用整数的理论无疑了。我们首先对以上圆方程移项开方，考虑到圆的对称性，我们其实只需要考虑圆的八分之一即可。这里考虑`0 < m < r`部分，`m == 0`表示在点在轴上，最后单独加上。 m=R2−n2=(R+n)(R−n)m = \sqrt{R^2 - n^2} = \sqrt{(R + n)(R - n)}m=√R2−n2=√(R+n)(R−n)由于 m 一定是整数，故根号内一定为完全平方数，由于排除了轴上的点，那么`-R < n < R`, 设`G = gcd(R + n, R - n)`, p2=(R+n)/Gp^2 = (R + n) / Gp2=(R+n)/G, q2=(R−n)/Gq^2 = (R - n) / Gq2=(R−n)/G, 于是我们有`m = Gpq`, `p > q`, 由于`G` 是`R + n` 和`R - n` 的最大公约数，故`p` 和`q`一定互质，且有：p2+q2=2R/Gp^2 + q^2 = 2R / Gp2+q2=2R/G由于`p`,`q` 都大于等于1，那么我们能推断出`G` 一定是 `2R` 的约数！根据约数(素数)部分的基础理论，我们可以在 O(2R)O(\sqrt{2R})O(√2R) 时间内找出所有约数。然后对以上等式进行缩放得到`p` 的范围，枚举求解，判断`p^2` 和`q^2` 是否互质(最大公约数是否为1)。 ### Java ~~~ import java.io.*; import java.util.*; class Point { long x; long y; Point(long x, long y) { this.x = x; this.y = y; } } public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); double xd = in.nextDouble(), yd = in.nextDouble(), rd = in.nextDouble(); // convert double to long(accurate) long x0 = (long)(xd * 1000), y0 = (long)(yd * 1000), r0 = (long)(rd * 1000); Point result = solve(x0, y0, r0); System.out.println(result.x + " " + result.y); } private static Point solve(long x0, long y0, long r) { Point res = new Point(Long.MIN_VALUE, Long.MIN_VALUE); long x_max = Long.MIN_VALUE, y_max = Long.MIN_VALUE; // p^2 + q^2 = 2R/divisor, p > q >= 1 // 1 <= q^2 < R/G < p^2 < 2R/G ==> p >= 2 List divisors = getDivisor(r << 1); for (long divisor : divisors) { long lower = Math.max(2, (long)Math.sqrt(r * 1.0/ divisor)); // long upper = (long)Math.sqrt(2.0 * r / divisor); for (long p = lower; p * p <= 2 * r / divisor; p++) { long q = (long)Math.sqrt(2.0 * r / divisor - p * p); // check if q is integer if (p * p + q * q != 2 * r / divisor) continue; // ensure p^2 and q^2 have no common divisor if (gcd(p * p, q * q) == 1) { long m = divisor * p * q; long n = r - p * p * divisor; List points = new ArrayList(); points.add(new Point(m + x0, n + y0)); points.add(new Point(m + x0, -1 * n + y0)); points.add(new Point(-1 * m + x0, n + y0)); points.add(new Point(-1 * m + x0, -1 * n + y0)); for (Point point : points) { updateAns(point, res); } } } } // axis point check List axis = new ArrayList(); axis.add(new Point(x0 + r, y0)); axis.add(new Point(x0 - r, y0)); axis.add(new Point(x0, y0 + r)); axis.add(new Point(x0, y0 - r)); for (Point point : axis) { updateAns(point, res); } // divide by 1000 res.x /= 1000; res.y /= 1000; return res; } public static void updateAns(Point p, Point res) { // point(x, y) in integer if ((p.x % 1000 == 0) && (p.y % 1000 == 0)) { if (p.x > res.x) { res.x = p.x; res.y = p.y; } else if (p.x == res.x && p.y > res.y) { res.y = p.y; } } } // enumerate all the divisor for n public static List getDivisor(long n) { List result = new ArrayList(); for (long i = 1; i * i <= n; i++) { if (n % i == 0) { result.add(i); // i * i <= n ==> i <= n / i if (i != n / i) result.add(n / i); } } Collections.sort(result); return result; } public static long gcd(long a, long b) { return (b == 0L) ? a : gcd(b, a % b); } } ~~~ ### 源码分析 由于更新结果的操作非常频繁，单独写一个方法较好。 ### 复杂度分析 求所有素数时间复杂度 O(n)O(\sqrt{n})O(√n), 判断是否互质时间复杂度 O(logn)O(\log n)O(logn). 枚举最大公约数时间复杂度约 (n)(\sqrt{n})(√n)，总的时间复杂度估算应该比 O(n)O(n)O(n) 小一些，但是小的不明显。**所以说，这种方法费了老大劲，但是吃力不讨好！笔试中这种方法极不可取！** ### 题解3 - 勾股数 除了以上使用数论部分整数分解的方法外，还可以巧用勾股数的特性，这种方法需要熟知勾股数的特性。设正整数 m,n,rm, n, rm,n,r 满足：m2+n2=r2m^2 + n^2 = r^2m2+n2=r2我们对上式两边进行平方可得：(m2−n2)2+(2mn)2=(m2+n2)2=(r2)2(m^2 - n^2)^2 + (2mn)^2 = (m^2 + n^2)^2 = (r^2)^2(m2−n2)2+(2mn)2=(m2+n2)2=(r2)2令 a=m2−n2a = m^2 - n^2a=m2−n2, b=2mnb = 2mnb=2mn, c=m2+n2c = m^2 + n^2c=m2+n2. 容易得到：a2+b2=c2a^2 + b^2 = c^2a2+b2=c2注意到上述推导可逆，那么也就是说只要我们找到正整数满足`m > n`就能找到所有可能的勾股数。且根据素勾股数的特性，`m`, `n` 为一奇一偶，不妨设其为`2k-1`, `2k`. 代入`c`中可知`c`为`4K + 1`. 即`c % 4 = 1`. 根据 [Tree of primitive Pythagorean triples](https://en.wikipedia.org/wiki/Tree_of_primitive_Pythagorean_triples) 中提到的方法，我们只需找出小于给定的`r`的素勾股数即可，然后判断是否能整除`r`. ### Java ~~~ import java.io.*; import java.util.*; import java.util.Queue; class Point { long x; long y; Point(long x, long y) { this.x = x; this.y = y; } } class Pythagorean { long x; long y; long z; Pythagorean(long x, long y, long z) { this.x = x; this.y = y; this.z = z; } } public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); double xd = in.nextDouble(), yd = in.nextDouble(), rd = in.nextDouble(); // convert double to long(accurate) long x0 = (long)(xd * 1000), y0 = (long)(yd * 1000), r0 = (long)(rd * 1000); Point result = solve(x0, y0, r0); System.out.println(result.x + " " + result.y); } private static Point solve(long x0, long y0, long r) { Point res = new Point(Long.MIN_VALUE, Long.MIN_VALUE); long x_max = Long.MIN_VALUE, y_max = Long.MIN_VALUE; // init Pythagorean pyth0 = new Pythagorean(3, 4, 5); Queue q = new LinkedList(); q.offer(pyth0); boolean update = true; while (!q.isEmpty()) { int qSize = q.size(); for (int i = 0; i < qSize; i++) { Pythagorean pyth = q.poll(); if ((r % pyth.z) == 0) { // System.out.println("x = " + pyth.x + ", y = " + pyth.y + ", r = " + pyth.z); long k = r / pyth.z; long kx = k * pyth.x; long ky = k * pyth.y; List points = new ArrayList(); points.add(new Point(x0 + kx, y0 + ky)); points.add(new Point(x0 - kx, y0 + ky)); points.add(new Point(x0 + kx, y0 - ky)); points.add(new Point(x0 - kx, y0 - ky)); if (kx != ky) { points.add(new Point(y0 + ky, x0 + kx)); points.add(new Point(y0 - ky, x0 + kx)); points.add(new Point(y0 + ky, x0 - kx)); points.add(new Point(y0 - ky, x0 - kx)); } for (Point point : points) { updateAns(point, res); } } // add next level Pythagorean for (Pythagorean p : nextPyths(pyth)) { if (p.z > r) continue; q.offer(p); } } } // axis point check List axis = new ArrayList(); axis.add(new Point(x0 + r, y0)); axis.add(new Point(x0 - r, y0)); axis.add(new Point(x0, y0 + r)); axis.add(new Point(x0, y0 - r)); for (Point point : axis) { updateAns(point, res); } // divide by 1000 res.x /= 1000; res.y /= 1000; return res; } public static List nextPyths(Pythagorean pyth) { List pyths = new ArrayList(); // method 1 Pythagorean pyth1 = new Pythagorean(0, 0, 0); pyth1.x = pyth.x - 2 * pyth.y + 2 * pyth.z; pyth1.y = 2 * pyth.x - 1 * pyth.y + 2 * pyth.z; pyth1.z = 2 * pyth.x - 2 * pyth.y + 3 * pyth.z; pyths.add(pyth1); // method 2 Pythagorean pyth2 = new Pythagorean(0, 0, 0); pyth2.x = pyth.x + 2 * pyth.y + 2 * pyth.z; pyth2.y = 2 * pyth.x + 1 * pyth.y + 2 * pyth.z; pyth2.z = 2 * pyth.x + 2 * pyth.y + 3 * pyth.z; pyths.add(pyth2); // method 3 Pythagorean pyth3 = new Pythagorean(0, 0, 0); pyth3.x = -1 * pyth.x + 2 * pyth.y + 2 * pyth.z; pyth3.y = -2 * pyth.x + pyth.y + 2 * pyth.z; pyth3.z = -2 * pyth.x + 2 * pyth.y + 3 * pyth.z; pyths.add(pyth3); return pyths; } public static void updateAns(Point p, Point res) { // point(x, y) in integer if ((p.x % 1000 == 0) && (p.y % 1000 == 0)) { if (p.x > res.x) { res.x = p.x; res.y = p.y; } else if (p.x == res.x && p.y > res.y) { res.y = p.y; } } } } ~~~ ### 源码分析 根据链接中提到的数据结构，使用队列按层次遍历较好，但是空间消耗较大，所以在入队时一定要剪枝。 ### 复杂度分析 时间复杂度最坏情况下需要遍历所有可能素勾股数。空间复杂度消耗也比较客观... ### Reference - [BZOJ 1041 [HAOI2008] 圆上的整点 题解与分析 - 初学者 - 博客频道 - CSDN.NET](http://blog.csdn.net/csyzcyj/article/details/10044629) - [[BZOJ1041 [HAOI2008]圆上的整点]数论、勾股数相关定理 | edward_mj](http://edward-mj.com/archives/166) - [勾股数 - 维基百科，自由的百科全书](https://zh.wikipedia.org/wiki/%E5%8B%BE%E8%82%A1%E6%95%B0) - [hihoCoder](http://hihocoder.com/discuss/question/2619)

# Microsoft 2015 September 2 本小节总结 Microsoft 2015年九月第一次大规模校招的题，题目列表见 [hihoCoder](http://hihocoder.com/contest/mstest2015sept2/problems). 这一场的题目感觉偏难。

# Problem C. Spring Outing ### Source - [hihoCoder](http://hihocoder.com/contest/mstest2015april2/problem/3) ### Problem 鏃堕棿闄愬埗:20000ms 鍗曠偣鏃堕檺:1000ms 鍐呭瓨闄愬埗:256MB ### 鎻忚堪 You class are planning for a spring outing. N people are voting for adestination out of K candidate places. The voting progress is below: First the class vote for the first candidate place. If more than half of theclass agreed on the place, the place is selected. The voting ends. Otherwise they vote for the second candidate place. If more than half of theclass agreed on the place, the place is selected. The voting ends. Otherwise they vote for the third candidate place in the same way and go on. If no place is selected at last there will be no spring outing and everybodystays at home. Before the voting, the Chief Entertainment Officer did a survey, found outevery one's preference which can be represented as a permutation of 0, 1, ...K. (0 is for staying at home.) For example, when K=3, preference "1, 0, 2, 3"means that the first place is his first choice, staying at home is the secondchoice, the second place is the third choice and the third place is the lastchoice. The Chief Entertainment Officer sends the survey results to the class. Soeverybody knows the others' preferences. Everybody wants his more preferedplace to be selected. And they are very smart, they always choose the optimalstrategy in the voting progress to achieve his goal. Can you predict which place will be selected? ### 杈撳叆 The first line contains two integers, N and K, the number of people in yourclass and the number of candidate places. The next N lines each contain a permutation of 0~K, representing someone'spreference. For 40% of the data, 1 <= N, K <= 10 For 100% of the data, 1 <= N, K <= 1000 ### 杈撳嚭 Output the selected place. Or "otaku" without quotes if no place is selected. ### 鏍蜂緥鎻愮ず In the sample case, if the second peoson vote against the first place, noplace would be selected finally because the first person must vote against thesecond place for his own interest. Considering staying at home is a worsechoice than the first place, the second person's optimal strategy is votingfor the first place. So the first place will be selected. 鏍蜂緥杈撳叆 ~~~ 2 2 1 0 2 2 1 0 ~~~ 鏍蜂緥杈撳嚭 ~~~ 1 ~~~

# Problem B. Numeric Keypad ### Source - [hihoCoder](http://hihocoder.com/contest/mstest2015april2/problem/2) ### Problem 鏃堕棿闄愬埗:10000ms 鍗曠偣鏃堕檺:1000ms 鍐呭瓨闄愬埗:256MB ### 鎻忚堪 The numberic keypad on your mobile phone looks like below: ~~~ 1 2 3 4 5 6 7 8 9 0 ~~~ Suppose you are holding your mobile phone with single hand. Your thumb pointsat digit 1. Each time you can 1) press the digit your thumb pointing at, 2)move your thumb right, 3) move your thumb down. Moving your thumb left or upis not allowed. By using the numeric keypad under above constrains, you can produce somenumbers like 177 or 480 while producing other numbers like 590 or 52 isimpossible. Given a number K, find out the maximum number less than or equal to K that canbe produced. ### 杈撳叆 The first line contains an integer T, the number of testcases. Each testcase occupies a single line with an integer K. For 50% of the data, 1 <= K <= 999. For 100% of the data, 1 <= K <= 10500, t <= 20. ### 杈撳嚭 For each testcase output one line, the maximum number less than or equal tothe corresponding K that can be produced. 鏍蜂緥杈撳叆 ~~~ 3 25 83 131 ~~~ 鏍蜂緥杈撳嚭 ~~~ 25 80 129 ~~~

# Problem A. Lucky Substrings ### Source - [hihoCoder](http://hihocoder.com/problemset/problem/1152) ### Problem 时间限制:10000ms 单点时限:1000ms 内存限制:256MB ### 描述 A string s is **LUCKY** if and only if the number of different characters in sis a [fibonacci number](http://en.wikipedia.org/wiki/Fibonacci_number). Givena string consisting of only lower case letters, output all its lucky non-emptysubstrings in lexicographical order. Same substrings should be printed once. ### 输入 A string consisting no more than 100 lower case letters. ### 输出 Output the lucky substrings in lexicographical order, one per line. Samesubstrings should be printed once. 样例输入 ~~~ aabcd ~~~ 样例输出 ~~~ a aa aab aabc ab abc b bc bcd c cd d ~~~ ### 题解 简单实现题，即判断 substring 中不同字符串的个数是否为 fibonacci 数，最后以字典序方式输出，且输出的字符串中相同的只输出一次。分析下来需要做如下几件事： 1. 两重 for 循环取输入字符串的所有可能子串。 1. 判断子串中不同字符的数目，这里使用可以去重的数据结构`Set`比较合适，最后输出`Set`的大小即为不同字符的数目。 1. 判断不同字符数是否为 fibonacci 数，由于子串数目较多，故 fibonacci 应该首先生成，由于字符串输入最大长度为100，故使用哈希表这种查询时间复杂度为 O(1)O(1)O(1) 的数据结构。 1. 将符合条件的子串加入到最终结果，由于结果需要去重，故选用`Set`数据结构。 ### Java ~~~ import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); String input = in.nextLine(); Set result = solve(input); for (String s : result) { System.out.println(s); } } public static Set solve(String input) { Set fibonacci = fibonacci_number(input.length()); Set res = new TreeSet(); for (int i = 0; i < input.length(); i++) { for (int j = i + 1; j <= input.length(); j++) { String substr = input.substring(i, j); if (isFibonacci(substr, fibonacci)) { res.add(substr); } } } return res; } public static boolean isFibonacci(String s, Set fibo) { Set charSet = new HashSet(); for (Character c : s.toCharArray()) { charSet.add(c); } // convert charSet.size() to long if (fibo.contains((long)charSet.size())) { return true; } else { return false; } } public static Set fibonacci_number(int n) { // generate fibonacci number till n Set fibonacci = new HashSet(); long fn2 = 1, fn1 = 1, fn = 1; fibonacci.add(fn); for (int i = 3; i <= n; i++) { fn = fn1 + fn2; fibonacci.add(fn); fn2 = fn1; fn1 = fn; } return fibonacci; } } ~~~ ### 源码分析 fibonacci 数组的生成使用迭代的方式，由于保存的是`Long`类型，故在判断子串 size 时需要将 size 转换为`long`. Java 中常用的 Set 有两种，无序的`HashSet`和有序的`TreeSet`. ### 复杂度分析 遍历所有可能子串，时间复杂度 O(n2)O(n^2)O(n2), fibonacci 数组和临时子串，空间复杂度 O(n)O(n)O(n).

# Microsoft 2015 April 2 本小节总结 Microsoft 2015年四月第二次招实习生的题，题目列表见 [hihoCoder](http://hihocoder.com/contest/mstest2015april2/problems).

# Problem D. Recruitment ### Source - [hihoCoder](http://hihocoder.com/contest/mstest2015april/problem/4) ### Problem 鏃堕棿闄愬埗:10000ms 鍗曠偣鏃堕檺:1000ms 鍐呭瓨闄愬埗:256MB ### 鎻忚堪 A company plans to recruit some new employees. There are N candidates (indexedfrom 1 to N) have taken the recruitment examination. After the examination,the well-estimated ability value as well as the expected salary per year ofeach candidate is collected by the Human Resource Department. Now the company need to choose their new employees according to these data. Tomaximize the company's benefits, some principles should be followed: 1. There should be exactly X males and Y females. 2. The sum of salaries per year of the chosen candidates should not exceedthe given budget B. 3. The sum of ability values of the chosen candidates should be maximum,without breaking the previous principles. Based on this, the sum of the salaryper year should be minimum. 4. If there are multiple answers, choose the lexicographically smallest one.In other words, you should minimize the smallest index of the chosencandidates; If there are still multiple answers, then minimize the secondsmallest index; If still multiple answers, then minimize the third smallestone; ... Your task is to help the company choose the new employees from thosecandidates. ### 杈撳叆 The first line contains four integers N, X, Y, and B, separated by a singlespace. The meanings of all these variables are showed in the descriptionabove. 1 <= N <= 100, 0 <= X <= N, 0 <= Y <= N, 1 <= X +Y <= N, 1 <= B <= 1000. Then follows N lines. The i-th line contains the data of the i-th candidate: acharacter G, and two integers V and S, separated by a single space. Gindicates the gender (either "M" for male, or "F" for female), V is the well-estimated ability value and S is the expected salary per year of thiscandidate. 1 <= V <= 10000, 0 <= S <= 10. We assure that there is always at least one possible answer. ### 杈撳嚭 On the first line, output the sum of ability values and the sum of salariesper year of the chosen candidates, separated by a single space. On the second line, output the indexes of the chosen candidates in ascendingorder, separated by a single space. 鏍蜂緥杈撳叆 ~~~ 4 1 1 10 F 2 3 M 7 6 M 3 2 F 9 9 ~~~ 鏍蜂緥杈撳嚭 ~~~ 9 9 1 2 ~~~

# Problem C. Islands Travel ### Source - [hihoCoder](http://hihocoder.com/contest/mstest2015april/problem/3) ### Problem 时间限制:10000ms 单点时限:1000ms 内存限制:256MB ### 描述 There are N islands on a planet whose coordinates are (X1, Y1), (X2, Y2), (X3,Y3) ..., (XN, YN). You starts at the 1st island (X1, Y1) and your destinationis the n-th island (XN, YN). Travelling between i-th and j-th islands willcost you min{|Xi-Xj|, |Yi-Yj|} (|a| denotes the absolute value of a. min{a, b}denotes the smaller value between a and b) gold coins. You want to know whatis the minimum cost to travel from the 1st island to the n-th island. ### 输入 Line 1: an integer N. Line 2~N+1: each line contains two integers Xi and Yi. For 40% data, N<=1000，0<=Xi,Yi<=100000. For 100% data, N<=100000，0<=Xi,Yi<=1000000000. ### 输出 Output the minimum cost. 样例输入 ~~~ 3 2 2 1 7 7 6 ~~~ 样例输出 ~~~ 2 ~~~

# Problem B. Professor Q's Software ### Source - [hihoCoder](http://hihocoder.com/contest/mstest2015april/problem/2) ### Problem 鏃堕棿闄愬埗:10000ms 鍗曠偣鏃堕檺:1000ms 鍐呭瓨闄愬埗:256MB ### 鎻忚堪 Professor Q develops a new software. The software consists of N modules whichare numbered from 1 to N. The i-th module will be started up by signal Si. Ifsignal Si is generated multiple times, the i-th module will also be startedmultiple times. Two different modules may be started up by the same signal.During its lifecircle, the i-th module will generate Ki signals: E1, E2, ...,EKi. These signals may start up other modules and so on. Fortunately thesoftware is so carefully designed that **there is no loop in the startingchain of modules**, which means eventually all the modules will be stoped.Professor Q generates some initial signals and want to know how many timeseach module is started.  ### 杈撳叆 The first line contains an integer T, the number of test cases. T test casesfollows. For each test case, the first line contains contains two numbers N and M,indicating the number of modules and number of signals that Professor Qgenerates initially. The second line contains M integers, indicating the signals that Professor Qgenerates initially. Line 3~N + 2, each line describes an module, following the format S, K, E1,E2, ... , EK. S represents the signal that start up this module. K representsthe total amount of signals that are generated during the lifecircle of thismodule. And E1 ... EK are these signals. For 20% data, all N, M <= 10For 40% data, all N, M <= 103For 100% data, all 1 <= T <= 5, N, M <= 105, 0 <= K <= 3, 0<= S, E <= 105. **Hint: HUGE input in this problem. Fast IO such as scanf and BufferedReader are recommended.** ### 杈撳嚭 For each test case, output a line with N numbers Ans1, Ans2, ... , AnsN. Ansiis the number of times that the i-th module is started. In case the answersmay be too large, output the answers modulo 142857 (the remainder of divisionby 142857). 鏍蜂緥杈撳叆 ~~~ 3 3 2 123 256 123 2 456 256 456 3 666 111 256 256 1 90 3 1 100 100 2 200 200 200 1 300 200 0 5 1 1 1 2 2 3 2 2 3 4 3 2 4 5 4 2 5 6 5 2 6 7 ~~~ 鏍蜂緥杈撳嚭 ~~~ 1 1 3 1 2 2 1 1 2 3 5 ~~~

# Problem A. Magic Box ### Source - [hihoCoder](http://hihocoder.com/contest/mstest2015april/problem/1) ### Problem 鏃堕棿闄愬埗:10000ms 鍗曠偣鏃堕檺:1000ms 鍐呭瓨闄愬埗:256MB ### 鎻忚堪 The circus clown Sunny has a magic box. When the circus is performing, Sunnyputs some balls into the box one by one. The balls are in three colors:red(R), yellow(Y) and blue(B). Let Cr, Cy, Cb denote the numbers of red,yellow, blue balls in the box. Whenever the differences among Cr, Cy, Cbhappen to be x, y, z, all balls in the box vanish. Given x, y, z and thesequence in which Sunny put the balls, you are to find what is the maximumnumber of balls in the box **ever**. For example, let's assume x=1, y=2, z=3 and the sequence is RRYBRBRYBRY. AfterSunny puts the first 7 balls, RRYBRBR, into the box, Cr, Cy, Cb are 4, 1, 2respectively. The differences are exactly 1, 2, 3. (|Cr-Cy|=3, |Cy-Cb|=1, |Cb-Cr|=2) Then all the 7 balls vanish. Finally there are 4 balls in the box,after Sunny puts the remaining balls. So the box contains 7 balls at most,after Sunny puts the first 7 balls and before they vanish. #### 杈撳叆 Line 1: x y z Line 2: the sequence consisting of only three characters 'R', 'Y' and 'B'. For 30% data, the length of the sequence is no more than 200. For 100% data, the length of the sequence is no more than 20,000, 0 <= x,y, z <= 20. ### 杈撳嚭 The maximum number of balls in the box **ever**. ### 鎻愮ず Another Sample | Sample Input | Sample Output | |-----|-----| | (0 0 0)RBYRRBY | 4 | 鏍蜂緥杈撳叆 ~~~ 1 2 3 RRYBRBRYBRY ~~~ 鏍蜂緥杈撳嚭 ~~~ 7 ~~~

# Microsoft 2015 April 本小节总结 Microsoft 2015年四月第一次招实习生的题，题目列表见 [hihoCoder](http://hihocoder.com/contest/mstest2015april/problems).

# Microsoft 本章总结 Microsoft 校招的一些题。

# Problem A. Password Attacker ### Source - [Dashboard - Round B APAC Test - Problem A. Password Attacker](https://code.google.com/codejam/contest/4214486/dashboard#s=p0) ### Problem Passwords are widely used in our lives: for ATMs, online forum logins, mobile device unlock and door access. Everyone cares about password security. However, attackers always find ways to steal our passwords. Here is one possible situation: Assume that Eve, the attacker, wants to steal a password from the victim Alice. Eve cleans up the keyboard beforehand. After Alice types the password and leaves, Eve collects the fingerprints on the keyboard. Now she knows which keys are used in the password. However, Eve won't know how many times each key has been pressed or the order of the keystroke sequence. To simplify the problem, let's assume that Eve finds Alice's fingerprints only occurs on M keys. And she knows, by another method, that Alice's password contains N characters. Furthermore, every keystroke on the keyboard only generates a single, unique character. Also, Alice won't press other irrelevant keys like 'left', 'home', 'backspace' and etc. Here's an example. Assume that Eve finds Alice's fingerprints on M=3 key '3', '7' and '5', and she knows that Alice's password is N=4-digit in length. So all the following passwords are possible: 3577, 3557, 7353 and 5735. (And, in fact, there are 32 more possible passwords.) However, these passwords are not possible: ~~~ 1357 // There is no fingerprint on key '1' 3355 // There is fingerprint on key '7', so '7' must occur at least once. 357 // Eve knows the password must be a 4-digit number. ~~~ With the information, please count that how many possible passwords satisfy the statements above. Since the result could be large, please output the answer modulo 1000000007(109+7). #### Input The first line of the input gives the number of test cases, T.For the next T lines, each contains two space-separated numbers M and N, indicating a test case. #### Output For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the total number of possible passwords modulo 1000000007(109+7). #### Limits **Small dataset** T = 15.1 ≤ M ≤ N ≤ 7. **Large dataset** T = 100.1 ≤ M ≤ N ≤ 100. #### Smaple ~~~ Input Output 4 1 1 Case #1: 1 3 4 Case #2: 36 5 5 Case #3: 120 15 15 Case #4: 674358851 ~~~ ### 题解 题目看似很长，其实简单来讲就是用 M 个 不同的字符组成长度为 N 的字符串，问有多少种不同的排列。这里 M 小于 N，要是大于的话就是纯排列了。这道题我最开始想用纯数学方法推导公式一步到位，实践下来发现这种想法真是太天真了，这不是数学竞赛... 即使用推导也应该是推导类似动态规划的状态转移方程。 这里的动态规划不太明显，我们以状态`dp[m][n]`表示用 m 个不同的字符能组成长度为 n 的不同字符串的个数。这里需要注意的是最后长度为 n 的字符串中必须包含 m 个不同的字符，不多也不少。接下来就是寻找状态转移方程了，之前可能的状态为`dp[m - 1][n -1], dp[m - 1][n], dp[m][n - 1]`. 现在问题来了，怎么解释这些状态以寻找状态转移方程？常规方法为正向分析，即分析`m ==> n`, 但很快我们可以发现`dp[m - 1][n]`这个状态很难处理。既然正向分析比较麻烦，我们不妨试试反向从`n ==> m`分析，可以发现字符串个数由 n 变为 n-1，这减少的字符可以分为两种情况，一种是这个减少的字符就在前 n - 1个字符中，另一种则不在，如此一来便做到了不重不漏。相应的状态转移方程为： ~~~ dp[i][j] = dp[m][n-1] * m + dp[m - 1][n - 1] * m ~~~ 第一种和第二种情况下字符串的第 n 位均可由 m 个字符中的一个填充。初始化分两种情况，第一种为索引为0时，其值显然为0；第二种则是 m 为1时，容易知道相应的排列为1。最后返回 `dp[M][N]`. ### Java ~~~ import java.util.*; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int T = in.nextInt(); // System.out.println("T = " + T); for (int t = 1; t <= T; t++) { int M = in.nextInt(), N = in.nextInt(); long ans = solve(M, N); // System.out.printf("M = %d, N = %d\n", M, N); System.out.printf("Case #%d: %d\n", t, ans); } } public static long solve(int M, int N) { long[][] dp = new long[1 + M][1 + N]; long mod = 1000000007; for (int j = 1; j <= N; j++) { dp[1][j] = 1; } for (int i = 2; i <= M; i++) { for (int j = i; j <= N; j++) { dp[i][j] = i * (dp[i][j - 1] + dp[i - 1][j - 1]); dp[i][j] %= mod; } } return dp[M][N]; } } ~~~ ### 源码分析 Google Code Jam 上都是自己下载输入文件，上传结果，这里我们使用输入输出重定向的方法解决这个问题。举个例子，将这段代码保存为`Solution.java`, 将标准输入重定向至输入文件，标准输出重定向至输出文件。编译好之后以如下方式运行： ~~~ java Solution < A-large-practice.in > A-large-practice.out ~~~ 这种方式处理各种不同 OJ 平台的输入输出较为方便。 ### 复杂度分析 时间复杂度 O(mn)O(mn)O(mn), 空间复杂度 O(mn)O(mn)O(mn). ### Reference - [Google-APAC2015-"Password Attacker" - dmsehuang的专栏](http://blog.csdn.net/dmsehuang/article/details/40807799)

# APAC 2015 Round B - [Dashboard - Round B APAC Test - Google Code Jam](https://code.google.com/codejam/contest/4214486/dashboard)

# Google APAC 本章总结 Google APAC 的一些题。

# Part III - Contest 本节主要总结一些如 Google APAC, Microsoft 校招等在线测试的题。

# Longest Consecutive Sequence ### Source - leetcode: [Longest Consecutive Sequence | LeetCode OJ](https://leetcode.com/problems/longest-consecutive-sequence/) - lintcode: [(124) Longest Consecutive Sequence](http://www.lintcode.com/en/problem/longest-consecutive-sequence/) ### Problem Given an unsorted array of integers, find the length of the longestconsecutive elements sequence. #### Example Given `[100, 4, 200, 1, 3, 2]`,The longest consecutive elements sequence is `[1, 2, 3, 4]`. Return itslength: `4`. #### Clarification Your algorithm should run in O(*n*) complexity. ### 题解 首先看题要求，时间复杂度为 O(n)O(n)O(n), 如果排序，基于比较的实现为 nlognn \log nnlogn, 基数排序需要数据有特征。故排序无法达到复杂度要求。接下来可以联想空间换时间的做法，其中以哈希表为代表。这个题要求返回最长连续序列，不要求有序，非常符合哈希表的用法。**由于给定一个数其连续的数要么比它小1，要么大1，那么我们只需往左往右搜索知道在数组中找不到数为止。**结合哈希表查找为 O(1)O(1)O(1) 的特性即可满足要求。 ### Java ~~~ public class Solution { /** * @param nums: A list of integers * @return an integer */ public int longestConsecutive(int[] num) { if (num == null || num.length == 0) return 0; // add number to hashset Set hashset = new HashSet(); for (int n : num) { hashset.add(n); } int lcs = 0; for (int n : num) { int i = n, count = 1; hashset.remove(n); // i-- while (hashset.contains(--i)) { count++; hashset.remove(i); } // i++ i = n; while (hashset.contains(++i)) { count++; hashset.remove(i); } // update lcs lcs = Math.max(lcs, count); } return lcs; } } ~~~ ### 源码分析 首先使用 HashSet 建哈希表，然后遍历数组，依次往左往右搜相邻数，搜到了就从 Set 中删除。末尾更新最大值。 ### 复杂度分析 时间复杂度和空间复杂度均为 O(n)O(n)O(n).