w****f
发帖数: 684 | 1 Array based hashset, methods: insert(), delete(), find(). Implement a
printAll() to print the reverse order of insertion. Example, insert a, b, c
, print c, b, a.
始终没明白题意和考点。我说加一个stack 保存index，interviewer不太满意，提
示delete 还没用。。。还提示array-based。。。
还有hashset／hashtable有ordering？ |
p*****2
发帖数: 21240 | 2
c
没明白。array based hashset的三个function已经有了是吗？
如果
insert a, b, c
delete b,
应该print c a?
【在 w****f 的大作中提到】
: Array based hashset, methods: insert(), delete(), find(). Implement a
: printAll() to print the reverse order of insertion. Example, insert a, b, c
: , print c, b, a.
: 始终没明白题意和考点。我说加一个stack 保存index，interviewer不太满意，提
: 示delete 还没用。。。还提示array-based。。。
: 还有hashset／hashtable有ordering？
|
w****f
发帖数: 684 | 3 Yes, 三个function已经有了，可以修改。
insert：a b c
print: c b a
My solution: stack keep track the ordering. But interviewer 不满意，提示
delete() and the hashset is array-based...
可惜愚钝。。。 |
p*****2
发帖数: 21240 | 4
知不知道hashset是如何用array来实现的？
如果print 之前 delete b了， 应该print c b a, 还是 c a 呢？
stack的话你删除一个元素挺麻烦吧？
【在 w****f 的大作中提到】
: Yes, 三个function已经有了，可以修改。
: insert：a b c
: print: c b a
: My solution: stack keep track the ordering. But interviewer 不满意，提示
: delete() and the hashset is array-based...
: 可惜愚钝。。。
|
w****f
发帖数: 684 | 5 也可能这题是考communication skill。。。
没用过hashset，不清楚
应该c a
是额外加一个stack， 只保存index。 s
【在 p*****2 的大作中提到】
:
: 知不知道hashset是如何用array来实现的？
: 如果print 之前 delete b了， 应该print c b a, 还是 c a 呢？
: stack的话你删除一个元素挺麻烦吧？
|
p*****2
发帖数: 21240 | 6
靠。他说delete是不是说你那个stack的不work呀？
【在 w****f 的大作中提到】
: 也可能这题是考communication skill。。。
:
: 没用过hashset，不清楚
: 应该c a
: 是额外加一个stack， 只保存index。 s
|
k****i
发帖数: 552 | 7 in the array, keep an extra doubly link pointing to the next item being
added, and the previous one.
every time you delete, update the links.
Not sure if that's what the interview wants.
c
【在 w****f 的大作中提到】
: 也可能这题是考communication skill。。。
:
: 没用过hashset，不清楚
: 应该c a
: 是额外加一个stack， 只保存index。 s
|
p*****2
发帖数: 21240 | 8
如果这样的话要那个array有什么用呀？
【在 k****i 的大作中提到】
: in the array, keep an extra doubly link pointing to the next item being
: added, and the previous one.
: every time you delete, update the links.
: Not sure if that's what the interview wants.
:
: c
|
w****f
发帖数: 684 | 9 不是，原题没有stack。 可是我不知如何keep the order of insertion？ 只好说加
一个stack并修改insert和find。好像用不到delete。
还有，要求keep hashset after printAll。
【在 p*****2 的大作中提到】
:
: 如果这样的话要那个array有什么用呀？
|
p*****2
发帖数: 21240 | 10
题目里不是有delete函数吗？既然有的话就可以delete元素呀。那stack就不行了呀。
【在 w****f 的大作中提到】
: 不是，原题没有stack。 可是我不知如何keep the order of insertion？ 只好说加
: 一个stack并修改insert和find。好像用不到delete。
: 还有，要求keep hashset after printAll。
|
|
|
k****i
发帖数: 552 | 11 It's array based. You should ask if you can modify the array.
if it's a phone screen, should not be a super complex solution.
【在 p*****2 的大作中提到】
:
: 题目里不是有delete函数吗？既然有的话就可以delete元素呀。那stack就不行了呀。
|
p*****2
发帖数: 21240 | 12
刚想明白什么是array based hashset。你那解是可以的。就是复杂度高些。不过再加
个hashtable也没啥意思。
【在 k****i 的大作中提到】
: It's array based. You should ask if you can modify the array.
: if it's a phone screen, should not be a super complex solution.
|
p*****2
发帖数: 21240 | 13 想到一个办法
array index是hashcode % size
array里的元素是
class Element:
object
prev
next
总是保留最后加入的元素的index
加入新元素的时候，把最后元素index的next设成新元素的id，新元素的prev设成上一
个元素id
这样就可以反向打印了。删除的时候更新一下就可以了。 |
w****f
发帖数: 684 | 14
keep an extra double linked list, update the list when insert/delete.
It's better.
【在 k****i 的大作中提到】
: in the array, keep an extra doubly link pointing to the next item being
: added, and the previous one.
: every time you delete, update the links.
: Not sure if that's what the interview wants.
:
: c
|
w****f
发帖数: 684 | 15 你这是hashset ＋ double link，
牛。。。
【在 p*****2 的大作中提到】
: 想到一个办法
: array index是hashcode % size
: array里的元素是
: class Element:
: object
: prev
: next
: 总是保留最后加入的元素的index
: 加入新元素的时候，把最后元素index的next设成新元素的id，新元素的prev设成上一
: 个元素id
|
p*****2
发帖数: 21240 | 16 代码
size=100
class Element:
def __init__(self,obj,prev):
self.obj=obj
self.prev=prev
self.next=-1
class HashSet:
l=[None]*size
last=-1
def insert(self,obj):
h=hash(obj)%size
if self.l[h]==None:
self.l[h]=Element(obj,self.last)
if self.last!=-1:
self.l[self.last].next=h
self.last=h
def delete(self,obj):
h=hash(obj)%size
if self.l[h]!=None:
pv=self.l[self.last].prev
if self.l[h].prev==-1:
if self.l[h].next!=-1:
self.l[self.l[h].next].prev=-1
elif self.l[h].next==-1:
if self.l[h].prev!=-1:
self.l[self.l[h].prev].next=-1
else:
self.l[self.l[h].prev].next=self.l[h].next
self.l[self.l[h].next].prev=self.l[h].prev
self.l[h]=None
if h==self.last:
self.last=pv
def prinths(self):
i=self.last
while i!=-1:
print self.l[i].obj
i=self.l[i].prev |
h*****3
发帖数: 1391 | 17 不知道insert同一个数的时候,会不会分配多个空间,如果可以的话,对每个input的数
insert2遍,这样必然有一个被放在了冲突数组中.所有input的数必然都在冲突数组中.
而且冲突空间的数是按照输入顺序排列的.
print的时候,从array的last index读,每读一个,print,然后delete,find,delete,这样
,读到头时,所有的输入就都reversed了. |
Z*****Z
发帖数: 723 | 18 膜拜
【在 p*****2 的大作中提到】
: 代码
: size=100
: class Element:
: def __init__(self,obj,prev):
: self.obj=obj
: self.prev=prev
: self.next=-1
:
: class HashSet:
: l=[None]*size
|
p*****2
发帖数: 21240 | 19
HashSet不允许insert duplicate吧？
【在 h*****3 的大作中提到】
: 不知道insert同一个数的时候,会不会分配多个空间,如果可以的话,对每个input的数
: insert2遍,这样必然有一个被放在了冲突数组中.所有input的数必然都在冲突数组中.
: 而且冲突空间的数是按照输入顺序排列的.
: print的时候,从array的last index读,每读一个,print,然后delete,find,delete,这样
: ,读到头时,所有的输入就都reversed了.
|
p*****2
发帖数: 21240 | 20
其实是hashset+double link+hashtable. :)
【在 w****f 的大作中提到】
: 你这是hashset ＋ double link，
: 牛。。。
:
|
|
|
p*****2
发帖数: 21240 | 21
Python里边类成员总是要写成self.XXX吗？这么写就比较麻烦了。
【在 Z*****Z 的大作中提到】
: 膜拜
|
Z*****Z
发帖数: 723 | 22 好像缺了不行
从语法上说可以不叫self，叫一个更短的名字。不过叫self是个strong convention
【在 p*****2 的大作中提到】
:
: Python里边类成员总是要写成self.XXX吗？这么写就比较麻烦了。
|
w****f
发帖数: 684 | 23 Python? 没用过。
【在 p*****2 的大作中提到】
: 代码
: size=100
: class Element:
: def __init__(self,obj,prev):
: self.obj=obj
: self.prev=prev
: self.next=-1
:
: class HashSet:
: l=[None]*size
|
