n tech

gistfile1.txt

### Бинарное дерево

Реализовать простейшее сортированное бинарное дерево интов (без балансировки), у которого есть две операции:
* Вставка
* Нахождение *диаметра*

Где *диаметр* - расстояние между двумя наиболее удалёнными узлами дерева.

Реализовать за приемлемое время/память, обосновать

[10 6 12 4 7 - - 2 5 - 8 - - - - 1 - - - - - - - 9]

//       10 5 8 12  2
//      10
/     6    12 
//  4   7
/ 2  5    8
/1           9

class Tree {
	private static class Node {
  	Node left;
    Node right;
    int val;
    public Node(int val) {
    	this.val = val;
    }
  }
  
  private Node head;
  
  public void add(int newVal) {
  	if (head == null) {
    	head = new Node(newVal);
    } else {
    	add(head, newVal);
    }
  }
  
  private void add(Node head, int newVal) {
  	if (head.val == newVal) return;
  	if (head.val > newVal) {
    	if (head.left != null) {
      	add(head.left, newVal);
      } else {
      	head.left = new Node(newVal);
        return;
      }
    }
    
    if (head.val < newVal) {
    	if (head.right != null) {
      	add(head.right, newVal);
      } else {
      	head.right = new Node(newVal);
        return;
      }
    }
  }
  
  public int diametr() {
  	if (head == null) return 0;
    
  	Queue<Node> q = new ArrayDequeu<>();
    q.put(head);
    int maxx = 1;
    while(q.size() > 0) {
    	Node n = q.pop();
      
      int maxDeepLeft = 0;
      int maxDeepRight = 0;
      if (n.left != null) {
      	maxDeepLeft = calcDeep(n.left);
        q.put(n.left);
      }
      if (n.right != null) {
      	maxDeepRight = calcDeep(n.right);
        q.put(n.right);
      }
      maxx = max(maxDeepLeft + maxDeepRight + 1, maxx);
    }
    return maxx;
  }
  
  private int calcDeep(Node node) {
  	Queue<Pair<Node, Integer>> q = new ArrayDeque<>();
    q.put(new Pair<>(node, 1));
    int maxx = 1;
    while(q.size() > 0) {
    	Pair<Node, Integer> p = q.pop(); // return and remove from beginning
      Node n = p.first;
      int currVal = p.second;
      maxx = max(maxx, currVal);
      if (n.left != null) {
      	q.put(new Pair<>(n.left, currVal + 1));
      }
    	if (n.right != null) {
      	q.put(new Pair<>(n.right, currVal + 1));
      }
    }
  	return maxx; 
  }
}




* Есть бэкенд, бэк - чёрная коробка. 10 узлов
* Есть балансер, мы его пишем. 10 узлов
* Клиенты в сервис через балансер, ходят много и клиентов тоже много
* Балансировка по балансерам - DNS
* Как ограничить каждого пользователя по IP до N запросов/час (с некоторой точностью)


# Алгоритм.
## Вариант 1
Хранить все таймстампы.
Проблемы: скорость, объём памяти

nlogllog


111100011
111111110

## Вариант 2