1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Designing a hashset with LinkedLists as buckets

Discussion in 'Programming/Internet' started by Aviral Srivastava, Aug 2, 2020.

  1. I am solving a problem on Leetcode that requires me to design a hash set. I intend to solve it using linked lists where each linked list would represent a bucket.

    I am intending to implement this: [​IMG]

    However, I am failing in one large test case.

    This is my solution that failed a test case mentioned below:

    class MyHashSet:

    def __init__(self):
    """
    Initialize your data structure here.
    """
    self.key_range = 769
    self.buckets = [Bucket() for _ in range(self.key_range)]

    def add(self, key: int) -> None:
    _hash_ = self._hash(key)
    bucket = self.buckets[_hash_]
    bucket.insert(key)

    def _hash(self, key):
    return key % self.key_range

    def remove(self, key: int) -> None:
    _hash_ = self._hash(key)
    bucket = self.buckets[_hash_]
    bucket.delete(key)

    def contains(self, key: int) -> bool:
    """
    Returns true if this set contains the specified element
    """
    _hash_ = self._hash(key)
    bucket = self.buckets[_hash_]
    return bucket.check_val(key)


    class Node:
    def __init__(self, val):
    self.val = val
    self.next = None


    class Bucket:
    def __init__(self):
    self.head = Node('*')
    self.curr = self.head

    def insert(self, val):
    if not self.check_val(val):
    self.curr.next = Node(val)
    self.curr = self.curr.next

    def delete(self, val):
    curr = self.head.next
    prev = self.head
    # found = False
    while curr is not None:
    if curr.val == val:
    prev.next = curr.next
    return
    prev = curr
    curr = curr.next

    def check_val(self, val):
    curr = self.head.next
    while curr:
    if curr.val == val:
    return True
    curr = curr.next
    return False



    The failed test case is:

    Input:

    ["MyHashSet","contains","remove","add","add","add","add","contains","add","add","contains","contains","add","contains","add","add","add","contains","remove","add","add","contains","add","add","add","add","remove","add","add","add","add","contains","add","add","contains","contains","contains","remove","add","add","contains","remove","remove","add","add","add","add","add","contains","remove","contains","add","contains","add","contains","remove","add","add","remove","contains","add","add","add","add","add","add","add","contains","remove","add","add","remove","remove","add","remove","add","remove","add","add","add","add","add","add","add","remove","add","remove","remove","add","add","add","add","contains","add","add","remove","add","add","add","remove","add","add","add","add","contains","add","add","add","remove","contains","add","add","add","add","add","remove","add","contains","contains","add","add","add","add","contains","remove","add","contains","add","contains","contains","add","add","contains","add","add","add","add","add","add","add","contains","remove","add","contains","add","remove","add","remove","remove","add","add","contains","add","remove","contains","add","add","add","add","add","add","add","contains","remove","remove","contains","add","contains","remove","add","add","add","add","contains","add","remove","add","remove","add","remove","add","add","add","remove","contains","add","add","add","add","remove","add","add","contains","contains","contains","remove","contains","remove","add","contains","add","add","add","add","remove","add","add","add","remove","remove","add","add","add","add","remove","add","remove","contains","add","contains","add","contains","add","contains","add","add","add","remove","add","add","add","add","add","contains","add","add","add","add","add","add","remove","add","remove","add","add","add","contains","add","add","remove","remove","remove","contains","remove","add","add","remove","add","contains","add","add","remove","contains","add","add","add","contains","remove","add","add","remove","contains","remove","add","contains","remove","add","add","add","add","contains","add","contains","add","remove","contains","add","add","add","add","add","add","add","remove","contains","contains","add","remove","add","remove","contains","add","contains","add","remove","add","add","add","add","remove","add","add","add","add","add","remove","contains","add","add","remove","contains","add","add","contains","add","remove","add","remove","add","add","remove","contains","add","add","add","contains","add","add","add","remove","add","remove","contains","add","add","contains","add","contains","add","add","remove","add","contains","contains","remove","contains","add","contains","add","add","remove","remove","add","add","remove","add","contains","add","add","add","contains","add","add","add","add","add","contains","add","add","contains","add","add","add","remove","add","add","add","add","add","add","add","add","remove","add","add","contains","remove","add","remove","contains","add","add","add","remove","add","add","contains","contains","add","contains","add","add","remove","add","add","remove","remove","add","add","add","contains","add","add","remove","add","remove","add","add","add","contains","add","add","add","add","contains","add","remove","add","add","remove","add","add","contains","add","add","add","add","contains","add","contains","add","add","add","add","add","remove","remove","remove","remove","contains","add","add","add","contains","add","contains","remove","add","add","contains","add","add","contains","add","contains","add","remove","add","remove","add","add","contains","add","add","add","add","add","add","add","add","add","add","add","add","add","contains","add","add","remove","add","add","remove","add","remove","remove","remove","contains","remove","contains","remove","add","remove","add","add","remove","add","add","remove","add","add","remove","add","contains","remove","add","contains","contains","remove","add","contains","add","add","contains","contains","add","add","add","add","contains","add","contains","add","add","remove","add","remove","contains","add","remove","remove","add","add","contains","contains","contains","add","contains","add","add","remove","add","add","add","remove","add","add","add","add","contains","remove","remove","contains","add","add","add","add","add","add","remove","contains","remove","add","add","add","contains","add","remove","add","add","remove","add","add","add","add","remove","remove","remove","add","contains","add","add","add","add","add","add","add","remove","add","add","add","add","add","add","add","remove","add","add","add","add","remove","add","add","add","contains","add","remove","add","add","add","add","add","add","add","add","add","contains","remove","remove","contains","add","remove","add","contains","add","remove","add","contains","add","add","add","add","contains","add","add","contains","contains","contains","add","remove","contains","add","add","remove","add","add","add","add","remove","add","contains","add","add","remove","contains","contains","add","add","add","add","add","add","add","remove","contains","remove","add","add","add","remove","contains","remove","contains","add","add","remove","remove","remove","add","add","contains","add","add","add","add","remove","add","add","add","add","remove","add","add","contains","add","add","add","remove","contains","remove","contains","contains","add","add","add","add","contains","add","add","remove","add","add","add","contains","add","add","add","contains","add","remove","add","add","remove","add","add","add","add","add","contains","add","add","add","contains","add","contains","contains","remove","remove","add","add","remove","add","add","contains","add","add","contains","add","add","contains","add","add","add","contains","add","add","add","add","add","remove","add","remove","add","add","remove","add","add","remove","add","add","add","add","remove","add","add","add","add","add","add","add","add","add","remove","add","contains","add","add","add","contains","contains","remove","add","add","contains","remove","add","remove","contains","remove","add","add","add","contains","contains","add","contains","add","add","add","contains","add","add","add","contains","add","add","contains","contains","remove","add","contains","contains","remove","add","add","contains","remove","add","add","contains","remove","add","add","add","contains","add","add","remove","add","add","add","add","contains","remove","remove","contains","contains","remove","add","add","contains","add","remove","contains","add","add","contains","contains","remove","add","add","add","add","add","add","contains","remove","contains","add","remove","add","add","remove","contains","remove","remove","remove","remove","add","add","add","contains","contains","add","add","add","add","add","remove","remove","add","contains","contains","add","add","contains","add","add","add","add","add","add","add","add","add","add","remove","remove","add","add","add","contains","add","add","add","contains","add","add","remove","contains","add","remove","remove","add","add","add","add","add","add","contains","add","add","add","remove","add","contains","add","remove","add","add","add","contains","add","add","add","add","remove","add","contains","remove","contains","remove","add","contains","add","add","remove","add","add","remove","add","remove","add","remove","add","contains","contains","add","contains","remove","contains","remove","add","remove","add","remove","add","remove","add","contains","add","remove"]
    [[],[624],[182],[74],[647],[724],[575],[802],[343],[320],[329],[343],[339],[618],[493],[592],[894],[724],[537],[404],[301],[727],[750],[437],[364],[243],[436],[262],[412],[246],[985],[592],[187],[644],[578],[320],[412],[31],[297],[887],[74],[601],[995],[498],[808],[821],[443],[139],[808],[90],[703],[275],[364],[839],[785],[151],[575],[937],[615],[571],[459],[978],[530],[649],[743],[672],[539],[644],[955],[509],[692],[320],[19],[726],[242],[426],[242],[359],[969],[208],[963],[205],[687],[527],[435],[969],[387],[723],[46],[124],[584],[754],[359],[981],[753],[275],[277],[99],[849],[237],[855],[398],[170],[977],[965],[832],[371],[284],[968],[978],[106],[815],[737],[503],[72],[203],[685],[647],[268],[315],[753],[602],[353],[626],[96],[637],[521],[292],[654],[686],[774],[148],[72],[146],[384],[760],[769],[51],[606],[993],[80],[349],[13],[731],[120],[525],[656],[18],[445],[448],[4],[126],[214],[569],[774],[594],[814],[57],[823],[240],[92],[424],[165],[879],[1],[555],[317],[969],[145],[530],[364],[402],[617],[398],[71],[213],[290],[488],[702],[522],[837],[361],[247],[352],[575],[623],[760],[139],[224],[547],[283],[985],[57],[590],[302],[816],[277],[690],[65],[80],[185],[780],[238],[484],[906],[445],[429],[59],[475],[562],[989],[524],[946],[599],[543],[573],[753],[150],[290],[588],[415],[173],[828],[57],[550],[180],[977],[474],[378],[64],[436],[377],[2],[837],[646],[947],[937],[234],[388],[988],[90],[221],[960],[592],[576],[247],[769],[134],[216],[973],[868],[262],[836],[629],[766],[998],[141],[992],[36],[317],[547],[765],[320],[976],[556],[784],[606],[289],[504],[112],[10],[402],[28],[175],[489],[459],[237],[711],[787],[913],[814],[162],[343],[265],[865],[750],[787],[986],[112],[417],[51],[40],[745],[433],[584],[212],[408],[644],[591],[59],[298],[16],[989],[986],[304],[506],[85],[131],[934],[257],[372],[690],[960],[151],[712],[976],[643],[900],[853],[33],[58],[220],[217],[498],[825],[116],[586],[69],[158],[121],[388],[112],[474],[750],[253],[77],[110],[987],[680],[227],[60],[495],[586],[989],[727],[649],[199],[985],[554],[848],[522],[943],[831],[121],[390],[106],[717],[220],[563],[15],[24],[840],[674],[936],[973],[111],[260],[586],[341],[422],[806],[966],[694],[99],[425],[860],[493],[157],[487],[509],[967],[370],[790],[460],[383],[777],[660],[144],[106],[728],[192],[953],[456],[936],[81],[69],[988],[732],[836],[301],[882],[906],[637],[438],[334],[456],[848],[38],[288],[563],[653],[30],[110],[230],[144],[561],[404],[216],[360],[639],[509],[764],[253],[385],[114],[552],[255],[549],[752],[441],[464],[862],[747],[870],[717],[296],[491],[155],[500],[513],[25],[894],[192],[199],[24],[737],[486],[4],[227],[895],[998],[387],[126],[68],[772],[594],[710],[243],[279],[191],[730],[160],[784],[378],[53],[260],[564],[974],[751],[913],[167],[303],[81],[552],[405],[348],[775],[222],[731],[594],[953],[255],[740],[110],[980],[175],[500],[921],[366],[805],[476],[738],[869],[114],[348],[916],[598],[815],[632],[24],[968],[78],[285],[182],[229],[247],[745],[574],[837],[908],[314],[990],[577],[22],[221],[525],[628],[228],[696],[145],[398],[652],[431],[380],[574],[253],[408],[137],[71],[120],[185],[156],[392],[395],[875],[957],[241],[938],[525],[902],[706],[416],[699],[265],[39],[810],[963],[288],[991],[483],[991],[520],[190],[772],[432],[695],[112],[321],[447],[234],[55],[239],[993],[937],[624],[689],[787],[921],[292],[611],[888],[151],[463],[745],[367],[694],[567],[352],[439],[377],[616],[499],[995],[454],[578],[743],[771],[758],[279],[349],[721],[831],[394],[412],[454],[344],[920],[832],[151],[312],[830],[217],[815],[254],[497],[882],[997],[380],[734],[399],[720],[568],[860],[689],[814],[194],[503],[169],[459],[99],[99],[142],[301],[784],[472],[812],[204],[618],[675],[267],[725],[572],[77],[786],[634],[980],[829],[930],[754],[481],[484],[423],[377],[425],[521],[53],[552],[698],[664],[412],[666],[255],[308],[822],[931],[99],[123],[667],[931],[724],[515],[99],[270],[240],[808],[129],[6],[266],[806],[314],[235],[668],[236],[966],[173],[639],[306],[782],[135],[918],[285],[185],[880],[686],[58],[598],[290],[623],[71],[726],[436],[55],[305],[410],[313],[777],[554],[177],[456],[85],[436],[921],[523],[623],[736],[917],[860],[572],[183],[630],[676],[866],[754],[723],[400],[533],[606],[583],[524],[624],[407],[697],[823],[917],[192],[514],[535],[131],[966],[100],[639],[383],[35],[251],[838],[614],[118],[654],[927],[111],[674],[431],[816],[679],[352],[734],[887],[129],[185],[257],[332],[187],[727],[434],[750],[949],[335],[427],[259],[365],[642],[422],[121],[212],[857],[208],[148],[175],[945],[522],[197],[619],[862],[768],[835],[595],[841],[528],[113],[560],[449],[795],[421],[40],[314],[417],[219],[655],[859],[293],[10],[844],[263],[98],[682],[120],[809],[810],[235],[587],[681],[121],[410],[661],[806],[976],[3],[938],[806],[648],[227],[351],[192],[266],[694],[736],[428],[123],[933],[147],[407],[612],[619],[488],[608],[897],[87],[214],[275],[567],[259],[78],[288],[614],[338],[313],[498],[519],[421],[968],[742],[8],[170],[421],[977],[293],[941],[702],[841],[953],[210],[176],[487],[849],[846],[484],[339],[397],[249],[645],[285],[974],[975],[844],[670],[560],[951],[2],[661],[57],[580],[56],[693],[254],[751],[366],[97],[423],[625],[452],[34],[140],[285],[235],[873],[366],[81],[590],[229],[722],[669],[753],[797],[55],[400],[838],[34],[635],[97],[657],[910],[201],[223],[841],[248],[657],[545],[240],[622],[180],[201],[795],[571],[864],[632],[492],[857],[73],[849],[826],[513],[468],[114],[122],[643],[553],[907],[276],[874],[99],[1],[172],[239],[520],[148],[761],[100],[227],[592],[442],[652],[7],[105],[624],[780],[247],[772],[862],[57],[676],[191],[762],[116],[327],[859],[198],[596],[565],[119],[112],[219],[296],[982],[502],[623],[57],[513],[260],[368],[118],[118],[69],[795],[766],[481],[499],[433],[66],[374],[44],[981],[294],[418],[552],[384],[999],[196],[400],[925],[222],[678],[657],[684],[308],[423],[282],[487],[229],[598],[149],[247]]


    Output:

    [null,false,null,null,null,null,null,false,null,null,false,true,null,false,null,null,null,true,null,null,null,false,null,null,null,null,null,null,null,null,null,true,null,null,false,true,true,null,null,null,true,null,null,null,null,null,null,null,true,null,false,null,true,null,false,null,null,null,null,false,null,null,null,null,null,null,null,true,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,true,null,null,null,null,null,null,null,null,null,null,null,false,null,null,null,null,true,null,null,null,null,null,null,null,true,false,null,null,null,null,false,null,null,false,null,false,false,null,null,true,null,null,null,null,null,null,null,false,null,null,false,null,null,null,null,null,null,null,false,null,null,true,null,null,null,null,null,null,null,false,null,null,false,null,true,null,null,null,null,null,true,null,null,null,null,null,null,null,null,null,null,true,null,null,null,null,null,null,null,true,false,false,null,true,null,null,false,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,false,null,false,null,false,null,true,null,null,null,null,null,null,null,null,null,true,null,null,null,null,null,null,null,null,null,null,null,null,true,null,null,null,null,null,false,null,null,null,null,null,false,null,null,null,false,null,null,null,true,null,null,null,null,true,null,null,false,null,null,null,null,null,true,null,true,null,null,true,null,null,null,null,null,null,null,null,true,false,null,null,null,null,false,null,true,null,null,null,null,null,null,null,null,null,null,null,null,null,false,null,null,null,false,null,null,true,null,null,null,null,null,null,null,true,null,null,null,false,null,null,null,null,null,null,true,null,null,true,null,true,null,null,null,null,false,true,null,true,null,true,null,null,null,null,null,null,null,null,false,null,null,null,false,null,null,null,null,null,true,null,null,true,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,false,null,null,null,true,null,null,null,null,null,null,true,false,null,true,null,null,null,null,null,null,null,null,null,null,true,null,null,null,null,null,null,null,null,false,null,null,null,null,true,null,null,null,null,null,null,null,true,null,null,null,null,true,null,false,null,null,null,null,null,null,null,null,null,false,null,null,null,true,null,false,null,null,null,true,null,null,true,null,false,null,null,null,null,null,null,true,null,null,null,null,null,null,null,null,null,null,null,null,null,false,null,null,null,null,null,null,null,null,null,null,true,null,true,null,null,null,null,null,null,null,null,null,null,null,null,null,false,null,null,true,true,null,null,true,null,null,false,false,null,null,null,null,true,null,false,null,null,null,null,null,true,null,null,null,null,null,false,true,false,null,true,null,null,null,null,null,null,null,null,null,null,null,true,null,null,true,null,null,null,null,null,null,null,true,null,null,null,null,false,null,null,null,null,null,null,null,null,null,null,null,null,null,true,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,true,null,null,null,null,null,null,null,null,null,null,null,true,null,null,true,null,null,null,true,null,null,null,true,null,null,null,null,true,null,null,false,false,false,null,null,true,null,null,null,null,null,null,null,null,null,true,null,null,null,true,false,null,null,null,null,null,null,null,null,false,null,null,null,null,null,true,null,true,null,null,null,null,null,null,null,true,null,null,null,null,null,null,null,null,null,null,null,null,true,null,null,null,null,false,null,true,false,null,null,null,null,false,null,null,null,null,null,null,false,null,null,null,false,null,null,null,null,null,null,null,null,null,null,true,null,null,null,true,null,false,true,null,null,null,null,null,null,null,true,null,null,true,null,null,false,null,null,null,true,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,false,null,null,null,true,true,null,null,null,true,null,null,null,false,null,null,null,null,false,true,null,false,null,null,null,false,null,null,null,true,null,null,false,true,null,null,true,false,null,null,null,true,null,null,null,true,null,null,null,null,true,null,null,null,null,null,null,null,true,null,null,false,true,null,null,null,true,null,null,false,null,null,true,false,null,null,null,null,null,null,null,false,null,true,null,null,null,null,null,false,null,null,null,null,null,null,null,false,false,null,null,null,null,null,null,null,null,false,true,null,null,false,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,false,null,null,null,true,null,null,null,true,null,null,null,null,null,null,null,null,null,true,null,null,null,null,null,true,null,null,null,null,null,false,null,null,null,null,null,null,false,null,false,null,null,true,null,null,null,null,null,null,null,null,null,null,null,true,false,null,false,null,true,null,null,null,null,null,null,null,null,true,null,null]


    Expected Output:

    [null,false,null,null,null,null,null,false,null,null,false,true,null,false,null,null,null,true,null,null,null,false,null,null,null,null,null,null,null,null,null,true,null,null,false,true,true,null,null,null,true,null,null,null,null,null,null,null,true,null,false,null,true,null,false,null,null,null,null,false,null,null,null,null,null,null,null,true,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,true,null,null,null,null,null,null,null,null,null,null,null,false,null,null,null,null,true,null,null,null,null,null,null,null,true,false,null,null,null,null,false,null,null,false,null,false,false,null,null,true,null,null,null,null,null,null,null,false,null,null,false,null,null,null,null,null,null,null,false,null,null,true,null,null,null,null,null,null,null,false,null,null,false,null,true,null,null,null,null,null,true,null,null,null,null,null,null,null,null,null,null,true,null,null,null,null,null,null,null,true,false,false,null,true,null,null,false,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,false,null,false,null,false,null,true,null,null,null,null,null,null,null,null,null,true,null,null,null,null,null,null,null,null,null,null,null,null,true,null,null,null,null,null,false,null,null,null,null,null,false,null,null,null,false,null,null,null,true,null,null,null,null,true,null,null,false,null,null,null,null,null,true,null,true,null,null,true,null,null,null,null,null,null,null,null,true,false,null,null,null,null,false,null,true,null,null,null,null,null,null,null,null,null,null,null,null,null,false,null,null,null,false,null,null,true,null,null,null,null,null,null,null,true,null,null,null,false,null,null,null,null,null,null,true,null,null,true,null,true,null,null,null,null,false,true,null,true,null,true,null,null,null,null,null,null,null,null,false,null,null,null,false,null,null,null,null,null,true,null,null,true,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,false,null,null,null,true,null,null,null,null,null,null,true,false,null,true,null,null,null,null,null,null,null,null,null,null,true,null,null,null,null,null,null,null,null,false,null,null,null,null,true,null,null,null,null,null,null,null,true,null,null,null,null,true,null,false,null,null,null,null,null,null,null,null,null,false,null,null,null,true,null,false,null,null,null,true,null,null,true,null,false,null,null,null,null,null,null,true,null,null,null,null,null,null,null,null,null,null,null,null,null,false,null,null,null,null,null,null,null,null,null,null,true,null,true,null,null,null,null,null,null,null,null,null,null,null,null,null,false,null,null,true,true,null,null,true,null,null,false,false,null,null,null,null,true,null,false,null,null,null,null,null,true,null,null,null,null,null,false,true,false,null,true,null,null,null,null,null,null,null,null,null,null,null,true,null,null,true,null,null,null,null,null,null,null,true,null,null,null,null,false,null,null,null,null,null,null,null,null,null,null,null,null,null,true,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,true,null,null,null,null,null,null,null,null,null,null,null,true,null,null,true,null,null,null,true,null,null,null,true,null,null,null,null,true,null,null,false,true,false,null,null,true,null,null,null,null,null,null,null,null,null,true,null,null,null,true,false,null,null,null,null,null,null,null,null,false,null,null,null,null,null,true,null,true,null,null,null,null,null,null,null,true,null,null,null,null,null,null,null,null,null,null,null,null,true,null,null,null,null,false,null,true,false,null,null,null,null,false,null,null,null,null,null,null,false,null,null,null,false,null,null,null,null,null,null,null,null,null,null,true,null,null,null,true,null,false,true,null,null,null,null,null,null,null,true,null,null,true,null,null,false,null,null,null,true,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,false,null,null,null,true,true,null,null,null,true,null,null,null,false,null,null,null,null,false,true,null,false,null,null,null,false,null,null,null,true,null,null,false,true,null,null,true,false,null,null,null,true,null,null,null,true,null,null,null,null,true,null,null,null,null,null,null,null,true,null,null,false,true,null,null,null,true,null,null,false,null,null,true,false,null,null,null,null,null,null,null,false,null,true,null,null,null,null,null,false,null,null,null,null,null,null,null,false,false,null,null,null,null,null,null,null,null,false,true,null,null,false,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,false,null,null,null,true,null,null,null,true,null,null,null,null,null,null,null,null,null,true,null,null,null,null,null,true,null,null,null,null,null,false,null,null,null,null,null,null,false,null,false,null,null,true,null,null,null,null,null,null,null,null,null,null,null,true,false,null,false,null,true,null,null,null,null,null,null,null,null,true,null,null]


    I then took a look at the solution and figured out that it intends to add a new node at the head, whereas I append the new node to the tail. Here, the node represents a unique value in the bucket. In my opinion, both the ways should work and so says the author:


    For a value that was never seen before, we insert it to the head of the bucket, though we could also append it to the tail. It is a choice that we made, which could fit better the scenario where redundant values are operated in nearby time windows, since it is more likely that we spot the value at the head of the bucket rather than walking through the entire bucket.

    The solution that worked:

    class MyHashSet:

    def __init__(self):
    """
    Initialize your data structure here.
    """
    self.key_range = 769
    self.buckets = [Bucket() for _ in range(self.key_range)]

    def _hash(self, key):
    return key % self.key_range

    def add(self, key: int) -> None:
    bucket_index = self._hash(key)
    self.buckets[bucket_index].insert(key)

    def remove(self, key: int) -> None:
    bucket_index = self._hash(key)
    self.buckets[bucket_index].delete(key)

    def contains(self, key: int) -> bool:
    """
    Returns true if this set contains the specified element
    """
    bucket_index = self._hash(key)
    return self.buckets[bucket_index].check_val(key)


    class Node:
    def __init__(self, val, next_node=None):
    self.val = val
    self.next = next_node


    class Bucket:
    def __init__(self):
    self.head = Node('*')


    def insert(self, val):
    if not self.check_val(val):
    self.head.next = Node(val, self.head.next)

    def delete(self, val):
    curr = self.head.next
    prev = self.head
    # found = False
    while curr is not None:
    if curr.val == val:
    prev.next = curr.next
    return
    prev = curr
    curr = curr.next

    def check_val(self, val):
    curr = self.head.next
    while curr:
    if curr.val == val:
    return True
    curr = curr.next
    return False



    I failed to see what is wrong with appending values at the end.

    Login To add answer/comment
     

Share This Page