파이썬 알고리즘 인터뷰 해시 문제

해시맵 디자인 

1) 개별 체이닝 방식을 이용한 해시 테이블 구현

 

class MyHashMap :
	def __init__(self, key = None, value = None):
   		self.size = 
      	self.table = colections.defaultdict(ListNode)

	def put(self, key:int, value: int) -> None:
    	if self.table[index].value is None:   # value로 해야 존재하지 않는 인덱스 조회에 대한 에러 발생 X
        self.table[index] = ListNode(key, value)
        return
        
        #해시 충돌 발생 경우 chaning으로 풀기
        
        #인덱스에 노드가 존재하는 경우 연결 리스트로 처리한다 
        while self.table[index]:
        	#종료 조건 1 이미 키가 존재하는 경우
            if self.table[index].key = key
            	# 해당 value값을 업데이트
            	self.table[index].value = value
            	return 
            #종료 조건 2 다음으로 검색할 게 없어. 모든 탐색이 끝날 때 
            if self.table[index].next is None:
            	break
            #위 조건 만족안하면 다음꺼로 이동
            self.table[index] = self.table[index].next
        #업데이트 안하게 되면 그냥 해당 인덱스에 노드에 새 노드가 생성되면서 연결
        self.table[index].next = ListNode(key, value)

   	def get(self, key : int) -> int:
   		index = hash_function(key)
        #해당 인덱스에 아무것도 없으면 -1 리턴
        if self.table[index].vallue is None:
        	return -1
        #만약 값이 존재하면 return self.table[index].value을 쓴다
        #하나 이상의 노드가 존재할 수 있기에 p.next로 탐색하면서 일치하는 키를 찾아야한다

   	def remove(self, key : int) -> None:
    	# 인덱스에 값이 없으면 return 
        # 인덱스의 첫번째 노드일때 삭제
        if self.table[index].key == key:
        	#빈노드 할당
        	self.table[index] = ListNode() if self.table[index].next is None else self.table[index].next
            return
        # 연결 리스트 노드 삭제
        prev = self.table[index]
        while p:
        	if p.key == key:
            	#이전 노드의 다음을 현재 노드의 다음으로 연결
            	prev.next = p.next
                return
            prev, p = p, p.next
                return

 

 

 

상위 K 빈도 요소

1) Counter를 이용한 음수 순 추출

키 : 요소 값

저장 값 : 빈도 수  collections.Counter(nums)

k번 추출 : 우선 순위 큐 (음수로 변환해서 가장 빈도 수가 높은 값이 가장 큰 음수)

 

힙의 삽입 방식

 1) 리스트로 모두 삽입하고, 마지막에 heapify()

 2) 매번 heappush() <- 매번 heapify()가 일어나는 원래 힙의 삽입방식

for lst in lists:
	# 각 연결 리스트의 루트를 힙에 저장
	heapq.heqppush(lst.val, lst))
    #lst 는 연결 리스트 3개로 구성된 입력값
    
    for i in range(len(lists)):
    	heapq.heappush(heap, lists[i].val, i, lists[i])))
    	
    #heappop()으로 추출하면 가장 작은 노드의 연결리스트부터 차례로 나오게 됨