Apollo Connecting the World

Diligence and Intelligence

Posts Tagged ‘computer science

[zz]大数据量,海量数据 处理方法总结

leave a comment »

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

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

1.Bloom filter

适用范围:可以用来实现数据字典,进行数据的判重,或者集合求交集

基本原理及要点:
对 于原理来说很简单,位数组+k个独立hash函数。将hash函数对应的值的位数组置1,查找时如果发现所有hash函数对应位都是1说明存在,很明显这 个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字,因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter,用一个counter数组代替位数组,就可以支持删除了。

还有一个比较重要的问题,如 何根据输入元素个数n,确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况 下,m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些,因为还要保证bit数组里至少一半为0,则m应 该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。

举个例子我们假设错误率为0.01,则此时m应大概是n的13倍。这样k大概是8个。

Read the rest of this entry »

Written by apollozhao

2013/12/13 at 07:05

[zz]计算机算法和竞赛教材介绍

leave a comment »

现在公认最好的入门书籍是“白书”《算法竞赛入门经典》(建议每位队员都应该要买这本书),之后应该就是《算法导论》和《算法艺术与信息学竞赛》了,另外《组合数学》和《离散数学》也是值得学习的,这个对训练逻辑思维、数学思维有很大的好处,比如东欧强队都非常注重这方面的训练,而国内注重的是算法训练。

关于题目的好书有:《ACM国际大学生程序设计竞赛题解(1) 》《ACM国际大学生程序设计竞赛题解(2)》《ACM国际大学生程序设计竞赛亚洲区预选赛真题题解》

关于OJ做题的好书有《挑战编程:程序设计竞赛训练手册》,另外一本国内的《程序设计导引及在线实践》

以下来自网络转载:

acm算法书籍收藏推荐

我常感叹到,学计算机的人是幸福的,因为在这个领域中有如此多的通俗易懂(相对来说)的经典好书,你需要做的只是坚持把它们一本一本读下去而已。学力学就没有这样的好事了(抱怨一下),除了论文就是论文,满篇公式,晦涩坚深,真不是给人看的(虽然我也没看过几篇)。在这里列出一些我看过或者准备看的算法书籍,以供参考。

Read the rest of this entry »

Written by apollozhao

2013/02/19 at 14:07

[zz]数据结构+算法面试100题~~~摘自CSDN,作者July

with one comment

Also see these 2 links:

https://apollozhao.wordpress.com/2011/05/20/zz%E5%90%84%E5%A4%A7%E5%85%AC%E5%8F%B8%EF%BC%88google%EF%BC%8Cmicrosoft%EF%BC%8Cbaidu%EF%BC%8C-microsoft-research-asia-etc-%EF%BC%89%E5%AE%9E%E4%B9%A0%E7%94%9F%E9%9D%A2%E8%AF%95%E9%A2%98%E6%80%BB/

https://apollozhao.wordpress.com/2012/03/31/zz%E9%87%8D%E7%A3%85%E5%88%86%E4%BA%AB%EF%BC%9A%E5%BE%AE%E8%BD%AF%E7%AD%89%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95%E9%9D%A2%E8%AF%95100%E9%A2%98%E5%85%A8%E9%83%A8%E7%AD%94%E6%A1%88/

This post has something more at the end.

——

1.把二元查找树转变成排序的双向链表(树)
题目:
输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点,只调整指针的指向。
10
/ /
6  14
/ / / /
4  8 12 16
转换成双向链表
4=6=8=10=12=14=16。

首先我们定义的二元查找树 节点的数据结构如下:
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
2.设计包含min函数的栈(栈)
定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。
3.求子数组的最大和(数组)
题目:
输入一个整形数组,数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。

Read the rest of this entry »

[zz]APL — The God’s Language 上帝的编程语言

leave a comment »

There are three things a man must do
Before his life is done;
Write two lines in APL,
And make the buggers run.
— Stan Kelly-Bootle, The Devil’s DP Dictionary, 1981
这几天大师兄没来实验室,问了下老板才发现是参加ICFP比赛去了(一个关于functional programming language的比赛)。说到FP,老板饶有兴致地向我们介绍了APL这门语言。APL的全称就叫A Programming Language, 一般一个传奇性的东西名字都普通得不能再普通,就好比武侠小说里一把牛逼的宝剑上刻的名字是“无名”这种情况。当时看了下wiki百科,瞬间就被震到了, 因为这是一门比lisp,scheme都还要再high-level的语言,我老板称它为”The God’s Language”。当你看到下面的介绍时,就会发现用这种语言写程序的人,要么是天才,要么是疯子。

每种程序语言都会吹嘘这门语言和其他语言在哪些方面上有多么多么不同,但是当你看到一个APL程序的时候,你会发现这尼玛才是真正的不同!一个APL程序根本就长得很怪异,像一些代数公式一样。当你想要写APL程序的时候,还需要准备一个专门的APL键盘,这种键盘长得下面这个样子:

Read the rest of this entry »

Written by apollozhao

2012/07/19 at 02:17

[zz]UIUC某童鞋收集的代码合集,大赞啊!

leave a comment »

https://netfiles.uiuc.edu/jbhuang1/www/resources/vision/index.html

Computer Vision Resources

Maintained by Jia-Bin Huang

Submit resource links here

Lastest Update: July 4, 2011

Read the rest of this entry »

Written by apollozhao

2012/04/29 at 03:19

Posted in Computer Science

Tagged with , ,

算法和数据结构的可视化演示

leave a comment »

Written by apollozhao

2011/06/16 at 12:31

[zz]各大公司(Google,Microsoft,Baidu, Microsoft Research Asia etc.)实习生面试题总汇

leave a comment »

from: http://blog.renren.com/share/228066793/6584972503

1.把二元查找树转变成排序的双向链表(树)

题目:

输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。

要求不能创建任何新的结点,只调整指针的指向。

10

/ \

6  14

/ \ / \

4  8 12 16

转换成双向链表

4=6=8=10=12=14=16。

首先我们定义的二元查找树 节点的数据结构如下:

struct BSTreeNode

{

int m_nValue; // value of node

BSTreeNode *m_pLeft; // left child of node

BSTreeNode *m_pRight; // right child of node

};

Read the rest of this entry »

Written by apollozhao

2011/05/20 at 20:23