0%

Quoting wikipedia

In object-oriented programming and software engineering, the visitor design pattern is a way of separating an algorithm from an object structure on which it operates. A practical result of this separation is the ability to add new operations to existing object structures without modifying the structures. It is one way to follow the open/closed principle.

As mentioned, the goal is to separate the algorithm from objects which it operates on.

As a result, it allow us to add new operations without modifying the objects.

In C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// ivisitor.h
#ifndef INCLUDE_VISITOR_H
#define INCLUDE_VISITOR_H

struct Rider;
struct Skier;

struct IVisitor {
virtual ~IVisitor() = default;
virtual void visit(Rider *student) = 0;
virtual void visit(Skier *student) = 0;
};

#endif /* INCLUDE_VISITOR_H */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// student.h
#ifndef INCLUDE_STUDENT_H
#define INCLUDE_STUDENT_H

#include "ivisitor.h"

struct Student {
virtual ~Student() = default;
virtual void accept(IVisitor *visitor) = 0;
};

struct Skier : public Student {
void accept(IVisitor *visitor) override { visitor->visit(this); } // Second dispatch
};

struct Rider : public Student {
void accept(IVisitor *visitor) override { visitor->visit(this); } // Second dispatch
};

#endif /* INCLUDE_STUDENT_H */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// main.cc
#include "student.h"
#include "student_visitor.h"
#include <iostream>
#include <memory>
#include <vector>

using namespace std;

struct RentalVisitor : IVisitor {
void visit(Rider *rider) { std::cout << "Prepare snowboard..." << std::endl; }
void visit(Skier *skier) { std::cout << "Prepare ski..." << std::endl; };
};

struct TeachVisitor : IVisitor {
void visit(Rider *rider) { std::cout << "Teach a rider" << std::endl; }
void visit(Skier *skier) { std::cout << "Teach a skier" << std::endl; };
};

// Add new visitor to perform new functionality

int main(int, char **) {
vector<unique_ptr<Student>> students;
students.emplace_back(make_unique<Skier>());
students.emplace_back(make_unique<Rider>());

RentalVisitor rental_visitor;
TeachVisitor teach_visitor;
for (auto &s : students) {
s->accept(&rental_visitor); // First dispatch
s->accept(&teach_visitor); // First dispatch
}
}

In Python

Traditional double dispatch

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
'''
Implement visitor pattern via double dispatch.
'''
from __future__ import annotations

from abc import ABC, abstractmethod
from typing import List


class IVisitor(ABC):
'''
Visitor interface
'''
@abstractmethod
def visit_skier(self, student):
...

@abstractmethod
def visit_rider(self, student):
...


class Student(ABC):
@abstractmethod
def accept(self, visitor):
...


class Skier(Student):
def accept(self, visitor):
visitor.visit_skier(self)


class Rider(Student):
def accept(self, visitor):
visitor.visit_rider(self)


#
# Concrate visitors
#
class RentalVisitor(IVisitor):
def visit_skier(self, student):
print('Prepare ski...')

def visit_rider(self, student):
print('Prepare snowboard...')


class TeachVisitor(IVisitor):
def visit_skier(self, student):
print('Teach skier...')

def visit_rider(self, student):
print('Teach rider...')

# Add new visitor to perform new functionality

def main():
rental_visitor = RentalVisitor()
teach_visitor = TeachVisitor()

students: List[Student] = [Skier(), Skier(), Rider()]
for s in students:
s.accept(rental_visitor)
s.accept(teach_visitor)


if __name__ == "__main__":
main()

Annotation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
from __future__ import annotations

from abc import ABC, abstractmethod
from typing import List


class Student(ABC):
...


class Skier(Student):
...


class Rider(Student):
...


# A couple helper functions first

def _qualname(obj):
'''Get the fully-qualified name of an object (including module).'''
return obj.__module__ + '.' + obj.__qualname__


def _declaring_class(obj):
'''Get the name of the class that declared an object.'''
name = _qualname(obj)
return name[:name.rfind('.')]


# Stores the actual visitor methods
_methods = {}


def _visitor_impl(self, arg):
'''Actual visitor method implementation.'''
method = _methods[(_qualname(type(self)), type(arg))]
return method(self, arg)


def visitor(arg_type):
'''Decorator that creates a visitor method.'''

def decorator(fn):
declaring_class = _declaring_class(fn)
_methods[(declaring_class, arg_type)] = fn

# Replace all decorated methods with _visitor_impl
return _visitor_impl

return decorator


class RentalVisitor:
@visitor(Skier)
def visit(self, student):
print('Prepare ski...')

@visitor(Rider)
def visit(self, student):
print('Prepare snowboard...')


# Add new visitor to perform new functionality

def main():
rental_visitor = RentalVisitor()

students: List[Student] = [Skier(), Skier(), Rider()]
for s in students:
rental_visitor.visit(s)

print(_methods)


if __name__ == '__main__':
main()

To briefly explain why we want to empty the inbox and methods to quickly archive
hundreds or thousands emails if your already accumulated.

WHY

Just google Empty email inbox, you will find lots of articles talk about why
you want to do it. In short, you needs empty inbox by archiving emails for

  • Organization
    • get rid of junk
    • unsubscribe from emails you do not want
  • Feeling in control
  • Not missing important email
  • Efficiency
    • Force to make decision when receiving new email

To those who are new to Archive, you will not lose any email by archiving it.
Archived emails can always be found in All mails.

HOW - for gmail users.

Manually

In gmail, setup following configs

  • [All settings] -> [General]: Maximum page size: 100
  • [All settings] -> [General]: Keyboard shortcuts: ON

Now, you can archive emails from your inbox with shortcut.

  • * + a to select all emails.
  • e to archive selected emails.

Repeated above steps until your inbox is empty.

Automation with Apple Script

If you have couple thousands of email, the manual procedures will be quite annoying.
We can automate that with Apple Script if you are using MacOS.

  • Open MacOS embedded application Automator
  • Click New Document
  • Select Quick Action as type of new document
  • Click Choose
  • Change Workflow receives current to no input
  • Click Record
  • Open gmail in your browser and repeat steps in above section to archive 100 emails
  • Click STOP button in Automator‘s popup
  • Modify script to repeat the recorded operations

Please check this video, for details.

If all you have is a hammer, everything looks like a nail

- Abraham Maslow, 1962

List, Stack, LinkedList

Heap, Priority Queue

Sliding Window

Monotonic Stack

Monotonic Queue

Rare technique

  1. KMP
  2. Manacher’s algorithm

Tree

DFS

BFS

Trie

Advanced Tree

Binary Index Tree (Fenwick Tree)

Segment Tree

Self-Balanced Tree, RB Tree

Union-Find

Graph

DFS/BFS

Cycle Detection

Topologic Sort

Euler Path

Shortest Path

Dijkstra

Bellman-Ford

Floyd-Warshall

Minimal Spanning Tree

Kruskal’s Algorithm

Prim’s Algorithm

Tarjan’s Algorithm

Strong Connected Component

Cutting Edge

Cutting Point

Dynamic Programming

Bit Mask

##

uncategorized

  1. Binary Lifting

What is a Graph

Non-directed

Directed

Cycle Detection

Non-directed Graph

Union-Find

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class UF:
def __init__(self):
self.uf = {}

def find(self, x: int) -> int:
uf = self.uf
uf.setdefault(x, x)
if uf[x] != x:
uf[x] = self.find(uf[x])
return uf[x]

def union(self, x: int, y: int) -> None:
# x -> y
uf = self.uf
uf[self.find(x)] = self.find(y)

def detect_cycle(n: int, edges: List[Tuple[int, int]]) -> bool:
uf = UF()

for u, v in edges:
if uf.find(u) == uf.find(v):
return True
uf.union(u, v)

return False

assert True == detect_cycle(4, [(0, 2), (1, 0), (2, 1), (1, 3)])
assert False == detect_cycle(4, [(0, 1), (2, 1), (1, 3)])

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def detect_cycle(n: int, edges: List[Tuple[int, int]]) -> bool:

def dfs(u: int, p: int) -> bool:
visited.add(u)

for v in graph[u]:
if v == p: continue
if v in visited or dfs(v, u):
return True

return False

graph, visited = defaultdict(set), set()

for u, v in edges:
graph[u].add(v)
graph[v].add(u)

for u in range(n):
if u not in visited and dfs(u, None):
return True
return False

assert True == detect_cycle(4, [(0, 2), (1, 0), (2, 1), (1, 3)])
assert False == detect_cycle(4, [(0, 1), (2, 1), (1, 3)])

Directed Graph

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def detect_cycle(n: int, edges: List[Tuple[int, int]]) -> bool:

def dfs(u: int) -> bool:
visited.add(u), stack.add(u)

for v in graph[u]:
if v in stack or v not in visited and dfs(v):
return True

stack.remove(u)
return False

graph, visited, stack = defaultdict(set), set(), set()

for u, v in edges:
graph[u].add(v)

for u in range(n):
if u not in visited and dfs(u):
return True
return False

assert True == detect_cycle(4, [(0, 2), (1, 0), (2, 1), (1, 3)])
assert False == detect_cycle(4, [(0, 2), (0, 1), (2, 1), (1, 3)])

Euler Path

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def find_euler_path(start: int, edges: List[Tuple[int, int]]) -> List[int]:
# Assume euler path does exist
def dfs(u):
while graph[u]:
v = graph[u].pop()
dfs(v)
ret.append(u)

graph, ret = defaultdict(set), []
for u, v in edges:
graph[u].add(v)

dfs(start)
return ret[::-1]

print(find_euler_path(0, [(0, 1), (1, 0), (1, 2), (2, 3), (3, 1), (1, 4)] ))

Shortest Path

Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from sortedcontainers import SortedList
def dijkstra(n: int, edges: List[Tuple[int, int, int]], begin: int, end: int) -> List[int]:
graph, dist, prev = defaultdict(dict), defaultdict(lambda: math.inf), {}

for u, v, w in edges:
graph[u][v] = w

q = SortedList([(0, begin)])
dist[begin] = 0
while q:
_, u = q.pop(0)
for v, w in graph[u].items():
if dist[v] > dist[u] + w:
q.discard((dist[v], v)) # this will reduce the time complexity from O(E*log(V)) to O(V*log(V))
prev[v] = u
dist[v] = dist[u] + w
q.add((dist[v], v))

if dist[end] == math.inf:
return []

def bt(cur):
if cur == begin:
return [begin]
return bt(prev[cur]) + [cur]
return bt(end)

print(dijkstra(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, 3]], 0, 4))

Bellman Ford

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def bellman_ford(n: int, edges: List[Tuple[int, int, int]], begin: int, end: int) -> List[int]:
dist = defaultdict(lambda: math.inf)
dist[begin], prev = 0, {}

for _ in range(n):
upd = 0
for u, v, w in edges:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
prev[v] = u
upd += 1
if not upd:
break

for u, v, w in edges:
if dist[u] + w < dist[v]:
raise Exception('Negative cycle')

def bt(u):
if u == begin:
return [begin]
return bt(prev[u]) + [u]
return bt(end)

print(bellman_ford(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, 3]], 0, 4))

Floyd Warshall

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def floyd_warshall(n: int, edges: List[Tuple[int, int, int]], begin: int, end: int) -> int:
dist = defaultdict(lambda: math.inf)

for u, v, w in edges:
dist[(u, v)] = w

for k in range(n):
for u in range(n):
for v in range(n):
if dist[(u, k)] + dist[(k, v)] < dist[(u, v)]:
dist[(u, v)] = dist[(u, k)] + dist[(k, v)]

return dist[(begin, end)]

print(floyd_warshall(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, 3]], 0, 4))

Minimal Spanning Tree

Kruskal’s method

1
2
3
4
5
6
7
8
9
10
11
def kruskal(n: int, edges: List[Tuple[int, int, int]]) -> int:
uf, ret = UF(), []

for u, v, w in sorted(edges, key=lambda x: x[2]):
if uf.find(u) != uf.find(v):
ret.append((u, v, w))
uf.union(u, v)

return ret if len(set(map(uf.find, range(n)))) == 1 else []

print(kruskal(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, 3]]))

Prim’s method

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from sortedcontainers import SortedList
def prim(n: int, edges: List[Tuple[int, int, int]]) -> int:
graph = defaultdict(dict)
for u, v, w in edges:
graph[u][v] = w

start = 0
pq, ret, visited, prev = SortedList([(0, start, None)]), [], set(), {}

while pq:
if len(visited) == n:
break
w, u, p = pq.pop(0)
if u in visited: continue

visited.add(u), ret.append((p, u, w))

for v, w in graph[u].items():
if v in visited: continue
if v in prev and prev[v][1] >= w:
pq.remove((prev[v][1], v, prev[v][0]))
prev[v] = (u, w)
pq.add((w, v, u))

return ret[1:] if len(visited) == n else []

print(prim(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, 3]]))

Tarjan’s algorithm

Strong Connected Component

Cutting Edge

Cutting Vertex

Q1. 1592. Rearrange Spaces Between Words

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def reorderSpaces(self, text: str) -> str:
words = text.split()
spaces, n = text.count(' '), len(words)
ret = ''

for i, word in enumerate(words):
ret += word
if n > 1 and i != n-1:
ret += ' ' * (spaces // (n-1))

return ret + ' ' * ((spaces % (n-1)) if n>1 else spaces)
Read more »

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Fraction:
def __init__(self, numerator: int, denominator: int):
self.numerator = numerator
self.denominator = denominator

def __str__(self):
return f'{self.numerator} / {self.denominator}'

def __lt__(self, rhs: Fraction):
l, r = self.numerator * rhs.denominator, self.denominator * rhs.numerator
return l < r

def __add__(self, rhs: Fraction):
numerator, denominator = self.numerator * rhs.denominator + rhs.numerator * self.denominator, \
self.denominator * rhs.denominator
gcd_val = math.gcd(numerator, denominator)
return Fraction(numerator // gcd_val, denominator // gcd_val)

def __sub__(self, rhs: Fraction):
numerator, denominator = rhs.numerator, rhs.denominator
return self.__add__(Fraction(-numerator, denominator))

Prerequisite

  1. What is a binary-heap
  2. It takes O(N) to heapify an array contains N integer

N*Log(K)

1
2
3
4
5
6
7
def get_k_smallest(k: int, arr: List[int]):
heap = []
for num in arr:
heapq.heappush(heap, -num) # we push -num as we want to build a max-heap
if len(heap) > k:
heapq.heappop(heap)
return [-num for num in heap]

K*Log(N)

1
2
3
def get_k_smallest(k: int, arr: List[int]):
heapq.heapify(arr)
return [heapq.heappop(arr) for i in range(k)]

K*Log(K)

1
2
3
4
5
6
7
8
9
10
def get_k_smallest(k: int, arr: List[int]):
heapq.heapify(arr)
heap = [(arr[0], 0)]
ret = []
for _ in range(k):
num, idx = heapq.heappop(heap)
ret.append(num)
heapq.heappush(heap, (arr[idx*2+1], idx*2+1))
heapq.heappush(heap, (arr[idx*2+2], idx*2+2))
return ret

Test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import heapq
import timeit


def timer(function):
def new_function(*args, **kw):
start_time = timeit.default_timer()
ret = function(*args, **kw)
elapsed = timeit.default_timer() - start_time
print('Function "{name}" took {time} seconds to complete.'.format(name=function.__name__, time=elapsed))
return ret
return new_function

@timer
def addition():
total = 0
for i in range(0,1000000):
total += i
return total



@timer
def get_k_smallest1(k: int, arr: List[int]):
heap = []
for num in arr:
heapq.heappush(heap, -num) # we push -num as we want to build a max-heap
if len(heap) > k:
heapq.heappop(heap)
return [-num for num in heap]


@timer
def get_k_smallest2(k: int, arr: List[int]):
heapq.heapify(arr)
return [heapq.heappop(arr) for i in range(k)]


@timer
def get_k_smallest3(k: int, arr: List[int]):
heapq.heapify(arr)
heap = [(arr[0], 0)]
ret = []
for _ in range(k):
num, idx = heapq.heappop(heap)
ret.append(num)
heapq.heappush(heap, (arr[idx*2+1], idx*2+1))
heapq.heappush(heap, (arr[idx*2+2], idx*2+2))
return ret

k = 5
arr = [randrange(0, 100000000) for i in range(10000000)]

ans = set(sorted(arr)[:k])
assert ans == set(get_k_smallest1(k, list(arr)))
assert ans == set(get_k_smallest2(k, list(arr)))
assert ans == set(get_k_smallest3(k, list(arr)))

'''
» /usr/local/opt/python@3.8/bin/python3.8 /Users/yongcao/Program/tmp/py.py yongs-MBP
Function "get_k_smallest1" took 3.168419736999999 seconds to complete.
Function "get_k_smallest2" took 0.3814774750000005 seconds to complete.
Function "get_k_smallest3" took 0.37742361599999974 seconds to complete.
'''

Find Strong Connected Components (SCC)

Video

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def find_scc(n: int, edges: List[List[int]]):
graph = defaultdict(set)
for u, v in edges:
graph[u].add(v)
graph[v].add(u)

ids, low = [-1] * n, [-1] * n
stack, in_stack = [], [False] * n
id_max = 0

def dfs(u):
nonlocal id_max
stack.append(u)
in_stack[u] = True
ids[u] = low[u] = id_max
id_max += 1

for v in graph[u]:
if ids[v] == -1: dfs(v)
if in_stack[v]:
low[u] = min(low[u], low[v])

if low[u] == ids[u]:
while True:
node = stack.pop()
in_stack[node] = False
if node == u: break

for i in range(n):
if ids[i] == -1:
dfs(i)
return low
Read more »

Undirected Graph

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def hasCycle(n: int, edges: List[List]) -> bool:
def dfs(u, parent):
visited.add(u)
for v in graph[u]:
if v == parent: continue
if v in visited or dfs(v, u):
return True
return False

graph, visited = defaultdict(set), set()
for u, v in edges:
graph[u].add(v)
graph[v].add(u)

for u in range(n):
if u not in visited and dfs(u, None):
return True
return False
Read more »

Q1. 1534. Count Good Triplets

Given an array of integers arr, and three integers a, b and c. You need to find the number of good triplets.

A triplet (arr[i], arr[j], arr[k]) is good if the following conditions are true:

0 <= i < j < k < arr.length
|arr[i] - arr[j]| <= a
|arr[j] - arr[k]| <= b
|arr[i] - arr[k]| <= c
Where |x| denotes the absolute value of x.

Return the number of good triplets.

Note

From constrain 3 <= arr.length <= 100, we know this can be solved by complete search aka Brute force

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def countGoodTriplets(self, A: List[int], a: int, b: int, c: int) -> int:
ret = 0
def dfs(arr, idx):
nonlocal ret
if len(arr) == 3:
if abs(arr[0]-arr[1]) <= a and abs(arr[1]-arr[2]) <= b and abs(arr[0]-arr[2]) <= c:
ret += 1
return
for i in range(idx, len(A)):
dfs(arr+[A[i]], i+1)
dfs([], 0)
return ret
Read more »