苏格兰的紫杉木
paramore · 共 62 篇文章
日程安排问题
<算法基础>上的贪婪算法讲的真是好啊,分析的很精到,例子也很实际,遇到了一个新问题: 日程安排,n个日程,以及数组d,d[i]表示任务i的完成期限,数组g,g[i]表示i在d[i]前完成可以获得的收益,求最大收 益序列。 n^2的方法不说了,先快排g,降序,按照g顺序把遍历到的每个i插入数组j中,用并查集记录i的位置变化,最终时间复杂度O(nlogn)+O(n)<并查集的平摊复杂度> 具体实现后面贴上,此处先mark之 八卦一下,Gilles的<算法基础>我觉得甚至比算法导论还要好,贪心以及概率算法讲的尤其好
2012-03-27 22:57 · 说的是算法 · 评论(0)
被译文骗了个球的题目
看到一道题目,开始挺昏沉,加上翻译是在碉堡,没理解,后来大悟,这个题目编程之美上有嘛,就是个位操作统计个数的问题,easy: 一个数组A[1,n]能容纳n个数字,现将0到n这n+1个数字,随机的放入到数组中。最后会有一个数字没有进入数组。现在让你找出这个数字。但是有如下的限制,不能直接访问数组的整个元素,只能访问“A[i]的第j位”。写出代码找出该元素。能否将时间复杂度控制在O(n)。 然后一同比较最低位的1,o个数,每次去除一半的数据,得出: 线性复杂度,好了,收工。。。
2012-03-26 19:33 · interview baby · 评论(0)
在十年后依然是这个中国的中国里,怀念海子
哎,javaeye的编辑器再次让我崩溃了。。 怀念总是无限,唯有黑暗,给我无名的鼓励。 海子的诗句: 风后面是风,天空上面是天空,道路前面还是道路。 ——《四姐妹》 面朝大海,春暖花开 作者:海子 从明天起,做一个幸福的人 喂马、劈柴,周游世界 从明天起,关心粮食和蔬菜 我有一所房子,面朝大海,春暖花开 从明天起,和每一个亲人通信 告诉他们我的幸福 那幸福的闪电告诉我的 我将告诉每一个人 给每一条河每一座山取一个温暖的名字 陌生人,我也为你祝福 愿你有一个灿烂的前程 愿你有情人终成眷属 愿你在尘世获得幸福 我只愿面朝大海,春暖花开
2012-03-26 16:53 · life ft. time · 评论(0)
网络传输或写磁盘struct问题
写磁盘时应该注意: (引自短歌老大)直接fwrite并非不可以,只是可移植性太差。一般我们把数据写入文件都是为了进行数据交换,而直接把一个结构体用一次fwrite调用写入文件后是否可以再用一次fread正确读出取决于写入代码和读出代码编译时的字长、对齐逻辑和字节序等问题(这句话长点,大家凑合着看),严重影响可移植性。 把一个结构体写入文件时我觉得要注意以下几点: 1:要按不同域分别写入,以避免对齐方式的影响; 2:要设计好不同数据的长度,不要用sizeof来获得,以避免字长的影响; 3:要设计好字节顺序,每次写入一个字节,以避免 字节序的影响; 4:要存储逻辑结构而不是数据结构。比如当存储链…
2012-03-22 10:21 · interview baby · 评论(0)
海量数据处理中的hash单调问题
参加百度的面试,面试官提了一个海量数据问题,貌似自己的回答没能让人家满意,纠结点是: 大规模数据一般先用hash来分为小的数据段,然后在内存里处理之,然而如果hash后hash值还是各不相同(及其变态的情况),怎么办? 回来思考了下,下面是自己的想法,大家说说看: 如果一遍hash后,数据还是十分单调,可以采用另一个hash函数,或者不是单纯按照hash值分类,而是按照hash后的值范围,例如,原来hash(query)%100, 现在可以1-10为一个文件,间隔10建立子数据集,应该能解决问题吧? 轻拍。。。
2012-03-21 19:58 · interview baby · 评论(0)
设计数据访问策略
百度的面试题一道: 在处理磁盘数据时,需要首先将其读入内存才能进行处理。如果要读取的数据已经在内存中,则可以直接访问内存。通常来说内存是有限的,因此要读取新的数据时必须覆盖内存中一部分原有的数据。假设现在有n块同样大小的数据,内存一共可以容纳m块数据。现在给出一系列对这些数据的读取请求,要求它们必须按照给定的顺序被读取,同时要求读取磁盘的次数尽可能地少。请简述一个策略满足这样的要求。 解析:目标是最小化磁盘读取次数,分两部分: 内存中的m块数据按照LRU策略组织,由于已经给出了读取请求,或许可以进一步提高swap的效率, 磁盘上数据用B树或者其变种实现,最小化磁盘读取。
2012-03-20 22:43 · interview baby · 评论(0)
最in的女演员
立此存念; Dana Delany < Tombstone> Kate Beckinsale Rhona Mitra <oh i just love her> Scarlett Johansson Cameron Diaz Jessica Biel <blade> Camilla Belle <When a Stranger Calls> Renee Zellweger <Bridget Jones's Diary>
2012-03-08 14:33 · life ft. time · 评论(0)
通讯层与序列化
通讯层: 封装与网络通讯 传输数据相关的API,成熟的框架有mina等 序列化/反序列化: 这个多了 gpb,json等等 rpc: 我觉得这个是更多关系业务层逻辑上的过程功能,底层的实现调用可以是通讯 序列化这些。 看了tim的文章 ,网络相关的问题在他的眼里通讯层与实际的IDC关系比较密切,也可以抽象出更多的问题,引用tim的话: “ 目前考虑到的原因有 Connection pool作用。为了节点间更高的throughput, 通常两节点之间会使用n个固定连接来传输。n可设为CPU内核数大小。 多节点互相连接的处理。一个节点需要连接n个节点发送信息。如果这部分逻辑放在业务调用层来实现,…
2012-03-07 20:41 · distributed & · 评论(0)
分布式系统设计笔记
应对单点故障,SIGSEGV: consistent hash read through cache 前者的优点不想再提了:震荡最小,常用的优化 包括,虚拟化节点, 分布式系统焦点:高并发 高性能 高可扩展 容错设计思想 分布式存储 数据的一致性(Merkle Tree) 高速读写访问 低延迟 新浪微博的处理:tweet异步处理,为了解决队列的延时问题,采用分级队列,来进一步提高异步处理的效率 sina app API设计: 安全 易用 稳定 灾难恢复
2012-03-07 20:36 · distributed & · 评论(0)
异步系统设计泛谈
今天看很久前的新浪工程师在Qcon上的ppt,提到应对系统高峰时的应对,有以下几点异步考虑: 不同步等待, 将消息存入消息队列, 轻量级发表(貌似不相关鸟) 最近异步概念漫天飞,node里面基于事件的异步处理,erlang,scala这一票采用异步actor模式的语言框架,以及高性能的linux异步io,到系统架构级别的异步处理,层出不穷,准备深入学习各种异步的种种。。。 <未完待续>
2012-03-07 19:45 · distributed & · 评论(0)
+-的类型转换
c中变量间赋值可能会出现类型转换的情况,而+-可以进行类型转换,如下代码1: short a = 1; a += 1L; 编译不会出错;而代码2: short b = 1; b = b + 1L; 需要进行强制类型转换,否则会编译出错: b =(short)( b + 1L);
2012-02-28 15:28 · c++ · 评论(0)
转 读《史玉柱谈创业》
读《史玉柱谈创业》 2009-12-24 18:52:59| 分类: 读书 |字号 订阅 也算跟着史总干了快三个年头了,利用闲暇时间读了读本书,对老板和对公司的了解更多了一层。 干啥事都不容易,要胆大心细。 好好学习,天天向上! 史玉柱精彩语录 哈佛营销第一法则:产品差异化,创造营销事件,让媒体作为新闻自觉去报道。 如果没有价格上的优势与技术上的绝对优势,千万不要进入红海市场,否则你会必输无疑! 不要总想着同竞争对手对立,而是要想办法让自己弥补竞争对手的不足。 做连锁经营业务,一定要做一套傻瓜版的营销手册与管理手册,只有这样,才能实现远距离的管理。 要花大的精力建立一个连最基层的员工都可以看…
2012-02-12 16:41 · 笔记 · 评论(0)
转-reinterpret_cast
reinterpret_cast reinterpret_cast是C++里的 强制类型转换 符。 操作符修改了操作数类型,但仅仅是重新解释了给出的对象的比特模型而没有进行二进制转换。 例如:int *n= new int ; double *d=reinterpret_cast<double*> (n); 在进行计算以后, d 包含无用值. 这是因为 reinterpret_cast 仅仅是复制 n 的比特位到 d, 没有进行必要的分析。 因此, 需要谨慎使用 reinterpret_cast. == =========================================== …
2012-02-12 15:22 · c++ · 评论(0)
[转]做生意,做事
做生意的十大禁忌: 一忌:坐门等客。经商不跑不活,商品市场瞬息万变,商品交流讲究时效性,坐门难见客。只有跑动,才能得知市场信息,找准时机,方能盈利。 二忌:没胆量。俗话说,只要有七分把握便可行动,余下的三分把握靠你争取。遇事下不了决心,错过时机不得利,要知道经商中十拿九稳赚钱的事是不多的。 三忌:商品越贵越不卖。商品不可能只涨价不跌价,贵到一定程度,只要赚钱便卖,无论赚多赚少都要满足,若坐等高价,十有八九要吃亏。 四忌:把钱存起来。赚了后不愿再投入,把活钱变成死钱,只有得寸进尺,不断扩大经营规模,发展壮大自己事业才 能更上一层楼。 五忌:好高鹜远。看不起小本小利,想一口吃成胖子,这样永远也发…
2012-02-11 19:40 · 笔记 · 评论(0)