Есть одна задача, которая дважды попадалась мне на собесах. Как это часто бывает, первый раз я эту задачу полностью завалил, а второй раз написал какую-то кривую хрень. И это при том, что всё решение сводилось к знанию всего одной конкретной структуры данных.

Поэтому сегодня поделюсь с вами этой структурой на примере той самой задачи, вдруг пригодится.

Задача такая: вот у нас есть трекер посещений сайта, с двумя методами:

class WebsiteTracker{
    fun visit() {}
    fun count(): Int {}
}

Метод visit дёргается когда человек заходит на сайт. Метод count должен возвращать количество посещений за последние 5 минут. Для упрощения не нужно париться насчёт многопоточности и считать уникальных посетителей только реализовать эти два метода, причём максимально эффективно. Задача сложнее, чем кажется на первый взгляд, можете попробовать что-то накидать перед тем, как читать дальше.

Не буду долго мучить, все делается через Кольцевой буфер. По сути это такой массив, который работает как круг. Когда буфер заполняется и вы добавляете новый элемент, самый старый автоматически удаляется. Почему он называется кольцевым? Потому что при итерации, дойдя до последнего элемента, мы снова переходим к первому, замыкая круг.

В Kotlin, разумеется, нет такой структуры, однако её очень просто сделать при помощи LinkedHashMap. Фишка этой мапы не только в том, что она сохраняет порядок добавления, а ещё и в том, что у неё есть волшебный метод removeEldestEntry. Переопределив его, можно задать правило, по которому старые элементы будут автоматически вычищаться при добавлении новых.

Поэтому задаём правило, что нужно удалять, если значение ключа отличается от текущего времени более чем на 300 секунд:

val visits = object : LinkedHashMap<Long, Int>() {
  override fun removeEldestEntry(
      eldest: MutableMap.MutableEntry<Long, Int>
  ): Boolean = eldest.key < currentTimeMillis() - 300*1000
}

Всё, что осталось – это реализовать наши методы:

fun visit() {
    val timeSlot = (currentTimeMillis() / 1000) * 1000
    visits[timeSlot] = (visits[timeSlot] ?: 0) + 1
}

fun count(): Int {
    val cutoff = сurrentTimeMillis() - timeWindow
    visits.entries.removeIf { it.key < cutoff }
    return visits.values.sum()
}

Может возникнуть вопрос, нафига нам нужно пробегаться по коллекции в методе count? Это для кейса, когда долго никто не заходил на сайт, в таком случае у нас не будут вытесняться старые элементы.

Второй вопрос, который может возникнуть: мы же итерируемся по целой коллекции это же не оптимально? У нас гарантированно не более 300 элементов, пробежаться по ним также быстро как ты в свой первый раз.