q****m
发帖数: 177 | 1 能举个例子吗？
比如这个文件有如下四行，但是不能一次性读入内存
doctor
nurse
teacher
student
如何多次hash?
每一
in
val |
|
s********k
发帖数: 6180 | 2 用什么最好？fread，fseek或者先用mmap？如果内存一下装不下，怎么能分段读？
谢谢 |
|
w***g
发帖数: 5958 | 3 1B 32-bit interger也就4G, 怎么读都差不多， 应该能一次读进来。建议用fread，最
portable。 |
|
s********k
发帖数: 6180 | 4 fread和mmap哪个效率高？另外fread的话size是整个binary file，还是分次一点点读？ |
|
s********k
发帖数: 6180 | 5 另外如果我并不知道事先知道这个文件大小，只是大概知道1B或者更多，那怎么做？直
接用ftell先算size（如果一次内存装不下怎么算）？还是干脆一次4G的读进来，如果
没有读完继续读？ |
|
|
|
d****n
发帖数: 1637 | 8 fread 就行了，４００Ｇ也就几分钟。
你考虑的是速度也不是内存，不用搞那么复杂。 |
|
s********k
发帖数: 6180 | 9 400G怎么装进内存？或者fread内部是怎么工作的呢？一次装不下怎么弄？ |
|
|
w***g
发帖数: 5958 | 11 【 以下文字转载自 Programming 讨论区 】
发信人: wdong (cybra), 信区: Programming
标 题: 算法导论重点
发信站: BBS 未名空间站 (Mon Oct 15 17:15:36 2012, 美东)
上次在CS版答应给划重点的，发到这儿算了。我手上是第二版。我觉得转行的没有基础
的看完下面这些(约300页，全书1/3的样子）在算法上基本上能达到科班出身水平。可
以按书本身的顺序看，也可以按下面给出的顺序看。
A. 基本概念
1-3 pp.1-61
B. 基本程序设计方法
穷举法 看眼八皇后问题的接法和产生全排列的方法
贪心法 16.1-16.3 pp.370-393
23.1-23.2 pp.561-580
动态规划 15.1-15.4 pp.323-356
分治法(divide and conquer) 本书没有专门的章节讲这个，需要自己随便上网搜搜。
结合下面章节看
选中位数 9.1-9.3 183-189
快速排序和二分查找
回溯(recursion) 这个是具体的实现方法，可以和... 阅读全帖 |
|
g*****e
发帖数: 282 | 12 os用virtual mem给你搞定了。当然你也可以自己分block读入 |
|
m*******1
发帖数: 77 | 13 程序里面怎么分block实现？
os用virtual mem给你搞定了。当然你也可以自己分block读入 |
|
g*****e
发帖数: 282 | 14 os用virtual mem给你搞定了。当然你也可以自己分block读入 |
|
m*******1
发帖数: 77 | 15 程序里面怎么分block实现？
os用virtual mem给你搞定了。当然你也可以自己分block读入 |
|
b***i
发帖数: 3043 | 16 一个方案是两个线程。
另一个方案，就是看楼主的题目是不是就是要求可以用recursion，不然我说了，然后
再加上各种额外的限制不就不行了？
方法是这样的，traverse1(int seq, Node * node) 将返回node为头的从小开始第seq
个数。
main的程序写个循环什么的，分别从两个BST读入第0个数字，第1个数字什么的。然后
比较，直到最后。这样当然很浪费，每次都要从头寻找，但是要求就是这样，有什么办
法。 |
|
h*******e
发帖数: 1377 | 17 看windows programming 最初unicode 就是wstring 之类的吧比正常 长两倍定义函数
全用 w**就行了。。现在的unicode 不知道怎么处理的。。一些oj里面 似乎普通函数
就能读入汉字。。只要顺序输出就行了。。。 |
|
O******i
发帖数: 269 | 18 面官后来反馈说，the best O(1) solution I know so far is to use a trie
真的能用trie达到O(1)么？如何实现？
*******************************************************************
给定一个大整数N,比如N = 100, 有如下的初始有序序列位于[0, N - 1]之间
[0 1] [4 5 6] [9 10 11] [20] [50] [90] [95 96] [98 99]
请设计一个数据结构保存这个初始序列，然后写一个函数，接受一个input参数x, 满足
0 <= x <= N - 1
1) 假如x在该结构中不存在，出错处理
2) 假如x在该结构中存在，返回x之后第一个不存在的数，并把该数写入结构中
例如
x = 8, 出错，初始序列中没有8
x = 5, 返回7， 序列变为
[0 1] [4 5 6 7] [9 10 11] [20] [50] [90] [95 96] [98 99]
x = 4, 返回8, 序列变为
[0 1] [4... 阅读全帖 |
|
O******i
发帖数: 269 | 19 确实是只有删除了。
现在才知道这题应该这样分析才有冷静的思路
1) 读入初始数据后，就是正数轴上以非负整数为端点的一系列排序好且不相交的线段
，有些线段退化为单个的离散点
2) 给定的x, 必须位于某条线段上
3) 下一个数，就是扩展x所在线段(长度增加1）后新的右端点
4) 线段扩展后，填补了gap,可能导致两条相邻的线段合并为一条更长的线段
5) 如果我们用有序数组(每个元素是一个区间)表示这些线段，就是经典的合并区间那
道题，但是考虑到删除两个区间为一个区间会引起其他元素的O(N)移动，改用平衡BST,
可以把这个操作降为O(logN)
这道题的核心，一个是“以线代点", 另外一个是“以树代替数组”
可惜我明白的太晚了，虽然区间合并题和BST都知道，就是没有想到把这两个结合起来。 |
|
p*****2
发帖数: 21240 | 20
我忘记了是提交结果了。当时想着是程序有内存限制，比如一般250M这样。但是
hackercup是直接提交结果的，没有这个问题。所以可以一次读入内存。 |
|
G*******l
发帖数: 19 | 21 yes~ 差不多就是这个想法，当然有没有空格都没关系，因为我们知道要读入的长度，
这个长度之后长度内的字符都属于这个node的value ：） |
|
l****i
发帖数: 2772 | 22 不在乎空间的话，加一些辅助，我觉得应该可以做到O(n).就像楼上那位兄弟说的，可
以用hashtable记录出现的数。我觉得可以用2个hashtable，一个记录start的数和位置
，一个记录end的数和位置。如果一个新读入的数字，替换了一个interval的end，同时
替换了一个interval的start，就合并这2个interval。
大家觉得呢？ |
|
w****5
发帖数: 46 | 23 1 看你连接时选择什么连接方式，如果是静态连接，则有；动态连接则没有
2 scanf始终是从标准输入，即0号文件读入。在unix上，0号文件通常是个character
device file，但也可以重定向成一个regular file，pipe等 |
|
h*******e
发帖数: 1377 | 24 最近写了两个 个c++的 parse xml 的小程序 大体思路是 每次读 进一个 字符 判
断[ 如果是的话 进入时间 tag函数 处理里面的时间 tag 之后 读入 后面的字符直
到】
理论上 正文 不会有 【字符。。碰到下一个[字符 开始新的一组时间函数。 关键你要
自己查一下生成这个log文件的程序 或者找相关人士 明确一下log 文件的语法。。
比如我parse xml就要压栈什么的。。这个log文件似乎用不到。 |
|
m***l
发帖数: 45 | 25 谢指点
请问如果不能用stream的话应该怎么读入呢?
array |
|
f*******t
发帖数: 7549 | 26 这题我不会做，貌似有个常见版本是读入这些pair然后建立一棵树，谁有好的解法？ |
|
r*****n
发帖数: 2 | 27 onsite之后有个interviewer旅游去了，4周之后才拿到feedback，提交HC之后又一周没
动静了，给recruiter发信也不回。实在等得心烦。发个面经就算挂了然后move on吧。
是fresh master.
两轮电面，都是经典题。写完2个题还有点时间，讨论了一个设计题，我到现在也不理
解题意。
有一种新型存储设备，特点是：
1. 价格贵，稳定性高
2. 可读写，但写入的内容不能修改
如何利用它的特点设计一个存储系统。在聊天过程中增加了一些条件，如果有个人写了
个脚本不停用同样的内容写你的文件系统怎么办，怎么判断每次写入的东西是不是新的
呢。
4轮Onsite 3个印度人一个欧洲人。都是从简单的题开始，不停改改改。都讨论了项目
经验，还问得很细。写完代码都是要照相的，我有个题是开始写得挺干净，后来条件加
加加就改花了，然后interviewer掏出手机拍了一张。。我觉得是不是可以在写完第一
版之后就请他拍一张先。。。
1.一个binary search变体。 写完之后开始抠代码，说如果把终止条件从low<=high 改
成low阅读全帖 |
|
e******i
发帖数: 106 | 28
额，读入输入流么，输出是打印出来就可以了么？
可否再详细点，谢谢！ |
|
c******5
发帖数: 84 | 29 昨天刚面的，今天知道挂了。。。
第一轮: 实现一个简化版的boggle game，给定一个dictionary，我用dfs做的
第二轮：给一个int array, 不用division,replace each element with the
multiplication of all elements other than that element
第三轮:给一个method char[] read(int n)，读入n个字符，输出到数组中，让实现一
个String readline()，字符流以null结尾
第四轮：实现method: int getNthPrime(int n)，找出第n个质数，n从0开始，这题没
打好，想错了，用了sieve of eratosthenes.
唉，感觉面试时一旦想错了如果面试官不提示的话，就万劫不复了。。。 |
|
|
|
|
z*******3
发帖数: 13709 | 33 不考虑mapreduce你就自己实现一个mapreduce么
用spring来做mapreduce
同样原理，impl一下就好了
还能怎么做？不能全部读入内存，就只能拆分
挨个处理，话说mapreduce也是这个思想
要是这个如果不让做，那还能怎么做？
多线程？要问问考官要求什么 |
|
f*********m
发帖数: 726 | 34 能说说这个题吗？一般要维护一个12months的数组吧？最小的时间单位，就是说最短过
多久，读入新的同时删掉旧的？
p1: coding题目
Given continuous incoming real time stock price stream,
1) design data structure to support query for max, min price in the past
12 months. |
|
|
p*****3
发帖数: 488 | 36 来自主题: JobHunting版 - 周末上道题 Design一个数据结构，找出无限输入流中任意时刻第k大的数，
O(n)时间，O(k)空间，n为当前读入的数据个数 |
|
c********e
发帖数: 186 | 37 来自主题: JobHunting版 - 周末上道题 Min-Heap，先读够k个数，然后每次读入一个数X，比较X与heap的root，如果root < X,
remove root and insert X. |
|
G***l
发帖数: 355 | 38 这不是熟练的问题，真正的project跟做题不是一回事，99.9%以上的code，除了不
出错之外，最最重要的是人容易看懂和要添加/修改功能的时候容易不容易。人家都说
了It is not enough to write code that is merely correct。
就提到的这些要求，看看你的code满足了多少？
clear,concise:
你觉得
if (room[new_location[0]][ new_location[1]] == '@' ||room[new_
location[0]][ new_location[1]] == '-' )
66 return(previous_sign);
67 else
68 return(room[new_location[0]][ new_location[1]]);
这样的code clear&concise么？如果你读别人这样的code，会不会觉得烦人？clear&
concise的code不需要看题目一眼看过去就能大概明白是在干嘛。
well docu... 阅读全帖 |
|
z****e
发帖数: 54598 | 39 看了下内森的文章
其实也没啥很fancy的东西
简单说构架无非就是
用hadoop保存history documents，主要数据源
然后建view，也就是预处理查询，用它自己写的elephonedb
从hadoop中拨取出key value pair，然后存起来
这样对于历史部分数据的查询，就是直接访问elephonedb，然后做加法了
然后对于实时部分的处理，就是storm+cassandra
由于这部分数据仅仅是最近数小时内的数据
所以就算全部读入内存，其实也没啥大不了的
加强监控，不要让内存爆掉，不要让gc停顿时间太长
剩下的也就是在query时候提供数据就好了
最后把实时数据和历史数据的查询做一个加法就是最后的结果 |
|
t******i
发帖数: 483 | 40 刚发现 让我们用的是 int read(char* buf, int len) 和char * readLine()是两个东
西。
read(buf, len)的返回值和len不一样，就可以block了。
int read(char* buf, int len) 主要计算每次读入len长有没有终止 |
|
w*******e
发帖数: 395 | 41 你的代码好像有问题。
如果read()没有读满max_size, eof已经为1了，这个时候buffer是没有填满的。在此之
前如果hit了一个‘n’。currentPos会记录'n‘后面的一个位置。
当第二次进入该函数的时候，你的while循环会从currentPos一直都到buffer的尾端，
而实际上，由于上次hit了eof，buffer是没有填满的。你的代码读入了一些多余的数据。 |
|
n******r
发帖数: 869 | 42 贡献好文：
http://coolshell.cn/articles/4990.html
月光博客6月12日发表了《写给新手程序员的一封信》，翻译自《An open letter to
those who want to start programming》，我的朋友（他在本站的id是Mailper）告诉
我，他希望在酷壳上看到一篇更具操作性的文章。因为他也是喜欢编程和技术的家伙，
于是，我让他把他的一些学习Python和Web编程的一些点滴总结一下。于是他给我发来
了一些他的心得和经历，我在把他的心得做了不多的增改，并根据我的经历增加了“进
阶”一节。这是一篇由新手和我这个老家伙根据我们的经历完成的文章。
我的这个朋友把这篇文章取名叫Build Your Programming Technical Skills，我实在
不知道用中文怎么翻译，但我在写的过程中，我觉得这很像一个打网游做任务升级的一
个过程，所以取名叫“技术练级攻略”，题目有点大，呵呵，这个标题纯粹是为了好玩
。这里仅仅是在分享Mailper和我个人的学习经历。（注：省去了我作为一个初学者曾
经学习过的一些技术(今天明显... 阅读全帖 |
|
m**********4
发帖数: 774 | 43 我是C＋＋盲，不知道这个CODE是不是有BUG：
１.你的read() return value是int，你可以直接转成char没有问题吗？
２.不知道unordered_set是啥，好象可以count。但你边读入边比较,这个count在到了
１以后就没有更新了吧，所以如果一个string出现了１０次，你要print 9次，这个对
吗？ |
|
w********s
发帖数: 214 | 44 implement linux command tail.
We will focus only on "-n" and "-f" options.
tail FILE 是显示打印文件最后10行。tail -n 5表示打印文件最后五行。
The -f option causes tail to not stop when end of file is
reached, but rather to wait for additional data to be appended
to
the input.
有两个concern，
文件可能很大，所以不能全部读入，问怎么解决。
文件可能大得超过了内存，问怎么读。
(2) Two cases for value of N (A) N is small to fit in memory (B) N is large
to fit in memory
Please email your code and clear instructions to execute your program. |
|
l*y
发帖数: 21010 | 45 O(n)啊
input的array你至少得全部读入吧，那就是o(n)了
weighted 很简单啊
a*1 + b*2 + c*3
b*1 + c*2 + d*3
第二个就是减去a+b+c啊 |
|
b******p
发帖数: 49 | 46
这题我完全没做出来
面试官没让我写code，我就和他说了，建一个hash table，或是建一个bloom filter之类
他说这些不行，又补充说：
blacklist是一个链表，所以二分查找的代价和数组的二分查找不一样
他说要“incremental”的解法
也就是将整个blacklist读入，再建hash table的方法通通不行
他说，譬如blacklist里面有几百万个数怎么办？几百万个数就是~400MB，超过了CPU的
缓存的大小。如果建hash table，性能会损失非常大。所以，我说的方法全都错误，不
是他想要的。估计是因此被拒了。
后来才知道这个是CareerCup 12.3这道题目。
没做过，真该面壁思过去… |
|
h****g
发帖数: 105 | 47 第二题： O(n)遍历数组求和，假设多的数字是a，miss的数字数b，那么求的和是sum(
Zn)+a-b. 第二遍就平方之和，结果是sqr(Zn)+a^2-b^2. 然后可以得到a+b. a和b也
可以求出来了，这题偏向数学吧。
第三题应该是对的，用一个长度为k的heap来读入streaming当中的数，只是复杂度应该
是O（nlogk） |
|
h****g
发帖数: 105 | 48 第二题： O(n)遍历数组求和，假设多的数字是a，miss的数字数b，那么求的和是sum(
Zn)+a-b. 第二遍就平方之和，结果是sqr(Zn)+a^2-b^2. 然后可以得到a+b. a和b也
可以求出来了，这题偏向数学吧。
第三题应该是对的，用一个长度为k的heap来读入streaming当中的数，只是复杂度应该
是O（nlogk） |
|
B***n
发帖数: 84 | 49 来自主题: JobHunting版 - 狗狗家面筋 悲剧了，贴出来攒点人品
顺便大家帮忙分析下题目难度，还有我的回答有没有什么低级错误。除了LRU在
leetcode上有，其他的我都不知道该说简单呢还是难呢，看到要实现memcpy然后就吓了
一跳。
1. switch的工作原理流程。
2. 估计挂在这里了。
1）. 生死棋盘游戏。
我只想到最简单的方法，遍历所有cell，根据规则更新棋盘是生是死。还有别的更好方
法吗？
2）. 生成迷宫，基本上不怎么会。
我先说随机生成0/1。但可能会出现迷宫不可解的情况，然后我就差不多挂了。
求更好方法。
3. 从文件中读入记录，然后生成树，计算pathsum，
文件记录格式，node, parent, weight.
然后讨论一些特殊的情况。
4. LRU实现，我其中用的了map，顺便写一个hash table实现map。
我其中有一行出现了bug，删除的时候忘记更新map了。
5. 实现memcpy，这个比较没头绪，不知道要考啥，先写一个最简单的
大概是 *dst = *src， 之类的，然后问怎么优化让他更快点，
因为刚开始用的是 char 的指针，我说把指针变成 uint_32t 会更快点，当... 阅读全帖 |
|
f********x
发帖数: 2086 | 50 已悲剧了，尽量全写中文，因为以前看见有一道题明显是从这里首发，被别人拷到别了
的网站。
两个电面，面谈4轮加上中午HM吃饭。电面有一轮明显是国人大哥让我水过了，做了一
道很简单的题，还扯淡了下东北部天气，只有半小时不到就完了，还给了正面评价。面
谈3个国人，两个烙印。3个国人都面的还可以。感觉烙印HM那轮聊的不好，我确实也代
码写的不够好，他也全程没兴趣的样子。最后一轮女烙印我面的也不好。她中间貌似不
认识java里的enum，一开始很质疑我写enum，后来感觉是用她电脑现查的，然后就同意
我说的了........
题有
最大子序列（及变种）
一个数列，每个数位置错位不到k，求排序算法，问复杂度（O(nlgk)）
八个球，其中一个重量可能轻可能重，3次找出来（这题是那一轮答的好，貌似没题了
才随便问的）
单例模式
带peekMin的队列的变种
生产者消费者多线程（含文件读入输出）
final finally finalize
垃圾回收机制（早晨坐在lobby等待的时候看的，居然直接用上了）
Y家的面试内容明显和别家不同 |
|
