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

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

Задача такая: вот у нас есть трекер посещений сайта, с двумя методами:
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 элементов, пробежаться по ним также быстро как ты в свой первый раз.
😁175👍5🗿3🤔1



tgoop.com/dev_easy_notes/384
Create:
Last Update:

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

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

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

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 элементов, пробежаться по ним также быстро как ты в свой первый раз.

BY Dev Easy Notes




Share with your friend now:
tgoop.com/dev_easy_notes/384

View MORE
Open in Telegram


Telegram News

Date: |

Select: Settings – Manage Channel – Administrators – Add administrator. From your list of subscribers, select the correct user. A new window will appear on the screen. Check the rights you’re willing to give to your administrator. As five out of seven counts were serious, Hui sentenced Ng to six years and six months in jail. Telegram users themselves will be able to flag and report potentially false content. With the administration mulling over limiting access to doxxing groups, a prominent Telegram doxxing group apparently went on a "revenge spree." Hui said the time period and nature of some offences “overlapped” and thus their prison terms could be served concurrently. The judge ordered Ng to be jailed for a total of six years and six months.
from us


Telegram Dev Easy Notes
FROM American