Implement functionality of hashmap with the following functions, all O(1) time:


  • 0
    V
    • put(K, V)
    • get(K) -> V
    • delete(K)
    • getRandom() -> K, V

  • 0

    Similar to insert delete, getRandom O(1). Keep a list of keys contained in the map and grab a random key from the list and return the key, value pair when getRandom is called. To maintain this list in O(1) time, we would need to keep an extra hashmap to store the indices of each key. Put will be amortized O(1) as we'd need to allocate more memory when inserting elements into the list.

    class RandomHash:
    
    	def __init__(self):
    		self.M = {}
    		self.P = {}
    		self.elems = []
    
    	def put(self, k, v):
    		if k in self.M:
    			self.M[k] = v
    		else:
    			self.M[k] = v
    			self.P[k] = len(self.elems)
    			self.elems.append(k)
    
    	def get(self, k):
    		if k not in self.M: return None
    		return self.M[k]
    
    	def delete(self, k):
    		if k not in self.M: return False
    		p = self.P[k]
    		self.elems[p], self.elems[-1] = self.elems[-1], self.elems[p]
    		self.P[self.elems[p]] = p
    		del M[k]
    		del P[k]
    		self.elems.pop()
    		return True
    
    	def getRandom(self):
    		if not self.elems: return None
    		k = self.elems[random.randint(1, len(self.elems)) - 1]
    		return k, M[k]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.