###Google面试题分析：色子问题
####原题
n个色子，每个色子m面，每一面的值分别是1-m。你将n个色子同时抛，落地后将所有朝上面的数字加起来，记为sum。给定一个数字x，如果sum>x，则你赢。给定n，m，x，求你赢的概率。
- 1<=n<=100
- 1<=m<=10
- m<=x<n*x
MILO sing1ee
🏠
sing1ee
/ gist:6097409
Created
July 28, 2013 04:31
You are given n dices each with heads numbered from 1 to m. You are to throw the n dices and note down the sum of the numbers on each of the n dices. You'll be give a number x and its a win if the sum obtained is greater than x. The problem is the find out the winning probability given n, m and x. Note 1<=n<=100, 1<=m<=10, m<=x<=n*m.
sing1ee
/ gist:6088874
Created
July 26, 2013 13:32
If you're given a list of countries and its corresponding population, write a function that will return a random country but the higher the population of the country, the more likely it is to be picked at random.
###选择旅游国家
####原题
有一个待选国家的列表，以及国家的相对热门程度，请给出一个算法，随机选择一个国家，并且保证，越是热门的国家，随机选择它的可能性就越高。
####分析
每当我们遇到一个题目的时候，都要对题目进行充分的理解，有哪些条件，目标是什么。这个题目看完之后，我们能够得到两个要点：
sing1ee
/ gist:6086124
Created
July 26, 2013 04:14
Bag A = 10 Red balls. Bag B = 10 Green balls. Shuffle bag A move three balls from A => B then Shuffle bag B move three balls from B => A Which bag is likely have more number of balls of other color.
###谁多谁少
####原题
盒子A有10个红球，盒子B有十个绿球。进行如下的操作：
- 随机从A中拿三个球放入B中
- 随机从B中拿三个球放入A中
sing1ee
/ gist:6071044
Last active
December 20, 2015 04:29
There is an island which is represented by square matrix NxN. A person on the island is standing at any given co-ordinates (x,y). He can move in any direction one step right, left, up, down on the island. If he steps outside the island, he dies. Let island is represented as (0,0) to (N-1,N-1) (i.e NxN matrix) & person is standing at given co-ord…
###死亡小岛
####原题
一个小岛，表示为一个N×N的方格，从(0,0)到(N-1, N-1)，一个人站在岛上，位置(x, y)，他可以上下左右走，一步一个格子，他选择上下左右的可能性是一样的。当他走出小岛，就意味着死亡。假设他要走n步，请问他死亡的概率有多大？请写出求解代码。
####分析 遇到这样的问题，就试着走几步好了。当一个人在(x,y)的时候，假设他此时，死亡的概率为p(x,y,n)，然后，他有四种选择，而且是可能性相同，就是说，选择上下左右的概率都是1/4：
- 选择上边，死亡的概率是多少呢？此时位置为(x, y-1)，剩余的步数为n-1,则概率为p(x, y - 1, n - 1)
###第一张A的概率
####原题
52张牌，四张A，随机打乱后问，从左到右1张一张翻直到出现第一张A，请问平均要翻几张牌？
####第一种分析
摸到第一张A之前的都是其他的牌，那么，之前会有多少种可能呢？ 之前可能会有0张，1张。。。。48张。考虑4张A在牌中的位置，他们把其他牌分成了5份（四个点把直线分成五段）。每一份的个数从0-48不等，完全随机的情况下，每份的平均长度为48/5=9.6，摸完这9.6张后，接下来的就是第一张A，故平均需要摸9.6+1=10.6张，即11张。
sing1ee
/ gist:6061288
Created
July 23, 2013 09:59
Given a normal dice and a dice with blank faces, fill in the blank dice with numbers from 0-6 so that the probability of each number coming up, when you roll the two dice together, is equal.
###色子玄机
####原题
有两个色子，一个是正常的，六面分别1-6的数字；另一个六面都是空白的。现在有0-6的数字，请给出一个方案，将0-6中的任意数字涂在空白的色子上，使得当同时扔两个色子时，以相等的概率出现某一个数字。如果一个色子是1，另一个色子是2，则出现的数字是3。依次类推。
####分析
首先，深入理解题目。两个色子，一个色子上1到6，是正常的，可以理解为，随手一扔，每个数字出现的概率是相同的，都是1/6；另一个呢？空白的，不过我们可以自己涂上0-6的数字，包括0和6。然后扔完了之后，一个色子上面出现a，另一个色子出现b，最终把a+b作为一个数字。有多少个不同的数字呢？假设有n个，则题目要求是每一个出现的概率都是1/n。
sing1ee
/ gist:6050943
Last active
December 10, 2017 12:01
Suppose we are given an array A[1 .. n] with the special property that A[1] ≥ A[2] and
A[n − 1] ≤ A[n]. We say that an element A[x] is a local minimum if it is less than or equal
to both its neighbors, or more formally, if A[x − 1] ≥ A[x] and A[x] ≤ A[x + 1]. For example,
there are five local minima in the following array:
9 7 7 2 1 3 7 5 4 7 3 3…
###找数组的波谷
####原题
一个数组A[1...n]，满足A[1]>=A[2], A[n] >= A[n-1]。A[i]被成为波谷，意味着：A[i-1] >= A[i] <= A[i+1]。请给出一个算法，找到数组中的一个波谷。O(n)的方法，是很直接，有更快的方法么？
####分析
这个题目遍历一遍数组，显然就可以找到全部的波谷。时间复杂度O(n)，空间复杂度是O(1)。但是如果我们只需要找到一个波谷，是否有更快的方法呢？更快的方法O(1)是不可能的，那只有O(logn)，自然就想到二分查找。这个题目如果进行二分呢？我们看下面的数组A：
###QuickSort on Singly Linked List
#####Rationale
- 思路和数据的快速排序一样，都需要找到一个pivot元素、或者节点。然后将数组或者单向链表划分为两个部分，然后递归分别快排。
- 针对数组进行快排的时候，交换交换不同位置的数值，在分而治之完成之后，数据就是排序好的。那么单向链表是什么样的情况呢？除了交换节点值之外，是否有其他更好的方法呢？可以修改指针，不进行数值交换。这可以获取更高的效率。
- 在修改指针的过程中，会产生新的头指针以及尾指针，要记录下来。在partition之后，要将小于pivot的的部分、pivot、以及大于pivot的部分重新串起来成为一个singly linked list。
#####Choose pivot
- choose the first node or the last node
###leetcode Pow(x, n)
####思路
- 尽量减少计算乘法的次数
- 如果n是奇数，则 pow(x, n) = x * pow(x, n - 1)
- 如果n是偶数，则 pow(x, n) = pow(x, n >> 1) * pow(x, n >> 1)
####NOTE
- n < 0时
- n = 0时