Rookie Engineer

If you aren't the kind of person that feels this way naturally, you'll need to become one in order to make it as a hacker. Otherwise you'll find your hacking energy is sapped by distractions like sex, money, and social approval.

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  24 Posts :: 0 Stories :: 2 Comments :: 0 Trackbacks

常用链接

留言簿

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜


输入: 一个最多包含n=10^7的正整数文件,每个正整数都要小于n.
输出: 按升序
约束: 最多有(大约)1MB的内存空间可用.


1. 如果不缺内寸, 如何使用一个具有库的语言来实现一种排序算法以表示和排序集合?
C++
set/vector

C
qsort

2. 如何使用位逻辑运算(例如与, 或, 移位)来实现向量?
1个int 32bit, 4字节, 所以N个数的话就需要 1+N/32 ~ 10^7/32 = 312500, --> 312500 *4 = 1.192 ~1.25 MB
如果用0表示无此位置数据,1表示有此位置数据,可用如下字符串来表示集合 {3,5,7,8}: 1101 0100.

SET/CLR
ps: a[i>>SHIFT] 对应 1+N/32;
     1<<(i & MASK) 对应到此位置有数据.

3. 生成小于N且没有重复的整数
randint

4. 可以用k趟算法完成对最多n个小于n的无重复正整数的排序, 时间kn, 空间n/k.
5. 上面的程序都是不存在错误处理和限定.

程序员拿到题目应该多思考, 而不是直接code, 其实有些题目在了解了之后往往比想象的来的简单~~
posted on 2013-04-30 09:33 micwu 阅读(349) 评论(0)  编辑 收藏 引用 所属分类: Programming Pearls

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理