Google今年2011笔试题暗示搞软件没前途,囧

今天晚上Google的2011年校园招聘宣讲会分别在北大和清华举行,其中北大本来是350人的会场,去了大约600多人,爆满,那场面绝对是人山人海,彩旗飘飘。经过了大约一个小时多的宣讲和问答,开始现场笔试环节,一共10个选择题和三个算法题,只有选择题答对了6个以上的人才有机会让面试官看你后面的算法题。然后明天下午会通知笔试通过的人进行面试,Google的效率就像其搜索引擎一样迅速,效率可见一般。

其中前10个选择题中有一个特别雷人的,题如下:

现在北京有一套房子,价格200万,假设房价每年上涨10%,一个软件工程师每年固定能赚40万。如果他想买这套房子,不贷款,不涨工资,没有其他收入,每年不吃不喝不消费,那么他需要几年才能攒够钱买这套房子?
A, 5年
B, 7年
C, 8年
D, 9年
E, 永远买不起

继续阅读

海量数据处理专题(四)——Bit-map

【什么是Bit-map】

所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。

如果说了这么多还没明白什么是Bit-map,那么我们来看一个具体的例子,假设我们要对0-7内的5个元素(4,7,2,5,3)排序(这里假设这些元素没有重复)。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数,我们就只需要8个Bit(1Bytes),首先我们开辟1Byte的空间,将这些空间的所有Bit位都置为0(如下图:)

继续阅读

一个易用,高效,精确的纳秒级C#时间计数器

我们在平时的项目中,时常会遇到这样的问题,当我们要评价一个算法的好坏时(这里指的是时间复杂度量级相同的两个算法);当我们要测试一段代码的性能时。。。我们都需要一个高精度的时间。如何来得到一个高精度的时间,而且又不影响我们的测试准确性呢?平时大家可能采用的方法是:new两个time,然后两个Time相减,得到一个TimeSpan,这样就可以得到一个毫秒级的时间(当然了,这个是一个并不精确的毫秒级时间),但是,那如果你要求的精度更好,需要达到微秒,纳秒级呢?这时候使用系统提供的Time类就不行了。

我曾经也遇到过类似的问题,于是在这里就封装了自己的Code,提供一个使用方便,高效,精确的纳秒级计时器。

我采用的方法是使用两个Win32函数来实现的:

QueryPerformanceCounter():此函数用于获取精确的性能计数器数值。

QueryPerformanceFrequency():返回硬件支持的高精度计数器的频率(你可以理解为查询CPU的主频)。
这两个函数是Win32标准库函数,我们要使用它就需要P/Invoke技术。P/Invoke技术是由微软提供的用于Native和Managed之间资源和函数互访的一项技术。在.net平台中就是DllImport。 继续阅读

海量数据处理专题(三)——Hash

【什么是Hash】

Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

HASH主要用于信息安全领域中加密算法,它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做HASH值. 也可以说,hash就是找到一种数据内容和数据存放地址之间的映射关系。 继续阅读

海量数据处理专题(二)——Bloom Filter

【什么是Bloom Filter】

Bloom Filter是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的:在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合(false positive)。因此,Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下,采用Bloom Filter的数据结构,可以通过极少的错误换取了存储空间的极大节省。 这里有一篇关于Bloom Filter的详细介绍,不太懂的博友可以看看。

【适用范围】

可以用来实现数据字典,进行数据的判重,或者集合求交集 继续阅读

海量数据处理专题(一)——开篇

大数据量的问题是很多面试笔试中经常出现的问题,比如baidu google 腾讯 这样的一些涉及到海量数据的公司经常会问到。

下面的方法是我对海量数据的处理方法进行了一个一般性的总结,当然这些方法可能并不能完全覆盖所有的问题,但是这样的一些方法也基本可以处理绝大多数遇到的问题。下面的一些问题基本直接来源于公司的面试笔试题目,方法不一定最优,如果你有更好的处理方法,欢迎与我讨论。

本贴从解决这类问题的方法入手,开辟一系列专题来解决海量数据问题。拟包含 以下几个方面。

  1. Bloom Filter
  2. Hash
  3. Bit-Map
  4. 堆(Heap)
  5. 双层桶划分
  6. 数据库索引
  7. 倒排索引(Inverted Index)
  8. 外排序
  9. Trie树
  10. MapReduce

在这些解决方案之上,再借助一定的例子来剖析海量数据处理问题的解决方案。欢迎大家关注。

Top K算法详细解析—百度面试

问题描述:

这是在网上找到的一道百度的面试题:

搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。假设目前有一千万个记录,这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门。请你统计最热门的10个查询串,要求使用的内存不能超过1G。


问题解析:

【分析】:要统计最热门查询,首先就是要统计每个Query出现的次数,然后根据统计结果,找出Top 10。所以我们可以基于这个思路分两步来设计该算法。下面分别给出这两步的算法: 继续阅读

搜狗面试剖析

 1.为什么基类的析构函数是虚函数?
答:编译器总是根据类型来调用类成员函数。但是一个派生类的指针可以安全地转化为一个基类的指针。这样删除一个基类的指针的时候,C++不管这个指针指向一个基类对象还是一个派生类的对象,调用的都是基类的析构函数而不是派生类的。如果你依赖于派生类的析构函数的代码来释放资源,而没有重载析构函数,那么会有资源泄漏。所以建议的方式是将析构函数声明为虚函数。如果你使用MFC,并且以CObject或其派生类为基类,那么MFC已经为你做了这件事情;CObject的析构函数是虚函数。一个函数一旦声明为虚函数,那么不管你是否加上virtual 修饰符,它在所有派生类中都成为虚函数。但是由于理解明确起见,建议的方式还是加上virtual 修饰符。
 2.Union和sturct区别(是以选择题形式出现,一个具体的例子)
答:1. struct和union都是由多个不同的数据类型成员组成, 但在任何同一时刻, union中只存放了一个被选中的成员, 而struct的所有成员都存在。在struct中,各成员都占有自己的内存空间,它们是同时存在的。一个struct变量的总长度等于所有成员长度之和。在Union中,所有成员不能同时占用它的内存空间,它们不能同时存在。Union变量的长度等于最长的成员的长度。 2. 对于union的不同成员赋值, 将会对其它成员重写, 原来成员的值就不存在了, 而对于struct的不同成员赋值是互不影响的。
继续阅读