[答案]来自苹果、谷歌、微软等知名公司六道有趣智力面试题


http://www.acmerblog.com/interview-2-1549.html

NO.1

有20瓶药丸,其中19瓶装有1克/粒的药丸,余下一瓶装有1.1克/粒的药丸。给你一台称重精准的天平,怎么找出比较重的那瓶药丸?天平只能用一次。
称一堆药丸时,我们会有个“预期”重量。而借由预期重量和实测重量之间的差别,就能得出哪一瓶药丸比较重,前提是从每个药瓶取出不同数量的药丸。
将之前两瓶药丸的解法加以推广,就能得到完整解法:从药瓶#1取出一粒药丸,从药瓶#2取出两粒,从药瓶#3取出三粒,依此类推。如果每粒药丸均重1克,则称得总重量为210克(1 + 2 + … + 20 = 20 * 21 / 2 = 210),“多出来的”重量必定来自每粒多0.1克的药丸。
药瓶的编号可由算式(weight – 210 grams) / 0.1 grams得出。因此,若这堆药丸称得重量为211.3克,则药瓶#13装有较重的药丸。

NO.2

有个8×8棋盘,其中对角的角落上,两个方格被切掉了。给定31块多米诺骨牌,一块骨牌恰好可以覆盖两个方格。用这31块骨牌能否盖住整个棋盘?请证明你的答案(提供范例,或证明为什么不可能)。
尝试用骨牌盖住第1行,而第1行只有7个方格,因此有一块骨牌必须铺至第2行。而用骨牌盖住第2行时,我们又必须将一块骨牌铺至第3行。
enter image description here
要盖住每一行,总有一块骨牌必须铺至下一行。无论尝试多少次、多少种方法,我们都无法成功铺下所有骨牌。
其实,还有更简洁更严谨的证明说明为什么不可能。棋盘原本有32个黑格和32个白格。将对角角落上的两个方格(相同颜色)切掉,棋盘只剩下30个同色的方格和32个另一种颜色的方格。为方便论证起见,我们假定棋盘上剩下30个黑格和32个白格。
放在棋盘上的每块骨牌必定会盖住一个白格和一个黑格。因此,31块骨牌正好盖住31个白格和31个黑格。然而,这个棋盘只有30个黑格和32个白格,所以,31块骨牌盖不住整个棋盘。

NO.3

有两个水壶,容量分别为5夸脱(美制:1夸脱=0.946升,英制:1夸脱=1.136升)和3夸脱,若水的供应不限量(但没有量杯),怎么用这两个水壶得到刚好4夸脱的水?注意,这两个水壶呈不规则形状,无法精准地装满“半壶”水。
enter image description here
注意,许多智力题其实都隐含数学或计算机科学的背景,这个问题也不例外。只要这两个水壶的容量互质(即两个数没有共同的质因子),我们就能找出一种倒水的顺序组合,量出1到2个水壶容量总和(含)之间的任意水量。

NO.4

有个岛上住着一群人,有一天来了个游客,定了一条奇怪的规矩:所有蓝眼睛的人都必须尽快离开这个岛。每晚8点会有一个航班离岛。每个人都看得见别人眼睛的颜色,但不知道自己的(别人也不可以告知)。此外,他们不知道岛上到底有多少人是蓝眼睛的,只知道至少有一个人的眼睛是蓝色的。所有蓝眼睛的人要花几天才能离开这个岛?
解法
下面将采用简单构造法。假定这个岛上一共有n人,其中c人有蓝眼睛。由题目可知,c > 0。
1. 情况c = 1:只有一人是蓝眼睛的
假设岛上所有人都是聪明的,蓝眼睛的人四处观察之后,发现没有人是蓝眼睛的。但他知道至少有一人是蓝眼睛的,于是就能推导出自己一定是蓝眼睛的。因此,他会搭乘当晚的飞机离开。
2. 情况c = 2:只有两人是蓝眼睛的
两个蓝眼睛的人看到对方,并不确定c是1还是2,但是由上一种情况,他们知道,如果c = 1,那个蓝眼睛的人第一晚就会离岛。因此,发现另一个蓝眼睛的人仍在岛上,他一定能推断出c = 2,也就意味着他自己也是蓝眼睛的。于是,两个蓝眼睛的人都会在第二晚离岛。
3. 情况c > 2:一般情况
逐步提高c时,我们可以看出上述逻辑仍旧适用。如果c = 3,那么,这三个人会立即意识到有2到3人是蓝眼睛的。如果有两人是蓝眼睛的,那么这两人会在第二晚离岛。因此,如果过了第二晚另外两人还在岛上,每个蓝眼睛的人都能推断出c = 3,因此这三人都有蓝眼睛。他们会在第三晚离岛。
不论c为什么值,都可以套用这个模式。所以,如果有c人是蓝眼睛的,则所有蓝眼睛的人要用c晚才能离岛,且都在同一晚离开。

NO.5

有栋建筑物高100层。若从第N层或更高的楼层扔下来,鸡蛋就会破掉。若从第N层以下的楼层扔下来则不会破掉。给你2个鸡蛋,请找出N,并要求最差情况下扔鸡蛋的次数为最少。
解法
我们发现,无论怎么扔鸡蛋1(Egg 1),鸡蛋2(Egg 2)都必须在“破掉那一层”和下一个不会破掉的最高楼层之间,逐层扔下楼(从最低的到最高的)。例如,若鸡蛋1从5层和10层楼扔下没破掉,但从15层扔下时破掉了,那么,在最差情况下,鸡蛋2必须尝试从11、12、13和14层扔下楼。
具体做法
首先,让我们试着从10层开始扔鸡蛋,然后是20层,等等。
 如果鸡蛋1第一次扔下楼(10层)就破掉了,那么,最多需要扔10次。
 如果鸡蛋1最后一次扔下楼(100层)才破掉,那么,最多要扔19次(10、20、…、90、100层,然后是91到99层)。
这么做也挺不错,但我们只考虑了绝对最差情况。我们应该进行“负载均衡”,让这两种情况下扔鸡蛋的次数更均匀。
我们的目标是设计一种扔鸡蛋的方法,使得扔鸡蛋1时,不论是在第一次还是最后一次扔下楼才破掉,次数越稳定越好。
1(1) 完美负载均衡的方法应该是,扔鸡蛋1的次数加上扔鸡蛋2的次数,不论什么时候都一样,不管鸡蛋1是从哪层楼扔下时破掉的。
2(2) 若有这种扔法,每次鸡蛋1多扔一次,鸡蛋2就可以少扔一次。
3(3) 因此,每丢一次鸡蛋1,就应该减少鸡蛋2可能需要扔下楼的次数。例如,如果鸡蛋1先从20层往下扔,然后从30层扔下楼,此时鸡蛋2可能就要扔9次。若鸡蛋1再扔一次,我们必须让鸡蛋2扔下楼的次数降为8次。也就是说,我们必须让鸡蛋1从39层扔下楼。
4(4) 由此可知,鸡蛋1必须从X层开始往下扔,然后再往上增加X1层……直至到达100层。
5(5) 求解方程式X + (X1) + (X2) + … + 1 = 100,得到X (X + 1) / 2 = 100 → X = 14。
我们先从14层开始,然后是27层,接着是39层,依此类推,最差情况下鸡蛋要扔14次。
正如解决其他许多最大化/最小化的问题一样,这类问题的关键在于“平衡最差情况”。

NO.6

走廊上有100个关上的储物柜。有个人先是将100个柜子全都打开。接着,每数两个柜子关上一个。然后,在第三轮时,再每隔两个就切换第三个柜子的开关状态(也就是将关上的柜子打开,将打开的关上)。照此规律反复操作100次,在第i轮,这个人会每数i个就切换第i个柜子的状态。当第100轮经过走廊时,只切换第100个柜子的开关状态,此时有几个柜子是开着的?
解法
要解决这个问题,我们必须弄清楚所谓切换储物柜开关状态是什么意思。这有助于我们推断最终哪些柜子是开着的。
1. 问题:柜子会在哪几轮切换状态(开或关)?
柜子n会在n的每个因子(包括1和n本身)对应的那一轮切换状态。也就是说,柜子15会在第1、3、5和15轮开或关一次。
2. 问题:柜子什么时候还是开着的?
如果因子个数(记作x)为奇数,则这个柜子是开着的。你可以把一对因子比作开和关,若还剩一个因子,则柜子就是开着的。
3. 问题:x什么时候为奇数?
若n为完全平方数,则x的值为奇数。理由如下:将n的两个互补因子配对。例如,如n为36,则因子配对情况为:(1, 36)、(2, 18)、(3, 12)、(4, 9)、(6, 6)。注意,(6, 6)其实只有一个因子,因此n的因子个数为奇数。
4. 问题:有多少个完全平方数?
一共有10个完全平方数,你可以数一数(1、4、9、16、25、36、49、64、81、100),或者,直接列出1到10的平方:
1*1, 2*2, 3*3, …, 10*10
因此,最后共有10个柜子是开着的。

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts