interview question for programmers

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

https://gist.github.com/vasnake/4ce910892d286de2402adc24cbf9d886

---



Есть события: (время начала, время конца, тег "в метро", айди территории, флаг "вход", флаг "выход"),
заполнены поля могут быть как угодно, очередность событий может быть любая

    case class TelEventRecord(bts: Int, ets: Int,
                        transport: String,
                        zid: Int = -1,
                        enter: Boolean = false, exit: Boolean = false)

Надо обработать последовательность таких событий, чтобы получить последовательность "поездок"
от "входа" до "выхода": (начало поездки, конец, территория входа, выхода, было ли по ходу "метро")

    case class TripRawData(bts: Int, ets: Int, bzid: Int, ezid: Int, metro: Boolean)

Ситуация осложняется тем, что любая последовательность "входов" и/или "выходов" может быть схлопнута в 0 или 1 вход/выход.
Правила схлопывания такие: если в последовательности входов/выходов (промежуточные не учитываем) события отстают от соседей менее чем на 30 минут,
такая последовательность схлопывается. Если число событий четное, то в 0 событий. Если нечетное, то в 1, первое событие.
Смысл этого в том, что, к примеру, при въезде в страну, могут быть зарегистрированы события вход/выход/вход/выход с промежутком 29 минут 59 секунд.
Такая последовательность выбрасывается, считается, что въезда в страну не было. Флуктации.

Набор тестов для проверки таких условий:

    "rep#10 events2Trips" should "fold (enter,exit) into 1 trip" in {
        val events = Seq(
            TelEventRecord(1, 2, "", 3, true, false),
            TelEventRecord(1801, 1802, "", 4, false, true))
        val expected = Seq(TripRawData(1, 1801, 3, 4, false))
        val trips = events2trips(events)
        assert(trips === expected)
    }

    "rep#10 events2Trips" should "fold metro (enter,exit) into 1 trip" in {
        val events = Seq(
            TelEventRecord(1, 2, "metro", 3, true, false),
            TelEventRecord(1801, 1802, "", 4, false, true))
        val expected = Seq(TripRawData(1, 1801, 3, 4, true))
        assert(events2trips(events) === expected)

        val events2 = Seq(
            TelEventRecord(1, 2, "", 3, true, false),
            TelEventRecord(1801, 1802, "metro", 4, false, true))
        assert(events2trips(events2) === expected)
    }

    "rep#10 events2Trips" should "fold (enter, ..., exit) into 1 trip" in {
        val events = Seq(
            TelEventRecord(1, 2, "", 3, true, false),
            TelEventRecord(100, 200, "", 5, false, false),
            TelEventRecord(300, 400, "", 5, false, false),
            TelEventRecord(1801, 1802, "", 4, false, true))
        val expected = Seq(TripRawData(1, 1801, 3, 4, false))
        val trips = events2trips(events)
        assert(trips === expected)

        val events2 = Seq(
            TelEventRecord(1, 2, "", 3, true, false),
            TelEventRecord(100, 200, "", 5, false, false),
            TelEventRecord(300, 400, "metro", 5, false, false),
            TelEventRecord(1801, 1802, "", 4, false, true))
        assert(events2trips(events2) === Seq(TripRawData(1, 1801, 3, 4, true)))
    }

    "rep#10 events2Trips" should "fold (enter, enter, exit) into 1 trip" in {
        val events = Seq(
            TelEventRecord(1, 2, "", 3, true, false),
            TelEventRecord(1801, 1802, "", 4, true, false),
            TelEventRecord(18010, 18020, "", 4, false, true))
        val expected = Seq(TripRawData(1, 18010, 3, 4, false))
        val trips = events2trips(events)
        assert(trips === expected)
    }

    "rep#10 events2Trips" should "fold (enter, exit, exit) into 1 trip" in {
        val events = Seq(
            TelEventRecord(1, 2, "", 3, true, false),
            TelEventRecord(1801, 1802, "", 4, false, true),
            TelEventRecord(18010, 18020, "", 4, false, true))
        val expected = Seq(TripRawData(1, 1801, 3, 4, false))
        val trips = events2trips(events)
        assert(trips === expected)
    }

    "rep#10 events2Trips" should "ignore jiggle" in {
        val events = Seq(
            TelEventRecord(1, 2, "jgl", 3, true, false),
            TelEventRecord(3, 4, "jgl", 3, false, true),
            TelEventRecord(5, 6, "jgl", 3, true, false),
            TelEventRecord(1805, 1806, "jgl", 4, false, true))
        val expected = Seq(TripRawData(1, 1805, 3, 4, false))
        val trips = events2trips(events)
        assert(trips === expected)

        val events2 = Seq(
            TelEventRecord(1, 2, "", 3, true, false),
            TelEventRecord(1801, 1802, "", 4, false, true),
            TelEventRecord(1803, 1804, "", 4, true, false),
            TelEventRecord(1805, 1806, "", 4, false, true))
        assert(events2trips(events2) === Seq(TripRawData(1, 1801, 3, 4, false)))

        val events3 = Seq(
            TelEventRecord(1, 2, "", 3, true, false),
            TelEventRecord(3, 4, "", 3, false, true),
            TelEventRecord(1801, 1802, "", 4, false, true))
        assert(events2trips(events3) === Seq.empty[TripRawData])

        val events4 = Seq(
            TelEventRecord(1, 2, "", 3, true, false),
            TelEventRecord(1801, 1802, "", 4, false, true),
            TelEventRecord(1803, 1804, "", 4, true, false))
        assert(events2trips(events4) === Seq.empty[TripRawData])
    }

Говнокод лобового решения в императивном стиле (циклы, счетчики, буферы, мутабельные переменные) выглядит так:

    /**
      * Filter interleaving events: enter, exit, ...
      * Copy to enter event 'metro' tag if any intermediate event have it.
      * @param srtd events sorted by time
      * @return enter, exit, ... sequence
      */
    def normalizeInterleave(srtd: Seq[TelEventRecord]): Seq[TelEventRecord] = {
        // only interleaving in/out events
        var metro = false
        var enter: TelEventRecord = null
        var res = Seq.empty[TelEventRecord]

        if (srtd.size < 2) srtd
        else {
            for (n <- 0 until srtd.size) {
                val curr = srtd(n)
                metro = (curr.transport == transName)
                if (curr.enter) {
                    if (enter == null) enter = curr
                }
                else if (curr.exit) {
                    if (enter != null) {
                        if (metro) enter = enter.copy(transport = transName)
                        res = (res :+ enter) :+ curr
                        enter = null
                    }
                }
                else {
                    if (metro && enter != null) enter = enter.copy(transport = transName)
                }
            }
            if (enter == null) res else res :+ enter
        }
    }

    /**
      * Fold jiggle crossing: ignore short movements
      * @param srtd sorted by time events sequence
      * @return enter,exit, ... sequence w/o short trips
      */
    def normalizeJiggle(srtd: Seq[TelEventRecord]): Seq[TelEventRecord] = {
        // jiggle: if 2.ts - 1.ts < 30 min
        var temp = Seq.empty[TelEventRecord]
        var res = Seq.empty[TelEventRecord]

        if (srtd.size < 2) srtd
        else {
            var prev = srtd(0)
            temp = temp :+ prev
            for (n <- 1 until srtd.size) {
                val curr = srtd(n)
                if ((curr.bts - prev.bts) < jiggleLimit) {
                    temp = temp :+ curr
                }
                else {
                    val folded = if (temp.size % 2 == 0) Seq() else Seq(temp(0))
                    res = res ++ folded
                    temp = Seq(curr)
                }
                prev = curr
            }
            val folded = if (temp.size % 2 == 0) Seq() else Seq(temp(0))
            res ++ folded
        }
    }

    /**
      * Combine events sequence into trips sequence:
      * normalize in/out pairs, remove short trips
      * @param events events sequence
      * @return trips sequence
      */
    def events2trips(events: Seq[TelEventRecord]): Seq[TripRawData] = {
        var trips = Seq.empty[TripRawData]

        // remove cross-border repetitions: time to next cb event < 30 min        
        def normalize(srtd: Seq[TelEventRecord]): Seq[TelEventRecord] = {
            val interleaved = normalizeInterleave(srtd)
            normalizeJiggle(interleaved)
        }

        // collect in,out pairs into trips
        var prev: TelEventRecord = null
        def checkEvent(n: Int, srtd: Seq[TelEventRecord]): Unit = {
            val curr = srtd(n)
            if (curr.enter) { if (prev == null) prev = curr }
            else if (curr.exit) {
                if (prev != null) {
                    val metro = (prev.transport == transName || curr.transport == transName)
                    val trip = TripRawData(prev.bts, curr.bts, prev.zid, curr.zid, metro)
                    trips = trips :+ trip
                    prev = null
                }
            }
        }

        val srtd = normalize(events.sortBy(e => e.bts))
        if (srtd.size > 1) {
            for (n <- 0 until srtd.size) checkEvent(n, srtd)
        }

        trips.toVector
    }

Задача: написать понятное, эффективное и красивое решение в функциональном стиле. 

original post http://vasnake.blogspot.com/2017/01/interview-question-for-programmers.html