算法题

1

给一个input，是一句话有一些words，空格隔开。指定屏幕的行和列，问把这句话重复打印到屏幕上最多能打印多少遍。先写了个暴力的，一个一个词放进去看能打印多少遍。follow up，如果行和列非常大，这样解效率太低，有什么更好的方法。想了一会，可以弄个look up table。

Ans:key是每一个单词的index。value记录下以key为每行的第一个单词时，最后一个单词的index和这句话在这一行能打印多少遍。然后一行行找就行了，复杂度就是行的个数。

From Here

2

将一个正整数分成若干个数的和，求这些数的最大乘积。

最大乘积这题有O(n)的solution，p[n] = max(2 p[n-2], 3 p[n-3])

平面上有很多点，找一条平行于x轴的直线使这些点到该直线的距离之和最小，并证明。

不是平均值，是中位数的那个点。证明：你可以把点按照y轴排序好，把所有点group成pair，比如（－1，0，3，6，7）, 然后－1和7一组，0和6一组，3一组。然后就好证明了。

第二轮是面试官听口音应该是国人，比较nice。题目是给一个字典，里面全是string，字典很大，可能有几百万个string。然后写一个方法判断输入是否有一个typo，否则返回false。比如，字典有google，facebook，amazon等。输入google返回false，因为没有typo。输入geogle，返回true，因为有一个typo。输入geogla，返回false，因为有多于一个的typo。

From Here

3

给了一个matrix，每个matrix[i][j]有一个价格，给你一个budget，问如何求出最大面积的子矩阵，使得子矩阵的价格之和不超过budget。

private int findMaxLengthIn1DArray(int[] nums, int target) {
                int max = 0, i = 0, sta = 0, sum = 0;
                while (i < nums.length) {
                        sum += nums;
                        if (sum > target) {
                                max = Math.max(max, i-sta);
                        }
                        while (sum > target) {
                                sum -= nums[sta++];
                        }
                        i++;
                }
                return max == 0 ? nums.length : max;
        }

        public int getMaxArea(int[][] nums, int target) {
                int wid = nums.length, len = nums[0].length, max = 0;
                for (int j1 = 0; j1 < wid; j1++) {
                        int[] tmp = new int[len];
                        for (int j2 = j1; j2 < wid; j2++) {
                                for (int i = 0; i < len; i++) {
                                        tmp += nums[j2];
                                }
                                int tempMax = findMaxLengthIn1DArray(tmp, target);
                                max = Math.max(max, tempMax*(j2-j1+1));
                        }
                }
                return max;
        }

以上思路的优点在于合理利用two pointer，我原来还以为是有个left,right,原来是和minimum window substring有点类似。

第二轮面试官国人，上来的的问题是问我如果在谷歌搜索框里输入一个查询语句，请描述一下在点击回车之后会发生什么事情。因为自己做过搜索引擎，我当时以为他问搜索引擎的查询过程，然后有点答得不对题，后来才知道他问的是计算机网络的东西。我大概把这个网络部分的回答简化了，然后没有答完整。要是理解清楚题意的话，我觉得我会把应用层到物理层的过程都给他讲一遍。（居然考计算机网络，我去）第二个问题是说谷歌服务器每个上面都有自己的log，让我做一个log viewer服务器，自己定义接口，能够实现在log viewer查询所有的服务器端整合的log，（因为去一个个服务器上查询log可能太麻烦了），可以自己定义log viewer的功能。做完了后面试官说写的很好，然后跟我讨论了一下实现并发等，面试结束，然后就挂了。。。挂了。。。挂了。。。

From Here

4

Coding是Design a data structure that supports add(T val), remove(T val) and T removeRandomElement() all in O(1) time

map+array,用最后一个填补remove 的hole。

5

There are a large number of leaves eaten by caterpillars. There are 'K"' caterpillars which jump onto the leaves in a pre-determined sequence. All caterpillars start at position 0 and jump onto the leaves at positions 1,2,3...,N. Note that there is no leaf at position 0.
Each caterpillar has an associated 'jump-number'. Let the jump-number of the i-th caterpillar be A [i]. A caterpillar with jump number 7 keeps eating leaves in the order 1,241,3*1,... till it reaches the end of the leaves - i.e, it eats the leaves at the positions which are multiples of /'.
Given a set 'A' of 'IC elements. 'e<=15.,. 'N'<=109, we need to determine the number of uneaten leaves.
Input Format:
N -number of leaves
A - Given array of integers
Output Format:
An integer denoting the number of uneaten leaves.
Sample Input:
N = 10
A = [2,4,5]
Sample Output:
4
Explanation
1,3,7,9 are the leaves which are never eaten. All leaves which are multiples of 2, 4, and 5 have been eaten.

O(1) space O(k.2^k) time solution, where k is the number of caterpillars (independent of n):

Example with n = 10; A = [2,4,5];

Let S2 = set of numbers in range [1..10] that divisible by 2: S2 = {2,4,6,8,10}; |S2| = n/2;
Let S4 = set of numbers in range [1..10] that divisible by 4: S4 = {4,8}; |S4| = n/4;...
Let S5 = set of numbers in range [1..10] that divisible by 5: S5 = {5,10};
Let S24 = set of numbers in range [1..10] that divisible by 2 and 4: S24 = {4,8};
Let S25 = set of numbers in range [1..10] that divisible by 2 and 5: S25 = {10};
Let S54 = set of numbers in range [1..10] that divisible by 5 and 4: S54 = {};
Let S245 = set of numbers in range [1..10] that divisible by 2, 4 and 5: S245 = {};

Let S be the union of all these sets: S=S2 + S4 + S5 + S24 + S25 + S45 + S245 = {2,4,5,6,8,10};

Thus, the number of uneaten leaves is:4

其余部分就是怎么样生成subset的问题了。可以用dfs。

From Here

6

第一题： Given an array, find whether it exist an subarray that sum of subarray is equal to given number 第二题：上面那题的follow up，不过array变成了matrix，找的也是submatrix。。。.

简单的说就是给一个array，和一个数字，问存在一个subarray，他的和等于那个数字。注意，subarray的意思是一个连续的元素的subarray from array。解法是用一个新的数组保存从0到当前元素的和，然后再用hash表保存下，再搜索一次即可。

2dmatrix类似，先固定first row, last row,就变成1d的问题了。

可以n^3,和这个题目类似 http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/

from Here

7

G家 A. 给定一个产生[0,1]直接随机数的函数，以及一个三角形。要求调用这个函数随机产生一个在三角形内的点.

两个向量加一下就好啦比如说以某点为原点，向量a,b是两条边，那么取两个随机数, x<-(0,1), y<-(0,1) p = x|a|, q= 0.5y|b| 那么随机点的坐标就是 pa+q*b

给一个linkedlist，然后给了一些node。要求输出有几个group，group的定义是连在一起的node就算一个group。比如linkedlist是这样的1->2->3->4->5->6->7->8->9, 然后给的node是[3,4,7,2,5], 那就输出3 这题也是有很多优化和边角讨论

onsite round 5：一个binary image的编码，问怎么样编码最好。答案是4-tree，就是每次把图片分成4块，如果每一块只有一种颜色，就用一个leaf表示，否则就继续四分下去。题目就是，怎样把两棵这样的4-trees合并起来. visit 1point3acres.com for more.

From Here

8

there are n machines each contain different size of unsorted numbers, find the medianof all numbers.

Find Median

要求尽量减少数据在machine之间的传输次数。我一开始想到 Hash +relocation的方法来处理所有数，在算中数位置，面试官问有没有能减少mahcine传输的方法。提醒之后想到了quicksort找中数的方法，用在N machines 上面。

Leetcode decode way. 第二轮：一个美国哥们。1. write aninterface of random get number。写一个interface，insert() 插入 object，get() method随机返回一个object，remove（）随机返回并删除object。写出method并减少complexity。写出来在他的要求下改进的code，但被他发现了不少bug。2. given random list of ticket, decide if all tickets cancombine into a trip path。意思给一堆机票，能否吧所有机票连在一起成为一条path，可以从A出发，直接走到B。要求用掉所有机票。我给出的方法一直不能满足他的一些case，比如可以A---B---C---A----B---D这样的case。他给的提示方法，但还是没想出来。思路是拿到所有ticket之后找出起点和终点，起点出发的ticket一定比回来的多一张，终点回来的ticket比出发的多一张，找到之后再分析路径。最后才把方法搞明白，没写code。这轮有点惨。第三路：像是个ABC，题目是Given a Iterator of iterator, create a iterator which pop outelement of each iterator one by one. 意思是给一个iterator 的 iterator, 比如 Iterator A: 1à 2à3à4 Iterator B: 5-à6 Iterator C: 7à 8 à9 Create的iterator需要next（）这样的顺序： 1,5, 7, 2, 6, 8, 3, 9, 4 写的时候问了思路，做法是把iterator存到array里面了，通过index判断next（）的iterator在array哪一位。写完代码后他举例一种情况我的代码不能跑，想了之后改进说只存hasNext（）的iterator。这轮只有一题，写代码和go through代码花了不少时间。第四轮：一个老印，人挺友善的。题目都是抽象题，将思路为主。上来先让我解释Tree和Graph，以及他们的区别。让后给了个题目：一个类似graph，里面的每个element都是一个node，每个node都有若干个connecting 到其他nodes。从一个点出发，找到所有在这个neighbor中的node。一个Node不在这个neighbor中表示他和那个neighbor中所有点都没有connection。简答想了个DFS，然后讲下思路他说就可以了。第二题：给了N个machines，M个file，里面有若干个数（N>>M），还有一个 sum(machine_id , file_id)的函数，算出所有file的sum。一开始谢了个for循环，他说这样只能用一个machine。让后我说可以用MPI之类的东西，但code我一下子写不出来。让后他说用Java 的Thread也可以。我说我Thread不常用，可能写的不对（有点尴尬，Java基本只拿来刷题）。他说没关系，我大概写出了code（Thread 应该写错了），他就说可以了。基本就这些，请大家祝我好运，谢谢。