Monday, June 24, 2013

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/

No comments:

Post a Comment

Leetcode 316. Remove Duplicate Letters

 这道题表面问的是如何删除重复,实际在问如何从多个字符选取一个保留,从而让整个字符串按升序排列。那么策略就是对于高顺位的字符比如‘a',就要选靠前位置的保留,而低顺位字符如’z'则应该尽量选取靠后位置保留。 算法大概思路:每看到一个字符,我们要决定是否保留 1. ...