Apollo Connecting the World

Diligence and Intelligence

Archive for the ‘Computer Science’ Category

[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 »

发现这篇文章没有在自己的地盘上贴过,补一下。这是五月份的时候带队去 I/O,考虑到团内大部分人都没有去过硅谷,安排了不少参访行程。回来后,在内部写了一篇总结 (26000 字呢),删节后供 ifanr 发布

sv

五 月份,我和大约 10 位豌豆借着参加 Google I/O 的机会,花了一些时间在硅谷游荡。大部分豌豆都是第一次到硅谷,所以我们前后安排了对 13 家科技公司的拜访,帮助大家了解更多不同的做事方式,包括 Flipboard、Facebook、Google、LinkedIn、Evernote、Tango、Backplane、Mozilla、 Twitter、Pinterest、Asana、Dropbox、Zynga 等。

Read the rest of this entry »

Written by apollozhao

2013/08/16 at 06:28

[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]常用算法经典代码(C++版)

leave a comment »

常用算法经典代码(C++版)

一、快速排序

void qsort(int x,int y) //待排序的数据存放在a[1]..a[n]数组中

{int h=x,r=y;

int m=a[(x+y)>>1]; //取中间的那个位置的值

Read the rest of this entry »

Written by apollozhao

2012/10/24 at 04:05

[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]有关如何入门ACM

leave a comment »

一些题外话

首先就是我为什么要写这么一篇日志。原因很简单,就是因为前几天有个想起步做 ACM人很诚恳的问我该如何入门。其实就现在而言,我并不是很想和人再去讨论这样的话题,特别是当我发现我有很多的东西要学的时候,我实在是不想花太多的 时间在这种问题上。但是我当年也是纯凭热情搞ACM过来的,实在是不忍心打击一个同样有着满腔热情的起步者。所以干脆就多花点时间,总结一下我的一些观点 和看法,以后再让人问起这个问题的时候,也好不用再重复什么了。

其次,我在这篇文章中并不打算探讨特别细节的问题,比如说如果某些人想从中 得到诸如“该看哪本书入门比较好”或者“动态规划、搜索、图论该怎么学”之类问题的答案,恐怕要让您失望了。我觉得书和方法都是因人而异,对自己最好的方 法需要靠自己去摸索,抄别人是抄不来的。更何况当初我起步的时候也几乎是一个人单干,没什么人推荐好书之类,都是搜到哪本书里有我想看的东西然后就抓过来 看,感觉不行就再换一本。很多众口相传的好书,我第一次看的时候,其实里面绝大部分的内容我已经都学过了,所以这种书籍对初学者的作用,我本人并没有切身 的体会,而且也没有过相关的教学经验,所以不敢随意评价。

Read the rest of this entry »

Written by apollozhao

2012/06/15 at 04:00

Posted in Computer Science, Study

Tagged with , , , ,