Scribbling

To design a hashmap, we need 1) hashing function -- will use hash() method 2) an array for the hash table 3) Linkedlist for hash collision class Node: def __init__(self, key, val, nxt=None): self.key = key self.val = val self.nxt = nxt class LinkedList: def __init__(self): self.head = Node(0, 0) def append(self, key, val) -> None: prv, cur = self.head, self.head.nxt while cur is not None: if cur..

Greedy solution with heap & deque - append character with 'max frequency' currently - put the appended character to a deque for cool-down from collections import Counter, deque import heapq class Solution: def rearrangeString(self, s: str, k: int) -> str: if k = k: freq, char = q.popleft() if freq >= 1: heapq.heappush(h, (-freq, char)) return ''.join(ret) if len(ret) == len(s) else ""

Fenwick Tree (or Binary Indexed Tree) is very efficient in dealing with range queries, especially when elements get updated occasionally. For how it works, refer to the below video. He elaborates on the principle of the tree in a very clean way. https://www.youtube.com/watch?v=CWDQJGaN1gY&t=160s&ab_channel=TusharRoy-CodingMadeSimple Below is the python implementation of it. class Fenwick: """ Py..

Video I recommend: https://www.youtube.com/watch?v=SToUyjAsaFk In this post, I will cover "Recursive Descent Parsing". Details about it are well elaborated in the above video. This post is to summarize core concepts and implement the algorithm with an actual code. Goal: Implement a parser that parse an arithmetic experssion. - ( 3 + 5) * -2 Elements: Numbers Infix Operators (+, -, *, /) Prefix O..

Rabin-Karp Algorithm is an efficient algorithm to search a string pattern in a given sentence. The core of the idea is to use hash function to compare strings. Time complexity is O(n), where n is length of the string. However, this is true only when there is no hash collision. Time complexity is O(n * m) if hash function is poorly selected (producing many hash collisions), where m is length of t..

Python does not provide standard library for ordered set or ordered dictionary. However, there's an Apache2 licensed sorted collections library "SortedContainer". You can install the library with the following cmd. pip install sortedcontainers https://www.geeksforgeeks.org/python-sorted-containers-an-introduction/#:~:text=Sorted%20set%20is%20a%20sorted,must%20be%20hashable%20and%20comparable. Py..

클래스 메타프로그래밍은 실행 도중에 클래스를 생성하거나 커스터마이징 하는 기술이다. 클래스 데코레이터와 메타클래스는 이를 위한 방법이다. 메타클래스는 강력하지만, 어렵다. 클래스 데커레이터는 사용하기 쉽지만, 상속 계층 구조가 있는 경우에는 사용하기 어렵다. 1. 런타임에 클래스 생성하기 파이썬 표준 라이브러리에는 collections.namedtuple 이라는 클래스 팩토리가 있다. 클래스명과 속성명을 전달하면 이름 및 점 표기법으로 항목을 가져올 수 있다. 유사한 클래스 팩토리를 만들면서 런타임에 클래스 생성하는 방법을 확인해보자. def record(cls_name, field_names): try: field_names = field_names.replace(',', '').split() exce..

디스크립터를 이요하면 여러 속성에 대한 동일한 접근 논리를 재사용 가능하다. 디스크립터는 __get__(), __set__(), __delete__() 메서드로 구성된 프로토콜을 구현하는 클래스다. property 클래스는 디스크립터 프로토콜을 완벽히 구현한다. 아래 글에서 동적 속성을 구현함에 있어 프로퍼티 팩토리를 이용했었다. https://focalpoint.tistory.com/314 Python: Dynamic attributes and properties (동적 속성과 프로퍼티) 파이썬에서는 데이터 속성과 메서드를 통틀어 속성이라고 한다. 메서드는 단지 호출가능한 속성이다. 프로퍼티를 사용하면 클래스인터페이스를 변경하지 않고도 공개 데이터 속성을 접근자 메 focalpoint.tistory.c..

파이썬에서는 데이터 속성과 메서드를 통틀어 속성이라고 한다. 메서드는 단지 호출가능한 속성이다. 프로퍼티를 사용하면 클래스인터페이스를 변경하지 않고도 공개 데이터 속성을 접근자 메서드(getter & setter)로 대체할 수 있다. 파이썬 인터프리터는 obj.attr과 같은 점 표기법으로 표현되는 속성에 대한 접근을 __getattr__()과 __setattr__() 등 특별 메서드를 호출하여 평가한다. 사용자 정의 클래스는 __getattr__() 메서드를 오버라이드하여 '가상 속성'을 구현할 수 있다. 1. 동적 속성을 이용한 데이터 랭글링 다음과 같은 json data를 랭글링 하는 예제를 살펴보자. { "Schedule": { "conferences": [{"serial": 115 }], "ev..

크게 두 단계로 풀 수 있다. 1) 알파벳 조합이 동일한 집합끼리 나눈다. 2) 각 집합 내에서 단어를 연결하고, 소 집합의 갯수를 구한다. This prob can be solved within two steps. 1) Group words by alphabet combinations 2) Connect words in each group and then get the number of small groups Code is quite straightforward, so I guess there's no need to explain more. Time complexity would be (O(N**2*k)), where N is the number of words and k is length of a w..