zz. google onsite interview

A. 两个single linked list，每一个节点里面一个0-9的数字，输入就相当于两个大数
了。然后返回这两个数的和（一个新list）。这两个输入的list长度相等。
当时的要求是：1. 不用递归。2.然后要求算法在最好的情况下，只遍历两个list一次
。最差的情况下两遍。

当时让我首先说说什么情况2遍，什么情况1遍，然后开始写。这个题目看上去不难，但
是写起来挺考验基本功的。大家准备面试练习的时候可以写写。

B. Count Inversions
http://www.geeksforgeeks.org/counting-inversions/
刚开始想到这个解法，但是有个坎没绕过去，觉得有些情况下处理不了，后来经过沟通
发现其实可以。

A. 第一题比较简单，是leetcode上有的。若是逆序排列的话，那么就一级一级往上算，搞个count当进位。若是顺序的话，就需要两遍，因为single linked list只能往一边走。所以我的思路是，先计算第一遍，把和都存在一个数组里面，假如可以有额外空间的话，都不用再遍历第二遍，直接处理这个数组就好了。就能得出值，但若要inplace, 不能给additional space， 那么只能再走一遍。这个时候要注意9+9等于18的情况。

B. 此题就是找一个un sorted array里面，顺序不对的element对。比如2,4,1,3,5 就有 ［2，1］，［4，1］，［4，3］三对。

brute force O(n^2)这里就不说了。
网上有一种叫enhanced merge sort，就是recursively bottom up, 先把数组分两边，叫left, right。左边有一个元素a[i]比右边数组的一个元素a[j]大的，那么a[i]到a[mid]全是inversions. 这个时候左右 两边都是sorted的，因为是从最地层一路做上来的，每次找到的inversion count都相加。

http://www.geeksforgeeks.org/counting-inversions/