谷歌的一个编程面试问题

大家好！希望你们喜欢解决上周的挑战。如果你们还没看过，我会附上上周文章的链接，方便你们查看。

Coderbyte 上的挑战文章

以下是解决上周挑战的流行方法：

双指数方法：

一个更优化的解决方案（由于数字字符串已排序，因此可行）涉及在两个字符串的开头初始化两个索引。检查第一个字符串中索引处的元素是否等于、小于或大于第二个字符串中索引处的元素。如果相等，则将值推送到结果数组。由于字符串已排序，如果第一个字符串中的元素小于第二个字符串中的元素，则可以肯定第一个元素不存在于第二个字符串中。因此，您可以增加第一个索引以查看下一个值。如果第一个字符串中的元素大于第二个字符串中的元素，则可以肯定第二个字符串中的值不存在于第一个字符串中，并且可以增加第二个索引以查看下一个值。用代码来看可能更清楚！

 function intersection (arr) {
  const inBothArrays = []
  const [arr1, arr2] = arr.map((str) => str.split(', ').map((e) => parseInt(e)))

  let index1 = 0
  let index2 = 0

  while (index1 < arr1.length && index2 < arr2.length) {
    const elem1 = arr1[index1]
    const elem2 = arr2[index2]

    if (elem1 === elem2) {
      inBothArrays.push(elem1)
      index1++
      index2++
    } else if (elem1 > elem2) {
      index2++
    } else if (elem1 < elem2) {
      index1++
    }
  }

  return inBothArrays.join(',')
}

例如：

调用intersection([“3, 4, 7, 11, 15”, “1, 3, 5, 8, 11”]);你的函数应该返回“3,11”。

这里有一个例子可以更清楚地说明这一点。

记住，此解法只有在数组已排序的情况下才有效。其时间复杂度为O(n+m)。

本周的挑战：

本周，我们将解决 Google 真机面试中出现的一道编程题。记得前往Coderbyte提交你的代码！

编写一个函数，接受一个包含两个字符串的数组作为参数，每个字符串代表用逗号分隔的按键。在本题中，按键可以是可打印字符，也可以是退格键（用 表示-B）。你的函数应该判断这两个按键字符串是否等价。

你可以通过退格键删除前面的一个字符，将这样的按键字符串生成一个可打印的字符串。如果两个按键字符串生成相同的可打印字符串，则认为它们是等效的。例如：

checkEquivalentKeypresses(["a,b,c,d", "a,b,c,c,-B,d"]) // true
checkEquivalentKeypresses(["-B,-B,-B,c,c", "c,c"]) // true
checkEquivalentKeypresses(["", "a,-B,-B,a,-B,a,b,c,c,c,d"]) // false

玩得开心，你做到了！！

我们的时事通讯📫

每次发布重大功能时，我们都会发布一小段功能揭秘，以便我们的社区能够第一时间获悉我们的新动态。请在此处提供您的电子邮件地址，我们会将您添加到“第一时间知晓”列表中 :)