Задачи с собеседований: поиск одинаковых чисел в двух строках

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

Например: если входной массив [«1, 3, 4, 7, 13», «1, 2, 4, 13, 15»], то выходная строка должна быть «1, 4, 13», потому что эти числа появляются в обеих строках.

Решения

Перебирать элементы первой строки и каждый сравнивать с каждым элементом второй. Если совпадают — прибавлять к финальной. Очевидно, что это, скорее всего, неоптимальное решение, так как в нем, в худшем случае, каждый элемент первой строки нужно будет сравнивать с каждым элементом второй строки (если нет совпадений).

function FindIntersection (strArr) {
  const inBothStrings = []
  const arr1 = strArr[0].split(', ')
  const arr2 = strArr[1].split(', ')
  arr1.forEach(elementArr1 => {
    const numArr1 = parseInt(elementArr1)
    arr2.forEach(elementArr2 => {
      const numArr2 = parseInt(elementArr2)
      if (numArr1 === numArr2) {
        inBothStrings.push(numArr1)
      }
    })
  })
  return inBothStrings.join(',')
}

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

 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(',')
}