Как решить задачу с минимальным использованием памяти?

Question

[Александр Буки]

Готовлюсь к собесу в яндекс, помогите плз решить задачу.
Знаю только js, поэтому пишу на node js.

Задача:
Даны k отсортированных в порядке неубывания массивов неотрицательных целых чисел, каждое из которых не превосходит 100. Требуется построить результат их слияния: отсортированный в порядке неубывания массив, содержащий все элементы исходных k массивов.

Длина каждого массива не превосходит 10 ⋅ k.

Постарайтесь, чтобы решение работало за время k ⋅ log(k) ⋅ n, если считать, что входные массивы имеют длину n.

Формат ввода
Первая строка входного файла содержит единственное число k, k ≤ 1024.

Каждая из следующих k строк описывает по одному массиву. Первое число каждой строки равняется длине соответствующего массива, оставшиеся числа этой строки описывают значения элементов этого же массива. Элементы массивов являются неотрицательными целыми числами и не превосходят 100.

Формат вывода
Выходной файл должен содержать отсортированный в порядке неубывания массив, содержащий все элементы исходных массивов.

Пример
Ввод
4
6 2 26 64 88 96 96
4 8 20 65 86
7 1 4 16 42 58 61 69
1 84

Вывод
1 2 4 8 16 20 26 42
58 61 64 65 69 84 86
88 96 96

Мое решение падает на тестах из-за ограничения по памяти.

const readline = require('readline')
const fs = require('fs')
const path = require('path')
const rl = readline.createInterface({
  input: fs.createReadStream(path.join(__dirname, '/input.txt'))
})
let arr
const array = new Array(101)
rl.once('line', () => {
  rl.on('line', (line) => {
    arr = line.split(' ')
    for (let i = 1; i < arr[0] + 1; i++) {
      if (array[arr[i]]) {
        array[arr[i]] = array[arr[i]] + ' ' + arr[i]
      } else {
        array[arr[i]] = arr[i]
      }
    }
  })
    .on('close', () => {
      for (const val of array) {
        if (val) {
          process.stdout.write(val + ' ')
        }
      }
    })
})

Comments

[RAX7]

https://www.geeksforgeeks.org/merge-k-sorted-arrays/

Answer 1

[dollar]

Как решить задачу? Самому.

Дело в том, что подсказанное решение имеет примерно в 10 раз меньше эффективность обучения. То есть подсказанный вариант вы вряд ли запомните, даже если он будет простым и понятным, и позже не сможете применить в аналогичной ситуации. Нужно, чтобы вы именно сами нашли решение, тогда будет польза.

Ну а если это ваше реальное тестовое задание на собеседовании, чтобы пройти его, то как бы вообще без комментариев.

Answer 2

[Дмитрий Беляев]

Готовлюсь к собесу в яндекс

Рано Вам в Яндекс... задачка то уровня школьных олимпиад...

Постарайтесь, чтобы решение работало за время k ⋅ log(k) ⋅ n

А это точно задачка для Яндекса? Она решается за линейное время O(k ⋅ n) если чуть-чуть вникнуть в условия, а логарифмическое решение годно лишь для людей с ЕГЭ головного мозга, там как раз любят решения в стиле "слить все в 1 массив и отсортировать", при использовании qsort/merge-sort как раз будет O(k ⋅ log(k) ⋅ n)

Если читать из файла по 2 байта, то можно значительно сэкономить память, для формата 1- и 2-значные числа разделенные пробелом этого более чем достаточно.
Так же выходной массив можно не формировать, а сразу отдавать его на выход.
P.S. гуглите сортировку подсчетом, а решать задачу за Вас на тостере никто не будет

Comments

[Александр Буки]

Рано Вам в Яндекс... задачка то уровня школьных олимпиад...

в Яндекс-такси конечно же)

[Александр Буки]

Если читать из файла по 2 байта, то можно значительно сэкономить память, для формата 1- и 2-значные числа разделенные пробелом этого более чем достаточно.

Где можно почитать как это делается в node js?
В документации не получилось разобраться(

[Дмитрий Беляев]

Александр Буки, это в апи стримов:
Вполне можно читать стрим условно синхронно после события readable с помощью метода read, он же и позволяет читать определенное количество байт

[Александр Буки]

Дмитрий Беляев, я попробовал так. Теперь пишет, что ответ не правильный, строки идентичны с ожидаемым результатом

const buf = Buffer.allocUnsafe(1000)
let pos = 0
const fs = require('fs')
const path = require('path')

const fd = path.join(__dirname, '/input.txt')
var fp = fs.openSync(fd, 'r')

fs.read(fp, buf, 0, 4, pos, function (err, bytesRead, buff) {
  if (err) return
  const stringsAmount = buff.toString('utf8')
    .split('\n')[0]
  pos += stringsAmount.length + 1
  const length = stringsAmount * 10
  readNextChunk()
  const array = []
  function readNextChunk () {
    fs.read(fp, buf, 0, length, pos,
      function (err) {
        if (err) throw err
        const arrstr = buf.toString('utf8').split('\n')[0]
        const arr = arrstr.split(' ')
        for (let i = 1; i < arr.length; i++) {
          if (array[arr[i]]) {
            array[arr[i]]++
          } else {
            array[arr[i]] = 1
          }
        }
        pos += arrstr.length + 1
        if (pos <= stringsAmount * 15) {
          readNextChunk()
        } else {
          for (let i = 0; i < 101; i++) {
            if (array[i]) {
              for (let j = 0; j < array[i]; j++) {
                process.stdout.write(i.toString() + ' ')
              }
            }
          }
        }
      })
  }
})

[Александр Буки]

Дмитрий Беляев, нашел ошибку в предидущем комментарии