Здравствуйте, jhfrek, Вы писали:
J>PS. Смотрите какой у нас длинный тред получился, всего лишь про список для которого есть "общепринятая терминология в структурах данных" Оно вам надо на собеседовании обсуждать АТД и историю их становления? Может проще подробно сформулировать задачу на то, что вам хочется проверить?
Конечно же повторять тред на собеседовании нет возможности. Но если я хочу узнать, что человек подразумевает под списком и умеет ли пользоваться абстракцией — то нет, не проще.
J>Тем более что если человек не интересовался лиспом или хаскелем, то он и не будет знать про ваш набор операций. Или это заведомо плохие программисты которые вам не нужны?
Вовсе не нужно интересоваться лиспом и хаскелем что бы знать о стандартных операциях над списком. Для этого достаточно лишь знать что список это абстракция, и что типичной реализацией этой асбтракции является односвязный список, который часто и называют просто "списком", опуская односвязность. Лично я об этом узнал из книги для детей типа "Паскаль в картинках" (точное название не помню).
Re[26]: PS. Задача на собеседовании - обращение списка.
On 13.02.2013 12:57, samius wrote:
> Лично я об этом узнал из книги для детей типа > "Паскаль в картинках" (точное название не помню).
И почему я предполагал оное?
Posted via RSDN NNTP Server 2.1 beta
Re[27]: PS. Задача на собеседовании - обращение списка.
Здравствуйте, Vzhyk, Вы писали:
V>On 13.02.2013 12:57, samius wrote:
>> Лично я об этом узнал из книги для детей типа >> "Паскаль в картинках" (точное название не помню). V>И почему я предполагал оное?
Это риторический вопрос, или мне на него нужно ответить?
Re[28]: PS. Задача на собеседовании - обращение списка.
Здравствуйте, samius, Вы писали:
J>>то что в этой книжке нет базового набора операций, и определения базового набора нет S>Базовые операции над списком являются частью определения списка по Хоару. Вы смотрите на определение списка Хоара и видите в нем операции. И это в той самой книжке.
в русском издании не нашел
J>>а кого волнует ваше отношение? Я вам привел в рамках "общепринятой терминологии в структурах данных" три варианта набора операций. Пошлете претендента за то что он учился по Кнуту, а не по Хоору? S>У Кнута представление списка соответствует определению Хоара. Кстати, посмотрел бы я, как бы вы разворачивали список, данный в терминах Вирта (Open, Write, Read, Reset). Что-то мне кажется что код будет не сильно далек от моего.
разумеется
S>Нет, не послал бы. Посмотрел бы, что человек понимает под списком, и как бы взялся его разворачивать. Естественно без обращения к библиотечной функции разворота контейнера.
то есть все таки посмотрели бы, а не "я бы подумал, что интервьюер не знаком с общепринятой терминологией в структурах данных."
J>>исключительно если вы проводите теоретические изыскания, а не реальные программы пишите S>Я пишу реальные программы и ваш аргумент про файл неуместен. Редкий программист станет копировать файл для реализации функции tail для списка, реализованного на файле. Я бы такого точно не взял. Кстати, работа с последовательными файлами отлично ложится на концепцию списка Хоара.
правильно, он вообще обойдется без операции tail, если ее реализация требует копирования на данной операционной системе
S>>>1 — я удовлетворял ваше любопытство о том как реализовать разворот на операциях, определенных для абстрактного списка. Причем тут Паблик, казалось бы? J>>вы завалили собеседование, не написав ответ на задание данное с применением "общепринятой терминологии в структурах данных", а список я и без вас умею переворачивать S>Код, который я привел — он для вас, а не для собеседования. И если бы умели — не утверждали бы трижды что это невозможно.
и продолжу утверждать — написать код нужный Паблику при помощи ваших операций невозможно.
J>>не могли бы вы пройти по ссылке, которую я вам дал и почитать реплики Паблика? Если их окажеться недостаточно, посмотреть на ответы Паблика на другие похожие решения. Реализацию переворота на основе "базовых" операций вы первый привели. S>По ссылке, которую вы дали нет реплик Паблика. Искать ответы Паблика на похожие решения мне лень.
то есть ваше утверждение "И если бы умели — не утверждали бы трижды что это невозможно" основано на вашей лени... прискорбно
S>>>3 — указанное мной решение в общем случае не нуждается в дополнительной памяти на копию списка. J>>для сферического компилятора работающего на сферической операционке в вакууме S>Ну почему же? Конкретно на C++ под виндовсом без вакуума такой код сможет работать без дополнительной памяти.
а для ЕС ЭВМ с данными на магнитной ленте?
Re[26]: PS. Задача на собеседовании - обращение списка.
Здравствуйте, samius, Вы писали:
J>>PS. Смотрите какой у нас длинный тред получился, всего лишь про список для которого есть "общепринятая терминология в структурах данных" Оно вам надо на собеседовании обсуждать АТД и историю их становления? Может проще подробно сформулировать задачу на то, что вам хочется проверить? S>Конечно же повторять тред на собеседовании нет возможности. Но если я хочу узнать, что человек подразумевает под списком и умеет ли пользоваться абстракцией — то нет, не проще.
массив Кнутовской машины с числом на I месте и индексом следующего элемента на I+1 месте. Знаю реализацию операций Вставить, Найти, Следущий, Удалить, Отсортировать, Перевернуть. Я прошел собеседование?
J>>Тем более что если человек не интересовался лиспом или хаскелем, то он и не будет знать про ваш набор операций. Или это заведомо плохие программисты которые вам не нужны? S>Вовсе не нужно интересоваться лиспом и хаскелем что бы знать о стандартных операциях над списком. Для этого достаточно лишь знать что список это абстракция, и что типичной реализацией этой асбтракции является односвязный список, который часто и называют просто "списком", опуская односвязность. Лично я об этом узнал из книги для детей типа "Паскаль в картинках" (точное название не помню).
а я из Вирта, у которого другой набор операций. Что нам с этим делать...
А в какой такой книжке по Паскалю определяют операции tail, head и cons?
Re[27]: Задача на собеседовании - обращение списка.
Здравствуйте, jhfrek, Вы писали:
J>Здравствуйте, samius, Вы писали:
S>>Базовые операции над списком являются частью определения списка по Хоару. Вы смотрите на определение списка Хоара и видите в нем операции. И это в той самой книжке.
J>в русском издании не нашел
Я думал что определение в русской википедии взято из этой книги. Разве нет?
S>>Нет, не послал бы. Посмотрел бы, что человек понимает под списком, и как бы взялся его разворачивать. Естественно без обращения к библиотечной функции разворота контейнера.
J>то есть все таки посмотрели бы, а не "я бы подумал, что интервьюер не знаком с общепринятой терминологией в структурах данных."
Не вижу противоречия. Посмотрел бы и подумал бы.
S>>Я пишу реальные программы и ваш аргумент про файл неуместен. Редкий программист станет копировать файл для реализации функции tail для списка, реализованного на файле. Я бы такого точно не взял. Кстати, работа с последовательными файлами отлично ложится на концепцию списка Хоара.
J>правильно, он вообще обойдется без операции tail, если ее реализация требует копирования на данной операционной системе
А я вообще не пойму, откуда взялось требования копирования файла и на какой операционной системе. Пролейте свет, плиз.
S>>Код, который я привел — он для вас, а не для собеседования. И если бы умели — не утверждали бы трижды что это невозможно.
J>и продолжу утверждать — написать код нужный Паблику при помощи ваших операций невозможно.
может все-таки дадите ссылку на критерии Паблика? Глядя на стартовое сообщение топика я не вижу критериев, которые бы нарушал мой код.
S>>По ссылке, которую вы дали нет реплик Паблика. Искать ответы Паблика на похожие решения мне лень.
J>то есть ваше утверждение "И если бы умели — не утверждали бы трижды что это невозможно" основано на вашей лени... прискорбно
Нет, они основаны на ваших утверждениях вроде "Ну и, увы и ах, без знания внутреннего устройства вы задачу топикстартера не решите" в то время как я задачу считаю решенной, а вы отказываетесь приводить требования, которых я не вижу в стартовом посте.
S>>Ну почему же? Конкретно на C++ под виндовсом без вакуума такой код сможет работать без дополнительной памяти.
J>а для ЕС ЭВМ с данными на магнитной ленте?
А что принципиально меняет лента по отношению к микросхеме кроме времени доступа?
Re[27]: PS. Задача на собеседовании - обращение списка.
Здравствуйте, jhfrek, Вы писали:
J>Здравствуйте, samius, Вы писали:
S>>Конечно же повторять тред на собеседовании нет возможности. Но если я хочу узнать, что человек подразумевает под списком и умеет ли пользоваться абстракцией — то нет, не проще.
J>массив Кнутовской машины с числом на I месте и индексом следующего элемента на I+1 месте. Знаю реализацию операций Вставить, Найти, Следущий, Удалить, Отсортировать, Перевернуть. Я прошел собеседование?
В моем собеседовании более одного вопроса. На этот вы не ответили.
Представленный вами перечень операций неполон и выразить обращение списка (как и само определение списка) через него не выйдет. Ограничиваясь данными операциями вы даже перевернуть массив не сможете, кроме как вызвать операцию Массив.Перевернуть(). Что, в общем-то не повод зачитывать ответ.
J>а я из Вирта, у которого другой набор операций. Что нам с этим делать...
Может быть переходить к следующему вопросу, если они останутся.
J>А в какой такой книжке по Паскалю определяют операции tail, head и cons?
Помню лишь что желтая обложка, куча картинок, освещен сам язык, некоторые структуры данных и работа с ними, помню что был парсер арифметических выражений на основе обратной польской нотации. Как конкретно назывались операции — не помню, но за head/tail практически уверен. cons — х.з.
Re[28]: PS. Задача на собеседовании - обращение списка.
Здравствуйте, samius, Вы писали:
S>>>Конечно же повторять тред на собеседовании нет возможности. Но если я хочу узнать, что человек подразумевает под списком и умеет ли пользоваться абстракцией — то нет, не проще. J>>массив Кнутовской машины с числом на I месте и индексом следующего элемента на I+1 месте. Знаю реализацию операций Вставить, Найти, Следущий, Удалить, Отсортировать, Перевернуть. Я прошел собеседование? S>В моем собеседовании более одного вопроса. На этот вы не ответили. S>Представленный вами перечень операций неполон и выразить обращение списка (как и само определение списка) через него не выйдет. Ограничиваясь данными операциями вы даже перевернуть массив не сможете, кроме как вызвать операцию Массив.Перевернуть(). Что, в общем-то не повод зачитывать ответ.
нда... прискорбно что вы проводите собеседования, не зная как реализовать все эти операции на банальном массиве и полагая что я должен ограничиваться этими операциями. У массива есть доступ к элементам, этого достаточно что бы реализовать любые операции.
J>>а я из Вирта, у которого другой набор операций. Что нам с этим делать... S>Может быть переходить к следующему вопросу, если они останутся.
не, в компанию где программисты думают что у типа есть только список базовых операций из книжки с желтой обложкой и где они не способны реализовать сам тип, лучше не устраиваться. Так что следующего вопроса не будет
J>>А в какой такой книжке по Паскалю определяют операции tail, head и cons? S>Помню лишь что желтая обложка, куча картинок, освещен сам язык, некоторые структуры данных и работа с ними, помню что был парсер арифметических выражений на основе обратной польской нотации. Как конкретно назывались операции — не помню, но за head/tail практически уверен. cons — х.з.
печалька, человек обучавшийся программированию по книге для детей с желтой обложкой типа "Паскаль в картинках" завалил человека обучавшемуся программированию по Кнуту.
Вот она цена самоуверенности и лени при формулировании задач
Re[28]: Задача на собеседовании - обращение списка.
Здравствуйте, samius, Вы писали:
S>>>Базовые операции над списком являются частью определения списка по Хоару. Вы смотрите на определение списка Хоара и видите в нем операции. И это в той самой книжке. J>>в русском издании не нашел S>Я думал что определение в русской википедии взято из этой книги. Разве нет?
нет
S>>>Код, который я привел — он для вас, а не для собеседования. И если бы умели — не утверждали бы трижды что это невозможно. J>>и продолжу утверждать — написать код нужный Паблику при помощи ваших операций невозможно. S>может все-таки дадите ссылку на критерии Паблика? Глядя на стартовое сообщение топика я не вижу критериев, которые бы нарушал мой код.
а откуда взялись критерии? Он не озвучивал критериев, он так же как и вы полагал что список — это очевидная и однозначная вещь. Вот только однозначность оказалась не однозначной. И мое собеседование вы не прошли, не смотря на все заверения о необходимости для кандидата уточнять задачу, сами вы уточнять ничего не стали — кинулись писать код на основе своих представлений о списке.
S>Нет, они основаны на ваших утверждениях вроде "Ну и, увы и ах, без знания внутреннего устройства вы задачу топикстартера не решите" в то время как я задачу считаю решенной, а вы отказываетесь приводить требования, которых я не вижу в стартовом посте.
задача топикстартера была не перевернуть список, а перевернуть список состоящий из рекордов со ссылками. Это же список приведен и в википедии на картинке — http://en.wikipedia.org/wiki/List_(computing)
J>>а для ЕС ЭВМ с данными на магнитной ленте? S>А что принципиально меняет лента по отношению к микросхеме кроме времени доступа?
действительно, устройство с последовательным доступом и устройство с произвольным доступом, какие между ними могут быть принципиальные различия
Как вы возьмете tail от файла на ленте?
Re[29]: PS. Задача на собеседовании - обращение списка.
Здравствуйте, jhfrek, Вы писали:
J>Здравствуйте, samius, Вы писали:
S>>Представленный вами перечень операций неполон и выразить обращение списка (как и само определение списка) через него не выйдет. Ограничиваясь данными операциями вы даже перевернуть массив не сможете, кроме как вызвать операцию Массив.Перевернуть(). Что, в общем-то не повод зачитывать ответ.
J>нда... прискорбно что вы проводите собеседования, не зная как реализовать все эти операции на банальном массиве и полагая что я должен ограничиваться этими операциями. У массива есть доступ к элементам, этого достаточно что бы реализовать любые операции.
С разворотом массива через прямой доступ к элементам — это вы ошиблись топиком. Здесь пытаются развернуть список.
S>>Может быть переходить к следующему вопросу, если они останутся.
J>не, в компанию где программисты думают что у типа есть только список базовых операций из книжки с желтой обложкой и где они не способны реализовать сам тип, лучше не устраиваться. Так что следующего вопроса не будет
Нашим проще
S>>Помню лишь что желтая обложка, куча картинок, освещен сам язык, некоторые структуры данных и работа с ними, помню что был парсер арифметических выражений на основе обратной польской нотации. Как конкретно назывались операции — не помню, но за head/tail практически уверен. cons — х.з.
J>печалька, человек обучавшийся программированию по книге для детей с желтой обложкой типа "Паскаль в картинках" завалил человека обучавшемуся программированию по Кнуту.
Запылился у вас Кнут, мхом порос. Сдуйте пыль, стряхните мох, откройте первый том в районе раздела 2.2. Там увидите что список (линейный список у Кнута) это абстракция последовательности с условие на предшествование элементов друг другу. Далее рассматриваются различные способы реализации (последовательное распределение, связанное распределение, циклические списки, дважды связанные списки и многомерные массивы).
К сожалению, Кнут не рассматривает базовый набор операций над списками (в смысле минимальный полный набор), а просто указывает что с линейными списками могут выполняться следующие операции... И далее 9 операций в том числе не тривиальных (разбиение, слияние, сортировка, поиск). Но и операции "перевернуть" среди них нет. А то что вы можете перевернуть на собеседовании массив — это ваши личные успехи, которые вряд ли заинтересуют хоть какого-нибудь собеседователя.
J>Вот она цена самоуверенности и лени при формулировании задач
Да, отличный результат. Вас сдуло после первого вопроса, даже HR-ам не придется звонить вам с сообщением об отказе.
Re[29]: Задача на собеседовании - обращение списка.
Здравствуйте, jhfrek, Вы писали:
J>Здравствуйте, samius, Вы писали:
S>>Я думал что определение в русской википедии взято из этой книги. Разве нет?
J>нет
Ну тогда, пардон муа, отсылаю к желтой книжке про паскаль
S>>может все-таки дадите ссылку на критерии Паблика? Глядя на стартовое сообщение топика я не вижу критериев, которые бы нарушал мой код.
J>а откуда взялись критерии? Он не озвучивал критериев, он так же как и вы полагал что список — это очевидная и однозначная вещь.
Т.е. критерии вы за топикстартера выдумали? Ну что, поздравляю, хороший ход. Проблема лишь в том, что топикстартер продемонстрировал увлечение (как минимум) функциональными языками и в частности Haskell-ем, потому ваши предположения о том что он предполагал что список — это очевидная и однозначная вещь — это всего лишь ваши предположения. Мои предположения: ваши предположения далеки от действительности.
J>Вот только однозначность оказалась не однозначной. И мое собеседование вы не прошли, не смотря на все заверения о необходимости для кандидата уточнять задачу, сами вы уточнять ничего не стали — кинулись писать код на основе своих представлений о списке.
А, так это я у вас собеседование проходил? Извините, вам показалось. Я вам пытался разжевать кое-что, а не узнать, угадал ли я ваш правильный ответ.
S>>Нет, они основаны на ваших утверждениях вроде "Ну и, увы и ах, без знания внутреннего устройства вы задачу топикстартера не решите" в то время как я задачу считаю решенной, а вы отказываетесь приводить требования, которых я не вижу в стартовом посте.
J>задача топикстартера была не перевернуть список, а перевернуть список состоящий из рекордов со ссылками. Это же список приведен и в википедии на картинке — http://en.wikipedia.org/wiki/List_(computing)
Раз уж вы ссылаетесь на картинку в википедии в данной статье, то не сочтите за труд и прочитайте первый абзац о том что такое список (хинт: абстракция). Но да, таки один из наиболее частых способов реализации списка — односвязный список. Частый, но в стандарт C++ он попал лишь в 11-ом году.
S>>А что принципиально меняет лента по отношению к микросхеме кроме времени доступа?
J>действительно, устройство с последовательным доступом и устройство с произвольным доступом, какие между ними могут быть принципиальные различия
а какие могут быть принципиальные различия между фразами "не требует дополнительной памяти с последовательным доступом" и "не требует дополнительной памяти с произвольным доступом"
J>Как вы возьмете tail от файла на ленте?
Наверное прочитаю одну очередную запись.
Вообще говоря, я не понимаю ваших проблем. Ленты не используют таким образом, как их использует Машина Тюринга. Основное назначение лент — резервное копирование и архивация данных. Даже когда мои предки работали с лентами — им не хватало ума использовать ленты в качестве оперативной памяти. Максимум — для оверлеев. Рассказать почему?
Re[30]: PS. Задача на собеседовании - обращение списка.
Здравствуйте, samius, Вы писали:
J>>нда... прискорбно что вы проводите собеседования, не зная как реализовать все эти операции на банальном массиве и полагая что я должен ограничиваться этими операциями. У массива есть доступ к элементам, этого достаточно что бы реализовать любые операции. S>С разворотом массива через прямой доступ к элементам — это вы ошиблись топиком. Здесь пытаются развернуть список.
о как, вы что и правда не читали ни Кнута, ни Вирта с Дейкстрой и не знаете что список можно реализовать при помощи массива?
J>>печалька, человек обучавшийся программированию по книге для детей с желтой обложкой типа "Паскаль в картинках" завалил человека обучавшемуся программированию по Кнуту. S>Запылился у вас Кнут, мхом порос. Сдуйте пыль, стряхните мох, откройте первый том в районе раздела 2.2. Там увидите что список (линейный список у Кнута) это абстракция последовательности с условие на предшествование элементов друг другу. Далее рассматриваются различные способы реализации (последовательное распределение, связанное распределение, циклические списки, дважды связанные списки и многомерные массивы). S>К сожалению, Кнут не рассматривает базовый набор операций над списками (в смысле минимальный полный набор), а просто указывает что с линейными списками могут выполняться следующие операции... И далее 9 операций в том числе не тривиальных (разбиение, слияние, сортировка, поиск).
совершенно верно, так что ваш наезд про мох не в тему, я вам эти операции уже приводил
S>Но и операции "перевернуть" среди них нет. А то что вы можете перевернуть на собеседовании массив — это ваши личные успехи, которые вряд ли заинтересуют хоть какого-нибудь собеседователя.
и демагогия про переворот, основанная на незнании, тоже.
J>>Вот она цена самоуверенности и лени при формулировании задач S>Да, отличный результат. Вас сдуло после первого вопроса, даже HR-ам не придется звонить вам с сообщением об отказе.
куда меня сдуло? Если я увижу что у интервьюера знания об АТД базируются на никому неведомых книгах для детей, да еще если при этом он будет лениться объяснить и самоуверенно считать свои знания об АТД абсолютом, то я и сам уйду.
ЗЫ. Зачем вы влезли в мою беседу с ishmakov, если собирались хамить и обвиненять меня в некомпетентности? Развлекаетесь от лени и безделья?
Re[31]: PS. Задача на собеседовании - обращение списка.
Здравствуйте, jhfrek, Вы писали:
J>Здравствуйте, samius, Вы писали:
J>о как, вы что и правда не читали ни Кнута, ни Вирта с Дейкстрой и не знаете что список можно реализовать при помощи массива?
Нет, неправда. Разве что Вирта не читал (и не собираюсь). И знаю что можно развернуть список при помощи массива. Но вот то что вы на вопрос о развороте списка настаиваете на развороте массива — это меня смущает.
J>совершенно верно, так что ваш наезд про мох не в тему, я вам эти операции уже приводил
Да, приводили. Но вы как-то избегаете соглашаться со мной в том факте что у Кнута список — тоже абстракция.
S>>Но и операции "перевернуть" среди них нет. А то что вы можете перевернуть на собеседовании массив — это ваши личные успехи, которые вряд ли заинтересуют хоть какого-нибудь собеседователя.
J>и демагогия про переворот, основанная на незнании, тоже.
Демагогия — это у вас. Даже раздел демагогии так называется — "подмена тезиса". Мы здесь все еще обращаем список. Гляньте в название темы. Массив — это лишь частный случай реализации списка. Потому в задаче "обращение списка" зачет не получаете.
S>>Да, отличный результат. Вас сдуло после первого вопроса, даже HR-ам не придется звонить вам с сообщением об отказе.
J>куда меня сдуло? Если я увижу что у интервьюера знания об АТД базируются на никому неведомых книгах для детей, да еще если при этом он будет лениться объяснить и самоуверенно считать свои знания об АТД абсолютом, то я и сам уйду.
Вот, вы уйдете, а я прокомментирую это термином "сдуло".
J>ЗЫ. Зачем вы влезли в мою беседу с ishmakov, если собирались хамить и обвиненять меня в некомпетентности? Развлекаетесь от лени и безделья?
Мне не понравился ваш наезд "выдает узость мышления и незнание современных языков и библиотек у интервьюера" в отношении неопределенного круга лиц. Решил посмотреть на вашу узость мышления.
Re[30]: Задача на собеседовании - обращение списка.
Здравствуйте, samius, Вы писали:
J>>а откуда взялись критерии? Он не озвучивал критериев, он так же как и вы полагал что список — это очевидная и однозначная вещь. S>Т.е. критерии вы за топикстартера выдумали? Ну что, поздравляю, хороший ход. Проблема лишь в том, что топикстартер продемонстрировал увлечение (как минимум) функциональными языками и в частности Haskell-ем, потому ваши предположения о том что он предполагал что список — это очевидная и однозначная вещь — это всего лишь ваши предположения. Мои предположения: ваши предположения далеки от действительности.
ок, специально для вашей лени (выделение мое)
H>А как выглядит "правильное решение" этой задачи?
Паблик Морозов>Да никакого подвоха. Просто дан односвязный или двусвязный список, и надо его обратить (развернуть указатели на элементы), или как-нибудь поменять элементы местами (я обычно делаю небольшие вариации, чтобы не заучивали). Алгоритм — цикл на 4-5 строчек. Никаких специальных знаний не требуется. Можно и с рекурсией написать, если человеку так удобнее, но за этим последуют дополнительные вопросы. Переворот строки — из той же серии, просто я её уже не дают, поскольку уже не все помнять, что такое null-terminated строки и как писать на Си, а на джаве или сишарпе её писать не интересно.
...
UA>С голыми списками работают только на первом курсе университета чтобы понять как оно работает но в реальной работе велосипедостроение не приветствуется.
Паблик Морозов>Понятно, что не приветсвуется, я же написал, что задача нужна только для того, чтобы проверить, сможет ли человек написать примитивный алгоритм. Ведь давать реальные задачи невозможно по вполне очевидным причинам.
J>>Вот только однозначность оказалась не однозначной. И мое собеседование вы не прошли, не смотря на все заверения о необходимости для кандидата уточнять задачу, сами вы уточнять ничего не стали — кинулись писать код на основе своих представлений о списке. S>А, так это я у вас собеседование проходил? Извините, вам показалось. Я вам пытался разжевать кое-что, а не узнать, угадал ли я ваш правильный ответ.
не угадать, а уточнить задачу у меня или прочитав сообщения интервьюера ака Паблика Морозова
J>>задача топикстартера была не перевернуть список, а перевернуть список состоящий из рекордов со ссылками. Это же список приведен и в википедии на картинке — http://en.wikipedia.org/wiki/List_(computing) S>Раз уж вы ссылаетесь на картинку в википедии в данной статье, то не сочтите за труд и прочитайте первый абзац о том что такое список (хинт: абстракция). Но да, таки один из наиболее частых способов реализации списка — односвязный список. Частый, но в стандарт C++ он попал лишь в 11-ом году.
при чем здесь стандарт С++, если это азы зарождения структурного программирования еще прошлого века.
S>>>А что принципиально меняет лента по отношению к микросхеме кроме времени доступа? J>>действительно, устройство с последовательным доступом и устройство с произвольным доступом, какие между ними могут быть принципиальные различия S>а какие могут быть принципиальные различия между фразами "не требует дополнительной памяти с последовательным доступом" и "не требует дополнительной памяти с произвольным доступом"
это такой способ уйти от ответа, задав новый вопрос?
Хорошо, я отвечу сам на свой вопрос — вы не можете обратиться к конкретной записи на ленте, не считав предыдущие. Поэтому и памяти будет нужно больше, и времени будет нужно больше. Почитайте Кнута про сортировку, там есть глава в том числе и про выбор разных алгоритмов для памяти и ленты.
J>>Как вы возьмете tail от файла на ленте? S>Наверное прочитаю одну очередную запись.
мне казалось что tail возвращает список... Получается он возвращает запись?
S>Вообще говоря, я не понимаю ваших проблем. Ленты не используют таким образом, как их использует Машина Тюринга. Основное назначение лент — резервное копирование и архивация данных. Даже когда мои предки работали с лентами — им не хватало ума использовать ленты в качестве оперативной памяти. Максимум — для оверлеев. Рассказать почему?
даже когда вы работаете с жестким диском, для него действуют те же ограничения что и для ленты. С него хоть и можно считать с произвольного места, но времени на это надо...
Re[32]: PS. Задача на собеседовании - обращение списка.
Здравствуйте, samius, Вы писали:
J>>о как, вы что и правда не читали ни Кнута, ни Вирта с Дейкстрой и не знаете что список можно реализовать при помощи массива? S>Нет, неправда. Разве что Вирта не читал (и не собираюсь). И знаю что можно развернуть список при помощи массива. Но вот то что вы на вопрос о развороте списка настаиваете на развороте массива — это меня смущает.
я, настаиваю? Где? Я привел массив как один из возможных способов реализации списка, на котором можно реализовать абсолютно все операции для работы со списком.
J>>совершенно верно, так что ваш наезд про мох не в тему, я вам эти операции уже приводил S>Да, приводили. Но вы как-то избегаете соглашаться со мной в том факте что у Кнута список — тоже абстракция.
Вообще-то это я вам привел кнутовский список в качестве примера АТД, как доказательство того что ваша версия АТД с "базовыми" методами не единственно возможная
S>>>Но и операции "перевернуть" среди них нет. А то что вы можете перевернуть на собеседовании массив — это ваши личные успехи, которые вряд ли заинтересуют хоть какого-нибудь собеседователя. J>>и демагогия про переворот, основанная на незнании, тоже. S>Демагогия — это у вас. Даже раздел демагогии так называется — "подмена тезиса". Мы здесь все еще обращаем список. Гляньте в название темы. Массив — это лишь частный случай реализации списка. Потому в задаче "обращение списка" зачет не получаете.
не, это вы подменяете задачу "обращение списка" на задачу "обращение списка при помощи базовых операций из книжки для детей с желтой обложкой"
S>>>Да, отличный результат. Вас сдуло после первого вопроса, даже HR-ам не придется звонить вам с сообщением об отказе. J>>куда меня сдуло? Если я увижу что у интервьюера знания об АТД базируются на никому неведомых книгах для детей, да еще если при этом он будет лениться объяснить и самоуверенно считать свои знания об АТД абсолютом, то я и сам уйду. S>Вот, вы уйдете, а я прокомментирую это термином "сдуло".
ну, хамство ХР — хорошо известный факт
J>>ЗЫ. Зачем вы влезли в мою беседу с ishmakov, если собирались хамить и обвиненять меня в некомпетентности? Развлекаетесь от лени и безделья? S>Мне не понравился ваш наезд "выдает узость мышления и незнание современных языков и библиотек у интервьюера" в отношении неопределенного круга лиц. Решил посмотреть на вашу узость мышления.
а, сладкая месть принимается
вот только "я бы подумал, что интервьюер не знаком с общепринятой терминологией в структурах данных", с которого вы начали, — это совершенно голословное утверждение
Re[31]: Задача на собеседовании - обращение списка.
Здравствуйте, jhfrek, Вы писали:
J>Здравствуйте, samius, Вы писали:
J>>>а откуда взялись критерии? Он не озвучивал критериев, он так же как и вы полагал что список — это очевидная и однозначная вещь. S>>Т.е. критерии вы за топикстартера выдумали? Ну что, поздравляю, хороший ход. Проблема лишь в том, что топикстартер продемонстрировал увлечение (как минимум) функциональными языками и в частности Haskell-ем, потому ваши предположения о том что он предполагал что список — это очевидная и однозначная вещь — это всего лишь ваши предположения. Мои предположения: ваши предположения далеки от действительности.
J>ок, специально для вашей лени (выделение мое)
J>
H>>А как выглядит "правильное решение" этой задачи?
J>Паблик Морозов>Да никакого подвоха. Просто дан односвязный или двусвязный список, и надо его обратить (развернуть указатели на элементы), или как-нибудь поменять элементы местами (я обычно делаю небольшие вариации, чтобы не заучивали).
Отлично, только интересно, почему вы выделили то что в скобках, и не выделили альтернативный вариант "или как-нибудь поменять элементы местами"?
На всякий слуачай посмотрите на пост http://www.rsdn.ru/forum/job/4632386.1
Может поймете, насколько бы устроил топикстартера ваш разворот массива, да еще и без кода.
S>>А, так это я у вас собеседование проходил? Извините, вам показалось. Я вам пытался разжевать кое-что, а не узнать, угадал ли я ваш правильный ответ.
J>не угадать, а уточнить задачу у меня или прочитав сообщения интервьюера ака Паблика Морозова
Я не сомневаюсь в своей трактовке задачи топикстартера. А в вашей — сомневаюсь.
S>>Раз уж вы ссылаетесь на картинку в википедии в данной статье, то не сочтите за труд и прочитайте первый абзац о том что такое список (хинт: абстракция). Но да, таки один из наиболее частых способов реализации списка — односвязный список. Частый, но в стандарт C++ он попал лишь в 11-ом году.
J>при чем здесь стандарт С++, если это азы зарождения структурного программирования еще прошлого века.
не при чем. От темы список = абстракция вы опять ушли.
S>>а какие могут быть принципиальные различия между фразами "не требует дополнительной памяти с последовательным доступом" и "не требует дополнительной памяти с произвольным доступом"
J>это такой способ уйти от ответа, задав новый вопрос?
J>Хорошо, я отвечу сам на свой вопрос — вы не можете обратиться к конкретной записи на ленте, не считав предыдущие. Поэтому и памяти будет нужно больше, и времени будет нужно больше. Почитайте Кнута про сортировку, там есть глава в том числе и про выбор разных алгоритмов для памяти и ленты.
Для чтения предыдущих записей память не нужна (разве что под счетчик). А про время разговора не было, вы меня по дополнительной памяти пытаете. Я еще не забыл, о чем речь. На сортировку переходить не советую, у вас со списками еще проблемы.
J>>>Как вы возьмете tail от файла на ленте? S>>Наверное прочитаю одну очередную запись.
J>мне казалось что tail возвращает список... Получается он возвращает запись?
Нет, он вернет список, начинающийся с текущей позиции на ленте.
J>даже когда вы работаете с жестким диском, для него действуют те же ограничения что и для ленты. С него хоть и можно считать с произвольного места, но времени на это надо...
... куда меньше чем на ленте, но больше чем для "оперативной" памяти, с которой тоже случаются тормоза.
Что лента, что диск, что RAM, операция tail не требует дополнительной памяти в общем случае. А требует advance position. Что вы мне пытаетесь доказать?
Re[33]: PS. Задача на собеседовании - обращение списка.
Здравствуйте, jhfrek, Вы писали:
J>Здравствуйте, samius, Вы писали:
S>>Нет, неправда. Разве что Вирта не читал (и не собираюсь). И знаю что можно развернуть список при помощи массива. Но вот то что вы на вопрос о развороте списка настаиваете на развороте массива — это меня смущает.
J>я, настаиваю? Где? Я привел массив как один из возможных способов реализации списка, на котором можно реализовать абсолютно все операции для работы со списком.
Да нет же, вы привели массив как решение, которое собеседующий должен проглотить не жуя и подавиться.
S>>Да, приводили. Но вы как-то избегаете соглашаться со мной в том факте что у Кнута список — тоже абстракция.
J>Вообще-то это я вам привел кнутовский список в качестве примера АТД, как доказательство того что ваша версия АТД с "базовыми" методами не единственно возможная
Кнутовский список не является доказательством того что (не моя версия) с АлгТД и базовым набором операций не единственно возможная. Все операции, перечисленные Кнутом (а это просто перечисление операций без претензии на полноту и минимальность), могут быть реализованы с помощью версии списка на АлгТД. Наоборот — нет.
J>не, это вы подменяете задачу "обращение списка" на задачу "обращение списка при помощи базовых операций из книжки для детей с желтой обложкой"
Вы походу так и не поняли, что подразумевается под списком у взрослых. Освежите Кнута еще разок. И википедию (русскую, английскую).
S>>Вот, вы уйдете, а я прокомментирую это термином "сдуло".
J>ну, хамство ХР — хорошо известный факт
а XP здесь в каком смысле?
S>>Мне не понравился ваш наезд "выдает узость мышления и незнание современных языков и библиотек у интервьюера" в отношении неопределенного круга лиц. Решил посмотреть на вашу узость мышления.
J>а, сладкая месть принимается
J>вот только "я бы подумал, что интервьюер не знаком с общепринятой терминологией в структурах данных", с которого вы начали, — это совершенно голословное утверждение
В случае с неопределенным интервьюером — возможно. В вашем случае я уверен до сих пор.
Re[30]: PS. Задача на собеседовании - обращение списка.
On 14.02.2013 21:16, samius wrote:
> Запылился у вас Кнут, мхом порос. > К сожалению, Кнут не рассматривает базовый набор операций над списками
Читайте правильные книжки: "Паскаль в картинках".
Здравствуйте, Паблик Морозов, Вы писали:
ПМ>Почему 9 из 10 соискателей не могут её решить? Причём у людей минимум от 3-х лет опыта разработки, позиционируют они себя, как сеньёр-девелоперы, ЗП вроде конкурентноспособная (немного выше, если отсортировать вакансии с HH по зарплате и пропустить жöлтенькие).
Я тоже что там разворачивать? Там всего 13 строк:
template< typename Typelist, typename State = Null >
struct Reverse;
template< typename State >
struct Reverse< Null, State >
{
typedef State type;
};
template< typename Head, typename Tail, typename State, template<typename,typename> class Typelist >
struct Reverse< Typelist<Head,Tail>, State >
: Reverse< Tail, Typelist<Head,State> >
{};
принимается 
