[Hard] interview questions #7

[rygh4775]

[btakeya]

1. make links between synonyms.
2. traverse & count names 2-1. when name is synonym(s) found, merge all linked names

import scala.io.StdIn._
import scala.collection.mutable.Buffer

object Run extends App {
    def setup(): (Array[NameFreq], Array[NameLink]) = {
        val freqTimes = readInt()
        val freqs = (1 to freqTimes).map(_ => readLine())
            .map(line => { val toks = line.split(" "); (toks(0), toks(1).toInt) })
            .map(toks => new NameFreq(toks._1, toks._2))
            .toArray
        val linkTimes = readInt()
        val links = (1 to linkTimes).map(_ => readLine())
            .map(line => { val toks = line.split(" "); (toks(0), toks(1)) })
            .map(toks => new NameLink(toks._1, toks._2))
            .toArray

        (freqs, links)
    }

    def link(freqs: Array[NameFreq], links: Array[NameLink]): Array[NameMeta] = {
        val metas = freqs.map(n => new NameMeta(n.name, n.freq)).toArray

        def find(name: String): Option[NameMeta] = {
            def go(rest: Array[NameMeta], name: String): Option[NameMeta] = {
                if (rest.size == 0) None
                else {
                    if (rest.head.name == name) Some(rest.head)
                    else go(rest.tail, name)
                }
            }
            go(metas, name)
        }

        for (link <- links) {
            val freq1Opt = find(link.name1)
            val freq2Opt = find(link.name2)
            if (freq1Opt.nonEmpty && freq2Opt.nonEmpty) {
                val freq1 = freq1Opt.get
                val freq2 = freq2Opt.get
                freq1.links += freq2
                freq2.links += freq1
            }
        }

        metas
    }

    def uniqueCount(metas: Array[NameMeta]): Array[NameMeta] = {
        def merge(meta: NameMeta): NameMeta = {
            val represent = meta
            val queue: Buffer[NameMeta] = Buffer.empty
            queue ++= meta.links
            while (queue.size > 0) {
                val _meta = queue.remove(0) // dequeue
                _meta.visited = true
                represent addFreq _meta.freq
                queue ++= _meta.links.filter(l => l.visited == false)
            }
            represent
        }

        def go(rest: Array[NameMeta], resBuf: Array[NameMeta]): Array[NameMeta] = {
            if (rest.size == 0) resBuf
            else {
                val head = rest.head
                if (head.visited) go(rest.tail, resBuf)
                else {
                    head.visited = true
                    if (head.links.size == 0) go(rest.tail, resBuf :+ head)
                    else go(rest.tail, resBuf :+ merge(head))
                }
            }
        }

        go(metas, Array.empty)
    }

    val (freqs, links) = setup()
    val linked = link(freqs, links)
    val countList = uniqueCount(linked)
    println(countList.mkString("-"))
}

case class NameFreq(val name: String, val freq: Int)

case class NameLink(val name1: String, val name2: String)

class NameMeta(val name: String, var freq: Int, val links: Buffer[NameMeta], var visited: Boolean) {
    def this(name: String, freq: Int) = {
        this(name, freq, Buffer.empty, false)
    }

    def addFreq(f: Int) = this.freq += f

    override def toString() = s"NameMeta($name,$freq,${links.map(n => n.name).mkString("(", ",", ")")},$visited)"
}

// sample1
5
John 15
Jon 12
Chris 13
Kris 4
Christopher 19
4
Jon John
John Johnny
Chris Kris
Chris Christopher

// sample2
9
John 10
Jon 3
Davis 2
Kari 3
Johnny 11
Carlton 8
Carleton 2
Jonathan 9
Carrie 5
5
Jonathan John
Jon Johnny
Johnny John
Kari Carrie
Carleton Carlton