paramore
- 浏览: 50229 次
- 性别:
- 来自: 西安
-
最新评论
文章列表
<算法基础>上的贪婪算法讲的真是好啊，分析的很精到，例子也很实际，遇到了一个新问题：
日程安排，n个日程，以及数组d，d[i]表示任务i的完成期限，数组g,g[i]表示i在d[i]前完成可以获得的收益，求最大收 益序列。
n^2的方法不说了，先快排g，降序，按照g顺序把遍历到的每个i插入数组j中，用并查集记录i的位置变化，最终时间复杂度O（nlogn）+O(n)<并查集的平摊复杂度>
具体实现后面贴上，此处先mark之
八卦一下，Gilles的<算法基础>我觉得甚至比算法导论还要好，贪心以及概率算法讲的尤其好
被译文骗了个球的题目
- 博客分类：
- interview baby
看到一道题目，开始挺昏沉，加上翻译是在碉堡，没理解，后来大悟，这个题目编程之美上有嘛，就是个位操作统计个数的问题，easy：
一个数组A[1，n]能容纳n个数字，现将0到n这n+1个数字，随机的放入到数组中。最后会有一个数字没有进入数组。现在让你找出这个数字。但是有如下的限制，不能直接访问数组的整个元素，只能访问“A[i]的第j位”。写出代码找出该元素。能否将时间复杂度控制在O(n)。
然后一同比较最低位的1，o个数，每次去除一半的数据，得出：
线性复杂度，好了，收工。。。
哎，javaeye的编辑器再次让我崩溃了。。
怀念总是无限，唯有黑暗，给我无名的鼓励。
海子的诗句：
风后面是风，天空上面是天空，道路前面还是道路。
——《四姐妹》
面朝大海，春暖花 ...
写磁盘时应该注意：
（引自短歌老大）直接fwrite并非不可以，只是可移植性太差。一般我们把数据写入文件都是为了进行数据交换，而直接把一个结构体用一次fwrite调用写入文件后是否可以再用一次fread正确读出取决于写入代码和读出代码编译时的字长、对齐逻辑和字节序等问题（这句话长点，大家凑合着看），严重影响可移植性。
把一个结构体写入文件时我觉得要注意以下几点： 1：要按不同域分别写入，以避免对齐方式的影响； 2：要设计好不同数据的长度，不要用sizeof来获得，以避免字长的影响； 3：要设计好字节顺序，每次写入一个字节，以避免 字节序的影响； 4：要存储逻辑结构而不是数据结构。比如 ...
参加百度的面试，面试官提了一个海量数据问题，貌似自己的回答没能让人家满意，纠结点是：
大规模数据一般先用hash来分为小的数据段，然后在内存里处理之，然而如果hash后hash值还是各不相同（及其变态的情况），怎么办？
回来思考了下，下面是自己的想法，大家说说看：
如果一遍hash后，数据还是十分单调，可以采用另一个hash函数，或者不是单纯按照hash值分类，而是按照hash后的值范围，例如，原来hash(query)%100, 现在可以1-10为一个文件，间隔10建立子数据集，应该能解决问题吧？
轻拍。。。
设计数据访问策略
- 博客分类：
- interview baby
百度的面试题一道：
在处理磁盘数据时，需要首先将其读入内存才能进行处理。如果要读取的数据已经在内存中，则可以直接访问内存。通常来说内存是有限的，因此要读取新的数据时必须覆盖内存中一部分原有的数据。假设现在有n块同样大小的数据，内存一共可以容纳m块数据。现在给出一系列对这些数据的读取请求，要求它们必须按照给定的顺序被读取，同时要求读取磁盘的次数尽可能地少。请简述一个策略满足这样的要求。
解析：目标是最小化磁盘读取次数，分两部分：
内存中的m块数据按照LRU策略组织，由于已经给出了读取请求，或许可以进一步提高swap的效率，
磁盘上数据用B树或者其变种实现，最小化 ...
立此存念;
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>
通讯层与序列化
- 博客分类：
- distributed &
通讯层： 封装与网络通讯 传输数据相关的API，成熟的框架有mina等
序列化/反序列化： 这个多了 gpb，json等等
rpc： 我觉得这个是更多关系业务层逻辑上的过程功能，底层的实现调用可以是通讯 序列化这些。
看了tim的文章 ，网络相关的问题在他的眼里通讯层与实际的IDC关系比较密切，也可以抽象出更多的问题，引用tim的话：
“ 目前考虑到的原因有
Connection pool作用。为了节点间更高的throughput, 通常两节点之间会使用n个固定连接来传输。n可设为CPU内核数大小。
多节点互相连接的处理。一个节点需要连接n个节点发送信息 ...
分布式系统设计笔记
- 博客分类：
- distributed &
应对单点故障，SIGSEGV:
consistent hash
read through cache
前者的优点不想再提了：震荡最小，常用的优化 包括，虚拟化节点，
分布式系统焦点：高并发 高性能 高可扩展 容错设计思想 分布式存储 数据的一致性（Merkle Tree）
高速读写访问 低延迟
新浪微博的处理：tweet异步处理，为了解决队列的延时问题，采用分级队列，来进一步提高异步处理的效率
sina app API设计： 安全 易用 稳定
灾难恢复
异步系统设计泛谈
- 博客分类：
- distributed &
今天看很久前的新浪工程师在Qcon上的ppt，提到应对系统高峰时的应对，有以下几点异步考虑：
不同步等待，
将消息存入消息队列，
轻量级发表（貌似不相关鸟）
最近异步概念漫天飞，node里面基于事件的异步处理，erlang，scala这一票采用异步actor模式的语言框架，以及高性能的linux异步io，到系统架构级别的异步处理，层出不穷，准备深入学习各种异步的种种。。。
<未完待续>
c中变量间赋值可能会出现类型转换的情况，而+-可以进行类型转换，如下代码1：
short a = 1;
a += 1L;
编译不会出错；而代码2：
short b = 1;
b = b + 1L;
需要进行强制类型转换，否则会编译出错：
b =（short）( b + 1L);
突然想研究下MongoDB，browser到官网，发现上面挂了个browser shell ，大喜啊，试试
转 读《史玉柱谈创业》
- 博客分类：
- 笔记
读《史玉柱谈创业》
2009-12-24 18:52:59| 分类： 读书|字号 订阅
reinterpret_cast
reinterpret_cast是C++里的强制类型转换符。 操作符修改了操作数类型,但仅仅是重新解释了给出的对象的比特模型而没有进行二进制转换。 例如：int *n= new int ; double *d=reinterpret_cast<double*> (n); 在进行计算以后, d 包含无用值. 这是因为 reinterpret_cast 仅仅是复制 n 的比特位到 d, 没有进行必要的分析。 因此, 需要谨慎使用 reinterpret_cast. == ============================== ...
做生意的十大禁忌：
一忌：坐门等客。经商不跑不活，商品市场瞬息万变，商品交流讲究时效性，坐门难见客。只有跑动，才能得知市场信息，找准时机，方能盈利。
二忌：没胆量。俗话说，只要有七分把握便可行动， ...