Daily Archives: September 2, 2012

max diff pairs in array revised version

    #include<stdio.h>#include<stdlib.h> int maxDiff( int *array, unsigned length );int getDiff( int *start, int *end, int **max, int **min );int maxDiff2( int *num, unsigned length );int getDiff2( int *num, unsigned length );int maxDiff3( int *num, unsigned length ); int main( … Continue reading

Posted in Uncategorized | Leave a comment

google 面试题

一面墙dimension: m*n, 家里有各种尺寸的照片,设计一个算法贴最多照片 http://www.mitbbs.com/article_t/JobHunting/32199615.html

Posted in Uncategorized | Leave a comment

G家面经

http://www.mitbbs.com/article_t/JobHunting/32197465.html 又Fail了,已经是连续两年了 1 An array with n elements which is K most sorted. 就是每个element的初始位置 和它最终的排序后的位置的距离不超过常数K,设计一个排序算法。should be faster than O(n*lgn) 2 Paint 一块画板上的区域。从一个点出发,直到所有相邻的和出发点一样颜色的点都 paint 上需要的颜色 3  又一个排序好的不知道长度的数组,在其中search 一个给定值 4  1..n 这些数有两个missing,find out which two are missing.

Posted in Uncategorized | Leave a comment

家onsite面经

http://www.mitbbs.com/article_t1/JobHunting/32162725_0_3.html   这周周二的onsite,一共五轮面试。安排比较混乱,其中一个interviewer,我干等了 半个小时,no show。联系HR,才知道这个interviewer已经休假5个月。所以后来又加 了一个interviewer。 感觉google的面试根本不考虑candidate的背景和经历,只考coding。我有朋友做到了 CS Top-4的正教授,去google面试仍然是一样的流程。这个确实让人非常frustrated。 1. Thesis discussion:老印,data base出身,鸡同鸭讲,面得很费劲,互相感觉都 不是很好。 2. 老中,coding:给一个N个node的BST,给一个Key,返回与key最接近的m个node(m<N ). 我开始说可以做inorder traverse,用一个priority queue保存跟key最近的m个value ,复杂度O(n);存在average O(log n)的算法,但不好写。结果还是被要求写O(log n) 的code。 这个算法不是很难(不确定是不是最优),但是在30分钟写出来确实不容易。 我的基本思路还是用priority queue,现在BST中查找key,返回指向value=key的node( 如果存在)或者应该插入该key的node(key不在BST中),然后从该node开始向前向后各m 次判断前驱或者后继是不是应该插入priority queue. 主要函数code最后虽然写出来了,不过lookUp、successor和predecessor这三个子函数 没来得及写。 3. 白人。问了一个随机采样方面的问题,比较简单。 3.5 lunch。以前实验室的一个哥们带我lunch然后骑着自行车在g campus逛了一圈 4.0 老中,no … Continue reading

Posted in Uncategorized | Leave a comment

这几个G家的design题怎么做

都是从版上看来的。不知道考点在哪里。大牛请指教。 1。一个大型cluster 包括thousands of nodes.  需要定期 upgrade 每个server跑的 OS image (也就是重装).  如何设计一个方案加速该过程。 2。一个sensor network有很多sensors, 一个server 定期query 每 个sensor的值。sensor may fail。如何让server 避免被block。 3。设计题是一堆机器生成unique ID,这些机器之间不能互相通信,也没有master。   . 第一题是不是能划分一个block,比如1mb一个block, 收到的OS file比如说有1GB那 么可以看成有1024个block, 当一个block接收完整后可以传给另外一台机器, 如此循环 ?? 带宽越大block设置的越小??? 2. 啥意思? 3. 假如有10台机器, 用同一个hash function, 每台机器知道自己的编号, … Continue reading

Posted in Uncategorized | Leave a comment

数对之差的最大值[算法]

  题目:在数组中,数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如在数组{2, 4, 1, 16, 7, 5, 11, 9}中,数对之差的最大值是11,是16减去5的结果。 #include<stdio.h>#include<stdlib.h> int maxDiff( int *array, unsigned length );int getDiff( int *start, int *end, int **max, int **min );int maxDiff2( int *num, unsigned length );int getDiff2( int *num, unsigned length );int maxDiff3( … Continue reading

Posted in Uncategorized | Leave a comment