Scala String Equality Вопрос из программирования Интервью

Поскольку мне нравилось программирование в Scala, для моего интервью с Google я попросил их дать мне вопрос о стиле Scala/функциональном программировании. Вопрос о функциональном стиле Scala, который я получил, был следующим:

У вас есть две строки, состоящие из буквенных символов, а также специальный символ, представляющий символ обратного пространства. Позвольте называть этот символ обратного пространства '/'. Когда вы попадаете на клавиатуру, вы вводите эту последовательность символов, включая символ backspace/delete. Решение, которое вы должны реализовать, должно проверить, производят ли две последовательности символов один и тот же вывод. Например, "abc", "aa/bc". "abb/c", "abcc/", "/abc" и "//abc" производят одинаковый вывод "abc". Поскольку это вопрос Scala/функционального программирования, вы должны реализовать свое решение в идиоматическом стиле Scala.

Я написал следующий код (может быть, это не совсем то, что я написал, я просто ушел из памяти). В основном я просто линейно перехожу через строку, добавляя символы в список, а затем сравниваю списки.

def processString(string: String): List[Char] = {
  string.foldLeft(List[Char]()){ case(accumulator: List[Char], char: Char) =>
    accumulator match {
      case head :: tail => if(char != '/') { char :: head :: tail } else { tail }
      case emptyList => if(char != '/') { char :: emptyList } else { emptyList }
    }
  }
}

def solution(string1: String, string2: String): Boolean = {
  processString(string1) == processString(string2)
}

Все идет нормально? Затем он спросил о сложности времени, и я ответил на линейное время (потому что вы должны обрабатывать каждый символ один раз) и линейное пространство (потому что вам нужно скопировать каждый элемент в список). Затем он попросил меня сделать это в линейном времени, но с постоянным пространством. Я не мог придумать, как это сделать, что чисто функционально. Он попробовал использовать функцию в библиотеке коллекций Scala, например, "zip" или "map" (я явно помню, как он говорил слово "zip").

Вот что. Я думаю, что физически невозможно сделать это в постоянном пространстве без какого-либо изменчивого состояния или побочных эффектов. Как будто я думаю, что он перепутал вопрос. Как вы думаете?

Можете ли вы решить это в линейном времени, но с постоянным пространством?

Ответ 1

Вам не нужно создавать вывод, чтобы найти ответ. Вы можете одновременно перебирать две последовательности и останавливаться на первой разнице. Если вы не находите разницы, и обе последовательности заканчиваются одновременно, они равны, иначе они разные.

Но теперь рассмотрим такие последовательности, как этот: aaaa/// чтобы сравнить с a. Вам нужно использовать 6 элементов из левой последовательности и один элемент из правой последовательности, прежде чем вы сможете утверждать, что они равны. Это означает, что вам нужно сохранить не менее 5 элементов в памяти, пока вы не сможете убедиться, что все они удалены. Но что, если вы повторили элементы с конца? Вам просто нужно было бы подсчитать количество обратных пространств, а затем просто игнорировать столько элементов, сколько необходимо в левой последовательности, не требуя держать их в памяти, так как вы знаете, что они не будут присутствовать в конечном выходе. Вы можете получить память O(1) используя эти два совета.

Я попробовал это и, похоже, работает:

def areEqual(s1: String, s2: String) = {
    def charAt(s: String, index: Int) = if (index < 0) '#' else s(index)

    @tailrec
    def recSol(i1: Int, backspaces1: Int, i2: Int, backspaces2: Int): Boolean = (charAt(s1, i1), charAt(s2, i2)) match {
        case ('/',  _) => recSol(i1 - 1, backspaces1 + 1, i2, backspaces2)
        case (_,  '/') => recSol(i1, backspaces1, i2 - 1, backspaces2 + 1)
        case ('#' , '#') => true
        case (ch1, ch2)  => 
            if      (backspaces1 > 0) recSol(i1 - 1, backspaces1 - 1, i2    , backspaces2    )
            else if (backspaces2 > 0) recSol(i1    , backspaces1    , i2 - 1, backspaces2 - 1)
            else        ch1 == ch2 && recSol(i1 - 1, backspaces1    , i2 - 1, backspaces2    )
    }
    recSol(s1.length - 1, 0, s2.length - 1, 0)
}

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

// examples from the question
val inputs = Array("abc", "aa/bc", "abb/c", "abcc/", "/abc", "//abc")
for (i <- 0 until inputs.length; j <- 0 until inputs.length) {
    assert(areEqual(inputs(i), inputs(j)))
}

// more deletions than required
assert(areEqual("a///////b/c/d/e/b/b", "b")) 
assert(areEqual("aa/a/a//a//a///b", "b"))
assert(areEqual("a/aa///a/b", "b"))

// not enough deletions
assert(!areEqual("aa/a/a//a//ab", "b")) 

// too many deletions
assert(!areEqual("a", "a/"))

PS: всего несколько заметок на самом коде:

Вывод типа Scala достаточно хорош, чтобы вы могли отбрасывать типы в частичной функции внутри вашей foldLeft
Nil - это идиоматический способ ссылаться на случай с пустым списком

Бонус:

У меня было что-то похожее на решение Тима, прежде чем реализовать мою идею, но я начал рано с шаблона соответствия только для символов, и это не очень хорошо, потому что в некоторых случаях требуется количество обратных пространств. В конце концов, я думаю, что более простой способ написать это сочетание соответствия шаблонов и условий. Ниже мое более длинное оригинальное решение, которое я дал выше, было реорганизованным латератором:

def areEqual(s1: String, s2: String) = {
    @tailrec
    def recSol(c1: Cursor, c2: Cursor): Boolean = (c1.char, c2.char) match {
        case ('/',  '/') => recSol(c1.next, c2.next)
        case ('/' ,   _) => recSol(c1.next, c2     )
        case (_   , '/') => recSol(c1     , c2.next)
        case ('#' , '#') => true
        case (a   ,   b) if (a == b) => recSol(c1.next, c2.next)
        case _           => false
    }
    recSol(Cursor(s1, s1.length - 1), Cursor(s2, s2.length - 1))
}

private case class Cursor(s: String, index: Int) {
    val char = if (index < 0) '#' else s(index)
    def next = {
      @tailrec
      def recSol(index: Int, backspaces: Int): Cursor = {
          if      (index < 0      ) Cursor(s, index)
          else if (s(index) == '/') recSol(index - 1, backspaces + 1)
          else if (backspaces  > 1) recSol(index - 1, backspaces - 1)
          else                      Cursor(s, index - 1)
      }
      recSol(index, 0)
    }
}

Ответ 2

Этот код занимает время O (N) и ему требуется только три целых числа дополнительного пространства:

def solution(a: String, b: String): Boolean = {

  def findNext(str: String, pos: Int): Int = {
    @annotation.tailrec
    def rec(pos: Int, backspaces: Int): Int = {
      if (pos == 0) -1
      else {
        val c = str(pos - 1)
        if (c == '/') rec(pos - 1, backspaces + 1)
        else if (backspaces > 0) rec(pos - 1, backspaces - 1)
        else pos - 1
      }
    }
    rec(pos, 0)
  }

  @annotation.tailrec 
  def rec(aPos: Int, bPos: Int): Boolean = {
    val ap = findNext(a, aPos)
    val bp = findNext(b, bPos)
    (ap < 0 && bp < 0) ||
    (ap >= 0 && bp >= 0 && (a(ap) == b(bp)) && rec(ap, bp))
  }

  rec(a.size, b.size)
}

Проблема может быть решена в линейном времени с постоянным дополнительным пространством: если вы сканируете справа налево, вы можете быть уверены, что / -symbols слева от текущей позиции не может влиять на уже обработанные символы (справа от текущее положение), поэтому нет необходимости их хранить. В каждом пункте вам нужно знать только две вещи:

Где вы находитесь в строке?
Сколько символов вы должны выбросить из-за обратных пространств

Это делает два целых числа для хранения позиций и еще одно целое число для временного хранения количества накопленных findNext пространств во время вызова findNext. Это всего три целых количества служебных данных.

Интуиция

Вот моя попытка сформулировать, почему сканирование справа налево дает вам алгоритм O (1):

Будущее не может повлиять на прошлое, поэтому нет необходимости помнить о будущем.

"Естественное время" в этой проблеме протекает слева направо. Поэтому, если вы просматриваете справа налево, вы перемещаетесь "из будущего в прошлое", и поэтому вам не нужно запоминать символы справа от вашей текущей позиции.

тесты

Вот рандомизированный тест, который делает меня довольно уверенным, что решение действительно правильно:

val rng = new util.Random(0)
def insertBackspaces(s: String): String = {
  val n = s.size
  val insPos = rng.nextInt(n)
  val (pref, suff) = s.splitAt(insPos)
  val c = ('a' + rng.nextInt(26)).toChar
  pref + c + "/" + suff
}

def prependBackspaces(s: String): String = {
  "/" * rng.nextInt(4) + s
}

def addBackspaces(s: String): String = {
  var res = s
  for (i <- 0 until 8) 
    res = insertBackspaces(res)
  prependBackspaces(res)
}

for (i <- 1 until 1000) {
  val s = "hello, world"
  val t = "another string"

  val s1 = addBackspaces(s)
  val s2 = addBackspaces(s)
  val t1 = addBackspaces(t)
  val t2 = addBackspaces(t)

  assert(solution(s1, s2))
  assert(solution(t1, t2))
  assert(!solution(s1, t1))
  assert(!solution(s1, t2))
  assert(!solution(s2, t1))
  assert(!solution(s2, t2))

  if (i % 100 == 0) {
    println(s"Examples:\n$s1\n$s2\n$t1\n$t2")
  }
}

Несколько примеров, которые генерирует тест:

Examples:
/helly/t/oj/m/, wd/oi/g/x/rld
///e/helx/lc/rg//f/o, wosq//rld
/anotl/p/hhm//ere/t/ strih/nc/g
anotx/hb/er sw/p/tw/l/rip/j/ng
Examples:
//o/a/hellom/, i/wh/oe/q/b/rld
///hpj//est//ldb//y/lok/, world
///q/gd/h//anothi/k/eq/rk/ string
///ac/notherli// stri/ig//ina/n/g
Examples:
//hnn//ello, t/wl/oxnh///o/rld
//helfo//u/le/o, wna//ova//rld
//anolq/l//twl//her n/strinhx//g
/anol/tj/hq/er swi//trrq//d/ing
Examples:
//hy/epe//lx/lo, wr/v/t/orlc/d
f/hk/elv/jj//lz/o,wr// world
/anoto/ho/mfh///eg/r strinbm//g
///ap/b/notk/l/her sm/tq/w/rio/ng
Examples:
///hsm/y//eu/llof/n/, worlq/j/d
///gx//helf/i/lo, wt/g/orn/lq/d
///az/e/notm/hkh//er sm/tb/rio/ng
//b/aen//nother v/sthg/m//riv/ng

Кажется, все работает нормально. Итак, я бы сказал, что Google-парень не испортился, выглядит как совершенно правильный вопрос.

Ответ 3

Если целью является минимальная занимаемая площадь памяти, трудно возразить против итераторов.

def areSame(a :String, b :String) :Boolean = {
  def getNext(ci :Iterator[Char], ignore :Int = 0) : Option[Char] =
    if (ci.hasNext) {
      val c = ci.next()
      if (c == '/')        getNext(ci, ignore+1)
      else if (ignore > 0) getNext(ci, ignore-1)
      else                 Some(c)
    } else None

  val ari = a.reverseIterator
  val bri = b.reverseIterator
  1 to a.length.max(b.length) forall(_ => getNext(ari) == getNext(bri))
}

С другой стороны, при споре с руководителями FP трудно защищать итераторы, поскольку они все касаются поддержания состояния.

Ответ 4

Вот версия с единственной рекурсивной функцией и без дополнительных классов или библиотек. Это линейное время и постоянная память.

def compare(a: String, b: String): Boolean = {
  @tailrec
  def loop(aIndex: Int, aDeletes: Int, bIndex: Int, bDeletes: Int): Boolean = {
    val aVal = if (aIndex < 0) None else Some(a(aIndex))
    val bVal = if (bIndex < 0) None else Some(b(bIndex))

    if (aVal.contains('/')) {
      loop(aIndex - 1, aDeletes + 1, bIndex, bDeletes)
    } else if (aDeletes > 0) {
      loop(aIndex - 1, aDeletes - 1, bIndex, bDeletes)
    } else if (bVal.contains('/')) {
      loop(aIndex, 0, bIndex - 1, bDeletes + 1)
    } else if (bDeletes > 0) {
      loop(aIndex, 0, bIndex - 1, bDeletes - 1)
    } else {
      aVal == bVal && (aVal.isEmpty || loop(aIndex - 1, 0, bIndex - 1, 0))
    }
  }

  loop(a.length - 1, 0, b.length - 1, 0)
}