Нашли или выдавили из себя код, который нельзя назвать нормальным,
на который без улыбки не взглянешь?
Не торопитесь его удалять или рефакторить, — запостите его на
говнокод.ру, посмеёмся вместе!
Итак, у вас есть два стека с ограничением на размер - N. Стеки поддерживают операции push, pop, top.
pop пустого стека, как и push заполненного стека вызывает соответствующее исключение.
Необходимо из этих двух стеков смоделировать стек с таким же размером, но с дополнительным свойством -\
push заполненного стека вызывает затирание последнего элемента стека, push(41,[1,2,3]) -> [41,1,2] ,\
где N=3.
Время пошло. Язык программирования любой.
Да, это не говнокод, но 90% кандидатов не могут ее решить. (Наверное, потому, что язык собеседования - 1С)
Нет, это не O(1).
Автор хочет, чтобы мы это решили за O(1).
Я вот не могу, например. Только это, скорее, не я не прошёл собеседование, а тот, кто задал задачу не прошёл собеседование у меня, потому что за O(1) тут нихуя не решается одними только pop и push.
разве что, в обратном порядке, и толкнуть новый элемент в другой стек, а поток из первого толкать вслед за ним пока толкается...на нормальный порядок нужно толкать обратно
Можно сделать, кстати, но только на один раз.
Хранить внутри два стека. Второй отличается от первого отсутствием элемента на дне. Когда первый переполняется, возвращать ссылку на второй.
Есть идея на N-раз: делать push (и, соответственно, pop) в стеки по-очереди. Нужно трэкать размеры моделируемого стэка и очерёдность помещения/удаления элементов. Но при переполнении обоих стэков нужно будет делать O(N) операций, чтобы привести стэк к нормальному виду.
вспомнилась ситуация с Zilog Z-80, где был только указатель стека, а дно - типа бесконечное, т.е. бесконечный push или pop гарантированно может затереть все (или половину) содержимое оперативной памяти ))
>затирание последнего элемента стека
Под последним элементом стека подразумевается последний засунутый в стек элемент? Это легко за О(1) (:
алексуй, ответь. (:
> тройка со дна стека вытолкнулась.
а может с вершины?
Предыдущих шагов не показывали и конкретно сторону со дном не указывали. пока это лишь ваши домыслы. (:
Если бы работодатель предложил мне решать такие задачи на собеседовании, я бы послал его на хер. Если у них принято писать заумные воркараунды вместо прямого элегантного быстрого решения - жить в IT-индустрии им осталось недолго.
Тогда мне кажется перспективной идея использовать стеки поочерёдно. Не вижу только, как бороться с энтропией для случая произвольного N. Для N=3 вроде можно умудриться реализовать за O(1).
вы не представляете (а может и представляете )) ), как много руководителей убеждены, что хороший программист - это у кого в голове хороший компилятор, выдающий все ворнинги, а сам этот программист способен писать хитровыебанный непонятный код.
Реализация на двух стеках
Очередь может быть построена из двух стеков S1 и S2 как показано ниже:
Процедура enqueue(x):
S1.push(x)
Процедура dequeue():
если S2 пуст:
если S1 пуст:
сообщить об ошибке: очередь пуста
пока S1 не пуст:
S2.push(S1.pop())
return S2.pop()
Я вообще человеческий язык не воспринимаю, похоже. Искренне не могу понять смысла предложения "необходимо из этих двух стеков смоделировать стек с таким же размером", как ни силюсь.
Сговняли совсем говнокод блеать!
Алехой, теперь выложите: Программа Хеллоу Ворлд! На ассемблере. Жду решений. Если за сутки не увижу правильных мыслей - дам ответ.
Это все навороты от лукавого. Они не всегда нужны. Некоторые вещи с RS делать проще. Некоторые с USB даже не возможны, например связь на большие расстояния. USB же не дальше 2х метров. Да схемотехника c USB сложнее. RS-232 с самым дешёвым 2ухжильным проводом может бить на 15 км, если его уметь готовить (достаточно два очень простых преобразователя и без промежуточных усилителей\повторителей).
ps: я не извращенец.
ппс: знаю, что на дворе уже 20тый век.
гугл в помощь. за 24 часа успеешь. (:
>а может и раньше
если не успеешь нагуглить раньше, то мы заминусуем (:
>если не увижу правильных мыслей
телепат в треде! живой и не в отпуске! (:
Гм, что-то мне ursus вспомнился...
а решение - с помощью второго буфера "копируем" pop-pop-pop,push-push-push элементы туда-обратно, имитируя операцию shift, затем последний push.
Автор хочет, чтобы мы это решили за O(1).
Я вот не могу, например. Только это, скорее, не я не прошёл собеседование, а тот, кто задал задачу не прошёл собеседование у меня, потому что за O(1) тут нихуя не решается одними только pop и push.
Хранить внутри два стека. Второй отличается от первого отсутствием элемента на дне. Когда первый переполняется, возвращать ссылку на второй.
Автор, ответь.
Под последним элементом стека подразумевается последний засунутый в стек элемент? Это легко за О(1) (:
алексуй, ответь. (:
http://caricatura.ru/parad/lock/pic/4027.jpg
а может с вершины?
Предыдущих шагов не показывали и конкретно сторону со дном не указывали. пока это лишь ваши домыслы. (:
Теперь понял. Я в отношении программирования думаю чисто по-английски, русский сразу в ступор вводит, особенно когда просят из "2 стеков сделать 1"
Не, автор темы по русски тоже не разговаривает. Ваш когнитивный диссонанс нам понятен.
len(stack3) = len(stack1) + len(stack2)
Алехой, теперь выложите: Программа Хеллоу Ворлд! На ассемблере. Жду решений. Если за сутки не увижу правильных мыслей - дам ответ.
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[];
Не вопрос. Легко:
ps: я не извращенец.
ппс: знаю, что на дворе уже 20тый век.
Интернет?
Не. Не слышал.
iTelepathist?
ORLY?
В 21м веке компы на рассоянии 15 километров соединяют через Инетнет обычно, а то и через оптику тонкую и желтую.