# implement the hash-table using Linear Probing # you may add further functions if required class HashTable:

# return the hash value for 'v' # See page #121 of Open Data Structure book # for implementation of a hash function def __hashed(self, k): pass

# returns value for the key 'k' # returns none if it doesn't exist # should run in O(1) def Get(self, k): pass

# store value 'v' for the key 'k' # if 'k' already in the table then overwrite # returns: old value of 'k' # should run in O(1) def Put(self, k, v): pass

# remove 'k' from the table if exists # returns: current value for the key 'k' # should run in O(1) def Remove(self, k): pass

# returns all keys as a list def Keys(self): pass

# returns all values as a list def Values(self): pass

# returns a list containing key value pairs as # tuples i.e. [(k,v)] def Entries(self): pass

# returns the number of elements def Size(self): pass

# returns True if the table is empty # otherwise returns false def IsEmpty(self): pass

# resize the array when the array def ReSize(self): pass # A wrapper for HashTable class to implement # logic for frequency # you may add further functions if required class FrequencyTable: # constructor def _init_(self): self.hashtable = HashTable()

# add e in the table and set counter to 1 # if already exists then add the counter # returns the value of counter after adding # should run in O(1) def Add(self, e): pass

# if the counter of e is greater # then 1 then reduce by 1 # otherwise remove the element # returns the current value of counter # should run in O(1) def Remove(self, e): pass

# returns the total number of elements/locations def Count(self): pass

# returns a list of tuples where first value # shows the element and second value shows frequency # [(1,2),(3,4)] shows two elements 1 and 3 with # frequency 2 and 4, respectivelly def Frequency(self): pass

# Driving code to load data from files and process # **************** # YOU ARE NOT REQUIRED TO CHANGE THIS CLASS ** # **************** class FrequencyUtility: # constructor def _init_(self, entrancefile, exitfile): self.entrance = entrancefile self.exit = exitfile # table to store data self.freqTable = FrequencyTable()

# process the data and returns freuence table def Process(self): self.__ProcessEntrance() self.__ProcessExit() return self.freqTable.Frequency()

# private method to process enterance data def __ProcessEntrance(self): f = open(self.entrance, "r") allLines = f.read().split(' ') f.close()

for aLine in allLines: if len(aLine)>0: self.freqTable.Add(int(aLine))

# private method to process exit data def __ProcessExit(self): f = open(self.exit, "r") allLines = f.read().split(' ') f.close()

for aLine in allLines: if len(aLine)>0: self.freqTable.Remove(int(aLine)) def Test(): d = FrequencyUtility("entrance.txt","exit.txt") print(d.Process())

python