编程面试中的Scala字符串相等性问题 [英] Scala String Equality Question from Programming Interview

问题描述

由于我喜欢使用Scala进行编程，因此在接受Google采访时，我要求他们给我一个Scala/函数式编程风格的问题.我得到的Scala功能样式问题如下:

Since I liked programming in Scala, for my Google interview, I asked them to give me a Scala / functional programming style question. The Scala functional style question that I got was as follows:

您有两个由字母字符和代表退格符号的特殊字符组成的字符串.我们将此退格字符称为"/".到达键盘时，您将键入此字符序列，包括退格/删除字符.您要实现的解决方案必须检查两个字符序列是否产生相同的输出.例如，"abc"，"aa/bc". "abb/c"，"abcc/"，"/abc"和"//abc"都产生相同的输出"abc".因为这是一个Scala/函数式编程问题，所以您必须以惯用的Scala样式实现您的解决方案.

You have two strings consisting of alphabetic characters as well as a special character representing the backspace symbol. Let's call this backspace character '/'. When you get to the keyboard, you type this sequence of characters, including the backspace/delete character. The solution you are to implement must check if the two sequences of characters produce the same output. For example, "abc", "aa/bc". "abb/c", "abcc/", "/abc", and "//abc" all produce the same output, "abc". Because this is a Scala / functional programming question, you must implement your solution in idiomatic Scala style.

我编写了以下代码(它可能与我写的不完全一样，我只是要消耗内存).基本上，我只是线性地遍历字符串，将字符放在列表之前，然后比较列表.

I wrote the following code (it might not be exactly what I wrote, I'm just going off memory). Basically I just go linearly through the string, prepending characters to a list, and then I compare the lists.

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"一词).

So far so good? He then asked for the time complexity and I responded linear time (because you have to process each character once) and linear space (because you have to copy each element into a list). Then he asked me to do it in linear time, but with constant space. I couldn't think of a way to do it that was purely functional. He said to try using a function in the Scala collections library like "zip" or "map" (I explicitly remember him saying the word "zip").

这是东西.我认为，在没有任何可变状态或副作用的情况下，在恒定的空间中进行此操作实际上是不可能的.就像我认为他搞砸了这个问题.你怎么认为?

Here's the thing. I think that it's physically impossible to do it in constant space without having any mutable state or side effects. Like I think that he messed up the question. What do you think?

您可以在线性时间内但空间不变的情况下求解它吗?

Can you solve it in linear time, but with constant space?

推荐答案

此代码花费O(N)时间，仅需要三个整数的额外空间:

This code takes O(N) time and needs only three integers of extra space:

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

可以在线性时间内以恒定的额外空间解决问题:如果从右向左扫描，则可以确保当前位置左侧的/符号不会影响已经处理的符号(到当前位置的右侧)，因此无需存储它们. 在每一点上，您只需要知道两件事:

The problem can be solved in linear time with constant extra space: if you scan from right to left, then you can be sure that the /-symbols to the left of the current position cannot influence the already processed symbols (to the right of the current position) in any way, so there is no need to store them. At every point, you need to know only two things:

1. 您在字符串中的什么位置?
2. 由于退格，您必须丢弃多少个符号

这使得两个整数用于存储位置，另一个整数用于临时存储在findNext调用期间累积的退格键的数量.这总共是三个整数的空间开销.

That makes two integers for storing the positions, and one additional integer for temporary storing the number of accumulated backspaces during the findNext invocation. That's a total of three integers of space overhead.

直觉

这是我尝试说明从右向左扫描为您提供O(1)算法的原因:

Here is my attempt to formulate why the right-to-left scan gives you a O(1) algorithm:

未来不能影响过去，因此无需记住未来.

此问题中的自然时间"从左到右流动.因此，如果您从右向左扫描，则意味着从未来到过去"，因此您无需记住当前位置右侧的字符.

The "natural time" in this problem flows from left to right. Therefore, if you scan from right to left, you are moving "from the future into the past", and therefore you don't need to remember the characters to the right of your current position.

测试

这是一个随机测试，这使我非常确定该解决方案实际上是正确的:

Here is a randomized test, which makes me pretty sure that the solution is actually correct:

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-guy并没有搞砸，看起来是一个非常有效的问题.

Seems to work just fine. So, I'd say that the Google-guy did not mess up, looks like a perfectly valid question.

这篇关于编程面试中的Scala字符串相等性问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！