Трудный вопрос на собеседовании #3

Александр Скакунов
Опубликовано 16.06.2008 в Статьи

Продолжаем серию переводов цикла “Трудные вопросы на собеседовании“.

Задача #3

Как вы обернете порядок слов (не символов) в строке длиной n при постоянном объеме дополнительной памяти (constant extra space) за линейное время (linear time)?

UPDATE: ответ.

Теги: задача, собеседование

(12 голосов, средний: 2.58 из 5)

Загрузка ...

Распределение голосов

Понравилась статья? Подпишись на обновления по RSS/E-mail

Все комментарии (40) к “Трудный вопрос на собеседовании #3”

Раковець Олександр 16.06.2008 в 12:27
Я б виділяв по слову з початку та кінця рядка, а тоді міняв їх місцями через додаткову пам’ять. І так, до зустрічі вказівників у середині рядка.
Хоча, я не до кінця зрозумів обмеження constant extra space.
mstar 16.06.2008 в 13:39
pregsplit на слова и реверс массива слов.

На счет памяти тоже не понял, что имелось в виду? кол-во байт и операции только с массивом символов?
Скакунов Александр 16.06.2008 в 14:15
Насколько я могу судить, “constant extra space” – расхожее понятие в области сортировки. Есть даже книжка “Constant-space string-matching“:

it [string-matching algorithm] processes the searched text with constant memory space in addition to the string
Алексей 16.06.2008 в 14:59
Пусть есть такая функция оборота части строки (псевдокод, str – строка, s – начальный индекс, e – конечный):
function reverse(str, s, e) {
for(i = s; i < e/2; i++) {
buf = str[i];
str[i] = str[e - i + 1];
str[e - i + 1] = buf;
}
}

Первым делом оборачиваем всю строку:
reverse(str, 0, n)

Затем последовательно находим границы слов (s_word, e_word) и для каждого вызываем:
reverse(str, s_word, e_word)

Вот как-то так примерно

Алексей 16.06.2008 в 15:01

Sorry за отвутствие отступов, пробую еще раз только функцию:


function reverse(str, s, e) {
  for(i = s; i < e/2; i++) {
    buf = str[i];
    str[i] = str[e - i + 1];
    str[e - i + 1] = buf;
  }
}

Алексей 16.06.2008 в 15:01
Хм… я ожидал что code сохранит форматирование
Алексей 16.06.2008 в 15:05
Да, добавлю сразу – str передается в функцию по ссылке.
the que 16.06.2008 в 16:05
ruby:
string.split.reverse.join(” “)
Скакунов Александр 16.06.2008 в 16:09
string.split.reverse.join(” “)

Прикольно
Правда, не соблюдено условие задачи – “constant extra space”, т.к. используется массив переменной длины.
serge lorich 17.06.2008 в 14:30
если используется массив той же длины что и строка, то это constant extra space?
оценка времени выполнения меня удручает
Andrey 17.06.2008 в 15:01
Перевертнуть всю строку, а потом перевернуть символы в каждом слове.

Olexiy 17.06.2008 в 16:16

C++

// Вважаємо, що слова в рядку розділяються пробілами.
void f(string& s) {
  reverse(s.begin(), s.end());
  int prev = 0;
  for (int i = 0; i < s.length(); i++)
    if (s[i] == ' ') {
      reverse(s.begin() + prev, s.begin() + i);
      prev = i;
    }
  reverse(s.begin() + prev, s.end());
}

Olexiy 17.06.2008 в 16:23

Упс, все-таки треба тестити спочатку.

void f(string& s) {
    reverse(s.begin(), s.end());
    int prev = -1;
    for (int i = 0; i < s.length(); i++)
        if (s[i] == ' ') {
            reverse(s.begin() + prev + 1, s.begin() + i);
            prev = i;
        }

    reverse(s.begin() + prev + 1, s.end());
}

Olexiy 17.06.2008 в 16:27
>> если используется массив той же длины что и строка, то это constant extra space?

це linear extra space.
Скакунов Александр 17.06.2008 в 16:30
если используется массив той же длины что и строка, то это constant extra space?

це linear extra space

Поприветствуем Олексия Орешко, координатора TopCoder!

Олексий, могли бы вы авторитетно объяснить, что такое этот constant extra space? Ибо народ конфузится, хотя ответы пишет правильные.
Olexiy 17.06.2008 в 16:55
Константна додаткова пам’ять (constant extra space) – розмір якої не залежить від розміру вхідних даних.

Лінійна додаткова пам’ять (constant extra space) – розмір якої лінійно залежить від розміру вхідних даних.

Звичайно, всі ці визначення мають на увазі пам’ять у найгіршому для вашої програми випадку.

Простими словами. Візьмемо вхідні дані (в нашому випадку – рядок) і почнемо їх збільшувати (дописувати до рядка символи). Якщо при кожному збільшенні рядка в два рази пам’ять збільшиться вдвічі – то це лінійна залежність. Якщо не зміниться ніяк – то пам’ять константна. Аналогічно з часом виконання.
Sasha 17.06.2008 в 16:59
Спробую пояснити на пальцях про “constant extra space”.

Якщо вашій програмі для обробки вхідних даних довжиною в одну букву (1 слово з однієї букви) необхідно виділити блоки пам’яті сумарним розміром в 1 МБ але коли на вхід передали стрічку, що містить 4 Мільярди слів по 100 букв у кожному слові – програмі все ще буде достатньо цього ж 1 МБ додаткової пам’яті.

У випадку
ruby:
string.split.reverse.join(” “)

Потрібно буде виділити масив, розмір якого залежить від вхідних даних а також створити копії всіх слів в стрічці і помістити їх у цей масив. Відповідно, оцінити розмір додаткової мам’яті не знаючи розміру вхідної стрічки – неможливо.
Olexiy 17.06.2008 в 17:08
2 Саша
>>Відповідно, оцінити розмір додаткової мам’яті не знаючи розміру вхідної стрічки – неможливо.

Наскільки я зрозумів, то пам’ять має бути лінійна як мінімум (копія всього ). Хоча, з іншого боку, мова програмування може оптимізувати деякі операції.
Olexiy 17.06.2008 в 17:19
Формальне визначення константної додаткової пам’яті.
Пам’ять константна (не залежить від входу), якщо існує такий об’єм пам’яті Х, що ваша програма не потребуватиме більше Х при жодних вхідних даних.

Пам’ять лінійна, якщо існує таке число Х, що ваша програма ніколи не потребуватиме більше, ніж Х * (розмір вхідних даних).

>> Раковець Олександр
Я б виділяв по слову з початку та кінця рядка, а тоді міняв їх місцями через додаткову пам’ять.

Тут обмеження на пам’ять може бути лінійним, якщо дати на вхід одне величезне слово (рядок без пробілів). Крім того, не розкрита тема обміну місцями слів різної довжини.
Oleksiy Glib 18.06.2008 в 01:05
похоже на задачки с алгоритмической олимпиады…

Сергей 18.06.2008 в 12:24


  char* str = "Hello my dear friend . How are you ?";
  Memo1->Lines->Add(str);
  Memo1->Lines->Add("---------------------------");
  unsigned nF = 0;
  unsigned nL = 0;
  unsigned len = strlen(str);
  for(unsigned i = 0; i Lines->Add(str);

Сергей 18.06.2008 в 12:24

char* str = "Hello my dear friend . How are you ?";
  Memo1->Lines->Add(str);
  Memo1->Lines->Add("---------------------------");
  unsigned nF = 0;
  unsigned nL = 0;
  unsigned len = strlen(str);
  for(unsigned i = 0; i Lines->Add(str);

Сергей 18.06.2008 в 12:25

{
    if(str[i] == ' ')
    {
      nF = nL;
      nL = i - 1;
      reverse(str,nF,nL);
      nL +=2;
    }
  }
  reverse(str,nL,len-1);

  reverse(str,0,len-1);
  Memo1->Lines->Add(str);

Сергей 18.06.2008 в 12:26
Сорри за пост 21. 22+23 моё решение.
P.S: Непонимаю почему в один не влезает..=(
Сергей 18.06.2008 в 12:27
Хмм…цикл такой for(unsigned i = 0; i < len; ++i)…
Sasha 18.06.2008 в 13:49
2 Olexiy
>> Наскільки я зрозумів, то пам’ять має бути лінійна як мінімум (копія всього ).
Копію всього робити непотрібно, оскільки результат роботи ф-ї записується в той же масив, де були вхідні дані.

>> Мова програмування може оптимізувати деякі операції.
Оптимізувати може компілятор (а не мова програмування). Оптимізація НІКОЛИ не рообить з неправильної програми – правильну і не змінює складність алгоритму (лінійний, логарифмічний).
Компілятор може лише замінювати деякі елементарні (з точки зору мови програмування) операції на еквівалентні або ж викидати частини коду що не впливають на результат.
Olexiy 18.06.2008 в 13:57
2 Саша
>> Потрібно буде виділити масив, розмір якого залежить від вхідних даних а також створити копії всіх слів в стрічці і помістити їх у цей масив.

Наскільки я зрозумів це речення, то копії всіх слів одночасно перепишуться в масив – тобто, власне, весь вміст входу (за виключенням пробілів) буде переписано.

Щодо оптимізації – я мав на увазі, що деталі реалізації можуть суттєво відрізнятись. Крім того, якщо ми використовуємо деякі бібліотечні методи, то деталі їх реалізації, очевидно, напряму впливає на складність кінцевої програми.
raggzy 18.06.2008 в 15:30
Как я понял условие:
Есть только ваша строка, никакой дополнительной памяти (даже копии строки), кроме како-то константного (5-10) кол-ва переменных (long”ов, например) быть не может.

Таким образом, строку нельзя ни разрезать, ни вставлять в нее ничего. Можно лишь только менять 2 символа с i и j позиций.

В таком ракурсе решение:
1. Просто развернуть строку
```
for (long i = 0; i < n/2; i++) {char a=s[i]; s[i] = s[n-i-1]; s[n-i-1]=a)
```
Кому не нравится, можете вынести char a за цикл.
Всего : Один проход по строке.
2. В полученной строке поразворачивать слова.
Это реализуется с помощью двух указателей, первый – на начало слова, другой на конец. Разворот такой же, как и в пункте 1.
```
long i,j = 0;
while true
{
while ((i < n) and whitespace(s[i])) i++; // передвигаем первый в начало слова
if (i==n) break;
j=i+1;
while ((j  "milk want I" -> "milk want I"
```
raggzy 18.06.2008 в 15:34
Еще раз алгоритм, бо система делает текст по дыбильному написанным
```
long i,j = 0;
while true
{
  while ((i < n) and whitespace(s[i])) i++; // передвигаем первый в начало слова
  if (i==n) break;
  j=i+1;
  while ((j < n) and !whitespace(s[j])) j++;
  reverse(s,i,j);// разворот найденого слова
  i=j;// переход к новому слову
}
```
Всего 3 прохода по строке. (1 – пункт один, 2 и 3-в вайле, просто разворот каждого слова по сути добавляет еще один проход)
raggzy 18.06.2008 в 15:43
чуваки сорри за and, должно быть &&, привык у ся передефайнивать
raggzy 18.06.2008 в 16:06
Эх. оказуется, ее уже решили идейно в посте 11….сорри за офтоп
Olexiy 18.06.2008 в 16:10
2 raggzy: Співбесіда ж на ІТ-позицію, а не на філолога – так що код потрібен
еуе 19.06.2008 в 09:45
прикол, решение сразу же было дано, но обсуждение не заканчивается, собрались звери просто рвут задачу на куски
Щетинин Сергей 19.06.2008 в 10:32
@ай,
5 баллов ))
Olexiy 19.06.2008 в 11:05
2 raggzy
У тебе, до речі, якщо рядок (після розвороту) закінчується словом, то це останнє слово буде написано ззаду наперед. Приклад: на “ab cd” видасть “cd ba”.
Olexiy 19.06.2008 в 11:23
2 Щетинин
Привіт Малюк, як життя?
Щетинин Сергей 19.06.2008 в 11:35
Привет Орех, дела хорошо, как у тебя?
aRt 19.06.2008 в 17:31
Да… помню задавал на собеседовании такую задачку )) пока что результат 50% .. правда решил ее давать только 2 челам )) обычно до нее дело не доходит..
Скакунов Александр 23.06.2008 в 14:24
Итак, правильный ответ:

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

Затем обратите порядок символов в каждом слове. Теперь буквы в словах располагаются в изначальном порядке (т.к. они были обращены два раза), но слова находятся в обратном порядке (первое слово – в конце, и т.д.)

За проявленную активность администрация developers.org.ua рада вручить футболку Олексию Орешко.
biltar 23.06.2008 в 23:53
Це буде більше ніж лінійний час, чи я помиляюся?

Украинское сообщество программистов

Трудный вопрос на собеседовании #3

Задача #3

Все комментарии (40) к “Трудный вопрос на собеседовании #3”

Оставить комментарий

Архив

Добавить статью

Популярные теги

Комментарии