微信

使用微信服务,更方便

职友集>程序员面试题 > 名企开放性面试题集

名企开放性面试题集

2015-03-05 06:30:01 阅读( 91 )

1725人 收藏本页

标签:程序员面试题

1. [Google], map server用户太多,如何做来提高系统的性能?

1. ajax,可以不用用户每次都download整个map,他们已经使用
2. 使用middleware,来维护数据库链接,并且做load balance等等
3. 使用distributed system,来使不同的用户使用不同的server.
后来居然问怎么来devide,回答说根据不同的ip来区别不同的物理地址,
居然又追问,还有没有其他方法,回答说解析他们的httprequest,
看看所在的不同的时区,不同的语言,国家什么的,blabla
4. 增加server的memory,提高cpu性能,等硬件方面.
5. 提高数据库性能,给数据库做partition,blabla…

 

最重要的是要先找出性能瓶颈在哪里

 

2. how to make copy big file to many machines faster

 

3. 写代码的时候,往往会给array定一个max_number, 如果现实中有可能出现高于这个数字,怎么测试?比如找出邻近的wifi网络数,max_number再怎么大,总有可能超出,怎么测试呢?而且比如这种情况还很难模拟(很难在现场设几百个网络吧),怎么测试?不准用动态数组。

 

4. 对于common sense的问题,要有所准备,比如为什么要来FB?为什么离开上一家公司?你有什么改进FB产品的建议?等等。

 

5. 一台服务器每过三天就要挂一次,需要重启才能再次使用,每次重启需要一分钟的时间;问有什么方法能解决这个问题。

 

 

一些有用的网上资源

http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/

 

http://www.4shared.com/document/qzFCPK8f/101_Dynamite_Answers_t
http://www.4shared.com/document/SmfrgYjD/Career_-_201_Best_Ques
http://www.4shared.com/document/Eqg6xcuH/Knockout_answers_to_to

 

http://courses.csail.mit.edu/iap/interview/materials.php

 

推荐“A Collection of Dice Problems”,面试facebook时遇到不少概率题,都不超出这篇文章的思路和难度。

http://www.ibm.com/developerworks/aix/tutorials/au-memorymanage

Lock-free algorithms。推荐
http://www.ibm.com/developerworks/java/library/j-jtp04186/index

 

排序和binary search算法题,推荐http://www.cs.princeton.edu/introcs/42sort

 

http://www.cl.cam.ac.uk/~cwc22/hashtable/

 

C++里创建二维数组,http://www.codeproject.com/KB/cpp/arrayDinamic.aspx

 

关于DP http://people.csail.mit.edu/bdean/6.046/dp/

 

http://www.algolist.net/

http://cslibrary.stanford.edu/

http://www.cs.bell-labs.com/cm/cs/pearls/

http://www.cs.berkeley.edu/~vazirani/algorithms.html















 

Algorithm to learn:

Interval tree, segment tree 

TrieString search algorithms 

Facebook system design question from glassdoor

Design the Facebook Credit system which is a application where users can buy/trade virtual currency and can use the virtual currency to purchase Facebook services, like paid apps.

 

Design a system to detect typos and provide suggestions to users.

考虑用户的历史数据

http://norvig.com/spell-correct.html

 

How will you design TinyUrl?

 

How will you design facebook newsfeed. Focus was on a design which could handle the huge number of status updates and display them on each of the user’s friend’s wall.

 

Facebook system design question from careercup

 

 

Question: Design a component that implements the following functionality..
1) Record an Event (For the sake of simplicity, treat the Event as an integer code)

2) Return the number of Events recorded in the last one minute.

3) Return the number of Events recorded in the last one hour.
i.e implement the following interface

- Design the interface first
- Give the implementation detail.



Open ended question:
What if there isn’t enough storage available to store each individual event ?



 

Say you need to design a web application which needs to support friends of
friends function(like in linked in, when you search a person, it will show
you if this person is linked with you, your connection or your connections’
conection…), we expect to have millions of users and each user may have
thousands of friends, how would you design/implement this function to make
it scalable.

 

Design Farmville,

Consider only crops and animals for now.

Whats classes will you have?
How will you handle interactions between various objects?
What design patterns can you use?

How will you handle millions of users?

 

How will you design the backend for facebook. To handle millions of users. Explain the following transactions
1) Adding/Deleting a friend
2) Friend suggestions

What if you cannot store all users on one server?

 

一些大规模网站会用到的常用组件和技术。

Memcached参见http://tech.idv2.com/2008/08/17/memcached-pdf/

一些要点如下

一个典型的用例:
初始化一个Memcache的对象:
$mem = new Memcache;

连接到我们的Memcache服务器端,第一个参数是服务器的IP地址,也可以是主机名,第二个参数是Memcache的开放的端口:
$mem->connect(“192.168.0.200″, 12000);

保存一个数据到Memcache服务器上,第一个参数是数据的key,用来定位一个数据,第二个参数是需要保存的数据内容,这里是一个字符串,第三个参数是一个标记,一般设置为0或者MEMCACHE_COMPRESSED就行了,第四个参数是数据的有效期,就是说数据在这个时间内是有效的,如果过去这个时间,那么会被Memcache服务器端清除掉这个数据,单位是秒,如果设置为0,则是永远有效,我们这里设置了60,就是一分钟有效时间:
$mem->set(‘key1′, ’This is first value’, 0, 60);

从Memcache服务器端获取一条数据,它只有一个参数,就是需要获取数据的key,我们这里是上一步设置的key1,现在获取这个数据后输出输出:
$val = $mem->get(‘key1′);
echo ”Get key1 value: “ . $val;

现在是使用replace方法来替换掉上面key1的值,replace方法的参数跟set是一样的,不过第一个参数key1是必须是要替换数据内容的key,最后输出了:
$mem->replace(‘key1′, ’This is replace value’, 0, 60);
$val = $mem->get(‘key1′);
echo “Get key1 value: ” . $val;

同样的,Memcache也是可以保存数组的,下面是在Memcache上面保存了一个数组,然后获取回来并输出
$arr = array(‘aaa’, ’bbb’, ’ccc’, ’ddd’);
$mem->set(‘key2′, $arr, 0, 60);
$val2 = $mem->get(‘key2′);
print_r($val2);

现在删除一个数据,使用delte接口,参数就是一个key,然后就能够把Memcache服务器这个key的数据删除,最后输出的时候没有结果
$mem->delete(‘key1′);
$val = $mem->get(‘key1′);
echo “Get key1 value: ” . $val . ””;

最后我们把所有的保存在Memcache服务器上的数据都清除,会发现数据都没有了,最后输出key2的数据为空,最后关闭连接
$mem->flush();
$val2 = $mem->get(‘key2′);
echo “Get key2 value: ”;
print_r($val2);
echo ””;

在多机并行的时候,有一个严重的问题是在增减机器后,会出现大范围的缓存失效(key被映射到不同的机器上),解决方法是使用consistent hashing, 介绍在:

http://tech.idv2.com/2008/07/24/memcached-004/#content_2_6

Consistent Hashing的简单说明

Consistent Hashing如下所示:首先求出memcached服务器(节点)的哈希值, 并将其配置到0~2^32的圆(continuum)上。 然后用同样的方法求出存储数据的键的哈希值,并映射到圆上。 然后从数据映射到的位置开始顺时针查找,将数据保存到找到的第一个服务器上。 如果超过2^32仍然找不到服务器,就会保存到第一台memcached服务器上。

 

图4 Consistent Hashing:基本原理

从上图的状态中添加一台memcached服务器。余数分布式算法由于保存键的服务器会发生巨大变化 而影响缓存的命中率,但Consistent Hashing中,只有在continuum上增加服务器的地点逆时针方向的 第一台服务器上的键会受到影响。

 

图5 Consistent Hashing:添加服务器

因此,Consistent Hashing最大限度地抑制了键的重新分布。 而且,有的Consistent Hashing的实现方法还采用了虚拟节点的思想。 使用一般的hash函数的话,服务器的映射地点的分布非常不均匀。 因此,使用虚拟节点的思想,为每个物理节点(服务器) 在continuum上分配100~200个点。这样就能抑制分布不均匀, 最大限度地减小服务器增减时的缓存重新分布。

通过下文中介绍的使用Consistent Hashing算法的memcached客户端函数库进行测试的结果是, 由服务器台数(n)和增加的服务器台数(m)计算增加服务器后的命中率计算公式如下:

(1 – n/(n+m)) * 100

 

另外还有一个需求是将memcache中的数据持久化,可以考虑定期持久化。

 

关于NoSQL的文章

http://sebug.net/paper/databases/nosql/Nosql.html

来自IT公司面试手册

下一篇:近段时间面试过的一些技术问题包括Java, 数据库和算法方面

上一篇:DisigenPattern设计模式

亲~ 如果您有更好的答案 可在评论区发表您独到的见解。

您想查看更多的信息: 面试题