Scala String Igualdad pregunta de la entrevista de programación

functional-programming scala-collections

Question

Como me gustó la programación en Scala, para mi entrevista en Google, les pedí que me dieran una pregunta sobre el estilo de programación funcional / Scala. La pregunta de estilo funcional de Scala que obtuve fue la siguiente:

Tiene dos cadenas que constan de caracteres alfabéticos, así como un carácter especial que representa el símbolo de retroceso. Llamemos a este carácter de retroceso ''/''. Cuando llega al teclado, escribe esta secuencia de caracteres, incluido el carácter de retroceso / eliminación. La solución que debe implementar debe verificar si las dos secuencias de caracteres producen el mismo resultado. Por ejemplo, "abc", "aa / bc". "abb / c", "abcc /", "/ abc" y "// abc" producen la misma salida, "abc". Debido a que esta es una pregunta de programación de Scala / funcional, debe implementar su solución en el estilo idiomático de Scala.

Escribí el siguiente código (puede que no sea exactamente lo que escribí, simplemente me estoy yendo de la memoria). Básicamente, solo voy linealmente a través de la cadena, anteponiendo los caracteres a una lista, y luego comparo las listas.

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)
}

¿Hasta ahora tan bueno? Luego pidió la complejidad del tiempo y yo respondí el tiempo lineal (porque tiene que procesar cada carácter una vez) y el espacio lineal (porque tiene que copiar cada elemento en una lista). Luego me pidió que lo hiciera en tiempo lineal, pero con espacio constante. No podía pensar en una forma de hacerlo que fuera puramente funcional. Dijo que intentara usar una función en la biblioteca de colecciones de Scala como "zip" o "map" (lo recuerdo explícitamente diciendo la palabra "zip").

Aquí está la cosa. Creo que es físicamente imposible hacerlo en un espacio constante sin tener ningún estado mutable o efectos secundarios. Como creo que él arruinó la pregunta. ¿Qué piensas?

¿Puedes resolverlo en tiempo lineal, pero con espacio constante?

Answer 1

Aquí hay una versión con una sola función recursiva y sin clases o bibliotecas adicionales. Esto es tiempo lineal y memoria constante.

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)
}

Answer 2

Este código toma tiempo O (N) y solo necesita tres enteros de espacio adicional:

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)
}

El problema se puede resolver en tiempo lineal con espacio adicional constante: si escanea de derecha a izquierda, puede estar seguro de que los símbolos / a la izquierda de la posición actual no pueden influir en los símbolos ya procesados ​​(a la derecha de la posición actual) de cualquier manera, por lo que no hay necesidad de almacenarlos. En cada punto, solo necesitas saber dos cosas:

1. ¿Dónde estás en la cadena?
2. ¿Cuántos símbolos tienes que tirar debido a los espacios en blanco?

Eso hace dos enteros para almacenar las posiciones, y un entero adicional para almacenar temporalmente el número de backspaces acumulados durante la invocación findNext . Eso es un total de tres enteros de sobrecarga de espacio.

Intuición

Aquí está mi intento de formular por qué el escaneo de derecha a izquierda le da un algoritmo O (1):

El futuro no puede influir en el pasado, por lo tanto, no hay necesidad de recordar el futuro.

El "tiempo natural" en este problema fluye de izquierda a derecha. Por lo tanto, si escanea de derecha a izquierda, se está moviendo "del futuro al pasado" y, por lo tanto, no necesita recordar los caracteres a la derecha de su posición actual.

Pruebas

Aquí hay una prueba aleatoria, lo que me hace bastante seguro de que la solución es realmente correcta:

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")
  }
}

Algunos ejemplos que genera la prueba:

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

Parece funcionar bien. Por lo tanto, diría que el chico de Google no se equivocó, parece una pregunta perfectamente válida.

Answer 3

No tienes que crear la salida para encontrar la respuesta. Puede iterar las dos secuencias al mismo tiempo y detenerse en la primera diferencia. Si no encuentra ninguna diferencia y ambas secuencias terminan al mismo tiempo, son iguales, de lo contrario son diferentes.

Pero ahora considere secuencias como esta: aaaa/// para comparar con a . Debe consumir 6 elementos de la secuencia izquierda y un elemento de la secuencia correcta antes de poder afirmar que son iguales. Eso significa que necesitaría mantener al menos 5 elementos en la memoria hasta que pueda verificar que todos se eliminaron. ¿Pero qué pasa si iteras elementos del final? Entonces solo deberá contar el número de espacios de retroceso y luego ignorar tantos elementos como sea necesario en la secuencia de la izquierda sin tener que guardarlos en la memoria, ya que sabe que no estarán presentes en la salida final. Puede alcanzar la memoria O(1) usando estos dos consejos.

Lo probé y parece funcionar:

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)
}

Algunas pruebas (todas pasan, déjeme saber si tiene más casos de borde en mente):

// 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/"))

PD: sólo unas pocas notas sobre el propio código:

• La inferencia de tipo Scala es lo suficientemente buena como para que pueda eliminar tipos en la función parcial dentro de su foldLeft
• Nil es la forma idiomática de referirse al caso de la lista vacía

Prima:

Tenía en mente algo como la solución de Tim antes de implementar mi idea, pero comencé temprano con la coincidencia de patrones solo en los caracteres y no encajaba bien porque algunos casos requieren la cantidad de espacios de retroceso. Al final, creo que una forma más ordenada de escribirlo es una combinación de coincidencia de patrones y condiciones. A continuación se encuentra mi solución original más larga, la que di arriba fue refaccionada a tiempo:

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)
    }
}

Answer 4

Si el objetivo es una huella de memoria mínima, es difícil discutir contra los iteradores.

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))
}

Por otro lado, cuando se discute con los directores de PF, es difícil defender a los iteradores, ya que se trata de mantener el estado.