Home

212. Word Search II Solution Use Trie to store all searched words. dfs across the board. If the node is inside Trie and is marked as isWord, it means it is a searched word and we can traverse the board to get it. Remove visited node in the board by marking them as # ```python class TireNode(): def init(self): self.childre...

128. Longest Consecutive Sequence Solution Find the smallest number in each sequence Get the length of the sequence by counting the number of larger numbers in the sequence Complexity: O(n) def longestConsecutive(self, nums): """ :type nums: List[int] :rtype: int """ set_nums = set(nums) res = 0 for num in nums: if num...

57. Insert Interval Solution 1 - Traversal Traverse the interval list one by one. Count the number of intervals that are considered. If the newInterval is completely larger than interval, insert the interval. If the newInterval is completely smaller than interval, break. If the newInterval is overlapping with the interval, merge it. ...

295. Find Median from Data Stream Solutions Keep 2 heap, one min_heap and one max_heap Let min_heap has at most 1 item more than max_heap The tops of two heaps will be the median of the whole list.

A distributed algorithm is self-stabilizing if Starting from any (legal or illegal) state, the protocol will eventually reach a legal state if there are no more faults Once the system is in a legal state, it will only transit to other legal states unless there are faults The Rotating Privilege Problem A ring of $n$ processes, each proce...

Leader Election on Anonymous Ring Anonymous Ring: No unique identifiers For low-end devices that do not have unique identifiers. Impossible using deterministic algorithms. Initial state, algorithm on each node, each step are the same $\rightarrow$ Final state is the same Leader Election on Ring Each node has a unique identifier Nodes ...

Goal Termination: All nodes (that have not failed) eventually decide Agreement: All nodes that decide should decide on the same value Validity: If all nodes have the same initial input, that value should be the only possible decision value. Otherwise nodes are allowed to decide on anything (except that they still need to satisfy the Agre...

Affine Rectification: remove projective distortion The image of $l_{\infin}$ is specified $l_{\infin}$ is a fixed line under affine transformation, i.e. $H_{31} = H_{32} = 0$ In general, under an affinity, a point on $l_{\infin}$ is mapped to another point on $l_{\infin}$ $H_p’ = H_AH_P^{-1} =H_A\begin{bmatrix}1 & 0 & l_1 \ 0 & 1...