i*****j
发帖数: 7 | 1 G家电面.题目完全没有见过，答的磕磕碰碰的，估计是挂了。
1. Suppose you have a bunch of phone numbers. Implement functions 1)
IsNumberTaken(phone #), GiveMeANumber() and ReturnBackANumber() in an
optimized way.
2. You have a 4G text file which each line contain some number of words. You
have only 1G of memory. Implement a function to truly randomize the file in
the unit of each line. For example, line 1, 2, 3, 4, 5, become something
like line 3, 5, 4, 2, 1. |
B*******1
发帖数: 2454 | 2 1. 觉得用trie
2. 跟random shuffle有什么区别啊？是不是要考虑有可能一行大于1G，内存装不下的问题？ |
y*******g
发帖数: 6599 | 3 无法读入内存，
一行大于1G不用考虑把
感觉类似merge sort, 只不过以前的sort/compare都改成shuffle就好了
把文件分成 N部分，每个分别shuffle, 然后merge的时候从N个文件里面随机去一个
的问题？
【在 B*******1 的大作中提到】
: 1. 觉得用trie
: 2. 跟random shuffle有什么区别啊？是不是要考虑有可能一行大于1G，内存装不下的问题？
|
d*******r
发帖数: 208 | 4 1. how about keep two hash_set taken, free? need to consider multithread
synchronizaton.
You
in
【在 i*****j 的大作中提到】
: G家电面.题目完全没有见过，答的磕磕碰碰的，估计是挂了。
: 1. Suppose you have a bunch of phone numbers. Implement functions 1)
: IsNumberTaken(phone #), GiveMeANumber() and ReturnBackANumber() in an
: optimized way.
: 2. You have a 4G text file which each line contain some number of words. You
: have only 1G of memory. Implement a function to truly randomize the file in
: the unit of each line. For example, line 1, 2, 3, 4, 5, become something
: like line 3, 5, 4, 2, 1.
|
l********g
发帖数: 24 | 5 Question 1, "GiveMeANumber() and ReturnBackANumber()" 是什么意思? 要返回什么
? |
d*******r
发帖数: 208 | 6 2. so total line # can be counted say 1....n. do a randome shuffle of these
line numbers. then output to a different file while reading the input file
arrange the lines with the random shuffle results.
You
in
【在 i*****j 的大作中提到】
: G家电面.题目完全没有见过，答的磕磕碰碰的，估计是挂了。
: 1. Suppose you have a bunch of phone numbers. Implement functions 1)
: IsNumberTaken(phone #), GiveMeANumber() and ReturnBackANumber() in an
: optimized way.
: 2. You have a 4G text file which each line contain some number of words. You
: have only 1G of memory. Implement a function to truly randomize the file in
: the unit of each line. For example, line 1, 2, 3, 4, 5, become something
: like line 3, 5, 4, 2, 1.
|
a**********2
发帖数: 340 | 7 1. bitset行吗？ 10^10/8才1G多，内存完全能放下 |
a**********2
发帖数: 340 | 8 文件不是random access的吧
的问题？
【在 B*******1 的大作中提到】
: 1. 觉得用trie
: 2. 跟random shuffle有什么区别啊？是不是要考虑有可能一行大于1G，内存装不下的问题？
|
f*********5
发帖数: 576 | 9 需要明确每次返回什么样的number.
如果随便的话
1)这个题跟实现LRU有点像
doubly linked list+hashtable
use hashtable to judge whether the number is in them
use linked list to add new number and return a number
2)也可以用stack+hashtable
each time just push/pop stack and update hashtable
You
in
【在 i*****j 的大作中提到】
: G家电面.题目完全没有见过，答的磕磕碰碰的，估计是挂了。
: 1. Suppose you have a bunch of phone numbers. Implement functions 1)
: IsNumberTaken(phone #), GiveMeANumber() and ReturnBackANumber() in an
: optimized way.
: 2. You have a 4G text file which each line contain some number of words. You
: have only 1G of memory. Implement a function to truly randomize the file in
: the unit of each line. For example, line 1, 2, 3, 4, 5, become something
: like line 3, 5, 4, 2, 1.
|
s*******f
发帖数: 1114 | 10 confused by the expression.
For random, how about generate random float for each unit in the line. when
reach '\n', sort these random numbers and their according units.
You
in
【在 i*****j 的大作中提到】
: G家电面.题目完全没有见过，答的磕磕碰碰的，估计是挂了。
: 1. Suppose you have a bunch of phone numbers. Implement functions 1)
: IsNumberTaken(phone #), GiveMeANumber() and ReturnBackANumber() in an
: optimized way.
: 2. You have a 4G text file which each line contain some number of words. You
: have only 1G of memory. Implement a function to truly randomize the file in
: the unit of each line. For example, line 1, 2, 3, 4, 5, become something
: like line 3, 5, 4, 2, 1.
|
|
|
k****n
发帖数: 369 | 11 wrong, you cannot random access the lines, or random write the lines.
these
【在 d*******r 的大作中提到】
: 2. so total line # can be counted say 1....n. do a randome shuffle of these
: line numbers. then output to a different file while reading the input file
: arrange the lines with the random shuffle results.
:
: You
: in
|
k****n
发帖数: 369 | 12 应该是这样的
【在 y*******g 的大作中提到】
: 无法读入内存，
: 一行大于1G不用考虑把
: 感觉类似merge sort, 只不过以前的sort/compare都改成shuffle就好了
: 把文件分成 N部分，每个分别shuffle, 然后merge的时候从N个文件里面随机去一个
:
: 的问题？
|
i*****j
发帖数: 7 | 13 这个思路很赞！
【在 y*******g 的大作中提到】
: 无法读入内存，
: 一行大于1G不用考虑把
: 感觉类似merge sort, 只不过以前的sort/compare都改成shuffle就好了
: 把文件分成 N部分，每个分别shuffle, 然后merge的时候从N个文件里面随机去一个
:
: 的问题？
|
i*****j
发帖数: 7 | 14 这个应该行。我答的是用两个BST存已用和可用的号码，O(lg(n))查找和插入/删除，对
方明显不满意。
【在 f*********5 的大作中提到】
: 需要明确每次返回什么样的number.
: 如果随便的话
: 1)这个题跟实现LRU有点像
: doubly linked list+hashtable
: use hashtable to judge whether the number is in them
: use linked list to add new number and return a number
: 2)也可以用stack+hashtable
: each time just push/pop stack and update hashtable
:
: You
|
b*****c
发帖数: 1103 | 15 第一题用2个hashtable，现在的和曾经取出过的，O(1） |
B*******1
发帖数: 2454 | 16 GiveMeANumber() and ReturnBackANumber()
这个ReturnBackANumber 究竟是什么意思啊？ 我觉得是取消号码的意思
那么GiveMeANumber我觉得是用户申请电话号码，返回一个还没有用过的，这种情况下
hashtable最坏情况也要一个个找一下吧？ |
b*****c
发帖数: 1103 | 17 任何一个号码要么是取出的，要么是未取出的
所以returnback就是从已取出的hashtable，转一个到未取出的hashtable
O(1)啊
【在 B*******1 的大作中提到】
: GiveMeANumber() and ReturnBackANumber()
: 这个ReturnBackANumber 究竟是什么意思啊？ 我觉得是取消号码的意思
: 那么GiveMeANumber我觉得是用户申请电话号码，返回一个还没有用过的，这种情况下
: hashtable最坏情况也要一个个找一下吧？
|
B*******1
发帖数: 2454 | 18 是的，但是一开始的时候给出一堆电话号码，然后他们全部都在取出那里，但是未取出
是空的
然后用户call GiveMeANumber（） 去申请一个号码，但是你的未取出hashtable还是空
的，你怎么找一个没有人的用户呢？ 难道我题意理解错了。
【在 b*****c 的大作中提到】
: 任何一个号码要么是取出的，要么是未取出的
: 所以returnback就是从已取出的hashtable，转一个到未取出的hashtable
: O(1)啊
|
b*****c
发帖数: 1103 | 19 一开始的时候给出一堆电话号码，然后他们全部都在"""未取出""""那里
call Giveme的意思就是取出一个， initial当然是未取出啦，一堆号码在仓库里等着
取出 |
B*******1
发帖数: 2454 | 20 谢谢，我理解错了。
【在 b*****c 的大作中提到】
: 一开始的时候给出一堆电话号码，然后他们全部都在"""未取出""""那里
: call Giveme的意思就是取出一个， initial当然是未取出啦，一堆号码在仓库里等着
: 取出
|
|
|
t*****n
发帖数: 25 | 21 G家电面都给result吗？我的电面是一阿三很简单，但都快十天了也没结果，email给
recruiter也没回，大概完了。是2nd电面了，1st电面5，6天就有结果了。 |
C*********1
发帖数: 6 | 22 能不能详细说一下merge的过程？
【在 y*******g 的大作中提到】
: 无法读入内存，
: 一行大于1G不用考虑把
: 感觉类似merge sort, 只不过以前的sort/compare都改成shuffle就好了
: 把文件分成 N部分，每个分别shuffle, 然后merge的时候从N个文件里面随机去一个
:
: 的问题？
|
t*****n
发帖数: 25 | 23 你怎样去号码？O(1)从hashtable. deque/linklist靠谱。
【在 b*****c 的大作中提到】
: 一开始的时候给出一堆电话号码，然后他们全部都在"""未取出""""那里
: call Giveme的意思就是取出一个， initial当然是未取出啦，一堆号码在仓库里等着
: 取出
|
b*****c
发帖数: 1103 | 24 ICollection *iColl = HashTable->Keys;
deque 不能实现指定number的 returnbacknumber(int number)吧
它只能pop,push头和尾，所以普适性还是HashTable好
【在 t*****n 的大作中提到】
: 你怎样去号码？O(1)从hashtable. deque/linklist靠谱。
|
r********g
发帖数: 1351 | 25 这N个文件每个都是local的随机吧？不过受楼上的启发，我觉得是：
先分成N个文件
文件Fi(0 <= i < N)自己先shuffle
文件Fi和文件F0-F(i-1)依次shuffle一遍（参见随机洗牌的算法，假设2个文件行数相
等，对每个line取随机数k, 如果k%N==0, 就把这一行互换）。
【在 y*******g 的大作中提到】
: 无法读入内存，
: 一行大于1G不用考虑把
: 感觉类似merge sort, 只不过以前的sort/compare都改成shuffle就好了
: 把文件分成 N部分，每个分别shuffle, 然后merge的时候从N个文件里面随机去一个
:
: 的问题？
|
j********x
发帖数: 2330 | 26 怎么可能是对的
你觉得一个truly random的sequence，会有两个元素总是出现在一个给定的长度的区间
里么。。。
【在 k****n 的大作中提到】
: 应该是这样的
|
a********m
发帖数: 15480 | 27 braket吧。
【在 i*****j 的大作中提到】
: 这个应该行。我答的是用两个BST存已用和可用的号码，O(lg(n))查找和插入/删除，对
: 方明显不满意。
|
a********m
发帖数: 15480 | 28 available hash table有点太复杂了。不知道有没有更好的办法。
【在 b*****c 的大作中提到】
: ICollection *iColl = HashTable->Keys;
: deque 不能实现指定number的 returnbacknumber(int number)吧
: 它只能pop,push头和尾，所以普适性还是HashTable好
|
y*******g
发帖数: 6599 | 29 什么叫两个元素总出现在给定长度？
比如 1, 2,3,4,5,6 分成2个
123
456
然后单独shuffle
213
654
最后merge比如265134
【在 j********x 的大作中提到】
: 怎么可能是对的
: 你觉得一个truly random的sequence，会有两个元素总是出现在一个给定的长度的区间
: 里么。。。
|
r********g
发帖数: 1351 | 30 1,2,3,4,5,6,7,8,9
按照你的办法：
147......
可能出现吗？
【在 y*******g 的大作中提到】
: 什么叫两个元素总出现在给定长度？
: 比如 1, 2,3,4,5,6 分成2个
: 123
: 456
: 然后单独shuffle
: 213
: 654
: 最后merge比如265134
|
|
|
y*******g
发帖数: 6599 | 31 为什么不可嫩？
1423
76589
merge的时候第一次取array 1: 1, 第二次还是取array1 : 14, 第三次取array2： 147
..
【在 r********g 的大作中提到】
: 1,2,3,4,5,6,7,8,9
: 按照你的办法：
: 147......
: 可能出现吗？
|
r********g
发帖数: 1351 | 32 ...还以为你是固定地split的，那你内存问题怎么解决？比如如果内存只能放3个数呢？
147
【在 y*******g 的大作中提到】
: 为什么不可嫩？
: 1423
: 76589
: merge的时候第一次取array 1: 1, 第二次还是取array1 : 14, 第三次取array2： 147
: ..
|
j********x
发帖数: 2330 | 33 不好意思，我看错了
这样是对的
【在 y*******g 的大作中提到】
: 什么叫两个元素总出现在给定长度？
: 比如 1, 2,3,4,5,6 分成2个
: 123
: 456
: 然后单独shuffle
: 213
: 654
: 最后merge比如265134
|
d*******l
发帖数: 338 | 34 第一个我觉得只要一个trie就可以，保存所有沒使用过的的电话号码。IsNumberTaken(
phone #)只要在trie里面找这个号码，找到了就是没被taken。
GiveMeANumber()，在trie里找最左边的那个叶节点就可以。删除这个节点。
ReturnBackANumber() ，把这个number重新放回trie中。
每个操作的代价都是号码的长度。这个其实比hashtable省空间和时间。
第二题我觉得上面说的先分成k份各自shuffle，再随机merge是对的。 |
m**q
发帖数: 189 | 35 我觉得第二个主要是文件无法直接shuffle，得分块后把每一块load到内存
的数组中，然后在数组中随机shuffle后输出。
没搞明白的是如何证明随机merge这样shuffle后的文件块能产生完全随机的结果呢？
IsNumberTaken(
【在 d*******l 的大作中提到】
: 第一个我觉得只要一个trie就可以，保存所有沒使用过的的电话号码。IsNumberTaken(
: phone #)只要在trie里面找这个号码，找到了就是没被taken。
: GiveMeANumber()，在trie里找最左边的那个叶节点就可以。删除这个节点。
: ReturnBackANumber() ，把这个number重新放回trie中。
: 每个操作的代价都是号码的长度。这个其实比hashtable省空间和时间。
: 第二题我觉得上面说的先分成k份各自shuffle，再随机merge是对的。
|
d*******l
发帖数: 338 | 36 我的一个想法：
假如内存大小是M，文件大小是N，把文件分成K块，就有N=KM。然后对每个块进行
shuffle，每个块都有M!种结果，总共有(M!)^K种结果。然后再考虑merge。每种merge
方法可以表示成一个长为N的序列，是M个1，M个2。。。M个K组成的序列的一个排列。
表示的意义就是依次从第几个块取东西。这种序列共有N!/(M!)^K种。一种merge方法和
一种分块shuffle的结果能唯一确定一种最后结果，不会有重复，所以这么操作最后可
能的结果就是(M!)^K*N!/(M!)^K=N!种结果。相当于是完全随机的。
【在 m**q 的大作中提到】
: 我觉得第二个主要是文件无法直接shuffle，得分块后把每一块load到内存
: 的数组中，然后在数组中随机shuffle后输出。
: 没搞明白的是如何证明随机merge这样shuffle后的文件块能产生完全随机的结果呢？
:
: IsNumberTaken(
|
s******n
发帖数: 226 | 37 很妙
不过如果disk不是unlimited 怎么办？ 怎么写进去呢？
merge
【在 d*******l 的大作中提到】
: 我的一个想法：
: 假如内存大小是M，文件大小是N，把文件分成K块，就有N=KM。然后对每个块进行
: shuffle，每个块都有M!种结果，总共有(M!)^K种结果。然后再考虑merge。每种merge
: 方法可以表示成一个长为N的序列，是M个1，M个2。。。M个K组成的序列的一个排列。
: 表示的意义就是依次从第几个块取东西。这种序列共有N!/(M!)^K种。一种merge方法和
: 一种分块shuffle的结果能唯一确定一种最后结果，不会有重复，所以这么操作最后可
: 能的结果就是(M!)^K*N!/(M!)^K=N!种结果。相当于是完全随机的。
|
s*********6
发帖数: 20 | 38 第一道题目应该还要考虑内存使用的问题。
电话号码如果是10位数，用trie表示，可能需要多到9^10字节的空间。
用push/pop stack，需要的空间更大。
如果限制内存1G或者4G，内存不一定够。
感觉用bitmap比较好。 |
d*******u
发帖数: 186 | 39 我回答第一题：
我假定a bunch of phone numbers是可用的电话号码。
初始化： 读入所有的电话号码建Trie (只需要十个分支，0～9).
IsNumberTaken(phone #) {
用phone #查询Trie如果能走到叶子，说明phone #可用，not taken,
return false.
else true.
}
GiveMeANumber() {
//从Trie中取出最左边的号码，返回该号码。
//也可以从Trie中取出随机的号码，返回该号码。
//对每一级节点，随机选一个分支。
//从Trie删除该号码。
}
ReturnBackANumber(phone #) {
把phone # 插入Trie中。
}
You
in
【在 i*****j 的大作中提到】
: G家电面.题目完全没有见过，答的磕磕碰碰的，估计是挂了。
: 1. Suppose you have a bunch of phone numbers. Implement functions 1)
: IsNumberTaken(phone #), GiveMeANumber() and ReturnBackANumber() in an
: optimized way.
: 2. You have a 4G text file which each line contain some number of words. You
: have only 1G of memory. Implement a function to truly randomize the file in
: the unit of each line. For example, line 1, 2, 3, 4, 5, become something
: like line 3, 5, 4, 2, 1.
|
i*****j
发帖数: 7 | 40 G家电面.题目完全没有见过，答的磕磕碰碰的，估计是挂了。
1. Suppose you have a bunch of phone numbers. Implement functions 1)
IsNumberTaken(phone #), GiveMeANumber() and ReturnBackANumber() in an
optimized way.
2. You have a 4G text file which each line contain some number of words. You
have only 1G of memory. Implement a function to truly randomize the file in
the unit of each line. For example, line 1, 2, 3, 4, 5, become something
like line 3, 5, 4, 2, 1. |
|
|
B*******1
发帖数: 2454 | 41 1. 觉得用trie
2. 跟random shuffle有什么区别啊？是不是要考虑有可能一行大于1G，内存装不下的问题？ |
y*******g
发帖数: 6599 | 42 无法读入内存，
一行大于1G不用考虑把
感觉类似merge sort, 只不过以前的sort/compare都改成shuffle就好了
把文件分成 N部分，每个分别shuffle, 然后merge的时候从N个文件里面随机去一个
的问题？
【在 B*******1 的大作中提到】
: 1. 觉得用trie
: 2. 跟random shuffle有什么区别啊？是不是要考虑有可能一行大于1G，内存装不下的问题？
|
d*******r
发帖数: 208 | 43 1. how about keep two hash_set taken, free? need to consider multithread
synchronizaton.
You
in
【在 i*****j 的大作中提到】
: G家电面.题目完全没有见过，答的磕磕碰碰的，估计是挂了。
: 1. Suppose you have a bunch of phone numbers. Implement functions 1)
: IsNumberTaken(phone #), GiveMeANumber() and ReturnBackANumber() in an
: optimized way.
: 2. You have a 4G text file which each line contain some number of words. You
: have only 1G of memory. Implement a function to truly randomize the file in
: the unit of each line. For example, line 1, 2, 3, 4, 5, become something
: like line 3, 5, 4, 2, 1.
|
l********g
发帖数: 24 | 44 Question 1, "GiveMeANumber() and ReturnBackANumber()" 是什么意思? 要返回什么
? |
d*******r
发帖数: 208 | 45 2. so total line # can be counted say 1....n. do a randome shuffle of these
line numbers. then output to a different file while reading the input file
arrange the lines with the random shuffle results.
You
in
【在 i*****j 的大作中提到】
: G家电面.题目完全没有见过，答的磕磕碰碰的，估计是挂了。
: 1. Suppose you have a bunch of phone numbers. Implement functions 1)
: IsNumberTaken(phone #), GiveMeANumber() and ReturnBackANumber() in an
: optimized way.
: 2. You have a 4G text file which each line contain some number of words. You
: have only 1G of memory. Implement a function to truly randomize the file in
: the unit of each line. For example, line 1, 2, 3, 4, 5, become something
: like line 3, 5, 4, 2, 1.
|
a**********2
发帖数: 340 | 46 1. bitset行吗？ 10^10/8才1G多，内存完全能放下 |
a**********2
发帖数: 340 | 47 文件不是random access的吧
的问题？
【在 B*******1 的大作中提到】
: 1. 觉得用trie
: 2. 跟random shuffle有什么区别啊？是不是要考虑有可能一行大于1G，内存装不下的问题？
|
f*********5
发帖数: 576 | 48 需要明确每次返回什么样的number.
如果随便的话
1)这个题跟实现LRU有点像
doubly linked list+hashtable
use hashtable to judge whether the number is in them
use linked list to add new number and return a number
2)也可以用stack+hashtable
each time just push/pop stack and update hashtable
You
in
【在 i*****j 的大作中提到】
: G家电面.题目完全没有见过，答的磕磕碰碰的，估计是挂了。
: 1. Suppose you have a bunch of phone numbers. Implement functions 1)
: IsNumberTaken(phone #), GiveMeANumber() and ReturnBackANumber() in an
: optimized way.
: 2. You have a 4G text file which each line contain some number of words. You
: have only 1G of memory. Implement a function to truly randomize the file in
: the unit of each line. For example, line 1, 2, 3, 4, 5, become something
: like line 3, 5, 4, 2, 1.
|
s*******f
发帖数: 1114 | 49 confused by the expression.
For random, how about generate random float for each unit in the line. when
reach '\n', sort these random numbers and their according units.
You
in
【在 i*****j 的大作中提到】
: G家电面.题目完全没有见过，答的磕磕碰碰的，估计是挂了。
: 1. Suppose you have a bunch of phone numbers. Implement functions 1)
: IsNumberTaken(phone #), GiveMeANumber() and ReturnBackANumber() in an
: optimized way.
: 2. You have a 4G text file which each line contain some number of words. You
: have only 1G of memory. Implement a function to truly randomize the file in
: the unit of each line. For example, line 1, 2, 3, 4, 5, become something
: like line 3, 5, 4, 2, 1.
|
k****n
发帖数: 369 | 50 wrong, you cannot random access the lines, or random write the lines.
these
【在 d*******r 的大作中提到】
: 2. so total line # can be counted say 1....n. do a randome shuffle of these
: line numbers. then output to a different file while reading the input file
: arrange the lines with the random shuffle results.
:
: You
: in
|
|
|
k****n
发帖数: 369 | 51 应该是这样的
【在 y*******g 的大作中提到】
: 无法读入内存，
: 一行大于1G不用考虑把
: 感觉类似merge sort, 只不过以前的sort/compare都改成shuffle就好了
: 把文件分成 N部分，每个分别shuffle, 然后merge的时候从N个文件里面随机去一个
:
: 的问题？
|
i*****j
发帖数: 7 | 52 这个思路很赞！
【在 y*******g 的大作中提到】
: 无法读入内存，
: 一行大于1G不用考虑把
: 感觉类似merge sort, 只不过以前的sort/compare都改成shuffle就好了
: 把文件分成 N部分，每个分别shuffle, 然后merge的时候从N个文件里面随机去一个
:
: 的问题？
|
i*****j
发帖数: 7 | 53 这个应该行。我答的是用两个BST存已用和可用的号码，O(lg(n))查找和插入/删除，对
方明显不满意。
【在 f*********5 的大作中提到】
: 需要明确每次返回什么样的number.
: 如果随便的话
: 1)这个题跟实现LRU有点像
: doubly linked list+hashtable
: use hashtable to judge whether the number is in them
: use linked list to add new number and return a number
: 2)也可以用stack+hashtable
: each time just push/pop stack and update hashtable
:
: You
|
b*****c
发帖数: 1103 | 54 第一题用2个hashtable，现在的和曾经取出过的，O(1） |
B*******1
发帖数: 2454 | 55 GiveMeANumber() and ReturnBackANumber()
这个ReturnBackANumber 究竟是什么意思啊？ 我觉得是取消号码的意思
那么GiveMeANumber我觉得是用户申请电话号码，返回一个还没有用过的，这种情况下
hashtable最坏情况也要一个个找一下吧？ |
b*****c
发帖数: 1103 | 56 任何一个号码要么是取出的，要么是未取出的
所以returnback就是从已取出的hashtable，转一个到未取出的hashtable
O(1)啊
【在 B*******1 的大作中提到】
: GiveMeANumber() and ReturnBackANumber()
: 这个ReturnBackANumber 究竟是什么意思啊？ 我觉得是取消号码的意思
: 那么GiveMeANumber我觉得是用户申请电话号码，返回一个还没有用过的，这种情况下
: hashtable最坏情况也要一个个找一下吧？
|
B*******1
发帖数: 2454 | 57 是的，但是一开始的时候给出一堆电话号码，然后他们全部都在取出那里，但是未取出
是空的
然后用户call GiveMeANumber（） 去申请一个号码，但是你的未取出hashtable还是空
的，你怎么找一个没有人的用户呢？ 难道我题意理解错了。
【在 b*****c 的大作中提到】
: 任何一个号码要么是取出的，要么是未取出的
: 所以returnback就是从已取出的hashtable，转一个到未取出的hashtable
: O(1)啊
|
b*****c
发帖数: 1103 | 58 一开始的时候给出一堆电话号码，然后他们全部都在"""未取出""""那里
call Giveme的意思就是取出一个， initial当然是未取出啦，一堆号码在仓库里等着
取出 |
B*******1
发帖数: 2454 | 59 谢谢，我理解错了。
【在 b*****c 的大作中提到】
: 一开始的时候给出一堆电话号码，然后他们全部都在"""未取出""""那里
: call Giveme的意思就是取出一个， initial当然是未取出啦，一堆号码在仓库里等着
: 取出
|
t*****n
发帖数: 25 | 60 G家电面都给result吗？我的电面是一阿三很简单，但都快十天了也没结果，email给
recruiter也没回，大概完了。是2nd电面了，1st电面5，6天就有结果了。 |
|
|
C*********1
发帖数: 6 | 61 能不能详细说一下merge的过程？
【在 y*******g 的大作中提到】
: 无法读入内存，
: 一行大于1G不用考虑把
: 感觉类似merge sort, 只不过以前的sort/compare都改成shuffle就好了
: 把文件分成 N部分，每个分别shuffle, 然后merge的时候从N个文件里面随机去一个
:
: 的问题？
|
t*****n
发帖数: 25 | 62 你怎样去号码？O(1)从hashtable. deque/linklist靠谱。
【在 b*****c 的大作中提到】
: 一开始的时候给出一堆电话号码，然后他们全部都在"""未取出""""那里
: call Giveme的意思就是取出一个， initial当然是未取出啦，一堆号码在仓库里等着
: 取出
|
b*****c
发帖数: 1103 | 63 ICollection *iColl = HashTable->Keys;
deque 不能实现指定number的 returnbacknumber(int number)吧
它只能pop,push头和尾，所以普适性还是HashTable好
【在 t*****n 的大作中提到】
: 你怎样去号码？O(1)从hashtable. deque/linklist靠谱。
|
r********g
发帖数: 1351 | 64 这N个文件每个都是local的随机吧？不过受楼上的启发，我觉得是：
先分成N个文件
文件Fi(0 <= i < N)自己先shuffle
文件Fi和文件F0-F(i-1)依次shuffle一遍（参见随机洗牌的算法，假设2个文件行数相
等，对每个line取随机数k, 如果k%N==0, 就把这一行互换）。
【在 y*******g 的大作中提到】
: 无法读入内存，
: 一行大于1G不用考虑把
: 感觉类似merge sort, 只不过以前的sort/compare都改成shuffle就好了
: 把文件分成 N部分，每个分别shuffle, 然后merge的时候从N个文件里面随机去一个
:
: 的问题？
|
j********x
发帖数: 2330 | 65 怎么可能是对的
你觉得一个truly random的sequence，会有两个元素总是出现在一个给定的长度的区间
里么。。。
【在 k****n 的大作中提到】
: 应该是这样的
|
a********m
发帖数: 15480 | 66 braket吧。
【在 i*****j 的大作中提到】
: 这个应该行。我答的是用两个BST存已用和可用的号码，O(lg(n))查找和插入/删除，对
: 方明显不满意。
|
a********m
发帖数: 15480 | 67 available hash table有点太复杂了。不知道有没有更好的办法。
【在 b*****c 的大作中提到】
: ICollection *iColl = HashTable->Keys;
: deque 不能实现指定number的 returnbacknumber(int number)吧
: 它只能pop,push头和尾，所以普适性还是HashTable好
|
y*******g
发帖数: 6599 | 68 什么叫两个元素总出现在给定长度？
比如 1, 2,3,4,5,6 分成2个
123
456
然后单独shuffle
213
654
最后merge比如265134
【在 j********x 的大作中提到】
: 怎么可能是对的
: 你觉得一个truly random的sequence，会有两个元素总是出现在一个给定的长度的区间
: 里么。。。
|
r********g
发帖数: 1351 | 69 1,2,3,4,5,6,7,8,9
按照你的办法：
147......
可能出现吗？
【在 y*******g 的大作中提到】
: 什么叫两个元素总出现在给定长度？
: 比如 1, 2,3,4,5,6 分成2个
: 123
: 456
: 然后单独shuffle
: 213
: 654
: 最后merge比如265134
|
y*******g
发帖数: 6599 | 70 为什么不可嫩？
1423
76589
merge的时候第一次取array 1: 1, 第二次还是取array1 : 14, 第三次取array2： 147
..
【在 r********g 的大作中提到】
: 1,2,3,4,5,6,7,8,9
: 按照你的办法：
: 147......
: 可能出现吗？
|
|
|
r********g
发帖数: 1351 | 71 ...还以为你是固定地split的，那你内存问题怎么解决？比如如果内存只能放3个数呢？
147
【在 y*******g 的大作中提到】
: 为什么不可嫩？
: 1423
: 76589
: merge的时候第一次取array 1: 1, 第二次还是取array1 : 14, 第三次取array2： 147
: ..
|
j********x
发帖数: 2330 | 72 不好意思，我看错了
这样是对的
【在 y*******g 的大作中提到】
: 什么叫两个元素总出现在给定长度？
: 比如 1, 2,3,4,5,6 分成2个
: 123
: 456
: 然后单独shuffle
: 213
: 654
: 最后merge比如265134
|
d*******l
发帖数: 338 | 73 第一个我觉得只要一个trie就可以，保存所有沒使用过的的电话号码。IsNumberTaken(
phone #)只要在trie里面找这个号码，找到了就是没被taken。
GiveMeANumber()，在trie里找最左边的那个叶节点就可以。删除这个节点。
ReturnBackANumber() ，把这个number重新放回trie中。
每个操作的代价都是号码的长度。这个其实比hashtable省空间和时间。
第二题我觉得上面说的先分成k份各自shuffle，再随机merge是对的。 |
m**q
发帖数: 189 | 74 我觉得第二个主要是文件无法直接shuffle，得分块后把每一块load到内存
的数组中，然后在数组中随机shuffle后输出。
没搞明白的是如何证明随机merge这样shuffle后的文件块能产生完全随机的结果呢？
IsNumberTaken(
【在 d*******l 的大作中提到】
: 第一个我觉得只要一个trie就可以，保存所有沒使用过的的电话号码。IsNumberTaken(
: phone #)只要在trie里面找这个号码，找到了就是没被taken。
: GiveMeANumber()，在trie里找最左边的那个叶节点就可以。删除这个节点。
: ReturnBackANumber() ，把这个number重新放回trie中。
: 每个操作的代价都是号码的长度。这个其实比hashtable省空间和时间。
: 第二题我觉得上面说的先分成k份各自shuffle，再随机merge是对的。
|
d*******l
发帖数: 338 | 75 我的一个想法：
假如内存大小是M，文件大小是N，把文件分成K块，就有N=KM。然后对每个块进行
shuffle，每个块都有M!种结果，总共有(M!)^K种结果。然后再考虑merge。每种merge
方法可以表示成一个长为N的序列，是M个1，M个2。。。M个K组成的序列的一个排列。
表示的意义就是依次从第几个块取东西。这种序列共有N!/(M!)^K种。一种merge方法和
一种分块shuffle的结果能唯一确定一种最后结果，不会有重复，所以这么操作最后可
能的结果就是(M!)^K*N!/(M!)^K=N!种结果。相当于是完全随机的。
【在 m**q 的大作中提到】
: 我觉得第二个主要是文件无法直接shuffle，得分块后把每一块load到内存
: 的数组中，然后在数组中随机shuffle后输出。
: 没搞明白的是如何证明随机merge这样shuffle后的文件块能产生完全随机的结果呢？
:
: IsNumberTaken(
|
s******n
发帖数: 226 | 76 很妙
不过如果disk不是unlimited 怎么办？ 怎么写进去呢？
merge
【在 d*******l 的大作中提到】
: 我的一个想法：
: 假如内存大小是M，文件大小是N，把文件分成K块，就有N=KM。然后对每个块进行
: shuffle，每个块都有M!种结果，总共有(M!)^K种结果。然后再考虑merge。每种merge
: 方法可以表示成一个长为N的序列，是M个1，M个2。。。M个K组成的序列的一个排列。
: 表示的意义就是依次从第几个块取东西。这种序列共有N!/(M!)^K种。一种merge方法和
: 一种分块shuffle的结果能唯一确定一种最后结果，不会有重复，所以这么操作最后可
: 能的结果就是(M!)^K*N!/(M!)^K=N!种结果。相当于是完全随机的。
|
s*********6
发帖数: 20 | 77 第一道题目应该还要考虑内存使用的问题。
电话号码如果是10位数，用trie表示，可能需要多到9^10字节的空间。
用push/pop stack，需要的空间更大。
如果限制内存1G或者4G，内存不一定够。
感觉用bitmap比较好。 |
d*******u
发帖数: 186 | 78 我回答第一题：
我假定a bunch of phone numbers是可用的电话号码。
初始化： 读入所有的电话号码建Trie (只需要十个分支，0～9).
IsNumberTaken(phone #) {
用phone #查询Trie如果能走到叶子，说明phone #可用，not taken,
return false.
else true.
}
GiveMeANumber() {
//从Trie中取出最左边的号码，返回该号码。
//也可以从Trie中取出随机的号码，返回该号码。
//对每一级节点，随机选一个分支。
//从Trie删除该号码。
}
ReturnBackANumber(phone #) {
把phone # 插入Trie中。
}
You
in
【在 i*****j 的大作中提到】
: G家电面.题目完全没有见过，答的磕磕碰碰的，估计是挂了。
: 1. Suppose you have a bunch of phone numbers. Implement functions 1)
: IsNumberTaken(phone #), GiveMeANumber() and ReturnBackANumber() in an
: optimized way.
: 2. You have a 4G text file which each line contain some number of words. You
: have only 1G of memory. Implement a function to truly randomize the file in
: the unit of each line. For example, line 1, 2, 3, 4, 5, become something
: like line 3, 5, 4, 2, 1.
|
y******u
发帖数: 804 | 79 第一题难道不可以这样？
电话号码没多少吧，北美电话就10位，也算长了。而且都是整数
就建boolean数组Taken，存这个号码是否正在使用。比如
号码 1234567890 就是 Taken[1234567890]=true
其实就是extreme的hash，哈哈～
这样建好二值数组，3个函数就要操作了吧。 |
z****u
发帖数: 104 | 80 如果题目包含了所有可能的电话号码，这个思路是最好的；
如果题目只包含了一部分电话号码，用 hash table 有可能会更有效
【在 y******u 的大作中提到】
: 第一题难道不可以这样？
: 电话号码没多少吧，北美电话就10位，也算长了。而且都是整数
: 就建boolean数组Taken，存这个号码是否正在使用。比如
: 号码 1234567890 就是 Taken[1234567890]=true
: 其实就是extreme的hash，哈哈～
: 这样建好二值数组，3个函数就要操作了吧。
|
|
|
J*********n
发帖数: 370 | 81 这是一轮还是两轮？
You
in
【在 i*****j 的大作中提到】
: G家电面.题目完全没有见过，答的磕磕碰碰的，估计是挂了。
: 1. Suppose you have a bunch of phone numbers. Implement functions 1)
: IsNumberTaken(phone #), GiveMeANumber() and ReturnBackANumber() in an
: optimized way.
: 2. You have a 4G text file which each line contain some number of words. You
: have only 1G of memory. Implement a function to truly randomize the file in
: the unit of each line. For example, line 1, 2, 3, 4, 5, become something
: like line 3, 5, 4, 2, 1.
|
r****t
发帖数: 10904 | 82 你对了。
【在 y******u 的大作中提到】
: 第一题难道不可以这样？
: 电话号码没多少吧，北美电话就10位，也算长了。而且都是整数
: 就建boolean数组Taken，存这个号码是否正在使用。比如
: 号码 1234567890 就是 Taken[1234567890]=true
: 其实就是extreme的hash，哈哈～
: 这样建好二值数组，3个函数就要操作了吧。
|
r****t
发帖数: 10904 | 83 trie is not efficient in space.
【在 d*******u 的大作中提到】
: 我回答第一题：
: 我假定a bunch of phone numbers是可用的电话号码。
: 初始化： 读入所有的电话号码建Trie (只需要十个分支，0～9).
: IsNumberTaken(phone #) {
: 用phone #查询Trie如果能走到叶子，说明phone #可用，not taken,
: return false.
: else true.
: }
: GiveMeANumber() {
: //从Trie中取出最左边的号码，返回该号码。
|
y*********r
发帖数: 94 | 84 这样的话，取新号的复杂度是O(n)
【在 y******u 的大作中提到】
: 第一题难道不可以这样？
: 电话号码没多少吧，北美电话就10位，也算长了。而且都是整数
: 就建boolean数组Taken，存这个号码是否正在使用。比如
: 号码 1234567890 就是 Taken[1234567890]=true
: 其实就是extreme的hash，哈哈～
: 这样建好二值数组，3个函数就要操作了吧。
|
y******u
发帖数: 804 | 85 用别方法不见得就不是O（n）
trie不是，恩。
【在 y*********r 的大作中提到】
: 这样的话，取新号的复杂度是O(n)
|
y*********r
发帖数: 94 | 86 可以把array和bitmap结合着用。用bitmap来存numbers。同时维护一个array来存各个
号码区间（比如，以0开头的，以1开头的。也可以是以00开头，01开头...99开头）的
计数，这样在GiveMeANumber()时只在还有剩余号码的区间里面去找。
【在 y******u 的大作中提到】
: 用别方法不见得就不是O（n）
: trie不是，恩。
|
H*M
发帖数: 1268 | 87 hashtable+linkedList也可以实现操作的时候O(1)吧
先把给的number也就是available的number放到hashtable里，同事互相链起来
isNumberTaken()直接search hashtable O(1)
GiveMeNumber()就从linkedList头取一个，并且删除hashtable里的 O(1)
ReturnBackAnumber()就insert进去到hashtable和list O(1)
trie的话，我觉得很难在面试时候implement阿，复杂了.
IsNumberTaken(
【在 d*******l 的大作中提到】
: 第一个我觉得只要一个trie就可以，保存所有沒使用过的的电话号码。IsNumberTaken(
: phone #)只要在trie里面找这个号码，找到了就是没被taken。
: GiveMeANumber()，在trie里找最左边的那个叶节点就可以。删除这个节点。
: ReturnBackANumber() ，把这个number重新放回trie中。
: 每个操作的代价都是号码的长度。这个其实比hashtable省空间和时间。
: 第二题我觉得上面说的先分成k份各自shuffle，再随机merge是对的。
|
y*********r
发帖数: 94 | 88 very nice
【在 H*M 的大作中提到】
: hashtable+linkedList也可以实现操作的时候O(1)吧
: 先把给的number也就是available的number放到hashtable里，同事互相链起来
: isNumberTaken()直接search hashtable O(1)
: GiveMeNumber()就从linkedList头取一个，并且删除hashtable里的 O(1)
: ReturnBackAnumber()就insert进去到hashtable和list O(1)
: trie的话，我觉得很难在面试时候implement阿，复杂了.
:
: IsNumberTaken(
|
