Вариант эффективного интервью

// Приветствуются конструктивные замечания по коду

function problem2(input) {
	var openIndex = input.indexOf('{');

	if (openIndex === -1) return [input];

	var result = [''];

	while (openIndex !== -1) {
		var firstPart = input.substring(0, openIndex);
		var parts = [];

		var openCount = 0;

		for (var i = openIndex + 1, length = input.length; i < length; ++i) {
			if (input[i] === '{')
				++openCount;
			else if (input[i] === '}') {
				--openCount;

				if (openCount < 0) {
					parts.push(input.substring(openIndex + 1, i));

					input = input.slice(i + 1);
					break;
				}
			}
			else if (openCount === 0 && input[i] === '|') {
				parts.push(input.substring(openIndex + 1, i));

				openIndex = i;
			}
		}


		var newResult = [];

		parts.forEach(function (part) {
			problem2(part).forEach(function (partResult) {
				result.forEach(function (resultItem) {
					newResult.push(resultItem + firstPart + partResult);
				});
			});
		});

		result = newResult;

		openIndex = input.indexOf('{');
	}

	if (input.length > 0) {
		result.forEach(function (element, index, array) {
			array[index] = element + input;
		});
	}

	return result;
}

import scala.util.parsing.combinator._
import scala.util.parsing.input.CharSequenceReader

sealed abstract trait Expr {
  def allStrings: List[String]
  def isLiteral = false
  def isEmpty = false
}
case class Literal(s: String) extends Expr {
  override def allStrings: List[String] = List(s)
  override def isLiteral = true
}
case object Empty extends Expr {
  override def allStrings: List[String] = Nil
  override def isEmpty = true
}
case class Multi(es: List[Expr]) extends Expr {
  override def allStrings: List[String] = es.flatMap(_.allStrings)
}
case class Concat(es: List[Expr]) extends Expr {
  override def allStrings: List[String] = allStrings(List(""), es)

  private def allStrings(prefixes: List[String], es: List[Expr]): List[String] = es match {
    case Nil => prefixes
    case h :: t => allStrings(for (p <- prefixes; s <- h.allStrings) yield p + s, t)
  }
}

trait ExprParsers extends RegexParsers {
  override val skipWhitespace = false

  def literal: Parser[Literal] = """[^{|}]+""".r ^^ { Literal(_) }
  def multi: Parser[Multi] = "{" ~> repsep(cexpr, "|") <~ "}" ^^ { l => Multi(l.distinct) }
  def concat: Parser[Concat] = (mexpr +) ^^ { Concat(_) }
  def cexpr: Parser[Expr] = concat
  def mexpr: Parser[Expr] = literal | multi
}

trait ExprOptParsers extends ExprParsers {
  override def cexpr: Parser[Expr] = super.cexpr ^^ { _ match {
    case Concat(List(x)) => x
    case Concat(l) if l.forall(_.isLiteral) => Literal(l.map(_ match {case Literal(t) => t}).mkString)
    case Concat(l) if l.exists(_.isEmpty) => Empty
    case x => x
  }}
  override def mexpr: Parser[Expr] = super.mexpr ^^ { _ match {
    case Multi(Nil) => Empty
    case Multi(List(x)) => x
    case Multi(l) if l.exists(_.isEmpty) => Empty
    case x => x
  }}
}

object Parser extends ExprOptParsers {
  private lazy val main: Parser[Expr] = phrase(cexpr)
  private def parse(s: String): Expr = main(new CharSequenceReader(s)) match {
    case Success(e, _) => e
    case NoSuccess(m, n) => throw new IllegalArgumentException("Parsing error at " + n.pos + "\n" +
        n.pos.longString + ": " + m)
  }

  def printAll(s: String): Unit = {
    val p = parse(s)
    println(p.allStrings.mkString("\n"))
    println(p)
  }

  def shouldFail(s: String): Unit = {
    try {
      val p = parse(s)
    } catch {
      case e: IllegalArgumentException => println(e.getMessage)
    }
  }

  def main(args: Array[String]): Unit = {
    shouldFail("{")
    shouldFail("}")
    shouldFail("")
    printAll("тест")
    printAll("тест {тест}")
    printAll("{тест} {тест}")
    printAll("{тест {тест}}")
    printAll("{}")
    printAll("{{{{{{{{{{тест {тест}}}}}}}}}}}")
    printAll("{A | B | C} тест")
    printAll("{A | B} {A | B}")
    printAll("{A |A | B} {A | B| B}")
    printAll("{Пожалуйста|Просто} сделайте так, чтобы это {удивительное|крутое|простое} тестовое предложение {изменялось {быстро|мгновенно} случайным образом|менялось каждый раз}.")
    printAll("{Пожалуйста|Просто} сделайте так, чтобы это {удивительное|крутое|простое} тестовое предложение {изменялось {быстро{}|мгновенно} случайным образом|менялось каждый раз}.")
  }
}