# Levithan

Leviathan, or The Matter, Forme and Power of a Common Wealth Ecclesiastical and Civil

# Reverse Pairs

Given an array `nums`, we call `(i, j)` an important reverse pair if `i < j` and `nums[i] > 2*nums[j]`.

You need to return the number of important reverse pairs in the given array.

Example1:

```Input: [1,3,2,3,1]
Output: 2```

Example2:

```Input: [2,4,3,5,1]
Output: 3```

Note:

1. The length of the given array will not exceed `50,000`.
2. All the numbers in the input array are in the range of 32-bit integer.
```# Solution 1: Using Binary Index Tree, which has O(nlogn) time complexity.

class BIT():
def __init__(self, n):
self.n = n + 1
self.sums = [0] * self.n

def update(self, i, delta):
while i < self.n:
self.sums[i] += delta
i += i & (-i)

def query(self, i):
res = 0
while i > 0:
res += self.sums[i]
i -= i & (-i)
return res

class Solution:
def reversePairs(self, nums: List[int]) -> int:
sorted_nums = sorted(list(set(nums + [x * 2 for x in nums])))
tree = BIT(len(sorted_nums))

res = 0
ranks = {}

for i, n in enumerate(sorted_nums):
ranks[n] = i + 1

for n in nums[::-1]:
res += tree.query(ranks[n] - 1)
tree.update(ranks[n * 2], 1)

return res```
```# Solution 2: At this time, we are going to use bisect. Got inspiration from Merge Sort (Divide and Conquer).

class Solution:
def reversePairs(self, nums: List[int]) -> int:
ranks = list()
ans = 0

for n in reverse(nums):
ans += bisect.bisect_left(ranks, n)
bisect.insort_left(ranks, n * 2)

return ans
```

# Binary Index Tree

```class BIT:
def __init__(self, n):
self.n = n + 1
self.sums = [0] * self.n

def update(self, i, delta):
while i < self.n:
self.sums[i] += delta
i += i & (-i)

def query(self, i):
res = 0
while i > 0:
res += self.sums[i]
i -= i & (-i)
return res```

# Largest Rectangle in Histogram

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = `[2,1,5,6,2,3]`.

The largest rectangle is shown in the shaded area, which has area = `10` unit.

Example:

```Input: [2,1,5,6,2,3]
Output: 10```

Actually, I have met this problem on the online assessment of Amazon a few days ago.

IT IS A REALLY TOUGH QUESTION FOR MY DUMB BRAIN!

```class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
heights.append(0)
stack = [-1]
ans = 0

for i in range(len(heights)):
while heights[i] < heights[stack[-1]]:
h = heights[stack.pop()]
w = i - stack[-1] - 1
ans = max(ans, h * w)
stack.append(i)

return ans```

# Is Graph Bipartite?

Given an undirected `graph`, return `true` if and only if it is bipartite.

Recall that a graph is bipartite if we can split it’s set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.

The graph is given in the following form: `graph[i]` is a list of indexes `j` for which the edge between nodes `i` and `j` exists.  Each node is an integer between `0` and `graph.length - 1`.  There are no self edges or parallel edges: `graph[i]` does not contain `i`, and it doesn’t contain any element twice.

```Example 1:
Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
Explanation:
The graph looks like this:
0----1
|    |
|    |
3----2
We can divide the vertices into two groups: {0, 2} and {1, 3}.
```
```Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation:
The graph looks like this:
0----1
| \  |
|  \ |
3----2
We cannot find a way to divide the set of nodes into two independent subsets.
```

Note:

• `graph` will have length in range `[1, 100]`.
• `graph[i]` will contain integers in range `[0, graph.length - 1]`.
• `graph[i]` will not contain `i` or duplicate values.
• The graph is undirected: if any element `j` is in `graph[i]`, then `i` will be in `graph[j]`.
```class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
color = collections.defaultdict(lambda: -1)

def dfs(v, cur_color):
if color[v] != -1: return color[v] == cur_color
color[v] = cur_color
return all(dfs(e, cur_color ^ 1) for e in graph[v])

return all(dfs(v, 0) for v in range(len(graph)) if color[v] == -1)```

# Redis – epoll

Redis 对 `epoll` 的封装其实也是类似的，使用 `epoll_create` 创建 `epoll` 中使用的 `epfd`

```static int aeApiCreate(aeEventLoop *eventLoop) {
aeApiState *state = zmalloc(sizeof(aeApiState));

if (!state) return -1;
state->events = zmalloc(sizeof(struct epoll_event)*eventLoop->setsize);
if (!state->events) {
zfree(state);
return -1;
}
state->epfd = epoll_create(1024); /* 1024 is just a hint for the kernel */
if (state->epfd == -1) {
zfree(state->events);
zfree(state);
return -1;
}
eventLoop->apidata = state;
return 0;
}```

```static int aeApiAddEvent(aeEventLoop *eventLoop, int fd, int mask) {
aeApiState *state = eventLoop->apidata;
struct epoll_event ee = {0}; /* avoid valgrind warning */
/* If the fd was already monitored for some event, we need a MOD
* operation. Otherwise we need an ADD operation. */
int op = eventLoop->events[fd].mask == AE_NONE ?

ee.events = 0;
if (mask & AE_WRITABLE) ee.events |= EPOLLOUT;
ee.data.fd = fd;
if (epoll_ctl(state->epfd,op,fd,&ee) == -1) return -1;
return 0;
}```

```typedef union epoll_data {
void    *ptr;
int      fd; /* 文件描述符 */
uint32_t u32;
uint64_t u64;
} epoll_data_t;

struct epoll_event {
uint32_t     events; /* Epoll 事件 */
epoll_data_t data;
};```

`aeApiPoll` 函数只需要将 `epoll_event` 数组中存储的信息加 入  `eventLoop`  的  `fired` 数组中，将信息传递给上层模块：

```static int aeApiPoll(aeEventLoop *eventLoop, struct timeval *tvp) {
aeApiState *state = eventLoop->apidata;
int retval, numevents = 0;

retval = epoll_wait(state->epfd,state->events,eventLoop->setsize,
tvp ? (tvp->tv_sec*1000 + tvp->tv_usec/1000) : -1);
if (retval > 0) {
int j;

numevents = retval;
for (j = 0; j < numevents; j++) {
struct epoll_event *e = state->events+j;

if (e->events & EPOLLOUT) mask |= AE_WRITABLE;
if (e->events & EPOLLERR) mask |= AE_WRITABLE;
if (e->events & EPOLLHUP) mask |= AE_WRITABLE;
eventLoop->fired[j].fd = e->data.fd;
}
}
return numevents;
}```

# Select

```int fd = /* file descriptor */

fd_set rfds;
FD_ZERO(&rfds);
FD_SET(fd, &rfds)

for ( ; ; ) {
select(fd+1, &rfds, NULL, NULL, NULL);
if (FD_ISSET(fd, &rfds)) {
/* file descriptor `fd` becomes readable */
}
}```
1. 初始化一个可读的 `fd_set` 集合，保存需要监控可读性的 FD；
2. 使用 `FD_SET` 将 `fd` 加入 `rfds`
3. 调用 `select` 方法监控 `rfds` 中的 FD 是否可读；
4. 当 `select` 返回时，检查 FD 的状态并完成对应的操作。

```static int aeApiCreate(aeEventLoop *eventLoop) {
aeApiState *state = zmalloc(sizeof(aeApiState));
if (!state) return -1;
FD_ZERO(&state->rfds);
FD_ZERO(&state->wfds);
eventLoop->apidata = state;
return 0;
}```

`aeApiAddEvent` 和 `aeApiDelEvent` 会通过 `FD_SET` 和 `FD_CLR` 修改 `fd_set` 中对应 FD 的标志位：

```static int aeApiAddEvent(aeEventLoop *eventLoop, int fd, int mask) {
aeApiState *state = eventLoop->apidata;
return 0;
}```

```static int aeApiPoll(aeEventLoop *eventLoop, struct timeval *tvp) {
aeApiState *state = eventLoop->apidata;
int retval, j, numevents = 0;

memcpy(&state->_rfds,&state->rfds,sizeof(fd_set));
memcpy(&state->_wfds,&state->wfds,sizeof(fd_set));

retval = select(eventLoop->maxfd+1,
&state->_rfds,&state->_wfds,NULL,tvp);
if (retval > 0) {
for (j = 0; j <= eventLoop->maxfd; j++) {
aeFileEvent *fe = &eventLoop->events[j];