Гайд Задачи с собеседований в Яндекс (которые я почему-то запомнил) #1: URLify

[sn0wyQ]

Давно меня не было в больших гонках... А тут такая идея для целой серии топиков!

Задача:
На вход дана строка. Требуется в ней все пробелы заменить на "%20". Например строка "купить кряк скита бесплатно" должна превратиться в строку "купить%20кряк%20скита%20бесплатно".
Сложность заключается в следующем: можно использовать только O(1) дополнительной памяти и сложность алгоритма должна быть O(N), где N - количество символов в строке.
(Чуть более простым языком - можно резервировать только фиксированное количество памяти [грубо говоря нельзя создавать вторую строку] и время выполнения алгоритма должно линейно зависеть от N [грубо говоря можно использовать не более kN операций для любого N, где k это фиксированное число {не зависит от N}])

Надеюсь прежде чем переходить к решению вы всё же хоть немного пошевелите остатками извилин...

Спойлер: Решение

Сначала пройдемся по строке и посчитаем общее количество пробелов. Так же заметим, что в итоговой строке каждый НЕ пробельный символ сдвинется относительно начальной позиции на 2*колво_пробелов_до_него символов вправо. Запишем тогда в переменную СМЕЩЕНИЕ 2*колво_пробелов и будем идти по символам строки справа налево и если текущий символ НЕ пробел, то перемещать его на СМЕЩЕНИЕ позиций вправо, иначе, если символ пробел, будем уменьшать СМЕЩЕНИЕ на 2 и в через СМЕЩЕНИЕ символов правее поменяем нужные символы на соответсвенно '%', '2" и '0'.

Спойлер: Код решения (C++)

void Urlify(std::string* str) {
  int offset = std::count(str->begin(), str->end(), ' ') * 2;
  str->resize(str->length() + offset);
  for (int index = str->length() - offset - 1; index >= 0; --index) {
    if (str->at(index) == ' ') {
      offset -= 2;
      str->at(index + offset) = '%';
      str->at(index + offset + 1) = '2';
      str->at(index + offset + 2) = '0';
    } else {
      str->at(index + offset) = str->at(index);
    }
  }
}

Надо вообще такое продолжать или не надо (если что это легкая задача относительно других)?

 

[familytrapper]

Давно меня не было в больших гонках... А тут такая идея для целой серии топиков!

Задача:
На вход дана строка. Требуется в ней все пробелы заменить на "%20". Например строка "купить кряк скита бесплатно" должна превратиться в строку "купить%20кряк%20скита%20бесплатно".
Сложность заключается в следующем: можно использовать только O(1) дополнительной памяти и сложность алгоритма должна быть O(N), где N - количество символов в строке.
(Чуть более простым языком - можно резервировать только фиксированное количество памяти [грубо говоря нельзя создавать вторую строку] и время выполнения алгоритма должно линейно зависеть от N [грубо говоря можно использовать не более kN операций для любого N, где k это фиксированное число {не зависит от N}])

Надеюсь прежде чем переходить к решению вы всё же хоть немного пошевелите остатками извилин...

Спойлер: Решение

Сначала пройдемся по строке и посчитаем общее количество пробелов. Так же заметим, что в итоговой строке каждый НЕ пробельный символ сдвинется относительно начальной позиции на 2*колво_пробелов_до_него символов вправо. Запишем тогда в переменную СМЕЩЕНИЕ 2*колво_пробелов и будем идти по символам строки справа налево и если текущий символ НЕ пробел, то перемещать его на СМЕЩЕНИЕ позиций вправо, иначе, если символ пробел, будем уменьшать СМЕЩЕНИЕ на 2 и в через СМЕЩЕНИЕ символов правее поменяем нужные символы на соответсвенно '%', '2" и '0'.

Спойлер: Код решения (C++)

void Urlify(std::string* str) {
  int offset = std::count(str->begin(), str->end(), ' ') * 2;
  str->resize(str->length() + offset);
  for (int index = str->length() - offset - 1; index >= 0; --index) {
    if (str->at(index) == ' ') {
      offset -= 2;
      str->at(index + offset) = '%';
      str->at(index + offset + 1) = '2';
      str->at(index + offset + 2) = '0';
    } else {
      str->at(index + offset) = str->at(index);
    }
  }
}

Надо вообще такое продолжать или не надо (если что это легкая задача относительно других)?

да, конечно

 

[weflown]

Спойлер: Решение на Golang

package main

import (
    "fmt"
    "strings"
)

func main() {
    fmt.Println(strings.Replace("кряк скита скачать бесплатно", " ", "%20", -1))
}

Я внатуре не уверен насчёт O-complexity, но щит.

Продолжай

 

[sn0wyQ]

Спойлер: Решение на Golang

package main

import (
    "fmt"
    "strings"
)

func main() {
    fmt.Println(strings.Replace("кряк скита скачать бесплатно", " ", "%20", -1))
}

Я внатуре не уверен насчёт O-complexity, но щит.

Продолжай

В python str.replace работает за O(n^2), в плюсах тоже. Да и впринципе основной задачей для собеседующегося тут как раз и является написание своего алгоритма (хотя зачастую предлагают написать сначала реализацию в одну строчку вроде твоей, а потом оптимизированный вариант)