1. 1C / Говнокод #8128

    −153

    1. 1
    2. 2
    3. 3
    4. 4
    5. 5
    6. 6
    Итак, у вас есть два стека с ограничением на размер - N. Стеки поддерживают операции push, pop, top.
    pop пустого стека, как и push заполненного стека вызывает соответствующее исключение.
    Необходимо из этих двух стеков смоделировать стек с таким же размером, но с дополнительным свойством -\
    push заполненного стека вызывает затирание последнего элемента стека, push(41,[1,2,3]) -> [41,1,2] ,\
    где N=3.
    Время пошло. Язык программирования любой.

    Да, это не говнокод, но 90% кандидатов не могут ее решить. (Наверное, потому, что язык собеседования - 1С)

    Запостил: alexoy, 08 Октября 2011

    Комментарии (78) RSS

    • Напоминаю, ассимптотика операций у нового стека, как и у любого уважающего себя стека, должна быть O(1)
      Ответить
    • Обычный циклический буфер, на первом курсе пишут реализацию. К чему это здесь, мне не понятно. Минусую.
      Ответить
      • К тому, что нет никаких массивов, только два стека.
        Ответить
        • Да, невнимательно прочитал. Тогда задача - ещё более унылое бесполезное говно.
          Ответить
    • алехуй, ты входишь в эти 90%? не переживай, собеседование пройти мы тебе не поможем. (:
      Ответить
      • Прошел, давно прошел. Через 24 часа выложу честное решение, а может и раньше, если не увижу правильных мыслей.
        Ответить
        • >Через 24 часа выложу честное решение
          гугл в помощь. за 24 часа успеешь. (:

          >а может и раньше
          если не успеешь нагуглить раньше, то мы заминусуем (:

          >если не увижу правильных мыслей
          телепат в треде! живой и не в отпуске! (:
          Ответить
        • > Через 24 часа выложу
          Гм, что-то мне ursus вспомнился...
          Ответить
          • Да. (: В конце будет эпикфейл. Тред утонет в минусах и алексуй ничего не выложит
            Ответить
    • не код, а надуманная задача, не имеющая практического применения - минус.

      а решение - с помощью второго буфера "копируем" pop-pop-pop,push-push-push элементы туда-обратно, имитируя операцию shift, затем последний push.
      Ответить
      • Константное время исполнения налицо. Плюс
        Ответить
      • Нет, это не O(1).
        Автор хочет, чтобы мы это решили за O(1).
        Я вот не могу, например. Только это, скорее, не я не прошёл собеседование, а тот, кто задал задачу не прошёл собеседование у меня, потому что за O(1) тут нихуя не решается одними только pop и push.
        Ответить
        • Вообще-то у этой задачи есть решение даже когда элементы стека - произвольные объекты, но оно очень неочевидное.
          Ответить
          • Представь, я сделал стек через массив длины ЭН, каким хуем ты сдвинешь все элементы массива за O(1)?
            Ответить
        • O(1)? по-моему, меньше, чем за О(n) не выйдет одними pop и push
          Ответить
        • разве что, в обратном порядке, и толкнуть новый элемент в другой стек, а поток из первого толкать вслед за ним пока толкается...на нормальный порядок нужно толкать обратно
          Ответить
          • Можно сделать, кстати, но только на один раз.
            Хранить внутри два стека. Второй отличается от первого отсутствием элемента на дне. Когда первый переполняется, возвращать ссылку на второй.
            Ответить
            • если бы тут были стеки-очереди, т.е. с операциями shift-unshift - то хватило бы пары операций. а так, чисто извращение
              Ответить
            • Тоже хотел сказать. +1 (:
              Ответить
            • Есть идея на N-раз: делать push (и, соответственно, pop) в стеки по-очереди. Нужно трэкать размеры моделируемого стэка и очерёдность помещения/удаления элементов. Но при переполнении обоих стэков нужно будет делать O(N) операций, чтобы привести стэк к нормальному виду.
              Ответить
              • полагаю, особенность стека в том, что мы никогда не знаем его размер, в данном случае - только исключения дают сигнал о переполнении или пустоте
                Ответить
                • не нужно полагать, лучше спросить топикстартера. (:
                  Автор, ответь.
                  Ответить
                  • вспомнилась ситуация с Zilog Z-80, где был только указатель стека, а дно - типа бесконечное, т.е. бесконечный push или pop гарантированно может затереть все (или половину) содержимое оперативной памяти ))
                    Ответить
          • то что ты описываешь, смахивает на зиппер - http://en.wikipedia.org/wiki/Zipper_%28data_structure%29
            Ответить
    • На с++ через итераторы есть доступ к любому элементу стека. Решается за О(1) без второго стека. (:
      Ответить
      • а если только 2 стека и только push\pop?
        Ответить
        • >затирание последнего элемента стека
          Под последним элементом стека подразумевается последний засунутый в стек элемент? Это легко за О(1) (:
          алексуй, ответь. (:
          Ответить
          • За О(1) и без дополнительного стека. Естественно, последний - тот, который выходит последним.
            Ответить
          • дан же пример
            Ответить
            • Туплю. :(:
              Ответить
              • Не, не туплю. На картинки сторона с затираемыми элементами не видна. Можно трактовать неоднозначно. (:
                Ответить
                • ну как же, был стек 1,2,3, втолкнули 41 - стал 41, 1, 2, тройка со дна стека вытолкнулась.
                  Ответить
                  • > тройка со дна стека вытолкнулась.
                    а может с вершины?
                    Предыдущих шагов не показывали и конкретно сторону со дном не указывали. пока это лишь ваши домыслы. (:
                    Ответить
    • В любом случае решается за O(1), если N<=1. (:
      Ответить
    • Если бы работодатель предложил мне решать такие задачи на собеседовании, я бы послал его на хер. Если у них принято писать заумные воркараунды вместо прямого элегантного быстрого решения - жить в IT-индустрии им осталось недолго.
      Ответить
      • Я с вами согласен, но в субботу вечером перед сном можно и поломать немного голову. (:
        Ответить
        • Тогда мне кажется перспективной идея использовать стеки поочерёдно. Не вижу только, как бороться с энтропией для случая произвольного N. Для N=3 вроде можно умудриться реализовать за O(1).
          Ответить
      • вы не представляете (а может и представляете )) ), как много руководителей убеждены, что хороший программист - это у кого в голове хороший компилятор, выдающий все ворнинги, а сам этот программист способен писать хитровыебанный непонятный код.
        Ответить
    • Что-то вы какие-то зацикленные на этих push pop.
      Ответить
      • стоп, а что значит операция top?
        Ответить
      • нашел только так, как предложил я:
        Реализация на двух стеках
        Очередь может быть построена из двух стеков S1 и S2 как показано ниже:
        Процедура enqueue(x):
            S1.push(x)
        
        Процедура dequeue():
            если S2 пуст:
                если S1 пуст:
                    сообщить об ошибке: очередь пуста
        
                пока S1 не пуст:
                    S2.push(S1.pop())
        
            return S2.pop()
        Ответить
    • лень
      Ответить
    • А через очередь и стек вы бы смогли это сделать?
      Ответить
    • ага, и через деку тоже :)
      Ответить
      • А очередь через стек и одну единственную переменную сделать сможете?
        Ответить
        • Нет. Зато могу сделать очередь через отвёртку и кожуру от банана.
          Ответить
      • а лучше комбинированный -- стек-очередь )
        Ответить
    • Я вообще человеческий язык не воспринимаю, похоже. Искренне не могу понять смысла предложения "необходимо из этих двух стеков смоделировать стек с таким же размером", как ни силюсь.
      Ответить
      • Как же вы понимаете пожелания пользователей ваших программ? :)
        Ответить
        • Обычно я не общаюсь с пользователями насчёт кода, всё что их заботит это интерфейсы.

          Теперь понял. Я в отношении программирования думаю чисто по-английски, русский сразу в ступор вводит, особенно когда просят из "2 стеков сделать 1"
          Ответить
          • >Теперь понял. русский сразу в ступор вводит
            Не, автор темы по русски тоже не разговаривает. Ваш когнитивный диссонанс нам понятен.
            Ответить
      • Я поясню:
        http://www.educaltai.ru/files/photo/1320276.jpg
        Ответить
      • stack1 + stack2 = stack3
        len(stack3) = len(stack1) + len(stack2)
        Ответить
    • Сговняли совсем говнокод блеать!
      Алехой, теперь выложите: Программа Хеллоу Ворлд! На ассемблере. Жду решений. Если за сутки не увижу правильных мыслей - дам ответ.
      Ответить
    • last in — first out
      1) S0[1,2,3], S1[];
      2) S0[3], S1[2,1];
      3) S0[], S1[2,1] ;
      4) S0[1,2], S1[];
      5) S0[4,1,2], S1[];
      Ответить
    • Во что скатился Говнокод! Может ещё кошечек постить будем? (В комментариях предвижу толпу ASCII-арта).
      Ответить
      • Пока что обойдёмся лошадками.
        Ответить
      • >Может ещё кошечек постить будем?
        Не вопрос. Легко:
        http://www.sunhome.ru/UsersGallery/052006/4122656.jpg
        Ответить
        • RS-232Govno
          Ответить
          • Да ерунда. До сих пор иногда пользуюсь. Он хоть и старый, но своё отрабатывает.
            Ответить
            • USB 3.0 — уже пора, можно.
              Ответить
              • Это все навороты от лукавого. Они не всегда нужны. Некоторые вещи с RS делать проще. Некоторые с USB даже не возможны, например связь на большие расстояния. USB же не дальше 2х метров. Да схемотехника c USB сложнее. RS-232 с самым дешёвым 2ухжильным проводом может бить на 15 км, если его уметь готовить (достаточно два очень простых преобразователя и без промежуточных усилителей\повторителей).

                ps: я не извращенец.
                ппс: знаю, что на дворе уже 20тый век.

                Интернет?
                Не. Не слышал.
                Ответить
                • >Интернет? Не. Не слышал.
                  iTelepathist?
                  Ответить
                • > 20тый век.
                  ORLY?
                  Ответить
                  • Ну а какой еще?

                    В 21м веке компы на рассоянии 15 километров соединяют через Инетнет обычно, а то и через оптику тонкую и желтую.
                    Ответить
                • Да и программировать его проще
                  Ответить
    • Поясните мысль.
      Ответить

    Добавить комментарий