boards

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字 访问原贴
JobHunting版 - 看看这道T家电面题如何优化
相关主题
● 请问：C++里一般用什么做hashtable？
● 请教个面试题， tree和hashmap的区别
● randomized quick sort的最坏情况时间复杂度
● 一道msft的题
● leetcode里面的Recover Binary Search Tree怎么用O(1)space
● 怎么理解递归解决的“swap every two elements in a linked list”？
● [合集] 一道CS面试题
● 刚完的amazon电话面试
● 电面结束之后
● 也问一个算法题
相关话题的讨论汇总
话题: unassigned话题: ssn话题: 随机话题: bst
进入JobHunting版参与讨论
1 (共1页)
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
8
又是老题吧？看看这个。
http://blog.sina.com.cn/s/blog_b9285de20101gx01.html
p*****2
发帖数: 21240
9
又是老题吧？看看这个。
http://blog.sina.com.cn/s/blog_b9285de20101gx01.html
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]
相关主题
● 一道msft的题
● leetcode里面的Recover Binary Search Tree怎么用O(1)space
● 怎么理解递归解决的“swap every two elements in a linked list”？
● [合集] 一道CS面试题
进入JobHunting版参与讨论
a***o
发帖数: 1182
11
哦,那就array+hashset

【在 a********3 的大作中提到】
: 这样算有规律的，三哥说有规律的会被别人猜到的不行
a********3
发帖数: 228
12
多谢指教，这个看来可以做

【在 p*****2 的大作中提到】
: 又是老题吧？看看这个。
: http://blog.sina.com.cn/s/blog_b9285de20101gx01.html
B***i
发帖数: 724
13
你们讨论复杂度的时候， n 是什么？
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 的大作中提到】
: 先都随机排序好,存好,然后一个一个取?
相关主题
● 刚完的amazon电话面试
● 电面结束之后
● 也问一个算法题
● 这是什么数据结构？
进入JobHunting版参与讨论
p*****2
发帖数: 21240
21
又是老题吧？看看这个。
http://blog.sina.com.cn/s/blog_b9285de20101gx01.html
p*****2
发帖数: 21240
22
又是老题吧？看看这个。
http://blog.sina.com.cn/s/blog_b9285de20101gx01.html
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
25
多谢指教，这个看来可以做

【在 p*****2 的大作中提到】
: 又是老题吧？看看这个。
: http://blog.sina.com.cn/s/blog_b9285de20101gx01.html
B***i
发帖数: 724
26
你们讨论复杂度的时候， n 是什么？
n******n
发帖数: 567
27
同问

【在 B***i 的大作中提到】
: 你们讨论复杂度的时候， n 是什么？
1 (共1页)
进入JobHunting版参与讨论
相关主题
● 也问一个算法题
● 这是什么数据结构？
● 那道经典的求和问题
● 攒人品，twitter二面面经
● 问一道google老题
● 请教一道题
● 问个关于set的题
● boggle的复杂度
● 报一个A家intern offer
● 感觉careercup的作者对DP的理解有问题
相关话题的讨论汇总
话题: unassigned话题: ssn话题: 随机话题: bst
除非另有声明，本站内容采用Creative Commons BY-NC-SA 3.0协议进行许可，转载请注明来自未名观察 - 隐私政策2011-07-24 10:06:12由admin编辑