Записки программиста, обо всем и ни о чем. Но, наверное, больше профессионального.

2017-01-10

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


Комментариев нет:

Отправить комментарий

Архив блога

Ярлыки

linux (241) python (191) citation (186) web-develop (170) gov.ru (159) video (124) бытовуха (115) sysadm (100) GIS (97) Zope(Plone) (88) бурчалки (84) Book (83) programming (82) грабли (77) Fun (76) development (73) windsurfing (72) Microsoft (64) hiload (62) internet provider (57) opensource (57) security (57) опыт (55) movie (52) Wisdom (51) ML (47) driving (45) hardware (45) language (45) money (42) JS (41) curse (40) bigdata (39) DBMS (38) ArcGIS (34) history (31) PDA (30) howto (30) holyday (29) Google (27) Oracle (27) tourism (27) virtbox (27) health (26) vacation (24) AI (23) Autodesk (23) SQL (23) Java (22) humor (22) knowledge (22) translate (20) CSS (19) cheatsheet (19) hack (19) Apache (16) Manager (15) web-browser (15) Никонов (15) functional programming (14) happiness (14) music (14) todo (14) Klaipeda (13) PHP (13) course (13) scala (13) weapon (13) HTTP. Apache (12) SSH (12) frameworks (12) hero (12) im (12) settings (12) HTML (11) SciTE (11) USA (11) crypto (11) game (11) map (11) HTTPD (9) ODF (9) Photo (9) купи/продай (9) benchmark (8) documentation (8) 3D (7) CS (7) DNS (7) NoSQL (7) cloud (7) django (7) gun (7) matroska (7) telephony (7) Microsoft Office (6) VCS (6) bluetooth (6) pidgin (6) proxy (6) Donald Knuth (5) ETL (5) NVIDIA (5) Palanga (5) REST (5) bash (5) flash (5) keyboard (5) price (5) samba (5) CGI (4) LISP (4) RoR (4) cache (4) car (4) display (4) holywar (4) nginx (4) pistol (4) spark (4) xml (4) Лебедев (4) IDE (3) IE8 (3) J2EE (3) NTFS (3) RDP (3) holiday (3) mount (3) Гоблин (3) кухня (3) урюк (3) AMQP (2) ERP (2) IE7 (2) NAS (2) Naudoc (2) PDF (2) address (2) air (2) british (2) coffee (2) fitness (2) font (2) ftp (2) fuckup (2) messaging (2) notify (2) sharepoint (2) ssl/tls (2) stardict (2) tests (2) tunnel (2) udev (2) APT (1) CRUD (1) Canyonlands (1) Cyprus (1) DVDShrink (1) Jabber (1) K9Copy (1) Matlab (1) Portugal (1) VBA (1) WD My Book (1) autoit (1) bike (1) cannabis (1) chat (1) concurrent (1) dbf (1) ext4 (1) idioten (1) join (1) krusader (1) license (1) life (1) migration (1) mindmap (1) navitel (1) pneumatic weapon (1) quiz (1) regexp (1) robot (1) science (1) serialization (1) spatial (1) tie (1) vim (1) Науру (1) крысы (1) налоги (1) пианино (1)