# Interview

```{toctree}
:hidden:

ad
```

## Algorithm
### 不同的二叉搜索树
https://leetcode.cn/problems/unique-binary-search-trees/description/


## Design
### 1. 手写cross entropy与softmax优化
原生softmax很容易溢出，需要使用一些优化操作减少对数和指数的计算。

```python
import torch
import torch.nn.functional as F
b, c = 2, 8

z = torch.randn(b, c) * 1000
y = torch.randint(0, c, (b, )).long()

def cross_entropy_with_logits1(z, y):
    p = torch.exp(z) / torch.exp(z).sum(dim=-1, keepdim=True)
    print(p)
    loss = (- y * torch.log(p)).sum(dim=-1)
    return loss

def cross_entropy_with_logits2(z, y):
    z = z - torch.max(z, dim=-1, keepdim=True).values
    p = torch.exp(z) / torch.exp(z).sum(dim=-1, keepdim=True)
    print(p)
    loss = (- y * torch.log(p)).sum(dim=-1)
    return loss

def cross_entropy_with_logits3(z, y):
    z = z - torch.max(z, dim=-1, keepdim=True).values
    loss = (- y * (z-torch.log(torch.exp(z).sum(dim=-1, keepdim=True)))).sum(dim=-1)
    return loss
print(cross_entropy_with_logits1(z, F.one_hot(y, num_classes=c)))
print(cross_entropy_with_logits2(z, F.one_hot(y, num_classes=c)))
print(cross_entropy_with_logits3(z, F.one_hot(y, num_classes=c)))
print(F.cross_entropy(z, y, reduction="none"))

```

**Reference**: 
- [有效防止softmax计算时上溢出（overflow）和下溢出（underflow）的方法](https://www.cnblogs.com/guoyaohua/p/8900683.html)

### 2. 自动微分计算图设计
pass

### 3. 大文件中位数
基数排序