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

// Максимальное количество последовательных единиц

// Дан массив nums содержащий только 0 (нули) и 1 (единицы),
// и целое число k. Верните максимальное количество последовательных
// единиц в массиве, если вы можете заменить не более k нулей на единицы.

// Пример 1:
// nums = [1,1,1,0,0, 0, 1,1,1,1, 0], k = 2
// Ответ: 6
// Замена: [1,1,1,0,0,<1>,1,1,1,1,<1>]
// ---------------
// Выделенные скобками (< >) числа были заменены с 0 на 1.
// Самый длинный подмассив подчеркнут.

// Пример 2:
// nums = [0,0,1,1 ,0, 0, 1,1,1, 0, 1,1,0,0,0,1,1,1,1], k = 3
// nums = [0,1,1,1 ,1, 1, 1,1,1, 0, 1,1,0,0,0,1,1,1,1]
// Ответ: 10
// Объяснение: [0,0,1,1,<1>,<1>,1,1,1,<1>,1,1,0,0,0,1,1,1,1]
// -------------------------
// Выделенные скобками (< >) числа были заменены с 0 на 1.
// Самый длинный подмассив подчеркнут.

// Ограничения:
// 1 <= nums.length <= 105
// nums[i] = 0 или 1.
// 0 <= k <= nums.length

Мой код (не завершен и не работает):

#include <stdio.h>

#define MAX_NUMBER_COUNT 105

int get_max_one_sequences(int nums[], int length, int k) {
    int i, start_index, current_count, max_count;
    if (!nums || length <= 0 || k < 0 || k >= length) return 0;
    if (length > MAX_NUMBER_COUNT) return 0;
    max_count = 0;
    current_count = -1;
    start_index = -1;
    for (i = 0; i < length; i++) {
        if (nums[i] == 1) {
            if (current_count < 0) { start_index = i; }
            current_count++;
        } else {
            if (max_count < current_count) { max_count = current_count; }
            current_count = -1;
        }
    }
    return max_count;
}

void print_array(int nums[], int length) {
    int i;
    if (!nums || length <= 0) return;
    for (i = 0; i < length; i++) {
        printf(i > 0 ? ", %d" : "%d", nums[i]);
    }
    putchar('\n');
}

#define ANSWER 6

int nums[] = { 1,1,1,0,0, 0, 1,1,1,1, 0 };

/**********************************************************************
1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0
k = 2
Result: 3 (must be: 6)
**********************************************************************/
int main(int argc, char *argv[]) {
    int length, k;
    k = 2;
    length = sizeof(nums) / sizeof(nums[0]);
    print_array(nums, length);
    printf("k = %d\n", k);
    printf("Result: %d (must be: %d)\n",
        get_max_one_sequences(nums, length, k), ANSWER);
    return 0;
}

смотри, тебе нужно заменить k последовательных нулей, без разрыва. в том смысле, что между ними могут быть единички, но не другие нолики.

заменяешь первые k ноликов единичками. Смотришь, какая длина получилась. А потом двигаешься вправо. Если встретил новый нолик, то должен первый нолик (самый левый) вернуть обратно в ноль. текущая длина — разница текущей позиции и позиции нолика.
А еже ли встретил единичку, то просто увеличиваешь значение текущей длины.

задача просто на аккуратную реализацию. какой-то сложный алгоритм не нужен.

Если умными словами, то это задача на два указателя — начало и конец подпоследовательности. нужно их продвигать вперед так, чтобы между ними было не больше k ноликов.

Здравствуйте, apachik, Вы писали:

A>смотри, тебе нужно заменить k последовательных нулей, без разрыва. в том смысле, что между ними могут быть единички, но не другие нолики.

A>заменяешь первые k ноликов единичками. Смотришь, какая длина получилась. А потом двигаешься вправо. Если встретил новый нолик, то должен первый нолик (самый левый) вернуть обратно в ноль. текущая длина — разница текущей позиции и позиции нолика.
A>А еже ли встретил единичку, то просто увеличиваешь значение текущей длины.

A>задача просто на аккуратную реализацию. какой-то сложный алгоритм не нужен.

A>Если умными словами, то это задача на два указателя — начало и конец подпоследовательности. нужно их продвигать вперед так, чтобы между ними было не больше k ноликов.

Здравствуйте, apachik, Вы писали:

A>задача просто на аккуратную реализацию. какой-то сложный алгоритм не нужен.
A>Если умными словами, то это задача на два указателя — начало и конец подпоследовательности. нужно их продвигать вперед так, чтобы между ними было не больше k ноликов.

Общую идею понял, спасибо, но как в данном случае подсчитать значение max_length (последовательность единиц на текущей итерации)? Не могу сообразить... Можно на примере?

nums[] = [0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0], k = 2

1. [<1>, <1>, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0] max_length = ???
2. [0, <1>, <1>, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0]
...
N-1. [0, 0, 0, 1, 1, 0, 0, 0, 0, 1, <1>, <1>, 0]
N. [0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, <1>, <1>]

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

В любом случае не представляю, как такое можно решить в режиме лайвкодинга, за 15-20 минут (а ожидали примерно такое время, раз дали задачу в самом конце).

Сама вакансия — ничего примечательного, обычный энтерпрайз на Java с вилкой ниже среднерыночной (в ВК у меня сейчас в 2 раза выше их максимума):

Младший backend-разработчик
от 80 000 до 120 000 ₽ за месяц, на руки

Обязанности

Разработка backend (приложений и микросервисов) по заданным спецификациям — описаниям API в Postman и описаниям логики работы.
Доработка, поддержка и оптимизация существующих приложений.
Участие в развитии продуктов: от обсуждения задач до запуска их в production.

Требования

Базовые знания одного из языков программирования — Python, Java, C#, PHP, Ruby, Go или JavaScript. У нас есть микросервисы почти на всех этих языках.
Понимание принципов ООП и паттернов проектирования.
Желателен базовый опыт работы с любым MVC-фреймворком.
Понимание принципов клиент-серверного взаимодействия, знание протокола HTTP и стандарта REST.
Знание языка запросов SQL, опыт с MySQL или PostgreSQL.
Приветствуется опыт работы с Git и Docker.
Желательно понимание принципов SOLID и чистой архитектуры.
Ответственное и внимательное отношение к задачам, аккуратность.
Базовое знание английского языка, умение читать технические тексты.

https://spb.hh.ru/vacancy/118348961

Они ждут, что гений вроде Криса Касперски пойдет лепить круды за 80 тысяч? Есть, конечно, бомжи-олимпиадники вроде Юрия Лазарева, но это товар штучный, и рассчитывать на подобные кадры довольно недальновидно.

Здравствуйте, Worminator X, Вы писали:

Нужно на каждой итерации подсчитывать единицы после последнего заменного нуля? Все равно тогда понадобится 2-й цикл, и будет квадратичная сложность.

nums[] = [0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0], k = 2

1. [<1>, <1>, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0] max_length = 2
2. [0, <1>, <1>, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0] max_length = 4
3. [0, 0, <1>, 1, 1, <1>, 0, 0, 0, 1, 0, 0, 0] max_length = 4
...
N-2. [0, 0, 0, 1, 1, 0, 0, 0, <1>, 1, <1>, 0, 0] max_length = 3
N-1. [0, 0, 0, 1, 1, 0, 0, 0, 0, 1, <1>, <1>, 0] max_length = 3
N. [0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, <1>, <1>] max_length = 2

Здравствуйте, Worminator X, Вы писали:


WX>Нужно на каждой итерации подсчитывать единицы после последнего заменного нуля? Все равно тогда понадобится 2-й цикл, и будет квадратичная сложность.

Количество нулей и единиц ты и так знаешь: хранишь в переменных, inc/dec при движении одного из указателей.
Оба указателя условно проходят весь массив -> 2N ~= O(N)

WX>В любом случае не представляю, как такое можно решить в режиме лайвкодинга, за 15-20 минут (а ожидали примерно такое время, раз дали задачу в самом конце).

возможно, такой код будет проще для понимания и реализации (я не запускал, мог ошибиться где-то на +-1):

def longestOnes(nums, k):
    left = 0
    max_len = 0
    zeros = 0

    while True:
        max_len = max(max_len, right - left + 1)
        if right == len(num):
            break
        if num[right] == 1:
            right += 1
            continue
        if num[right] == 0 and zeros < k:
            right += 1
            zeros += 1
            continue  
        if num[left] == 1:
            left += 1
            continue
        if num[left] == 0:
            left += 1
            zeros -= 1
            continue
    max_len = max(max_len, right - left + 1)

    return max_len

если дошли до конца, то конец
если можем подвинуть правый указатель без штрафа, то двигаем
если можем подвинуть со штрафом и лимит не исчерпали, то тоже двигаем
если ничего из верхнего не сработало, то приходится двигать левый указатель, возвращая штрафы

Здравствуйте, Worminator X, Вы писали:

WX>Помогите с решением задачи с собеседования.
WX>Тупил полчаса, время вышло, но так и не смог придумать подходящий алгоритм.
WX>Предположительно здесь нужны знания из дискретной математики, возможно, что-то связанное с комбинаторикой.
WX>Я пытался составить массив из последовательностей единиц, и затем для каждой последовательности перебирать всевозможные цепочки с заменой нулей.
WX>Но это ушло в кучу кода, квадратичную сложность и совершенно очевидно не было тем решением, на которое отводилось несколько минут.
WX>Принимаются любые идеи.

http://coliru.stacked-crooked.com/a/2b0e72cffb1f1060

#include <algorithm>
#include <iostream>
#include <ranges>

template <typename T>
concept Range = std::ranges::sized_range<T>
and std::same_as<std::ranges::range_value_t<T>, int>;

void print_range(const Range auto& range) {
   std::cout << "{";
   const char* delimiter = "";
   for (const int value : range) {
      std::cout << delimiter << value;
      delimiter = ", ";
   }
   std::cout << "}" << std::endl;
}

size_t get_max_one_sequences(const Range auto& range, size_t max_zero_count) {
   const auto find_zero = [&](auto iterator) {return std::find(iterator, std::end(range), 0); };
   const auto find_sequence_end = [&](auto iterator) {
      for (size_t n = max_zero_count; n and iterator != std::end(range); --n) {
         iterator = find_zero(std::next(iterator));
      }
      return iterator;
   };
   auto sequence_begin = std::begin(range);
   auto nearest_zero = find_zero(sequence_begin);
   auto sequence_end = find_sequence_end(nearest_zero);
   size_t max_sequence_length = size_t(std::distance(sequence_begin, sequence_end));

   while (sequence_end != std::end(range)) {
      sequence_begin = std::next(nearest_zero);
      nearest_zero = find_zero(sequence_begin);
      sequence_end = find_zero(std::next(sequence_end));
      const size_t sequence_length = size_t(std::distance(sequence_begin, sequence_end));
      if (max_sequence_length < sequence_length) {
         max_sequence_length = sequence_length;
      }
   }
   return max_sequence_length;
}

int main() {
   {  /**********************************************************************
      1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0
      k = 2
      Result: 6
      **********************************************************************/
      const int nums[] = { 1,1,1,0,0, 0, 1,1,1,1, 0 };
      const size_t k = 2;
      print_range(nums);
      std::cout << get_max_one_sequences(nums, k) << std::endl;
   }
   {  /**********************************************************************
      0,0,1,1 ,0, 0, 1,1,1, 0, 1,1,0,0,0,1,1,1,1
      k = 3
      Result: 10
      **********************************************************************/
      const int nums[] = { 0,0,1,1 ,0, 0, 1,1,1, 0, 1,1,0,0,0,1,1,1,1 };
      const size_t k = 3;
      print_range(nums);
      std::cout << get_max_one_sequences(nums, k) << std::endl;
   }
}

Здравствуйте, Worminator X, Вы писали:

WX>Максимальное количество последовательных единиц

WX>Дан массив nums содержащий только 0 (нули) и 1 (единицы),
WX>и целое число k. Верните максимальное количество последовательных
WX>единиц в массиве, если вы можете заменить не более k нулей на единицы.

Конфеты есть за собеседуемых — дело так себе, неблагодарное.

Пусть для пары индексов i,j, таких, что 0 <= i <= j <= N = len(nums)
подмассив nums[i:j] (полуоткрытый интервал, nums[i], nums[i+1], ..., nums[j-1])
содержит ровно z нулей, так, что z <= k.

Это инвариант нашего цикла.

Двигаешь в цикле правую границу j и хорошенько думаешь, что при этом происходит со счётчиком z и что нужно сделать с левой границей i.

Очевидно, что алгоритм линейный, потому что обе границы движутся строго вправо, — правая ровно N раз, а левая как повезёт, но не более N-k раз.

Здравствуйте, Worminator X, Вы писали:

WX>Помогите с решением задачи с собеседования.
WX>Тупил полчаса, время вышло, но так и не смог придумать подходящий алгоритм.
WX>Предположительно здесь нужны знания из дискретной математики, возможно, что-то связанное с комбинаторикой.

// Максимальное количество последовательных единиц

// Дан массив nums содержащий только 0 (нули) и 1 (единицы),
// и целое число k. Верните максимальное количество последовательных
// единиц в массиве, если вы можете заменить не более k нулей на единицы.

Тут всё просто как палка.
У тебя есть левая и правая границы.

1) Ставишь обе границы на нулевой индекс.
2) Двигаешь правую границу вправо, пока число нулей в интервале не станет k+1.
Это твой первый интервал (левая граница, правая граница-1).
3) Далее двигаешь левую границу до тех пор, пока лишний ноль не выйдет из интервала.
4) Далее двигаешь правую, пока не дойдёшь до следующего нуля.
Это твой очередной интервал (левая граница, правая граница-1).
5) Повторяешь пункты 3 и 4 пока массив не кончится.