ITeye博客

Algorithm

共 57 篇文章

Skpi List跳表

为什么选择跳表 目前经常使用的平衡数据结构有:B树,红黑树,AVL树,Splay Tree, Treep等。 想象一下,给你一张草稿纸,一只笔,一个编辑器,你能立即实现一颗红黑树,或者AVL树 出来吗? 很难吧,这需要时间,要考虑很多细节,要参考一堆算法与数据结构之类的树, 还要参考网上的代码,相当麻烦。 用跳表吧,跳表是一种随机化的数据结构,目前开源软件 Redis 和 LevelDB 都有用到它, 它的效率和红黑树以及 AVL 树不相上下,但跳表的原理相当简单,只要你能熟练操作链表, 就能轻松实现一个 SkipList。 有序表的搜索 考虑一个有序表: 从该有序表中搜索元素 < 23, …

2013-10-10 13:56 · Algorithm

DP模式

DP也练了一部分,找感觉。 说一下VIJOS上的。 ◆线性连接性的问题(包括分配问题,转换问题,连接问题,及宏观扩展),这样的例子比较多,方程就是由一维来记录处理到的线性位置作为阶段,然后用额外的未来记录分配的情况,之前临近的连接情况等,这样一个一个把状态连接起来得最优 例子: P1323化工厂装箱员 P1386矿工配餐 P1417魔法塔防 P1421更换轮胎 P1456最小总代价 P1470教主的后花园 P1002过河 ◆线性的选择问题 这种就是类似最长不上升子序列之类的那种,当处理到i时,在前面选择一个可能的情况跟他连起来,例子比如说: P1098合唱队形 P1331看球的巴士 ◆开放的…

2013-09-16 14:10 · Algorithm

2012年CS毕业生

1,简介 毕业答辩搞定,总算可以闲一段时间,把这段求职经历写出来,也作为之前三个半月的求职的回顾。 首先说说我拿到的offer情况: 微软,3面->终面,搞定 百度,3面->终面,口头offer 搜狗,2面,悲剧 腾讯,1面,悲剧 布丁移动,3面,搞定 涂鸦游戏,3面,搞定 友盟,3面->CEO面,搞定 雅虎,4面->终面,搞定 微策略,2面,悲剧 人民搜索,3面->终面,搞定 人人,2面+终面+Special面,搞定 Google,7面,搞定 求职经历分为 定位 、 准备 、 简历 、 笔试 和 面试 这五个部分,大家挑感兴趣的看就成。 我的求职经历适用但不限于码农,不适用与企事业单位(据…

2013-09-09 12:18 · Algorithm

Google仍鸡蛋[DP]

这道题是说,100层楼,两个一模一样的鸡蛋,某层之上扔鸡蛋就会碎。问要测试多少次才能找出这层楼来。我曾经在 去年初的这篇文章里面讨论过这个问题的解法 ,因为只想记录一下思路和讨论过程,写得很简略。现在,我想重新整理一下这个问题,再稍稍扩展和挖掘一下。希望可以用尽可能清晰易懂的描述,把这个问题的前后说清楚。 现在只有两个鸡蛋,而算法必须是可行的,就是说要能找出这一层来,所以你得假设你的运气最差,这就意味着,我求解的是在每种扔鸡蛋的策略下都有一个需要扔的次数的最大值,而现在需要求解的是这些最大值中的最小值的问题。如果我只有一枚鸡蛋,这就意味着,我只能从第一层开始老老实实地一层一层往上试,不能越层…

2013-09-05 11:08 · Algorithm

求字符串组合数

#include<iostream> #include<vector> #include<cstring> using namespace std; #include<assert.h> void Combination(char *string ,int number,vector<char> &result); void Combination(char *string) { assert(string != NULL); vector<char> result; int i , length = strlen(string); for(i = 1 ; i <= length ; ++i…

2013-08-29 10:57 · Algorithm

面试小集合

微软十五道面试题 **1、**有一个整数数组,请求出两两之差绝对值最小的值, 记住,只要得出最小值即可,不需要求出是哪两个数。 **2、**写一个函数,检查字符是否是整数,如果是,返回其整数值。 (或者:怎样只用4行代码编写出一个从字符串到长整形的函数?) **3、**给出一个函数来输出一个字符串的所有排列。 **4、**请编写实现malloc()内存分配函数功能一样的代码。 给出一个函数来复制两个字符串A和B。字符串A的后几个字节和字符串B的前几个字节重叠。 **5、**怎样编写一个程序,把一个有序整数数组放到二叉树中? **6、**怎样从顶部开始逐层打印二叉树结点数据?请编程。 **7、…

2013-06-09 10:35 · Algorithm

Twitter的系统编程

http://monkey.org/~marius/talks/twittersystems/#1 英文 http://www.csdn.net/article/2012-11-21/2812033-Systems-Programming-at-Twitter/2 【译文】

2013-06-09 10:20 · Algorithm · Data structure

概率随机问题

http://www.cnblogs.com/yysblog/archive/2012/06/27/2566276.html 1、问题定义可以简化如下:在不知道文件总行数的情况下,如何从文件中随机的抽取一行? 首先想到的是我们做过类似的题目吗?当然,在知道文件行数的情况下,我们可以很容易的用C运行库的rand函数随机的获得一个行数,从而随机的取出一 行,但是,当前的情况是不知道行数,这样如何求呢?我们需要一个概念来帮助我们做出猜想,来使得对每一行取出的概率相等,也即随机。这个概念即 蓄水池抽样(Reservoir Sampling) 。 有了这个概念,我们便有了这样一个解决方案:定义取出的行…

2013-05-27 21:20 · Algorithm · Probabilistic

概率相关问题

1、一个随机数产生器以概率p生成0,以概率(1-p)生成1,怎样生成等概率的0和1? 如果用这个随机数产生器产生两个位,出现00的概率为,出现01的概率为 ,出现10的概率为 ,出现11的概率为。看到没有,出现01和10的概率相等。那么我们就可以用这个随机数生成器每次产生2位,直到产生的是01或者10,当为01时,输出0,当为10时输出1。 问题扩展:还是给这么一个随机数产生器,要求等概率地产生 。 解法1:每次产生n位,当为仅第一位是1,其他是0时输出1,当仅有第二位是1,其他位是0是输出2,……当仅有第n位是1,其他是0时输出n。(这个解法有点0疼,好多信息都浪费了,复杂度太高了) 解法…

2013-05-27 20:48 · Algorithm · Probabilistic

一次遍历等概率选取字符串中的某个字符

http://blog.chinaunix.net/uid-7921481-id-3022614.html 存在一个等概率的0、1发生器。 给一个文本流,给定一个指定的字符'x',写一个函数,等概率地返回'x'的一个文本流偏移(就是'x'在字符串中的位置,比如文本为 axbx,那么x的偏移为{1, 3},最后你需要获得1或者3,概率分别为1/2 假设文本流每个字符1字节) ============================基本问题========================================= -------------------------------------…

2013-05-27 19:26 · Algorithm · Probabilistic

桶排序

桶排序 (Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。 例如要对大小为[1..1000]范围内的n个整数A[1..n]排序,可以把桶设为大小为10的范围,具体而言,设集合B[1]存储[1..10]的整数,集合B[2]存储(10..20]的整数,……集合B[i]存储((i-1)*10, …

2013-05-20 15:17 · Algorithm · Data structure

google面试

.谷歌面试题:给定能随机生成整数 1 到 5 的函数,写出能随机生成整数 1 到 7 的函数。 回答:此题的关键是让生成的 1 到 7 的数出现概率相同。 只要我们可以从 n 个数中随机选出 1 到 n 个数,反复进行这种运算,直到剩下最后一个数 即可。 我们可以调用 n 次给定函数,生成 n 个 1 到 5 之间的随机数,选取最大数所在位置即 可满足以上要求。 例如 初始的 7 个数[1,2,3,4,5,6,7]. 7 个 1 到 5 的随机数[5,3,1,4,2,5,5] 那么我们保留下[1,6,7], 3 个 1 到 5 的随机数[2,4,1] 那么我们保留下[6] 6 就是我们这次生…

2013-05-07 11:23 · Algorithm

抛硬币 直到连续出现两次字为止

题目: [plain] view plain copy 假设有一个硬币,抛出字(背面)和花(正面)的概率都是0.5,而且每次抛硬币与前次结果无关。现在做一个游戏,连续地抛这个硬币,直到连续出现两次字为止,问平均要抛多少次才能结束游戏?注意,一旦连续抛出两个“字”向上游戏就结束了,不用继续抛。 上面这个题目我第一次见到是在pongba的TopLanguage的一次 讨论 上,提出问题的人为Shuo Chen,当时我给出了一个解法,自认为已经相当简单了,先来考虑一下抛硬币的过程:首先先抛一枚硬币,如果是花,那么需要重头开始;如果是字,那么再抛一枚硬币,新抛的这枚如果也是字,则游戏结束,如果是花,…

2013-05-03 21:54 · Algorithm · Probabilistic

taobao

1.n个节点,网络上广播。广播算法:主动发给邻居一条消息。其它节点收到消息后,会给出发给他的邻居外的所有邻居发送一条消息,发完消息后就不再有动作。如果这个网络是一棵树(n-1),完全图,超立方体。。。发送消息的复杂度是多少? 2.12个人排队,前排的比后排的矮,且每排都从左到右有序。问有多少种排法。 3.将windows和unix格式混合的文本文件a.txt转换成纯unix格式的文本文件。 4.通过ssh登陆linux服务器启动一个长时间运行的进程,放在后台运行,做也号:%1,如何避免断开ssh而导致这个进程终止。 nohup命令:如果你正在运行一个进程,而且你觉得在退出帐户时该进程还不会结…

2013-05-03 13:39 · Algorithm

google笔试

1、假设在n进制下,下面的等式成立,n值是(d) 567*456=150216 a、 9 b、 10 c、 12 d、 18 2、文法G:S->uvSvu|w所识别的语言是:(d) a、uvw*vu b、(uvwvu)* c、uv(uv)*wvu(vu)* d、(uv)*w(vu)* 3、如下程序段输出是:(c) char str[][10]={"Hello","Google"}; char *p=str[0]; count<<strlen(p+10); a、0 b、5 c、6 d、10 4、cnt=0 while(x!=1){ cnt=cnt+1; if(x&1==0) x=x/2; el…

2013-05-03 12:54 · Algorithm

ms 两个数组,从每个数组中取一个数相加,求最大的前k个和

两个数组,从每个数组中取一个数相加,求最大的前k个和 比如: 数组A:1,2,3 数组B:4,5,6 则最大的前2个和:9,8。 ps:结果放到数组C[k]中 http://www.cnblogs.com/372465774y/archive/2012/07/09/2583866.html Sequence Time Limit:6000MS Memory Limit:65536K Total Submissions:5137 Accepted:1572 Description Given m sequences, each contains n non-negative integer. …

2013-05-02 20:16 · Algorithm

平面分割

分割平面和空间的相关公式 今天遇到一个折线切割平面的问题,习惯性的百度了一下,把自己搜集到的资料整理了一下。这些东西都是些数学问题,在另一方面证明了数学的神奇和博大精深。很佩服先贤们能够推到出这么神奇的公式出来。 这类题目相对而言比较简单,如果知道了递推公式剩下的事情就非常简单了。所以递推公式是最重要的。这一个类型的题目还是从简单的入手,才容易发现规律。至于这些题目的代码我在这就不写了,相信各位研究完递推公式之后就能够很轻松的写出来。 (1) n条直线最多分平面问题 题目大致如:n条直线,最多可以把平面分为多少个区域。 析:可能你以前就见过这题目,这充其量是一道初中的思考题。当有n-1条直线…

2013-05-02 15:51 · Algorithm

12个高矮不同的人排成两排

作者:baihacker 来源:http://hi.baidu.com/feixue http://hi.csdn.net/baihacker 问题描述: 12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种? 这个笔试题,很YD,因为把某个递归关系隐藏得很深. 问题分析: 我们先把这12个人从低到高排列,然后,选择6个人排在第一排,那么剩下的6个肯定是在第二排. 用0表示对应的人在第一排,用1表示对应的人在第二排,那么含有6个0,6个1的序列,就对应一种方案. 比如000000111111就对应着 第一排:0 1 2 3 4 5 第二排:…

2013-04-28 17:02 · Algorithm

F(n)完全覆盖中的计数问题

完全覆盖中的计数问题 山西省原平一中 任所怀 这几天阅读周沛耕老师主编的《数学兴趣与创造力》一书,读到“完全覆盖中的计数问题”这一节,感觉有点意思。于是自已试着做一个探索性研究,也不知会有什么新的发现,让我们带着一颗好奇的心开始我们的探索之旅。 完全覆盖指的是用一个长1宽2(以后记为1 2)的矩形小纸片去覆盖一个大小为 的矩形网格盘,要求小纸片不重叠、不伸出且不留空地,也就是不多不少恰好把矩形盘盖住。问这样的盖法有多少种? 处理这样的问题,我们当然是由易到难,由具体到抽象。先把这个大问题分解为几个小问题来逐步解决。 问题一:若矩形盘为 ,则盖法有多少种? 答:显然,如果k为奇数时,肯定无法完…

2013-04-28 15:47 · Algorithm

阿里巴巴笔试题

1、有一个虚拟存储系统,若进程在内存中占3页(开始时内存为空),若采用先进先出(FIFO)页面淘汰算法,当执行如下访问页号序列后1,2,3,4,5,1,2,5,1,2,3,4,5,会发生多少缺页? A、7 B、8 C、9 D、10 2、设有一个顺序栈S,元素s1、s2、s3、s4、s5、s6依次进栈,如果6个元素的出栈顺序为s2、s3、s4、s6、s5、s1,则顺序栈的容量至少应为多少? A、2 B、3 C、4 D、5 3、下列关于文件索引结构的叙述中,哪一个是错误的? A、采用索引结构,逻辑上连续的文件存放在连续的物理块中 B、系统为每个文件建立一张索引表 C、索引结构的优点是访问速度快,…

2013-04-28 13:04 · Algorithm