Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Задание при приеме на работу

Автор: codelord 17.1.2007, 23:28

Цитата Тестовое задание Существует текстовый файл следующего формата: 1.    Каждая строка может содержать идентификатор сущности-родителя и идентификаторы сущностей-детей, разделенные пробельными символами. 2.    Сами идентификаторы, как родителей, так и детей могут содержать любые символы, за исключением пробельных. 3.    Первым идентификатором в строке всегда является идентификатор сущности-родителя. 4.    Остальные идентификаторы, являются идентификаторами сущностей-детей. 5.    Минимальное содержимое строки идентификатор сущности-родителя и идентификатор сущности-ребенка. 6.    Каждая строка заканчивается знаком перевода строки (\n). 7.    Пустые строки игнорируются. 8.    Строки начинающиеся со знака ';' считаются комментариями и игнорируются. Необходимо написать программу, которая разбирает файл указанного формата (имя файла указывается в командной строке) и выводит информацию о зависимостях на экран. При наличии циклических зависимостей программа должна уведомлять об этом. При ошибках в исходных данных, программа должна уведомлять об этом с указанием номера строки. При дублировании описании зависимостей программа должна выдавать предупреждения об этом с указанием номера строки, в которой найдена дублирующая зависимость. Пример исходного файла: item0 item1 item2 item2 item22 item1 item11 item12 item13 Пример вывода после разбора: item0     item1   item11   item12   item13     item2   item22 Пример исходного файла с циклической зависимостью: item0 item1 item1 item0 Требования к написанию программы: 1.    Язык программирования С++. 2.    Разрешается использование только стандартных библиотек, а также STL и Boost. Критерии оценки программы (все критерии равнозначны): 1.    Правильность работы. 2.    Надежность работы. 3.    Понятность кода. 4.    Возможность повторного использования. 5.    Безопасность кода

Автор: Romikgy 17.1.2007, 23:36

и?

Автор: Daevaorn 17.1.2007, 23:38

Цитата(codelord @  18.1.2007,  00:28 ) 2.    Разрешается использование только стандартных библиотек, а также STL и Boost. жесть. уже можно не делать. фирма явно странная

Автор: S.A.G. 17.1.2007, 23:41

Наверное у них задача есть похожая

Автор: nickless 17.1.2007, 23:43

Цитата(Daevaorn @ 17.1.2007,  22:38) жесть. уже можно не делать. фирма явно странная Наверно просто надо чтобы человек _сам_ парсер написал, а не использовал что-то вроде lex+bison

Автор: Daevaorn 17.1.2007, 23:53

Цитата(nickless @  18.1.2007,  00:43 ) Наверно просто надо чтобы человек _сам_ парсер написал, а не использовал что-то вроде lex+bison   ну да во-первых STL уже часть стандартной библиотеки во-вторых boost::spirit это покруче чем "lex+bison":)

Автор: Void 17.1.2007, 23:55

Цитата(main @  18.1.2007,  01:41 ) Наверное у них задача есть похожая  Эта задача уже лет -цать как решается make. Цитата(nickless @  18.1.2007,  01:43 ) Наверно просто надо чтобы человек _сам_ парсер написал, а не использовал что-то вроде lex+bison Указан Буст, в Бусте есть Spirit, для данной задачи не хуже упомянутых тулз. Так что максимальное внимание последним шести строкам

Автор: Alexey_2007 17.1.2007, 23:56

Вся сложность в предобработке файла, все остальное сделать в принципе легко... предлагаю такую предобработку: 1) Для каждого имени запоминаем в каких строках оно есть, и в качестве кого (родителя\ребенка) итого у нас формируется массив структур - по структуре на имя 2) Если одно имя - является сыном нескольких отцов - выводим ошибку Пункты 3) - 4) выполняем пока не конец файла 3) Если нет имен, не упоминающихся в качестве детей в еще не выделенных строчках (изначально они все не выделены) - выводим ошибку 4) Все такие (не упоминающиеся)  имена добавляем в качестве детей к своим родителям (родители ищутся среди выделенных строк, если не находятся - это имя без родителей) и выделяем эти строки. 5) Выводим дерево на экран.... GAME OVER P.S: Классный тест... еще такие попадутся - пиши обязательно!!!! P.P.S: Народ, видимо вам предлагали решить задачу а не обсуждать фирму          Этот тест очень хорошо проверяет наличие работающего мозга.... а библиотеки в общем то не помогут здесь ИМХО.

Автор: nickless 18.1.2007, 00:03

Цитата(Daevaorn @ 17.1.2007,  22:53) во-вторых boost::spirit это покруче чем "lex+bison":) Интересно, надо будет почитать    ЗЫ Цитата(Alexey_2007 @ 17.1.2007, 22:56) 2) Если одно имя - является сыном нескольких отцов - выводим ошибку Это имхо не ошибка, просто тогда выйдет не дерево зависимостей, а граф: Код     Item1   /      \ Item2  Item3   \       /     Item4

Автор: codelord 18.1.2007, 00:36

Цитата P.P.S: Народ, видимо вам предлагали решить задачу а не обсуждать фирму  точно,  мне кажется она довольна сложна именно логикой (выстроить взаимоотношения родственников) а не тем чтобы пропарсить текст.

Автор: KpoHyc 18.1.2007, 00:46

codelord, а сроки? У меня висит аналогичное задание, только за клаву я сяду не раньше сдачи сессии) 19го - 21 го намереваюсь кончить...если еще надо будет - скину)

Автор: codelord 18.1.2007, 00:54

Цитата codelord, а сроки? У меня висит аналогичное задание, только за клаву я сяду не раньше сдачи сессии) 19го - 21 го намереваюсь кончить...если еще надо будет - скину)   да мне не надо, лучше здесь, любопытно будет посмотреть.

Автор: Alexey_2007 18.1.2007, 00:55

codelord, Я вроде написал логику на форуме.... если что не понятно - спрашивай... nickless, просто я так понял, что возможно только дерево.. ну если возможен граф - убрать это условие и всё

Автор: codelord 18.1.2007, 00:56

Цитата codelord, Я вроде написал логику на форуме.... если что не понятно - спрашивай... вы шутите штоль  вы лучше для себя ее решите. для меня не надо.  проблемы начнуться когда начнешь свою логику применять. задача трудная поэтому. За рабочий код ставлю три знака поощрения  за усердие, ум и желание

Автор: Alexey_2007 18.1.2007, 00:59

Ок просто не понял тогда

Автор: Anikmar 18.1.2007, 15:49

Если судить по примеру вывода после разбора - то все-таки там дерево, а не граф. Этот вопрос принципиальный с точки зрения вывода: показанный пример выводит дерево. А как выводить граф?

Автор: Void 18.1.2007, 17:14

Связный граф без циклов и есть дерево. Если есть циклы — надо сообщить об этом без вывода зависимостей, я так понял.

Автор: Mayk 18.1.2007, 17:29

Цитата(Void @  18.1.2007,  21:14 ) Если есть циклы — надо сообщить об этом без вывода зависимостей, я так понял. В примере nickless'а выше[A->{B C}->D на языке dot]  циклических зависимостей как раз и нет. Потому как D зависит от B и C, B зависит от A и C зависит от A. и других зависимостей нет. нет цикла. граф здесь ориентированный, и это надо учитывать. я безсовестно заменил в примере графа длинные названия ItemN... на A... Добавлено @ 17:43  Кстати, если под "выводом зависимостей на экран" подразуметь (подобно tsort(1))  Код \forall K,L Если элемент K зависит от L, то элемент L будет выведен перед элементом K и забить на красивые отступы, то эта самая топологическая сортировка как раз даст искомый результат, то у nickless'овского графа A->{B C}->D будет два валидных выхода: Код Α Β С D и Код A C B D

Автор: Anikmar 18.1.2007, 23:22

Честно говоря, мне не видится эта задача слишком сложной с точки зрения создания самой структуры зависимостей. Но пост Maykа как раз о той проблеме, которую я вижу: как это правильно вывести, если один потомок зависит от двух предков сразу? Или данная ситуация считается ошибочной? Если немного расширить исходные данные: A B C D B E F C E F То как это должно быть выведено? A  B   E <--- Т.е. по два раза вывести? Или это ошибочные данные   F <---  C   E <---   F <---  D  Или надо так вывести (полный бред по-моему) A  B C   E F Не совсем понятны условия. Если это обычное дерево - то не намного сложнее дерева подкаталогов получится

Автор: Дмитрий Т 22.1.2007, 11:17

Цитата(codelord @ 18.1.2007,  00:28) Критерии оценки программы (все критерии равнозначны): 3.    Понятность кода. 4.    Возможность повторного использования. Чтоб выполнить эти пункты логику программы, думаю, надо основвывать на паттерне "Composite" (Компоновшик) (см. книгу четырёх "Design Patterns. Elements of Reusable Object-Oriented Software.", есть на русском). Это не только прояснит логику, но и к тому же сразу скажет проверющему о хорошей квалификации программиста. Было бы время, я бы с удовольствием наваял решение. Хорошая задачка

Автор: SerpentVV 22.1.2007, 12:43

Цитата(nickless @  17.1.2007,  23:43 ) Наверно просто надо чтобы человек _сам_ парсер написал, а не использовал что-то вроде lex+bison   Дело не в написании парсера... Файл читается вполне стандартными средствами - оператором >> в строковые переменные. Дело именно в логике... Но логика тож не сильно сложная... Так как скорость в качестве критерия не фигурирует (видимо не случайно), то нужно использовать стандартный список list из STL list<string> children - это список детей... struct element { string родитель;    list<string> children; } list<element> tree; // фактически список-списков... После прочтения файла он просто выводится на экран в цикле... Для отслеживания циклических связей досточно проверять каждого дитятю на совпадение с родителем... Алгоритм скорости вроде O(n^2)

Автор: SaDFromSpb 22.1.2007, 19:19

codelord,  Готовь тесты, чтобы убедиться в работоспособности =) Мож найдется время вечерком - напишу чего-нить. Добавлено @ 19:28  Так действительно интересно, сколько давалось на эту задачку времени?

Автор: SaDFromSpb 28.1.2007, 17:54

Блин, времени вообще выделить не могу на это дело. Сейчас на работе полный аврал, плюс диплом доделывать надо. Единственное сложное и интересное место в этой задаче - это сортировка частично упорядоченного множества (упорядоченность заключается в правилах "кто чей родитель").  Ее алгоритм мы в универе давно еще проходили. Могу быстренько накидать, если нужно.

Автор: Rockie 29.1.2007, 23:21

imho это замыкание множества атрибутов над множеством функциональных зависимостей, алгоритм из области реляционных баз данных. Цитата Алгоритм CLOSURE ищет в F функциональную зависимость левая сторона которой содержится во множестве Xi. Если существует такая функциональная зависимость, тогда к Xi присоединяются атрибуты из правой части функциональной зависимости. В противном случае X+ равно текущему множеству Xi. Алгоритм CLOSURE строит замыкание множества атрибутов относительно множества функциональных зависимостей. Цитата CLOSURE (F, X, X+) Input: F – мфз над схемой R; X – множество атрибутов X ≤ R; Output: X+ - замыкание множества Begin     i:=0;  Xi := X;     repeat   i:=i+1;  Xi =Xi-1;   For all V→W in F     if V ≤ Xi then Xi := Xi U W;     until Xi = Xi-1;     return (X+ = Xi); End. к примеру имеем множество функциональных зависимостей: A->D AB->E BF->E CD->F E->C находим замыкание для множества атрибутов: AE Получаем: {AE, AEDC, AEDCF} Вроде так, если ничего не напутал. codelord, где-то валяются исходники, но к сожалению на Delphi. если нужно - стучи в ПМ. p.s.: imho странноватое тестовое задание. std::set + рутина, особые знания языка или ООП  такое задание не покажет, зато напрягает большое кол-во требований по интерфейсу(в какой строке ошибка и т.п., требование к возможности реутилизации кода). imho надо быть осторожней с этим работодателем.

Автор: SerpentVV 30.1.2007, 16:04

Если используется стандартные контейнеры, то STL уже имеет нужные сортировки... Нужно просто использовать...

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)