f****e
发帖数: 30 | 1 已经挂了。为下周google onsite求祝福
(1) 数组去duplicates
(2) 防火墙存了一组ip,进来一个ip，怎么查找在不在list里面。
给了hash solution,然后问，假设很多ip都是从amazon出来，他们前面两个byte的值一
样，这种情况怎么办。他期望的solution是trie,这里我有点不明白，因为你没有任何
先验知识这些ip是从一个地方不同机器出来的，难道观察trie每个节点下面有多少个
subtree,如果subtree数目==256，就把这些都剪了，然后加个mask?
(3) 一个大ascii文件，怎么样随机采样其中一行。然后问我怎么提高。
原来的算法只要scan文件一边，用一行的space,实在不觉得能改进。最后给了近似解，
用文件大小估计有多少个char,然后随即产生一个数，把文件指针指向相应的char,把那
一行剩下的都读出来。 | q*********u
发帖数: 280 | 2 ２的话应该就是最大有２５６叉的tree吧？
３，line ≈ filesize / maxlinesize ?
【在 f****e 的大作中提到】
: 已经挂了。为下周google onsite求祝福
: (1) 数组去duplicates
: (2) 防火墙存了一组ip,进来一个ip，怎么查找在不在list里面。
: 给了hash solution,然后问，假设很多ip都是从amazon出来，他们前面两个byte的值一
: 样，这种情况怎么办。他期望的solution是trie,这里我有点不明白，因为你没有任何
: 先验知识这些ip是从一个地方不同机器出来的，难道观察trie每个节点下面有多少个
: subtree,如果subtree数目==256，就把这些都剪了，然后加个mask?
: (3) 一个大ascii文件，怎么样随机采样其中一行。然后问我怎么提高。
: 原来的算法只要scan文件一边，用一行的space,实在不觉得能改进。最后给了近似解，
: 用文件大小估计有多少个char,然后随即产生一个数，把文件指针指向相应的char,把那
| n******r
发帖数: 1247 | 3 bless!
【在 f****e 的大作中提到】
: 已经挂了。为下周google onsite求祝福
: (1) 数组去duplicates
: (2) 防火墙存了一组ip,进来一个ip，怎么查找在不在list里面。
: 给了hash solution,然后问，假设很多ip都是从amazon出来，他们前面两个byte的值一
: 样，这种情况怎么办。他期望的solution是trie,这里我有点不明白，因为你没有任何
: 先验知识这些ip是从一个地方不同机器出来的，难道观察trie每个节点下面有多少个
: subtree,如果subtree数目==256，就把这些都剪了，然后加个mask?
: (3) 一个大ascii文件，怎么样随机采样其中一行。然后问我怎么提高。
: 原来的算法只要scan文件一边，用一行的space,实在不觉得能改进。最后给了近似解，
: 用文件大小估计有多少个char,然后随即产生一个数，把文件指针指向相应的char,把那
| y**i
发帖数: 1112 | 4 第三题是不是以前大家在版上讨论的每一行的随机概率是n/(n+1)（n是行数）来达到每
行概率相等？
【在 f****e 的大作中提到】
: 已经挂了。为下周google onsite求祝福
: (1) 数组去duplicates
: (2) 防火墙存了一组ip,进来一个ip，怎么查找在不在list里面。
: 给了hash solution,然后问，假设很多ip都是从amazon出来，他们前面两个byte的值一
: 样，这种情况怎么办。他期望的solution是trie,这里我有点不明白，因为你没有任何
: 先验知识这些ip是从一个地方不同机器出来的，难道观察trie每个节点下面有多少个
: subtree,如果subtree数目==256，就把这些都剪了，然后加个mask?
: (3) 一个大ascii文件，怎么样随机采样其中一行。然后问我怎么提高。
: 原来的算法只要scan文件一边，用一行的space,实在不觉得能改进。最后给了近似解，
: 用文件大小估计有多少个char,然后随即产生一个数，把文件指针指向相应的char,把那
| k**********i
发帖数: 177 | 5 这个是什么意思啊？
原帖在哪里啊？
【在 y**i 的大作中提到】
: 第三题是不是以前大家在版上讨论的每一行的随机概率是n/(n+1)（n是行数）来达到每
: 行概率相等？
| y**i
发帖数: 1112 | 6 就是不知道文件行数，只能读取一次，按行读取，怎样读取让取到每行的概率相等
原帖版面搜吧
【在 k**********i 的大作中提到】
: 这个是什么意思啊？
: 原帖在哪里啊？
| g**t
发帖数: 49 | 7 I guess, when you read the (k)th line, do $result = this line with
probability of (1/k)
【在 k**********i 的大作中提到】
: 这个是什么意思啊？
: 原帖在哪里啊？
| s**9
发帖数: 207 | 8
前缀相同的关键字在Patricia Trie上查找、存储的开销都小。
可不可以建一个指针数组，每个指针指一行？
最后给了近似解，
【在 f****e 的大作中提到】
: 已经挂了。为下周google onsite求祝福
: (1) 数组去duplicates
: (2) 防火墙存了一组ip,进来一个ip，怎么查找在不在list里面。
: 给了hash solution,然后问，假设很多ip都是从amazon出来，他们前面两个byte的值一
: 样，这种情况怎么办。他期望的solution是trie,这里我有点不明白，因为你没有任何
: 先验知识这些ip是从一个地方不同机器出来的，难道观察trie每个节点下面有多少个
: subtree,如果subtree数目==256，就把这些都剪了，然后加个mask?
: (3) 一个大ascii文件，怎么样随机采样其中一行。然后问我怎么提高。
: 原来的算法只要scan文件一边，用一行的space,实在不觉得能改进。最后给了近似解，
: 用文件大小估计有多少个char,然后随即产生一个数，把文件指针指向相应的char,把那
|
|
