juan_gandhi | Entries tagged with interview

You're viewing

juan_gandhi's journal
Create a Dreamwidth Account Learn More

Reload page in style: light

"Задача такая: есть Seq[Seq[String]]; сделать interleave. Я нарисовал tailrec версию, но... но надо было очередь мне впендюрить, конечно, а то не эффективно ж. Ну все равно. Работает."

Так это, меня зацепило, как же это на самом-то деле делать, чтобы эффективно и на структурах данных. Лег спать, перед сном подумал, и быстро понял.

We are having a special kind of tree: a root, and a bunch of branches, each one linear. Now we need to do BFS. For BFS we need a queue. That's the solution.

Problem: given a list of pairs of nonnegative integers, where pairs represent edges of a directed graph, check if the graph is a linear order.

Solutions:

def isLinear(src: List[(Int, Int)]): Boolean = {
  val m = src.toMap.withDefaultValue(-1)
  val tails = m.values.toSet
  src.isEmpty || (src.size == m.size) && {
    src find { case (a,_) => !tails(a) } match {
      case Some((start,_)) =>
        val visited =
          Stream.iterate(start)(m).takeWhile(0 <=).take(src.size+2)
        visited.length == src.size + 1
      case None => false
    }
  }
}