yaron's space
以技术为主
140个Google的面试题【转载】
七 16th
原文地址：http://coolshell.cn/articles/3345.html
来源：http://blog.seattleinterviewcoach.com/2009/02/140-google-interview-questions.html（墙）
某猎头收集了140多个Google的面试题，都张到他的Blog中了，主要是下面这些职位的，因为被墙，且无任何敏感信息，所以，我原文搬过来了。
- Product Marketing Manager
- Product Manager
- Software Engineer
- Software Engineer in Test
- Quantitative Compensation Analyst
- Engineering Manager
- AdWords Associate
这篇Blog例举了Google用来面试下面这几个职位的面试题。很多不是很容易回答，不过都比较经典与变态，是 Google，Microsoft，Amazon之类的公司的风格。对于本文，我没有翻译，因为我相信，英文问题是最好的。不过对于有些问题，我做了一些 注释，不一定对，但希望对你有帮助启发。对于一些问题，如果你百思不得其解，可以Google一下，StackOverflow或是Wikipedia上 可能会给你非常全面的答案。
Product Marketing Manager
- Why do you want to join Google?
- What do you know about Google’s product and technology?
- If you are Product Manager for Google’s Adwords, how do you plan to market this?
- What would you say during an AdWords or AdSense product seminar?
- Who are Google’s competitors, and how does Google compete with them?
- Have you ever used Google’s products? Gmail?
- What’s a creative way of marketing Google’s brand name and product?
- If you are the product marketing manager for Google’s Gmail product, how do you plan to market it so as to achieve 100 million customers in 6 months?
- How much money you think Google makes daily from Gmail ads?
- Name a piece of technology you’ve read about recently. Now tell me your own creative execution for an ad for that product.
- Say an advertiser makes $0.10 every time someone clicks on their ad. Only 20% of people who visit the site click on their ad. How many people need to visit the site for the advertiser to make $20?
- Estimate the number of students who are college seniors, attend four-year schools, and graduate with a job in the United States every year.
Product Manager
- How would you boost the GMail subscription base?
- What is the most efficient way to sort a million integers? （陈皓：merge sort）
- How would you re-position Google’s offerings to counteract competitive threats from Microsoft?
- How many golf balls can fit in a school bus? （陈皓：这种题一般来说是考你的解题思路的，注意，你不能单纯地把高尔夫球当成一个小立方体，其是一个圆球，堆起来的时候应该是错开的——也就是三个相邻 的球的圆心是个等边三角形）
- You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do?
- How much should you charge to wash all the windows in Seattle?
- How would you find out if a machine’s stack grows up or down in memory?
- Explain a database in three sentences to your eight-year-old nephew. （陈皓：用三句话向8岁的侄子解释什么是数据库，考你的表达能力了）
- How many times a day does a clock’s hands overlap?（陈皓：经典的时钟问题）
- You have to get from point A to point B. You don’t know if you can get there. What would you do?
- Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval? （陈皓：很不错的一道题，不要以为分类查询很容易，想想图书馆图书的分类查询问题吧。另外，你处想想如何在你在你的衣柜里实现一个相当于Hash表或是一 个Tree之类的数据结构）
- Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens? （陈皓：这个问题很有限制级，哈哈，非常搞的一个问题，注意wife们的递归，这类的问题是经典的分布式通讯问题，上网搜 一搜吧。）
- In a country in which people only want boys, every family continues to have children until they have a boy. If they have a girl, they have another child. If they have a boy, they stop. What is the proportion of boys to girls in the country?（陈皓：第一反应是——这个国家是中国。一个概率问题，其实，无论你怎么生，50%的概率是永远不变的。）
- If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)?
- If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands? (The answer to this is not zero!)
- Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, they only have one flashlight and it only has enough light left for seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it’s only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the campers make it across in 17 minutes?（陈皓：经典的过桥问题）
- You are at a party with a friend and 10 people are present including you and the friend. your friend makes you a wager that for every person you find that has the same birthday as you, you get $1; for every person he finds that does not have the same birthday as you, he gets $2. would you accept the wager?
- How many piano tuners are there in the entire world?
- You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighings?（陈皓：经典的称重问题。这样的问题花样很多，不过都不难回答）
- You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in order to maximize his share but live to enjoy it? (Hint: One pirate ends up with 98 percent of the gold.)
- You are given 2 eggs. You have access to a 100-story building. Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100th floor. Both eggs are identical. You need to figure out the highest floor of a 100-story building an egg can be dropped without breaking. The question is how many drops you need to make. You are allowed to break 2 eggs in the process. （陈皓：从3的倍数的楼层开始扔，比如3，6，9，12…..，如果鸡蛋在3n层碎了，那到在3n-1层扔第二个鸡蛋，如果没碎，则最高不碎楼层为3n- 1，否则为3n-2）
- Describe a technical problem you had and how you solved it.
- How would you design a simple search engine?
- Design an evacuation plan for San Francisco.
- There’s a latency problem in South Africa. Diagnose it. （陈皓：这个问题完全是在考你的解决问题的能力。没有明确的答案。不过，解决性能问题的第一步通常是找出瓶颈，找瓶颈有很多种方法，工具，二分查，时间记 录等等。）
- What are three long term challenges facing Google?
- Name three non-Google websites that you visit often and like. What do you like about the user interface and design? Choose one of the three sites and comment on what new feature or project you would work on. How would you design it?
- If there is only one elevator in the building, how would you change the design? How about if there are only two elevators in the building? （陈皓：经典的电梯设计问题，这种问题千变万化，主要是考你的设计能力和需求变化的适变能力，与此相似的是酒店订房系统。）
- How many vacuum’s are made per year in USA?
[编程之美]N个鸡蛋放到M个篮子的方法
七 5th
今天看到一个面试题目，题目大意：将n个鸡蛋放到m个篮子，同时保证不能有空篮子，且对于任意小于等于n的数，都能保证有几个篮子的鸡蛋数等于这个数
题目分析
第一眼看到这个题目时，感觉像是整数拆分问题，但是有两个限制：1. 不能有空篮子 2.保证能够针对任意<=n的数，都可以用几个篮子的鸡蛋的和来表示，所以应该不是整数拆分问题。
首先想到是就是穷举，也就是深度搜索，但是如何判断搜索的一个结果是否满足第二个条件呢？
这里可以通过归纳的方法，假设当前的前n个数为Sn，同时任意<=Sn的数都可以用前n个数某些数的和来表示，那么第n+1个数的范围是什么呢？
这里应该可以想到，如果第n+1个数>(Sn) + 1 的话，相当于有间隔，那么(Sn) + 1这个就无法表示，所以第n+1个数应该是<= Sn + 1，这样就可以满足
任意的<=S(n+1) 的数都可以用前n+1个数来表示；
同时在搜索的过程中保证序列是非降序的，而且会有剪枝的方法，实现具体看代码
代码实现
使用mmap实现文件的拷贝
七 4th
今天看csapp看到了虚拟存储器的映射以及mmap函数的用法，作为练习，使用mmap来实现文件的拷贝操作，同时与传统的文件拷贝操作进行了性能比较。
mmap与munmap函数介绍：
#include <unistd .h> #include <sys /mman.h> void *mmap(void *start, size_t length, int prot, int flag, int fd, off_t offset); //返回:若成功时则返回映射区域的指针，若出错则为MAP_FAILED(-1) </sys></unistd>
start: 最好从start开始的一个区域，这个是hint，具体映射结果还是要看返回结果
length: 映射区域的大小
prot: 映射区域的访问权限位 PROT_EXEC PROT_READ PROT_WRITE PROT_NONE
flags: 映射对象的类型 MAP_ANON MAP_PRIVATE MAP_SHARED
munmap函数删除映射区域
#include <unistd .h> #include <sys /mman.h> int munmap(void *start, size_t length); </sys></unistd>
实验
分别使用了mmap函数和普通的read write实现了文件的复制拷贝，下面是通过复制50M的文件性能分析：
[yangguang@sim124 ~]$ time ./workspace/mmapcopy linux-20101214.tar.gz ./output real 0m0.100s user 0m0.034s sys 0m0.065s
[yangguang@sim124 ~]$ time ./workspace/copy linux-20101214.tar.gz ./output real 0m5.016s user 0m0.000s sys 0m0.124s
可以看到使用mmap的性能明显高于使用Read write的方式，这里主要原因是使用mmap减少了用户态和内核态间数据
的拷贝
更多 >
[编程之美]使用最大堆和最小堆来求中位数
六 28th
好久没更新blog，都快荒废了，今天发个算法问题
题目介绍：
输入为不断地数字流，实时显示出当前已经输入的数字序列的中位数
解答：
求中位数的方法很多，对于大数据量最经典是桶的计数方法，但是对于这个问题不适用，因为数据是不断变化的
可以用最大堆和最小堆来解答这个问题：
1.假设当前的中位数为m，其中最大堆维护的是<=m的数字序列，最小堆维护的是>=m的数字序列，但是两个堆都不包含m
2.当新的数字到达时，比如为a，将a与m进行比较，若a<=m 则将其加入到最大堆中，否则将其加入到最小堆中
3.如果此时最小堆和最大堆的元素个数的差值>=2 ，则将m加入到元素个数少的堆中，然后从元素个数多的堆将根节点赋值到m，最后重建两个最大堆和最小堆，返回到2
vim中recording模式详解
六 9th
今天看到这个视频：http://v.youku.com/v_show/id_XODk1NjkyNTI=.html
里面有一段是对某一行进行修改，然后可以将这些修改应用到与这一行类似的其他行，然后就想到了vim中recording模式，今天好好总结学习下。
进入recording模式
在正常状态（正常状态 = !insert状态 && !visual状态）下，按q，再按下一个字母或数字，这个数字代表缓冲区的名字，是键盘操作存储的位置，这时编辑器下方就显示”recording(记录)”字样，然后进行操作，最后按q退出这中模式，这样在这期间进行的操作就保存在缓冲区中了
生效缓冲区的内容
怎样将同样的操作在类似的行上生效呢？
使用@后面加上缓冲区的名字即可
实际例子
在文本区中存在以下内容：
int a; int b; int c; int d;
然后将光标放入到第一行的第一个字符输入以下内容：qm$i=1+1<ESC>q
qm：表示进入recording模式，选择缓冲区m
$i:定位到行尾并进入插入模式
=1+1：表示插入的内容
<ESC>q：返回正常状态，并退出recording模式
最后将光标定位到第二行的行首，输入：@m
以下几行类似操作。
最后文本内容变为：
int a=1+1; int b=1+1; int c=1+1; int d=1+1;
参考资料：http://hi.baidu.com/xiaowp/blog/item/c27b50543bb08a53574e0066.html
SMTP邮件服务器postfix配置与使用
六 1st
最近要帮朋友配置一个SMTP服务器，需求就是每天需要向外发送上百万封邮件，google之，发现postfix邮件服务器比较靠谱, 能够发送外部邮件，于是就选它了
操作系统：CentOS 5 32bit
postfix安装
可以通过源码安装最新的版本，但是为了方便，我直接使用yum安装
sudo yum install postfix
配置文件路径:/etc/postfix/main.cf
postfix启动与停止命令：
sudo /etc/init.d/postfix start sudo /etc/init.d/postfix stop sudo /etc/init.d/postfix restart
postfix日志文件位置：/var/log/maillog
卸载sendmail
检查系统是否安装sendmail:
rpm –qa |grep sendmail
如果存在，卸载之
rpm -e sendmail --nodeps
安装cyrus-sasl-2.1.23
由于在centos 源中不存在，直接通过源码安装cyrus-sasl-2.1.23.tar.gz
下载地址
./configure &&make &&make install
这个软件包的作用就是postfix邮件服务器的认证，因为如果转发外部的邮件，必须使用smtpd_recipient_restrictions选项的值check_relay_domains或者是reject_unauth_destination，二者必须选一个，而relay_damains手工来配置允许的邮件域太麻烦，所以就选用sasl认证
修改sasl配置:/etc/sysconfig/saslauthd为
# Directory in which to place saslauthd's listening socket, pid file, and so # on. This directory must already exist. START=yes SOCKETDIR=/var/run/saslauthd # Mechanism to use when checking passwords. Run "saslauthd -v" to get a list # of which mechanism your installation was compiled with the ablity to use. #MECH="pam" MECHANISMS="pam" #使用linux自身的用户认证 # Additional flags to pass to saslauthd on the command line. See saslauthd(8) # for the list of accepted flags. #FLAGS=
然后重启saslauthd:
sudo /etc/init.d/saslauthd restart
测试saslauthd生效：
/usr/sbin/testsaslauthd -u liyg -p liyangguang
将sasl与postfix结合
在main.cf文件中加入：
#added by liyangguang smtpd_recipient_restrictions = permit_mynetworks,permit_sasl_authenticated,reject_unauth_destination #smtpd_client_restrictions = permit_sasl_authenticated smtpd_sasl_auth_enable = yes broken_sasl_auth_clients = yes smtpd_sasl_security_options = noanonymous
重启postfix ：sudo /etc/init.d/postfix restart。
然后通过foxmail客户端配置smtp服务器地址，测试发送邮件是否成功
参考资料：
http://yahoon.blog.51cto.com/13184/40091
http://www.postfix.org/RESTRICTION_CLASS_README.html
http://publish.it168.com/2006/0221/20060221219401.shtml
【编程之美】单链表是否存在环以及环入口的位置【转载】
五 26th
原文地址：http://blog.csdn.net/ssfp8762/archive/2009/07/08/4331419.aspx
有一个单链表，其中可能有一个环，也就是某个节点的next指向的是链表中在它之前的节点，这样在链表的尾部形成一环。
1、如何判断一个链表是不是这类链表？
2、如果链表为存在环，如果找到环的入口点？
扩展：判断两个单链表是否相交，如果相交，给出相交的第一个点。
解答：
一、判断链表是否存在环，办法为：
设置两个指针(fast, slow)，初始值都指向头，slow每次前进一步，fast每次前进二步，如果链表存在环，则fast必定先进入环，而slow后进入环，两个指针必定相遇。
二、链表环入口的位置计算
当fast若与slow相遇时，slow肯定没有走遍历完链表，而fast已经在环内循环了n圈(1<=n)。假设slow走了s步，则fast走了2s步（fast步数还等于s 加上在环上多转的n圈），设环长为r，则：
2s = s + nr
s= nr
设整个链表长L，入口环与相遇点距离为x，起点到环入口点的距离为a。
a + x = nr
a + x = (n – 1)r +r = (n-1)r + L – a
a = (n-1)r + (L – a – x)
(L – a – x)为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点，于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。
扩展问题：
判断两个单链表是否相交，如果相交，给出相交的第一个点（两个链表都不存在环）。
比较好的方法有两个：
一、将其中一个链表首尾相连，检测另外一个链表是否存在环，如果存在，则两个链表相交，而检测出来的依赖环入口即为相交的第一个点。
二、如果两个链表相交，那个两个链表从相交点到链表结束都是相同的节点，我们可以先遍历一个链表，直到尾部，再遍历另外一个链表，如果也可以走到同样的结尾点，则两个链表相交。
这时我们记下两个链表length，再遍历一次，长链表节点先出发前进(lengthMax-lengthMin)步，之后两个链表同时前进，每次一步，相遇的第一点即为两个链表相交的第一个点。
socket编程中如何区分不同的网络连接
五 25th
在网络编程中，服务器程序的代码结构一般如下：
socket() -> bind() -> listen() -> accept()
当有一个新的客户端连接时，accept建立一个新的socket，然后将sockfd返回，接下来数据的发送和接收就都在这个sockfd中进行
但是一直有一个问题我比较困惑：在服务器端，当有数据到达时，协议栈是如何将数据传递到正确的sockfd的呢（服务器端存在多个已连接的客户端）？因为不同的网络连接是使用同一个监听端口，如80端口，不可能为每一个建立的连接分配一个端口（事实也不是这样）；
上网搜寻一下，一个比较合理的解释：使用网络连接的源ip+源port来区分不同的数据连接，本身TCP协议中提供，而且可以唯一标识网络连接，因为不可能同一个客户端使用同一个端口进行来连接server的。
平面中两点的最近距离与最远距离
五 23rd
今天看编程之美，看到求平面中两点的最近距离，书中给出了O(nlogn)算法，主要是采用分治的方法来做的，首先将平面的点按x坐标分为两部分，分别求最近点对，然后是合并；合并过程中对于两个点分别在两个区域的分析非常巧妙，有效地减少了需要比较的点对的个数。
在poj中对应的题目3714
然后又看到了扩展问题：如何求平面中最远的两个点的距离
这个就不能继续套用“最近距离点对”的分治策略，上网查了下，原来是使用凸包算法+旋转卡壳算法，poj中对应的题目是2187和3608
这里简单记录下，明天做下这两个题目
关于凸包算法和旋转卡壳算法的介绍：
http://yishan.cc/blogs/gpww/archive/2011/02/16/graham-s-scan.aspx
http://www.cppblog.com/staryjy/archive/2010/09/25/101412.html
http://yishan.cc/blogs/gpww/archive/2011/02/15/1787.aspx
ax操作的时间复杂度为
近期评论