a********3 发帖数: 228 | 1 T家的第一面,我没有优化到三哥想要的程度。话说这个面试还是我骚扰recruiter两次
得来的。。。
题目是关于9位SSN号的随机分配和回收,实现下面两个函数。
SSN assignRandom()
//分配新的随机号。should randomly return an unassigned SSN and should make
this number unavailable for future assignRandom() calls
void release(SSN)
//回收一个随机号。should make the given SSN available for future
assignRandom() calls.
SSNs are in the range : [100000000 - 999999999]
实现assignRandom函数时,如果连续调用rand()函数直到找到一个unassigned,时间复
杂度最坏就可能是O(n)。我实现的是分别维护assigned和unassigned两个集合,
unassigned的集合用BST index,assignRandom时insert into unassigned BST,
release时delete from unassigned BST,时间复杂度是O(log n), 空间复杂度是O(n)。
三哥最后说有时间复杂度O(1),空间复杂度O(n)的解法。我没弄出来。难道是用
hashtable?hashtable不适用随机选一个元素吧? |
a***o 发帖数: 1182 | 2 先都随机排序好,存好,然后一个一个取?
【在 a********3 的大作中提到】 : T家的第一面,我没有优化到三哥想要的程度。话说这个面试还是我骚扰recruiter两次 : 得来的。。。 : 题目是关于9位SSN号的随机分配和回收,实现下面两个函数。 : SSN assignRandom() : //分配新的随机号。should randomly return an unassigned SSN and should make : this number unavailable for future assignRandom() calls : void release(SSN) : //回收一个随机号。should make the given SSN available for future : assignRandom() calls. : SSNs are in the range : [100000000 - 999999999]
|
j*****y 发帖数: 1071 | 3 这个和以前的那个释放繁忙服务器,标记一个服务器为繁忙的题目差不多吧
【在 a********3 的大作中提到】 : T家的第一面,我没有优化到三哥想要的程度。话说这个面试还是我骚扰recruiter两次 : 得来的。。。 : 题目是关于9位SSN号的随机分配和回收,实现下面两个函数。 : SSN assignRandom() : //分配新的随机号。should randomly return an unassigned SSN and should make : this number unavailable for future assignRandom() calls : void release(SSN) : //回收一个随机号。should make the given SSN available for future : assignRandom() calls. : SSNs are in the range : [100000000 - 999999999]
|
f*****e 发帖数: 2992 | 4 用数组就行,随机取一个,然后与head swap。release也是和head swap。
以前的帖子有一个和hash结合使用的变体比你这个复杂。
【在 a********3 的大作中提到】 : T家的第一面,我没有优化到三哥想要的程度。话说这个面试还是我骚扰recruiter两次 : 得来的。。。 : 题目是关于9位SSN号的随机分配和回收,实现下面两个函数。 : SSN assignRandom() : //分配新的随机号。should randomly return an unassigned SSN and should make : this number unavailable for future assignRandom() calls : void release(SSN) : //回收一个随机号。should make the given SSN available for future : assignRandom() calls. : SSNs are in the range : [100000000 - 999999999]
|
a********3 发帖数: 228 | 5 你说的head是unassigned的head指针?release不能和head swap吧,那个达不到O(1) |
a********3 发帖数: 228 | 6 求那个帖子link
【在 f*****e 的大作中提到】 : 用数组就行,随机取一个,然后与head swap。release也是和head swap。 : 以前的帖子有一个和hash结合使用的变体比你这个复杂。
|
a********3 发帖数: 228 | 7 这样算有规律的,三哥说有规律的会被别人猜到的不行
【在 a***o 的大作中提到】 : 先都随机排序好,存好,然后一个一个取?
|
p*****2 发帖数: 21240 | |
|
p*****2 发帖数: 21240 | |
d**********x 发帖数: 4083 | 10 用hashtable模拟shuffle数组的过程
要开的额外空间比较多,描述起来比较复杂
但是想好了并不是难题
【在 a********3 的大作中提到】 : T家的第一面,我没有优化到三哥想要的程度。话说这个面试还是我骚扰recruiter两次 : 得来的。。。 : 题目是关于9位SSN号的随机分配和回收,实现下面两个函数。 : SSN assignRandom() : //分配新的随机号。should randomly return an unassigned SSN and should make : this number unavailable for future assignRandom() calls : void release(SSN) : //回收一个随机号。should make the given SSN available for future : assignRandom() calls. : SSNs are in the range : [100000000 - 999999999]
|
|
|
a***o 发帖数: 1182 | 11 哦,那就array+hashset
【在 a********3 的大作中提到】 : 这样算有规律的,三哥说有规律的会被别人猜到的不行
|
a********3 发帖数: 228 | |
B***i 发帖数: 724 | |
a********3 发帖数: 228 | 14 T家的第一面,我没有优化到三哥想要的程度。话说这个面试还是我骚扰recruiter两次
得来的。。。
题目是关于9位SSN号的随机分配和回收,实现下面两个函数。
SSN assignRandom()
//分配新的随机号。should randomly return an unassigned SSN and should make
this number unavailable for future assignRandom() calls
void release(SSN)
//回收一个随机号。should make the given SSN available for future
assignRandom() calls.
SSNs are in the range : [100000000 - 999999999]
实现assignRandom函数时,如果连续调用rand()函数直到找到一个unassigned,时间复
杂度最坏就可能是O(n)。我实现的是分别维护assigned和unassigned两个集合,
unassigned的集合用BST index,assignRandom时insert into unassigned BST,
release时delete from unassigned BST,时间复杂度是O(log n), 空间复杂度是O(n)。
三哥最后说有时间复杂度O(1),空间复杂度O(n)的解法。我没弄出来。难道是用
hashtable?hashtable不适用随机选一个元素吧? |
a***o 发帖数: 1182 | 15 先都随机排序好,存好,然后一个一个取?
【在 a********3 的大作中提到】 : T家的第一面,我没有优化到三哥想要的程度。话说这个面试还是我骚扰recruiter两次 : 得来的。。。 : 题目是关于9位SSN号的随机分配和回收,实现下面两个函数。 : SSN assignRandom() : //分配新的随机号。should randomly return an unassigned SSN and should make : this number unavailable for future assignRandom() calls : void release(SSN) : //回收一个随机号。should make the given SSN available for future : assignRandom() calls. : SSNs are in the range : [100000000 - 999999999]
|
j*****y 发帖数: 1071 | 16 这个和以前的那个释放繁忙服务器,标记一个服务器为繁忙的题目差不多吧
【在 a********3 的大作中提到】 : T家的第一面,我没有优化到三哥想要的程度。话说这个面试还是我骚扰recruiter两次 : 得来的。。。 : 题目是关于9位SSN号的随机分配和回收,实现下面两个函数。 : SSN assignRandom() : //分配新的随机号。should randomly return an unassigned SSN and should make : this number unavailable for future assignRandom() calls : void release(SSN) : //回收一个随机号。should make the given SSN available for future : assignRandom() calls. : SSNs are in the range : [100000000 - 999999999]
|
f*****e 发帖数: 2992 | 17 用数组就行,随机取一个,然后与head swap。release也是和head swap。
以前的帖子有一个和hash结合使用的变体比你这个复杂。
【在 a********3 的大作中提到】 : T家的第一面,我没有优化到三哥想要的程度。话说这个面试还是我骚扰recruiter两次 : 得来的。。。 : 题目是关于9位SSN号的随机分配和回收,实现下面两个函数。 : SSN assignRandom() : //分配新的随机号。should randomly return an unassigned SSN and should make : this number unavailable for future assignRandom() calls : void release(SSN) : //回收一个随机号。should make the given SSN available for future : assignRandom() calls. : SSNs are in the range : [100000000 - 999999999]
|
a********3 发帖数: 228 | 18 你说的head是unassigned的head指针?release不能和head swap吧,那个达不到O(1) |
a********3 发帖数: 228 | 19 求那个帖子link
【在 f*****e 的大作中提到】 : 用数组就行,随机取一个,然后与head swap。release也是和head swap。 : 以前的帖子有一个和hash结合使用的变体比你这个复杂。
|
a********3 发帖数: 228 | 20 这样算有规律的,三哥说有规律的会被别人猜到的不行
【在 a***o 的大作中提到】 : 先都随机排序好,存好,然后一个一个取?
|
|
|
p*****2 发帖数: 21240 | |
p*****2 发帖数: 21240 | |
d**********x 发帖数: 4083 | 23 用hashtable模拟shuffle数组的过程
要开的额外空间比较多,描述起来比较复杂
但是想好了并不是难题
【在 a********3 的大作中提到】 : T家的第一面,我没有优化到三哥想要的程度。话说这个面试还是我骚扰recruiter两次 : 得来的。。。 : 题目是关于9位SSN号的随机分配和回收,实现下面两个函数。 : SSN assignRandom() : //分配新的随机号。should randomly return an unassigned SSN and should make : this number unavailable for future assignRandom() calls : void release(SSN) : //回收一个随机号。should make the given SSN available for future : assignRandom() calls. : SSNs are in the range : [100000000 - 999999999]
|
a***o 发帖数: 1182 | 24 哦,那就array+hashset
【在 a********3 的大作中提到】 : 这样算有规律的,三哥说有规律的会被别人猜到的不行
|
a********3 发帖数: 228 | |
B***i 发帖数: 724 | |
n******n 发帖数: 567 | 27 同问
【在 B***i 的大作中提到】 : 你们讨论复杂度的时候, n 是什么?
|